检测“点簇”（Clusters）的算法

Question

我有一个分布在二维区域上的“点”。我现在正在尝试检测“簇”(clusters)，也就是具有一定高密度点的区域。

您有什么关于如何优雅地检测这些区域的想法（或者链接到有关想法的文章）？

- Epaga

---

这里有一个很棒的聚类算法教程（链接），其中讨论了K-means和K-gaussians。 - Mike Caron

Answer 1

如何为您的空间定义一个任意分辨率，然后计算矩阵中每个点到所有点的距离度量，从而可以制作“热图”并使用阈值定义聚类。

这是一个很好的处理练习，也许以后我会发布解决方案。

编辑：

这就是解决方案：

//load the image
PImage sample;
sample = loadImage("test.png");
size(sample.width, sample.height);
image(sample, 0, 0);
int[][] heat = new int[width][height];

//parameters
int resolution = 5; //distance between points in the gridq
int distance = 8; //distance at wich two points are considered near
float threshold = 0.5;
int level = 240; //leven to detect the dots
int sensitivity = 1; //how much does each dot matters

//calculate the "heat" on each point of the grid
color black = color(0,0,0);
loadPixels();
for(int a=0; a<width; a+=resolution){
  for(int b=0; b<height; b+=resolution){
    for(int x=0; x<width; x++){
      for(int y=0; y<height; y++){
        color c = sample.pixels[y*sample.width+x];        
        /**
         * the heat should be a function of the brightness and the distance, 
         * but this works (tm)
         */
        if(brightness(c)<level && dist(x,y,a,b)<distance){
          heat[a][b] += sensitivity;
        }
      }
    }
  }
}

//render the output
for(int a=0; a<width; ++a){
  for(int b=0; b<height; ++b){
    pixels[b*sample.width+a] = color(heat[a][b],0,0);
  }
}
updatePixels();
filter(THRESHOLD,threshold);

编辑2（代码更高效但输出相同）：

//load the image
PImage sample;
sample = loadImage("test.png");
size(sample.width, sample.height);
image(sample, 0, 0);
int[][] heat = new int[width][height];
int dotQ = 0;
int[][] dots = new int[width*height][2];
int X = 0;
int Y = 1;


//parameters
int resolution = 1; //distance between points in the grid
int distance = 20; //distance at wich two points are considered near
float threshold = 0.6;
int level = 240; //minimum brightness to detect the dots
int sensitivity = 1; //how much does each dot matters

//detect all dots in the sample
loadPixels();
for(int x=0; x<width; x++){
 for(int y=0; y<height; y++){
   color c = pixels[y*sample.width+x];
   if(brightness(c)<level) {
       dots[dotQ][X] += x;
       dots[dotQ++][Y] += y;
   }
 }
}

//calculate heat
for(int x=0; x<width; x+=resolution){
 for(int y=0; y<height; y+=resolution){
   for(int d=0; d<dotQ; d++){
     if(dist(x,y,dots[d][X],dots[d][Y]) < distance)
       heat[x][y]+=sensitivity;
   }
 }
}

//render the output
for(int a=0; a<width; ++a){
 for(int b=0; b<height; ++b){
   pixels[b*sample.width+a] = color(heat[a][b],0,0);
 }
}
updatePixels();
filter(THRESHOLD,threshold);

/** This smooths the ouput with low resolutions
* for(int i=0; i<10; ++i) filter(DILATE);
* for(int i=0; i<3; ++i) filter(BLUR);
* filter(THRESHOLD);
*/

并且使用（缩小的）Kent样本的输出：

- krusty.ar

---

哎呀，对于一个n x n点的正方形来说，这是o(n^4)，或者对于较低分辨率r，o(n^2*((n/r)^2))。也许作为小图像的暴力方法还可以，但不适用于一般解决方案。 - SmacL

当然我不会在任何严肃的事情中使用这个，只是为了表明一点，如果这种方法有用，它可以被优化的很多方式。 - krusty.ar

@kent：有趣的部分是根据区域分组点，这样更容易看到确实存在区域。@smacl：你的评论让我感到不好，所以我更新了它，使其稍微不那么丑陋。 - krusty.ar

