• 1. 聚 类报告人:熊 赟
  • 2. 内容提要符号说明及定义 相似性度量 聚类分析中的数据类型 聚类的准则函数 聚类分析的过程 聚类方法与算法
  • 3. 符号说明 1.数据样本X,由d个属性值组成:X=(x1,x2,…,xd),其中xi表示样本中的各属性,d是样本或样本空间的维数(或属性个数)。 2.数据样本集记为X{X1,X2,…,Xn},第i个样本记为Xi={xi1,…,xid},许多情况下聚类的样本本集看成是一个n×d(n个样本×d个属性)的数据矩阵:
  • 4. 符号说明 3.簇Ci:数据样本集X分成k个簇,每个簇是相应数据样本的集合,相似样本在同一簇中,相异样本在不同簇中。 簇Ci(i=1,2,…,k)中样本的数量ni。簇记为Ci={Xj1i,Xj2i,…,Xjnii}, Ci(i=1,…,k)是X的子集,如下所示: C1∪C2∪…∪Ck=X 且 Ci∪Cj=ф,i≠j
  • 5. 符号说明 用下面的特征来描述簇: ①簇的质心(centroid):(样本的平均值)是簇的“中间值”(middle),但并不需要是簇中实际点。 令ni表示簇Ci中样本的数量,mi表示对应样本的均值: centroid= ②簇的半径,是簇中两个点间的均方差的平方根。
  • 6. 定 义 定义(聚类):给定一数据样本集X{X1,X2,…,Xn},根据数据点间的相似程度将数据集合分成k簇:{C1,C2,…,Ck}的过程称为聚类,∪i=1kCi=X,Ci∪Cj=ф,i≠j 。相似样本在同一簇中,相异样本在不同簇中。 关于同一簇中的样本比来自不同簇的样本更为相似的判断问题主要涉及以下两个独立的子问题: a.怎样度量样本之间的相似性; b.怎样衡量对样本集的一种划分的好坏。
  • 7. 相似性度量 相异度矩阵(dissimilarity matrix)用来存储n个样本两两之间的相似性,表现形式是一个n×n维的矩阵: d(Xi,Xj)是样本Xi和样本Xj间相异性的量化表示。 最明显的相似性度量是样本之间的距离。
  • 8. 相似性度量 Xi{xi1,…,xid}和Xj{xj1,…,xjd}是两个具有d个属性的两个样本。距离度量标准d(Xi,Xj)表示第i个样本与第j个样本间的距离。 在聚类分析中,最常用的距离定义如下: 最著名的距离度量标准是d维空间中的欧几里德距离: d(Xi,Xj)=( 2)1/2
  • 9. 相似性度量 更广义的d维空间中的度量为明考斯基距离度量 Lk(Xi,Xj)=( k)1/k 通常也被称为Lk范数,欧几里德距离即L2范数。而L1范数则常被称为曼哈坦距离或城区距离
  • 10. 相似性度量 例:对于一个4维向量X1={1,0,1,0}和X2={2,1,-3,-1},这些距离的度量标准 L1(X1,X2)=1+1+4+1=7, L2(X1,X2)=(1+1+16+1)1/2=4.36 L3(X1,X2)=(1+1+64+1)1/3=4.06。 Lk(Xi,Xj)=( k)1/k
  • 11. 聚类算法即是先定义一个合适的度量,然后计算任意两个样本之间的距离。当两个样本之间的欧几里德距离小于某个阈值d0时,这两个样本就属于同一类。距离阈值d0影响簇的数量和大小,d0越小,每个簇就越小,簇的数目就越多。如果d0太大,则所有样本将会被分为同一簇;如果d0太小,每个样本又会单成一类。
  • 12. 聚类分析中的数据类型1.区间标度变量(interval-valued variables) 2.二元变量(Binary Variables) 样本Xj   1 0 样本Xi 1 n1,1 n1,0 0 n0,1 n0,0 3.标称型、序数型、比例标度型变量 4.混合型变量
  • 13. 二元变量的相似度计算简单匹配系数(simple matching coefficient,SMC)评价这样的两个样本Xi和样本Xj之间的相异度 评价系数是Jaccard系数 例:样本Xi和样本Xj具有8个二元类型变量: Xi={0,0,1,1,0,1,0,1}和Xj={0,1,1,0,0,1,0,0} 则n1.1=2, n1.0=2, n0.1=1, n0.0 =3 Ssmc(Xi,Xj)=3/8,Sjc(Xi,Xj)=3/5
  • 14. 簇间的距离度量标准用于簇Ci和簇Cj之间的距离度量标准是: 1)最小距离: 其中Xi∈Ci和Xj∈Cj 2)最大距离: 其中Xi∈Ci和Xj∈Cj
  • 15. 3)中间距离: 其中mi和mj是Ci和Cj的质心 4)平均距离: 其中Xi∈Ci和Xj∈Cj,且ni和nj是类Ci和Cj间的样本数。簇间的距离度量标准
  • 16. 聚类的准则函数 误差平方和准则(sum-of-squared-error criterion): 其中X∈Ci,mi是Ci的质心 Je即所有样本的平方误差和。
  • 17. 聚类的分析过程
  • 18. 聚类技术概览 划分的方法 层次的方法 基于密度的方法 基于网格的方法 基于模型的方法
  • 19. 划分方法(partitioning method)划分方法的基本思想是,给定一个n个样本的数据库,划分方法将数据划分为k个划分(k<=n),每个划分表示一个簇,同时满足:a.每个簇至少包含一个样本;b.每个样本必须属于且仅属于一个簇。
  • 20. 基于质心的 k-means聚类算法1.选择一个含有随机选择样本的k个簇的初始划分,计算这些簇的质心。 2.根据欧氏距离把剩余的每个样本分配到距离它最近的簇质心的一个划分。 3.计算被分配到每个簇的样本的均值向量,作为新的簇的质心。 4.重复2,3直到k个簇的质心点不再发生变化或准则函数收敛。
  • 21. 基于质心的 k-means聚类算法坐标表示5个点{X1,X2,X3,X4,X5}作为一个聚类分析的二维样本:X1=(0,2),X2=(0,0),X3=(1.5,0),X4=(5,0),X5=(5,2)。假设要求的簇的数量k=2。 第1步:由样本的随机分布形成两个簇: C1={X1,X2,X4}和C2={X3,X5}。 这两个簇的质心M1和M2是: M1={(0+0+5)/3,(2+0+0)/3}={1.66,0.66}; M2={(1.5+5)/2,(0+2)/2}={3.25,1.00};
  • 22. 基于质心的 k-means聚类算法样本初始随机分布之后,方差是: e12=[(0-1.66)2+(2-0.66)2]+[(0-1.66)2+(0-0.66)2]+[(5-1.66)2+(0-0.66)2]=19.36; e22=8.12; 总体平方误差是:E2=e12+e22=19.36+8.12=27.48(公式)
  • 23. 基于质心的 k-means聚类算法第2步:取距离其中一个质心(M1或M2)最小的距离分配所有样本,簇内样本的重新分布如下: d(M1,X1)=(1.662+1.342)1/2=2.14 d(M2,X1)=3.40 ==>X1∈C1; d(M1,X2)=1.79 和 d(M2,X2)=3.40 ==>X2∈C1 d(M1,X3)=0.83 和 d(M2,X3)=2.01 ==>X3∈C1 d(M1,X4)=3.41 和 d(M2,X4)=2.01 ==>X4∈C2 d(M1,X5)=3.60 和 d(M2,X5)=2.01 ==>X5∈C2 新簇C1={X1,X2,X3}和C2={X4,X5}
  • 24. 基于质心的 k-means聚类算法第3步:计算新的质心: M1={0.5,0.67}; M2={5.0,1.0}。 相应的方差及总体平方误差分别是: e12=4.17; e22=2.00; E=6.17; 可以看出第一次迭代后,总体误差显著减小(从值27.48到6.17)。在这个简单的例子中,第一次迭代同时也是最后一次迭代,因为如果继续分析新中心和样本间的距离,样本将会全部分给同样的簇,不将重新分配,算法停止。
  • 25. k-means算法的变体要求用户必须事先给出要生成的簇的数目,选择初始划分的最佳方向、更新分区和停止准则 大小很不相同的簇或具有凹状的簇。 算法只有在簇的平均值被定义的情况下才能使用,这不适涉及有分类属性的数据。 k-prototypes算法对数值与离散两种混合的数据聚类, k-modes方法对离散属性 对噪音和异常点非常敏感
  • 26. 基于有代表性对象的技术k-mediods方法 基本策略:不采用簇中样本的平均值作为参照点,选用簇中位置最中心的对象――中心点作为参照点。 PAM(Partitioning Around Medoids围绕中心点划分) + Oi P Oj + + Orandom+ Oi Oj + P + OrandomC=d(p,Oi)-d(p,Oj) C=d(p,Orandom)-d(p,Oj)
  • 27. +Oi P Oj + + Orandom+Oi Oj + + P OrandomC=0 C=d(p,Orandom)-d(p,Oi) S= C
  • 28. PAM算法: 1.随机选择k个代表对象作为初始的中心点。 2.repeat 3.指派每个剩余对象给离它最近的中心点所代表的簇; 4.随机的选择一个非中心点对象Orandom 5.计算用Orandom代替Oj的总代价Tcih 6.if s为负,则Orandom代替Oj,形成新的k个中心点的集合 7.Until 不发生变化
  • 29. 层次聚类 凝聚的层次聚类采用自底向上策略,首先将每个样本作为一个簇,然后合并这些原子簇形成越来越大的簇,减少簇的数目,直到所有的样本都在一个簇中,或某个终结条件被满足。 分裂的层次聚类采用自顶向下策略,首先将所有样本置于一个簇中,然后逐渐细分为越来越小的簇,来增加簇的数目,直到每个样本自成一个簇,或者达到某个终结条件,例如达到了某个希望的簇的数目或两个最近的簇之间的距离超过了某个阈值。
  • 30. 凝聚层次聚类 1.初始化:计算包含每对样本间距离(如欧氏距离)的相似矩阵,把每个样本作为一个簇; 2.选择:使用相似矩阵查找最相似的两个簇; 3.更新:将两个簇合并为一个簇,簇的个数通过合并被更新;同时更新相似矩阵,将两个簇的两行(两列)距离用1行(1列)距离替换反映合并操作。 4.重复:执行n-1次步骤2和步骤3; 5.结束:当所有样本都合并成一个簇或满足指定的簇的数目时,整个过程结束。
  • 31. 一.单连接算法(single-linkage) (最近邻(Nearest Neighbor)): 基本思想:两个簇之间的距离用从两个簇中抽取的每对样本的最小距离 作为距离度量,一旦最近的两个类的距离超过某个任意给定的阈值,算法就自动结束。 二.全连接算法 三.平均连接算法凝聚层次聚类
  • 32. 先将五个样本都分别看成是一个簇,最靠近的两个簇是3和4,因为他们具有最小的簇间距离 D(3,4)=5.0。 第一步:合并簇3和4,得到新簇集合1,2,(34),5 单连接算法
  • 33. 更新距离矩阵: D(1,(34)) = min(D(1,3),D(1,4)) = min(20.6, 22.4) = 20.6; D(2,(34)) = min(D(2,3),D(2,4)) = min(14.1, 11.2) = 11.2; D(5,(34)) = min(D(3,5),D(4,5)) = min(25.0, 25.5) = 25.0. 原有簇1,2,5间的距离不变,修改后的距离矩阵如图所示,在四个簇1,2,(34),5中,最靠近的两个簇是1和5,它们具有最小簇间距离D(1,5)=7.07。 单连接算法
  • 34. 单连接算法
  • 35. 单连接算法单连接树
  • 36. 改进的层次聚类 BIRCH是一个综合的层次聚类方法,它引入了两个概念:聚类特征和聚类特征树(CF树) CURE方法采用了一种新颖的层次聚类算法,该算法选择基于质心和基于代表对象方法之间的中间策略。 ROCK方法是一个可选的凝聚的层次聚类算法,适用于分类属性。 Chameleon(变色龙)方法是一个在层次聚类中采用动态模型的层次聚类算法
  • 37. 基于密度的方法 基于样本之间的距离的聚类方法只能发现球状的簇,基于密度的方法可用来过滤“噪声”孤立点数据,以发现任意形状的簇。其主要思想是只要临近区域的密度(样本的数目)超过某个阈值则继续聚类。即对于给定簇中的每个样本,在一个给定范围的区域中必须至少包含某个数目的样本。
  • 38. 基于密度的方法 基于密度聚类的相关定义: a.给定对象半径ε内的区域称为该对象的ε-邻域。 b.如果一个对象的ε-邻域至少包含最小数目MinPts个对象,则称该对象为核心对象。 c.给定一个对象集合D,如果p是在q的ε-邻域内,而q是一个核心对象,则称对象p从对象q出发是直接密度可达的。
  • 39. 基于密度的方法 d.如果存在一个对象链p1,p2,…,pn,p1=q,pn=p,对pi∈D(1<=i<=n),pi+1是从pi关于ε和MinPts直接密度可达的,则对象p是从对象q关于ε和MinPts密度可达的。 e.如果对象集合D中存在一个对象o,使得对象p和q是从o关于ε和MinPts密度可达的,那么对象p和q是关于ε和MinPts密度相连的。
  • 40. 基于密度的方法 一.基于高密度连接区域的聚类方法:DBSCAN 二.通过对象排序识别聚类结构的聚类方法:OPTICS a.核心距离:一个对象p的核心距离是使得p成为核心对象的最小的ε。如果p不是核心对象,p的核心距离没有定义; b.可达距离:一个对象q关于另一个对象p的可达距离是p的核心距离和p与q的欧几里得距离之间的较大值。如果p不是一个核心对象,p和q之间的可达距离没有定义。 三.基于密度分布函数的聚类方法:DENCLUE
  • 41. 基于网格的方法 基于网格的多分辨率方法STING,在网格单元中收集统计信息。 WaveCluster是一个多分辨率的聚类方法,通过小波变换来转换原始的特征空间。 CLQUE是一个综合了基于密度和基于网格方法的聚类算法,对于大型数据库中的高维数据的聚类非常有效。
  • 42. 基于模型的方法 统计学方法和神经网络方法