有没有好的方法进行这种类型的挖掘？
我正在尝试找出在X和Y方向上最接近的点（在最后会提供样本数据集），想看看有没有比我现在这个简单（而且还没测试过）的方法更聪明的做法。这些点在空间中的分布大致如下图所示，我想找出图中框内标记的点组，也就是说，我想要的输出是一些点的组合：
Group 1: (1,23), (2,23), (3,23)...
Group 2: (68,200), (68,201), (68,203), (68,204), (68,100), (68,101), (68,101)...
对于水平带，我在想可以使用小的滑动窗口，比如大小为5或10（这个大小其实应该根据整体信息来决定，选择能聚集最多点的大小，但我还在探索一个好的方法），然后寻找连续的点，因为如果中间有断开，就不算是一个水平带了。
我猜这个方法对垂直带也适用，但并不是在所有情况下都有效，因为水平带和垂直带之间有一个微妙的区别：在水平带中，点需要很接近才能算作一组，而在垂直带中，点可以出现在任何地方就可以算作一部分。看看图中的大垂直带。所以我猜我可以找出那些具有相同x坐标的点（在这个例子中是x=68），这样应该能找到很多点。
除了这个简单的方法，我想不出有什么更聪明的解决方案，因为这个问题看起来 deceptively simple（表面上简单）。我是不是漏掉了什么？这个问题是否属于某个已知的类别，如果是的话，有没有好的、可扩展的方法来解决它？
样本数据集：
1,23
1,23
2,23
3,23
4,23
5,23
6,23
7,23
8,23
9,23
10,23
11,23
12,23
13,23
14,23
15,23
16,23
10,33
11,33
12,33
13,33
14,33
15,33
16,33
17,33
18,33
19,33
2,28
2,28
3,28
34,75
34,76
34,76
34,77
34,78
34,79
34,80
34,81
34,82
34,83
34,75
34,76
34,76
34,77
34,78
34,79
34,80
34,81
400,28
400,28
400,28
68,200
68,201
68,203
68,204
68,100
68,101
68,103
68,104
2 个回答
你可以试试使用 cluster模块。这个模块里面有K均值聚类算法的实现。你可以调整 getclusters 函数的参数来改变你想要的聚类数量。
s = '''
1,23
1,23
2,23
...
68,101
68,103
68,104
'''
from cluster import *
ll = [tuple(map(int,each.split(','))) for each in s.split()]
#horizontal
cl = HierarchicalClustering(ll, lambda x,y: abs(x[0]-y[0]))
for c in cl.getlevel(1):
print c
#vertical
cl = HierarchicalClustering(ll, lambda x,y: abs(x[1]-y[1]))
for c in cl.getlevel(1):
print c
这事儿有点晚了，但这个问题让我困扰了一段时间。我一直觉得可以用混合整数/线性规划的方法来解决，所以在这个问题上寻求帮助：用线性规划识别行和列的聚类
不过，在那里得到回复后，我意识到，至少在我理解的范围内，你的问题其实很简单（如果用约束编程来框架的话），可以用一个简单的程序轻松解决（你可能早就知道了）。换句话说，约束编程是个不错的解决方案，但至少用我找到的方法，得到的结果和更简单的方法是一样的。
下面我会解释我的思路，如何用约束求解包来实现，然后给出最终的简单算法。
混合整数编程解决方案
最重要的细节是水平组和垂直组之间的区别。就我所见，任何垂直对齐的东西都可以在同一组里。但水平组就不同了——组件必须靠得很近。
用约束来解决问题时，最难的部分似乎是找到一种方式来描述限制，让求解器能够理解。我这里不详细讲，但求解器的限制让人很沮丧。幸运的是，我觉得这里有办法做到这一点，那就是考虑水平邻居：如果一行有N个点，那么我们就有N-1组邻居（例如，4个点A、B、C和D就有三对AB、BC和CD）。
对于每一对，我们可以给一个分数，这个分数是它们之间的空格数（S_i）乘以某个因子K，还有一个标志（F_i），值为0或1。如果这一对在同一水平组里，我们就把标志设为1，否则设为0。
关键是要明白，所有对的标志集合完全定义了一个解决方案。我们可以遍历任何一行，把标志为1的对放在同一水平组里，每当标志为0时就开始一个新的水平组。然后，我们可以把所有大小为1的水平组转换成垂直组：任何不在水平组里的点必须在垂直组里（即使它只是一个点的垂直组）。
所以现在我们只需要一种方式来用标志表达一个最优解。我建议我们想要最小化：
sum(1 - F_i) + sum(K * S_i * F_i)
这个表达式有两个部分。第一个是每对的“1减去标志”的总和。当点在同一水平组时，标志为1，否则为0。所以最小化这个值就意味着我们希望水平组尽可能少。如果这是唯一的约束条件，我们可以通过把所有F_i设为1来让它变为0——也就是把一行中的所有对都放在同一组。
但第二个部分阻止我们选择如此极端的解决方案。它会对有间隙的组进行惩罚。如果一对在同一组，但之间有S_i个空格，那么我们就会有一个“惩罚”，值为K * S_i。
所以我们有一个权衡。我们希望有水平组，但又不想有间隙。最终的解决方案将取决于K——如果它很大，我们就不会在水平组中包含任何空格。但随着K的减小，我们会开始这样做，直到当它非常小（趋近于零）时，我们把一行中的所有点放在同一组里。
要使用这个方法，你需要选择一个K，计算S_i，然后把上面的表达式输入到约束系统中。系统会选择F_i来最小化这个表达式。最后，你会按照上面描述的方式扫描每一行，把F_i转换成组的模式，然后把单个点垂直分组。
解析解决方案
好的，太好了。到目前为止，我们有了一种可以交给约束引擎的方式来表达这个问题。
但这其实很简单！我们不需要复杂的约束引擎来解决这个问题——我们只需要看看这个表达式：
sum(1 - F_i) + sum(K * S_i * F_i)
这两个总和是针对同一对的，所以我们可以把所有东西放进总和里：
sum(1 - F_i + K * S_i * F_i)
sum(1 + F_i * (K * S_i - 1))
然后提取常数（这里的N是对的总数）：
N + sum(F_i * (K * S_i - 1))
现在注意，总和中的每一项都是独立的（并且是可加的）。所以对于每一项，我们想要最小值。我们有两个选择：
如果
F_i是0，那么整个项就是0。否则，
F_i是1，项的值是K * S_i - 1。
所以最佳选择取决于K * S_i是否大于1。如果K * S_i大于1，那么这一项的最小值是0，F_i应该是0。否则，第二个选择的值是负的，F_i应该是1。
简单算法
这意味着什么呢？这意味着对于每一对，我们只需查看空格数S_i。如果这个数大于1 / K，那么这两个点应该在不同的组里。否则，它们应该在同一组。
所以，所有这些复杂的数学、优化、约束和废话，归根结底就是：相邻对中的两个点之间有多远？如果它们之间的距离小于某个临界值，就把它们放在同一水平组里。否则，就把它们放在不同的组里。
所以，最终，这就是你的算法：
choose some cut-off value, X
place each point in its own, singleton, horizontal group
for each row with more than one point:
for each neighbouring pair in the row:
if the space between the pair is less than X:
join into a single horizontal group
for each column:
join any remaining singleton groups into a single vertical group
结论
你可以用约束编程技术来解决这个问题，但这些技术限制了只能描述系统的“正确”（通常是线性）方式的解决方案。
我能找到的最简单的方法等同于一个简单的直接算法，根据点之间的空格数将一行中的点分成水平组。
这一切都依赖于一堆关于你想要什么的假设，这些假设可能当然是过于简单化，或者根本就是错误的。