@kent：我同意。图像效果很酷，但处理需要一段时间。 - Mike Caron

Answer 2

我建议使用一种均值漂移核来找到你的点密度中心。 均值漂移演示 http://cvr.yorku.ca/members/gradstudents/kosta/compvis/file_mean_shift_path.gif 这个图显示了一个均值漂移核（最初位于簇边缘），收敛于簇的最高密度点。

理论上（简单概述）：

已经有几个回答暗示了使用均值漂移的方法：

• P Daddy 模糊图像并找到最暗的点实际上是一种 核密度估计（KDE）方法，这是均值漂移的理论基础。

• j0rd4n 和 Bill the Lizard 都建议将空间离散成块并检查它们的密度。

你在动画中看到的是这两个建议的结合：它使用一个移动的“块”（即核）来寻找局部最高密度。

均值漂移是一种迭代方法，使用称为核的像素邻域并使用它来计算底层图像数据的平均值。在这种情况下，平均值是核坐标的像素加权平均值。

在每次迭代中，核的平均值定义了下一次迭代的中心坐标-这被称为位移。因此得名“mean-shift”。迭代的停止条件是位移距离降至0（即我们处于邻域中最密集的地方）。

有关均值漂移的全面介绍（理论和应用），请参见此ppt演示文稿。

实践中，均值漂移的实现可在OpenCV中找到：

int cvMeanShift( const CvArr* prob_image, CvRect window,
                 CvTermCriteria criteria, CvConnectedComp* comp );

O'Reilly's Learning OpenCv (google book excerpts)还对其工作原理进行了很好的解释。基本上只需将您的点图像（prob_image）输入即可。

实际上，诀窍在于选择适当的卷积核大小。卷积核越小，您需要将其初始化得越接近聚类。卷积核越大，您的初始位置可以更随意。但是，如果您的图像中有几个点簇，则卷积核可能会在它们之间收敛。

- Ivan

---

这听起来很有趣，但（如果我错了请纠正我）这种方法并不是确定性的，因此在某些情况下并不适用。写得很好。 - Drew Noakes

如果确定性意味着算法对于给定的输入始终会给出相同的输出，那么它就是确定性的。谢谢。 - Ivan

不错的回答。但是请纠正我，这只会在 OP 的情况下给出“主要集群”，而他需要获取不同的集群。是吗？ - Btc Sources

Answer 3

为了帮助Trebs的陈述，我认为首先要实际定义聚类的定义很重要，当然，“点更接近”是相当模糊的。

拿我生成的这个样本集为例，我知道有一个聚类形状，我创建了它。

然而，以程序方式识别这个“聚类”可能很难。

人类可能认为这是一个大的环形聚类，但你的自动程序更可能决定它是一系列半密集的小聚类。

此外，请注意，存在超高密度区域，这在更大的背景下仅仅是干扰。

您需要考虑这种行为，并根据具体应用程序可能将相似密度的聚类链接在一起，仅由低密度的不重要空白分隔。

无论您开发什么，我至少会对它如何识别此数据集中的数据感兴趣。

（我认为研究HDRI ToneMapping背后的技术可能是必要的，因为这些工作基本上都是基于光密度的，有“局部”色调映射和“全局”色调映射，每个映射产生不同的结果）

- Kent Fredric

---

请参阅我对遗传算法的回答。在这种情况下，如果您提前知道环形聚类（或任何不寻常的形状）是可能的，您可以将该可能性直接建立在您的解决方案生成机制和适应性函数中。 - MusiGenesis

@Kent，如果您使用基于TIN的解决方案，可以通过最长边长度的数量级对三角形进行分组，从而解决此问题。因此，虽然我们看到了一个环面，但在您超密集区域中可能还有许多其他有趣的形状，值得进行自己的分析。谷歌多分辨率TIN或Voronoi。 - SmacL

Answer 4

对您的2D区域副本应用模糊滤镜。类似于：

1 2 3 2 1
2 4 6 4 2
3 6 9 6 3
2 4 6 4 2
1 2 3 2 1

“较暗”的区域现在标识出点的聚类。

- P Daddy

---

