有没有一种很好的方法来进行这种采矿？
Leg*_*end 14 python algorithm data-mining
我试图找到在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)应该给我很多积分.
除了这个简单的解决方案之外,我想不出任何可以在这里做的聪明,因为这个问题对我来说看似简单.我在这里错过了什么吗？这是否属于某些已知的问题,如果是这样,是否有一种良好且可扩展的方法来实现这一目标？
样本数据集:
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
and*_*oke 13
这有点晚了,但这个问题让我担心了一段时间.我确信它可以用混合整数/线性编程技术解决,并在这个问题上寻求帮助:使用线性编程识别列和行簇
然而,在得到回复之后,我明白你的问题,至少在我理解的情况下,是如此简单(当构成约束程序时),你可以通过一个简单的程序(你已经知道)轻松解决它.换句话说,约束编程是解决这个问题的一种很酷的方法,但是,至少在我发现的方法中,它会给你更简单的答案.
我将在下面解释我的推理,我将如何用约束求解包实现它,然后给出最终的,微不足道的算法.
混合整数编程解决方案
最重要的细节是水平和垂直组之间的差异.据我所知,任何垂直对齐的东西都可以在同一组中.但水平组是不同的 - 组件必须紧密相连.
解决约束问题最困难的部分似乎是找到一种以解算器可以理解的方式描述限制的方法.我不会在这里详细介绍,但求解者受到限制.幸运的是,我认为这里有一种方法可以做到这一点,它是考虑水平邻居:如果连续有N个点,那么我们就有了一N-1组邻居(例如,有4个点ABC和D有三对AB ,BC和CD).
对于每一对,我们可以给出一个分数,即它们之间的空格数(S_i)由某个因子缩放K,以及一个标志(F_i)为0或1.如果该对在同一水平组中,那么我们设置标志为1,否则为零.
至关重要的是要看到所有对的标志集完全定义了解决方案.我们可以遍历任何行,在同一水平组中放置标记为1的对,并在每次标志为0时开始一个新的水平组.然后,我们可以取所有大小为1的水平组并将它们转换为垂直组:任何不在水平组中的点必须在垂直组中(即使它只是一个垂直组).
所以我们现在需要的是一种用标志来表达最佳解决方案的方法.我建议我们要尽量减少:
sum(1 - F_i) + sum(K * S_i * F_i)
这有两个术语.第一个是每对的"一减去标志"的总和.当点在同一水平组中时,标志为1,否则为0.因此,最小化此值与说我们希望尽可能
少的水平组相同.如果这是唯一的约束,那么我们可以通过使所有F_i1 - 通过使所有对在同一组的行成员上来将其设置为零.
但第二个任期阻止我们选择这样一个极端的解决方案.它会对有缺口的群体进行惩罚.如果一对在同一组中,但是用S_i空格分隔,那么我们有一个"惩罚" K * S_i.
所以我们有一个权衡.我们想要横向组,但我们不想要差距.最终的解决方案将取决于K- 如果它很大,那么我们将不在水平组中包含任何空格.但随着它的减少,我们将开始这样做,直到它非常小(趋向于零),我们将所有内容放在一个组中.
要使用它,您可以选择一些K,计算S_i,并在约束系统中输入上面的表达式.然后系统将选择F_i最小化表达式.最后,您将F_i通过如上所述扫描每一行,然后垂直分组单例,将其转换为组的模式.
分析解决方案
好的.在这一点上,我们有办法表达我们可以给约束引擎的问题.
但解决它是微不足道的!我们不需要stinkin'约束引擎来解决这个问题 - 我们可以看看表达式:
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))
现在请注意,总和中的每个项都是独立的(和附加的).因此,对于每个术语,我们需要最小值.我们有两种选择:
if
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
结论
您可以使用约束编程技术来解决此问题,但此类技术仅限于以"正确"(通常为线性)方式描述系统的解决方案.
我能找到的最简单的这种方法相当于一个简单的直接算法,它根据它们之间的空格数将一行中的点划分为水平组.
这一切都取决于你想要什么的一堆假设,当然,这可能是过度简化,或者只是完全错误.