求分群/分组问题的算法优化

[熬锅肉]

请高手指点：

平面上点分群的问题：
1. 距离阈值：平面上很多点，如果两个点A、B之间距离少于t（dist(A,B)<t），则可以直接认

为是一组，如果超过t，则不直接识别为一组；
2. 连接性：但是，A、B个点之间的距离即使大于t，只要它们中间存在一个点C，使得dist

(A,C)和dist(B,C)都小于t，则A、B仍然认为是一组。
3. 扩展：A、B 之间存在一系列可以连接的点，而A、B可以与其中任意两个点相连，则A、B可

以认为是同一组。

我的思路比较笨，先取出A点，与所有剩下所有点比较距离，小于t的先归入A群，然后再从A群

中取出其他点，与剩下点继续对比，将距离小于t的也拉入A群，直到不能再拉。接着再从剩下

的点中建立第二个群搜寻。

因为点很多几百万至千万级别，所以运算速度是个问题。求算法优化.
另外，使用java编程，采用的arraylist存储

[tangboyun]

楼主你还少说一点：你的要求有多高，一定要100%准确么？
建议先搜索如下关键词：
Hierarchical clustering + single linkage

你的数据量可能不是现有的实现能满足的。要加速聚类，无非是如何缓存距离的计算结果，但你这里距离计算非常容易，可能根本就不需要考虑任何缓存。

[tangboyun]

再补充一点我的个人看法, 我觉得楼主在顶贴里, 最应该描述的是最原始的需求, 而不是达到该需求的路径, 因为很可能你一开始选择的路径就是错的.

如果我遇上楼主描述的这个case, 我绝对不会考虑任意形式的聚类，哪怕是K中心, 或者诸如你提出的那些rule. 因为:
1、楼主已经很清楚的知道分组的个数。
2、楼主的样本数量级在百万以上。以楼主描述的rule，即使可以区分样本数据，也无法
1) 描述、归纳分组的特性
2) 图形展示分界面
3) 归纳，概括数据总体

楼主这个case，比较适合直接拟合一个 由 2个双变量正态总体(A、B)组成的混合正态分布模型。参数只有5个，由期望最大化(EM)可以很容易估算这5个参数，
之后分类只要比较每个点在A、B的概率密度函数哪个高即可划分，甚至可以给出每个点在每个组的概率形式，更甚至可以给出前n个点的假阳性率（FDR），好处除了我上面说的那三点以外，还有：
1、不需要你去估计个啥t。
2、简单、稳健，常数时间划分。
3、对错误率上下界的描述 。
4、优美的图形展示( 不就是个教科书式的3D 概率密度函数的surface plot么)