有趣。不知道这种方法是否可以扩展到超过2个维度... - Drew Noakes

当然可以，但是你的矩阵也会呈指数增长。例如，一个三维矩阵将使用125个元素而不是25个。为了实现与上述相似的效果（我们称之为M）在二维中，你可以在z=0和z=4时使用M，在z=1和z=3时使用M * 2，在z=2时使用M * 3。对于更高维度的情况也是类似的。 - P Daddy

Answer 5

你可以尝试创建一个四叉树数据的表示。图中较短的路径将对应于高密度区域。

或者，更明确地说：给定一个四叉树和层序遍历，每个由“点”组成的较低级别节点将表示高密度区域。随着节点级别的增加，这些节点表示“点”的密度较低的区域。

- mepcotterell

---

我喜欢这个。我可以想到一些巧妙的算法来确定当前级别的其他四元格是否属于当前“簇”，但不幸的是，这个评论字段太小了... - Paul Tomblin

只要聚类是凸的，这是一个非常好的想法。 - Rich

有四叉树实现的链接吗？这样会有多快？ - Mike Caron

Answer 6

如何采用形态学方法？

将二值化图像进行膨胀处理，根据点的目标密度确定膨胀次数，这样聚集在一起的点就会被视为一个单独的对象。

OpenCV支持形态学操作（一些图像处理库也具有该功能）： http://www.seas.upenn.edu/~bensapp/opencvdocs/ref/opencvref_cv.htm#cv_imgproc_morphology

- Ian Hopkinson

Answer 7

1. 将概率密度函数拟合到数据中。我会使用“高斯混合模型”，并使用期望最大化算法进行拟合，该算法由K-means算法引导。有时仅使用K-means本身就足够了，但群集的数量需要通过模型顺序选择算法来引导。
2. 然后，可以使用该模型对每个点进行p(x)评分。即获取生成该点的模型的后验概率。
3. 找到最大的p(x)以找到群集中心。

这可以在像Matlab这样的工具中快速编写，使用机器学习工具箱。 MoG / EM学习/ K-Means聚类在Web /标准文本上广泛讨论。我的最爱是Duda / Hart的“模式分类”。

- graveca

Answer 8

这听起来像是一道学术问题。

我想到的解决方案涉及到R*树。这将您的总面积划分为单独大小和可能重叠的盒子。在这样做之后，您可以通过计算平均距离来确定每个盒子是否代表了一个“聚类”。

R*树

如果这种方法难以实现，您最好将数据网格分成相等大小的子网格，并确定每个子网格中是否发生了聚类；但是您需要非常注意边缘条件。我建议在初始划分之后，您可以重新组合具有特定阈值内定义边缘上数据点的区域。

- Bryan

Answer 9

“一定高密度的区域”意味着您知道每个单位面积内认为高密度的点数大约是多少。这使我倾向于采用网格方法，将整个区域分成适当大小的子区域，然后计算每个区域中的点数。一旦您找到网格中接近您阈值的区域，您可以搜索相邻的网格区域。

- Bill the Lizard

---

四叉树方法相比于这种方法的优点在于，四叉树不必提前定义单位面积，只需定义您认为是“簇”的点数即可。 - Paul Tomblin

我喜欢四叉树的方法，我点赞了它，但单位面积是问题的一部分。一个簇不仅仅是一些点的数量，而是一些彼此靠近的点的数量，也就是在一定区域内的点。 - Bill the Lizard

Answer 10

我认为这取决于点和聚类之间的分离程度。如果距离很大且不规则，我会最初三角剖分点，然后删除/隐藏所有具有统计学大边长度的三角形。其余的子三角形形成任意形状的聚类。遍历这些子三角形的边缘会产生多边形，可以用来确定每个聚类中具体的点。必要时，还可以将这些多边形与已知形状（例如Kent Fredric的环面）进行比较。

在我看来，网格方法对于快速而粗糙的解决方案是不错的，但在稀疏数据上很快就会变得非常饥饿。四叉树更好，但TIN是我个人喜欢的更复杂分析的选择。

- smacl

---

“Tringulate” 是指特定类型的三角测量，还是打字错误？ - Paul Tomblin