首页 > 代码库 > 聚类(Clustering)

聚类(Clustering)

 简介

    这大概是我第一次涉及到跟智能算法相关的东西——聚类。无奈,老师布置的作业,要求2-3天看完然后汇报。毕竟第一次看这一类的文章,如果理解有偏见,欢迎指出。我的邮箱:zhanghedong2012@126.com。

    先介绍一下什么是聚类(Clustering)吧。简单地说就是把相似的数据分到一组。比如你把人进行分组,如果是按性别分,那很容易,只有俩点。如果你按年龄或者身高分组,定义一下高的还是矮的进行分组就可以了。但是我们常常会遇到很多复杂的情况,比如人的健康情况,你要把健康情况不一样的进行分组。这个涉及到的数据维数就比较庞大了。因为健康跟人的年龄、身高体重比、血液成分含量等等都相关,人的不同器官的健康情况也可能不一样。这就需要对点进行复杂的聚类分析与处理了。

    http://www.cnblogs.com/CVFans/p/4103430.html 看到有大神把一些聚类算法讲述的非常详细,这里就不一一介绍,主要介绍一种聚类方式——Border-Peel Clustering(我称为去皮聚类),简单地说就是一层层地把外面关系小(密度小)的点剥开,直到剩下中间密度足够大的点。这种方式跟k-means方式相比,最大的有点在于没有输入参数,k-means可能因为初始参数输入的不合适导致某几个类可能没有点收敛得到。废话不多说,下面我们直接来讨论算法。

   顾名思义,“去皮”实际上就是去处边界点。那么什么是边界点呢?如何分离边界点和非边界点呢?所以,我们的任务就是:1、定义什么是边界点。2、定义边界点和它相邻的非边界点的关联。

  边界点的定义

   给定有$n$个点的点集$X=\left \{ x_{1},x_{2},\cdots,x_{n} \right \}\subset R^{d}$和描述点相似性的函数$d$:$R^{d}\times R^{d} \mapsto R$作为输入。$X^{1}=X$,我们用$X^{t}$表示第$t-1$次去皮后剩下的点,用$X^{T+1}$表示最终剩下的点(“核”)。

下面我们给出几个定义。

$N_{k}^{t}(x_{i})$,它包含k-最近邻点集合。

$b_{i}^{t}$,边界值。

$B_{i}^{t}$,边界分类值。如果$x_{i}$是边界点就定义为1,否则定义为0。

$RNN_{k}^{t}(x_{i})=\left \{ x_{j}\mid x_{i}\in N_{k}^{t}(x_{j}) \right \}$,表示$x_{i}$迭代$t$次之后的k-最近邻。

聚类(Clustering)