正文

算法流程如下：

有样本集D = { x 1 , x 2 , . . . , x m }最终聚类的类别数k ，最大迭代轮数n ，前后两次迭代计算出的类标中心的距离ϵ

1、随机选择k kk个样本点作为类标中心

2、计算每个样本点到所有类标中心点的距离；

3、将所有样本点划分到距离最近的类标中心所在的类标；

4、重新计算每个类的类标中心；

5、重复步骤2-4，直到两次迭代计算出的类标中心不发生变化或发生的变化小于ϵ 或者达到指定的最大迭代次数n 。

度聚类算法之 DBSCAN

基于密度的聚类(Density_Based Clustering)方法主要考虑的是样本分布的紧密程度，这里的紧密程度主要是用样本间的距离来衡量的。

通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连续性，并基于可连续性样本不断地扩展簇以获得最终的聚类结果。

DBSCAN是一种著名的密度聚类算法，它基于一组"领域"参数(ϵ , m p s \epsilon,mpsϵ,mps)来刻画样本分布的紧密程度。

对给定样本集D = { x 1 , x 2 , . . . , x m } }进行如下定义：

ϵ 领域

对于样本集D 中的样本点x i它的ϵ领域定义为与x i  距离不大于ϵ 的样本的集合，即

N ϵ ( x i ) = { x ∈ D ∣ d i s t ( x , x i ) ⩽ ϵ }

核心对象

如果样本x xx的ϵ \epsilonϵ领域内至少包含m p s 个样本，即

∣ N ϵ ( x i ) ∣ ⩾ m p s

则称x xx为核心对象

密度直达

如果x i 是一个核心对象，并且x j 位于它的ϵ领域内

,那么我们称x j  与x i  密度直达

密度可达

对于任意两个不同的样本点x i 与x j  ，如果存在样本序列p 1 , p 2 , . . . p n 其中p 1 = x i 、 p n = x j ，且p i + 1由p i ， i = 1 , 2 , . . . , n − 1密度直达，则称x i  与x j 密度可达。

密度相连

对于任意的两个不同样本点x i 与x j，如果存在第三个样本点x k  使得x i  与x j x均由x k x_ 密度可达，则称x i 与x j  密度相连。

其中：

红点表示核心对象；黑色圆圈表示核心对象的ϵ \epsilonϵ领域；绿色箭头表示密度直达；绿色箭头的连线表示密度相连；绿色连线上任意两点都是密度可达。

基于以上概念的定义，那么DBSCAN中簇的定义就十分简单了：

由密度可达关系导出的最大密度相连的样本合集，即为我们最终聚类的一个簇。

形式化的定义如下：给定领域参数( ϵ , m p s ) (簇C ⊆ D的非空样本子集有如下性质：

连接性(Connectivity)

对任意样本x i ∈ C与x j ∈ C C有x i  与x j密度相连；

最大性(Maximality)

x i ∈ C，且x j 由x i 有z j ∈ C

找出簇样本合集：

DBSCAN方法任意选择一个没有类别的核心对象作为种子(Seed)，然后找到所有这个核心对象的密度可达样本集合，即为一个聚类簇。

接着继续选择另一个没有类别的核心对象去寻找密度可达的样本合集，这样就得到了另一个聚类簇。

不断循环下去，直到使用核心对象都有类别为止。

算法形式化的描述如下：

层次聚类算法之 AGNES

层次聚类（Hierarchical Clustering）是聚类算法家族中的重要的成员，它通过合并和分裂构建树状的类簇。对数据的划分主要有两种方式： 自顶向下 的分裂和 自底向上 的聚合。每棵树的根是一个聚集所有样本的独有的类。

AGNES是一种采用自底向上聚合策略的层次聚类算法。它先将数据集中的每个样本看成是一个初始的聚类簇，然后在算法运行的每一步中找出距离最近的两个簇进行合并。该过程不断重复，直至达到预设的聚类簇的个数。

因此，这里的关键又是如何计算两个聚类簇之间的距离。

关于计算两个聚类簇C i 、 C j  之间的距离，有如下四个定义式：

在具体的应用中，为了防止噪声点的影响，一般选择后两种距离度量方法。

AGNES聚类算法的形式化描述如下：

算法输入：

训练集D = { x 1 , x 2 , . . . , x m }

类簇距离度量公式：d ( C i , C j )

聚类簇数目：k

算法输出：

聚类结果划分：C = { C 1 , C 2 , . . . , C k }

详细步骤：

for i = 1, 2,..., m:
  C_i = {x_i}
end for
for i = 1, 2,..., m:
  for j = i, i+1,..., m:
    D(i, j)=d(C_i, C_j)
    D(j, i)=D(i, j)
  end for
end for
// 初始化当前聚类簇数目
K = m
while K > k:
  find nearest class C_x C_y
  C_x = C_x cap C_y // merge into C_x
  for i = y+1, y+2,..., K:
    C_{i-1} = C_i
  end for
  delete row y and col y in D
  for j = 1, 2,..., K-1:
    D(x, j) = d(C_x, C_j)
  end for
  K = K - 1
end while