zwp@Office:东区管理科研楼1006Phone:63600565课件/~zwp/论坛
简介
1.1简介.......................11.2距离与相异性度量...............61.3聚类方法....................11
1.3.1系统聚类法...............121.3.2K-means.................191.3.3谱聚类..................241.4确定类的数目..................301.5聚类质量的评价.................38
PreviousNextFirstLastBackForward
1 1.1简介 •将一组数据依照内在相似性划分为多个类别，使类别内的数据相似度较大而类别间的数据相似度较小。
•聚类分析假设数据的特征允许我们可以识别不同的类别，但事先并不知道数据由几个组构成，因而是一种无监督的学习。
•同义词：datasegmentation（数据挖掘领域）、classdiscovery（机器学习领域）。
•应用领域包括经济领域，生物领域，数据挖掘等等 •例如商店希望刻画顾客群的特征，区分不同的客户类，挖掘有价值的客户，以制定不同的关系管理方式，提高客户对商业活动的响应率 PreviousNextFirstLastBackForward
1 相关的研究领域 –数据挖掘:各种各种复杂形状类的识别，高维聚类等–统计学:主要集中在基于距离的聚类分析，发现球状类–机器学习:无指导学习（聚类不依赖预先定义的类）–其他领域:空间数据技术,生物学,市场营销学 什么是类?
–至今还没有普遍接受的定义：哪些特征决定了一个类。
因此，不同的聚类方法多得到不同的聚类结果。
–直观上：一个类是一组个体（对象、点等），这些个体离这个类的中心个体比较“近”（在合适的度量下）；不同类的成员之间的距离“比较远”。
PreviousNextFirstLastBackForward
2 •在2D或3D散点图中，我们很容易的发现数据中的类。
•对发现的类我们经常赋予我们认为“应该”会存在的结构或者意义。
•必须注意：“类”可能仅仅是一个聚类方法的结果 •一个“类”依赖于如何定义它以及应用背景 PreviousNextFirstLastBackForward
3 聚类与分类(clusteringandclassification) •分类： –有类别标记信息,因此是一种监督学习–根据训练样本获得分类器，然后把每个数据归结到某个 已知的类，进而也可以预测未来数据的归类。
–分类具有广泛的应用，例如医疗诊断、信用卡的信用分 级、图像模式识别。
•聚类： –无类别标记,因此是一种无监督学习–无训练样本，根据信息相似度原则进行聚类，通过聚类， 人们能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间的关系 PreviousNextFirstLastBackForward
4 •使用可视化工具探测类 –多峰性是不同类存在的标志–多种可视化技术可以使用:PCA,FA,MDS,Manifest learning,SOM等等. PreviousNextFirstLastBackForward
5 1.2距离与相异性度量 •聚类就是发现数据中具有“相似性”(similarity)的个体 •选择合适的“相似性”度量是进行聚类的关键,相似性度量函数s(·,·)一般满足 1.0≤s(x,y)≤12.s(x,x)=13.s(x,y)=s(y,x) •也可以使用相异性(dissimilarity)来度量数据之间的接近程度.下面我们以相异性为例.相异性度量和相似性度量之间一般可以相互转换. •相异性度量多为某种”距离”度量 •样本点之间的相异性(距离)函数d(·,·)一般满足 PreviousNextFirstLastBackForward
6 1..d(x,y)≥
0,等号成立当且仅当x=y2.d(x,x)=0 metricdissimilarity 3.d(x,y)=d(y,x)4.d(x,y)≤d(x,z)+d(z,y)..5.d(x,y)≤max{d(x,z),d(z,y)} .如果还满足第5条,则称d为ultrametricdissimilarity •样本点之间的相异性记x,y∈Rp为两个样本点,则距离的选择非常重要,最好的距离准则往往要基于经验,知识和运气等得到. •一般要根据数据的类型选择合适的相异性(距离)度量准则. –比例尺度(区间尺度)下的样本数据点常用距离准则 PreviousNextFirstLastBackForward
7 Minkowski: [∑p ]1/m dm(x,y)= |xk−yk|m =∥x−y∥m k=
1 Manhattan:(city-blockdistance,box-cardistance) ∑pd(x,y)=|xk−yk|=∥x−y∥1 k=
1 Euclidean:d(x,y)=∥x−y∥
2 maximum:(Chebyshevdistance) d(x,y)=max|xi−yi|=∥x−y∥∞ Canberra:(非负量)d(x,y)=∑p|xk−yk|xk+yk k=
1 PreviousNextFirstLastBackForward
8 –0-1型变量:若x,y的元素均非零即
1,则 @x@
1 0 行和 y@
1 a b a+b
0 c d c+d 列和a+cb+dn=a+b+c+d binary(ard):Czekanowski: d(x,y)=b+c←no0-0matcha+b+c d(x,y)=b+c2a+b+c ←no0-0matchdouble1-1match .其他见课本表12.1. –属性变量:若x,y为属性变量,各有p和q个不同的类别,则度量两者之间的相似性常常基于列联表度量性检验 PreviousNextFirstLastBackForward
9 中的χ2统计量进行.Coef.ofcontingency Cramer’sVcontingencycoef. (χ2)1/2sij=χ2+n ( χ
2 )1/2 sij=nmin{p−1,q−1} •变量之间的相似性样本相关系数常常用来度量变量之间的相 似性,常常使用相关系数的绝对值度量变量之间的相似性.x的 第i个分量Xi和第j个分量Xj之间的相似性: ∑n(xik−x¯i)(xjk−x¯j) 样本相关系数rij=[∑ k=
1 ∑ ]1/2 nk=1(xik−x¯i)2nk=1(xjk−x¯j)
2 ∑nxx 夹角余弦θij=[∑ k=1ikjk ∑ ]1/2 nk=1x2iknk=1x2jk PreviousNextFirstLastBackForward 10 1.3 常见的聚类方法包括 聚类方法 PreviousNextFirstLastBackForward 11 1.3.1系统聚类法 •系统聚类法(Hierarchicalclustering,也称层次聚类法)是最经典和常用的聚类方法之
一. •系统聚类法需要度量样本点之间的距离(dissimilarity)和类与类之间的联接(linkage)程度 •系统聚类法包括两种 –聚合方法(agglomerativehierarchicalmethod):(自下而上)一开始将每个样本个体作为单独的一类，然后根据类间联接程度，合并相近的类，直到所有的类合并成一个类 –分裂方法(divisivehierarchicalmethod):(自上而下)一开始将所有的样本个体置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每个样本个体单独为一个类. •我们主要介绍聚合聚类方法 PreviousNextFirstLastBackForward 12 树状图(Dendrogram) 层次聚类的结果常常使用树状图(dendrogram)来表示.•每个节点表示一个类 •每个叶子节点表示一个独点(只含一个样本点的类). •根节点是包含了所有样本点的类 •每个中间节点有两个子节点,表示其通过合并这两个子类而来 •当叶子节点调整到高度0时候,则每个中间节点的高度与其两个子节点间的相异度大小成比例 •在合适的高度上对树进行切割得到聚类结果 PreviousNextFirstLastBackForward 13 类间联系程度度量(Linkagecriteriac)lusterI•singlelinkage D(
I,J)=min{dij}i∈I,j∈
J •pletelinkage D(
I,J)=max{dij}i∈I,j∈
J •averagelinkage
1 ∑ D(
I,J)=nI+nJdij i∈I,j∈
J . PreviousNextFirstLastBackForward clusterJ14 clusterI clusterJ •centroidlinkage:D(
I,J)=∥x¯I−x¯J∥ •wardmethod:分别计算 类I和J内各点到其重心 (均值)的平方欧式距离和 (称为离差平方和),分别记 为WI和WJ;然后将所有 . 点合并为
一 个类
M,计算其离差平方和WM,最后定义类I和J之间的平方距 离为 D(
I,J)=WM−WI−WJ 离差平方和法使得两个大的类倾向于有较大的距离，因而不易合并；相反，两个小的类却因倾向于有较小的距离而易于合并。
这往往符合我们对聚类的实际要求。
PreviousNextFirstLastBackForward 15 几种联系度量的特点: •Singlelinkage下的类有串链特点.合并两个类时只看它们最近的点而不管其他点,聚出的类呈现链状.因此适合于条形甚至S形的类.其聚类结果对相异度的单调变换不变. •Completelinkage避免出现链状类,但是会导致过大的类.因为其只考虑两类最相异(远)的点,故受异常点(距离别的类比所在类的点更近)影响严重.其聚类结果对相异度的单调变换不变. •Averagelinkage是前两者的权衡.但是当相异度进行单调变换时候,基于平均距离的聚类结果会发生变化. •Centroidlinkage下的聚类树状图可能会出现逆连(中间节点的高度在两个子节点高度之间),切割树时难以确定类数目 PreviousNextFirstLastBackForward 16 聚合聚类算法1..输入所有样本点,每个点为一个类
2.计算相异度(距离)矩阵(dij)
3.合并最小链接(linkage)的两个类
4.计算新的类和其他所有类之间链接大小
5.重复3-
4,直至所有类合并为一个类或者满足停止条件
6.输出树状图,切割树状图得到聚类结果..聚合聚类方法较分裂式聚类方法更常用,分裂方法由于难以指定合适分裂方法而不太常用.cluster包里的diana函数使用分裂式层次聚类方法(KaufmanandRousseeuw,1990). PreviousNextFirstLastBackForward 17 系统聚类方法的特点 •无需事先指定类的数目 •需要确定相异度和联接度量准则 •运算量较大,适用于不太大规模的数据 •一旦一个步骤(合并或分裂)完成,就不能撤销或修正,因此产生了改进的层次聚类方法,如BRICH,BURE,ROCK,Chameleon等. PreviousNextFirstLastBackForward 18 1.3.2K-means •流行和经典的聚类方法之
一,比层次聚类法运算量小,适用于小到中大规模样本数据 •需要事先指定聚类的数目k •思想:随机选择k个样本点，每个样本点初始地代表一个类的平均值或中心,对剩余每个样本点,根据其到类中心的距离,被划分到最近的类;然后重新计算每个类的平均值.不断重复这个过程,直到所有的样本都不能再分配为止. •适用于发现球状类 •不同的初始值,结果可能不同 •有些K-means算法的结果和数据输入顺序有关 •可能会陷入局部解 PreviousNextFirstLastBackForward 19 K-means算法MacQueen(1967)提出的经典算法.核心想法是:找出k个类, 使得每个数据点到与其最近的聚类中心的平方欧式距离和最小.算法如下
1.输入数据和聚类数目k
2.执行下面二者之
一 •随机将数据分为k个类C1,...,Ck,计算每个类的中心x¯i,i=1,...,k •指定k个类的中心xi,i=1,...,k,将所有数据点划分到离其最近的类中心所在的类
3.计算每个数据点到其所属类的中心的平方距离 ∑k∑ ESS= ∥xj−x¯i∥
2 i=1j∈Ci PreviousNextFirstLastBackForward 20
4.重新将每个数据点划分到离其最近的类中心所在的类,使得ESS减少.完成后重新计算各类的中心x¯i,i=1,...,k
5.重复3和
4,直至没有点需要进行调整(ESS不能减少) K-medoids方法是对K-means方法的推广:其类似于K-means算法,区别在于 •每个类使用“代表个体”代替K-means中的类个体平均 •可以使用相异度度量,而不像K-means仅限于平方欧式距离 •需要事先指定类的个数 •相比K-means方法更加稳健(对噪音和异常点) •Rbase的kmeans函数使用K-means算法,而cluster包的pam(partitioningaroundmedoids)函数使用K-medoids算法. PreviousNextFirstLastBackForward 21 •K-means和K-medoids算法的计算复杂度高,适于小规模数据. •大规模数据可以使用CLARA(ClusteringLARgeApplications,KaufmanandRousseeuw1990)算法:随机选择一部分的样本点,使用K-medoids算法 •以及改进的CLARANS(ClusteringLargeApplicationbaseduponRANdomizedSearch,NgandHan1994)算法等. PreviousNextFirstLastBackForward 22 K-medoids算法
1.输入相异度矩阵D=(dij)和聚类数目k
2.随机选择k个样本点作为类的中心点(medoids)
3.将每个样本点关联到和其相异度最小的中心点(即所有样本点划分成k个类)
4.对第l个类(l=1,...,k),寻找类内具有最小平均相异度的点 i0: ∑ i0=argmindij i∈Cl j∈Cl 从而得到第l个类的新的中心点
5.重复3和4直至没有个体能够调整 PreviousNextFirstLastBackForward 23 1.3.3谱聚类 •两种不同的准则–紧性patness):k-means,hierarchicalclustering–相连性(connectivity):spectralclustering 谱聚类(Spectralclustering)是现代流行聚类算法之
一，较传统的K-means和层次聚类要好。
PreviousNextFirstLastBackForward 24 •基于数据之间的相似度矩阵，使用特征向量(谱). •在低维空间表达原始数据后,在低维空间使用K-means进行聚类. •常使用无向图有权图来描述 •给定样本点V=(x1,...,xn),计算其相似度(图分析中称连接阵)矩阵
W,将数据划分为k个组,使得组内的点相似,而组间的点不相似 PreviousNextFirstLastBackForward 25 –对无向图中顶点之间的权重,常用Gaussiankernel建立:∥xi−xj∥ Wij=e−2σ
2,σ2控制相邻程度 –目标:使得组内具有较高权重,区间具有较小权重 •记W(
A,B)=∑i∈A,j∈BWij表示两个顶点集A和B之间的相似程度.从而寻找一个最优的划分集A1,...,Ak,使得下式 最小化 cut(A1,...,Ak)=12∑kW(Ai,A¯i)i=
1 其中A¯表示A的补集. PreviousNextFirstLastBackForward 26 •但是这样的目标函数对异常点敏感: •其中一种解决方法(Ncut,ShiandMalik,2000): 1∑kW(Ai,A¯i) Ncut(A1,...,Ak)=
2 vol(Ai) i=
1 PreviousNextFirstLastBackForward 27 其中vol(A)=∑i∈Adi=∑i∈A∑nj=1Wij. –识别最小的Ncut(A1,...,Ak)是NP-hard.–有一些基于线性代数的有效逼近算法 –基于Laplacian矩阵,或GraphLaplacian:L=D−
W,D=diag(d1,...,dn). –对指定的k(k>2),记hij=√
1,如果xi∈Aj,否则为vol(Aj)
0.H=(hij),则: minTrace(H′LH) Am⊂inVNcut(A1,...,Ak)⇐⇒sAt1.,...,AkH′DH=Ik 替换H=D−1/2T minTrace(T′D−1/2LD−1/2T), Relaxation!
!
!
=⇒sTt∈.Rn×kT′T=Ik. –最优的Topt为矩阵Lsym=D−1/2LD−1/2的前k个特征向量. PreviousNextFirstLastBackForward 28 –最终的解Hopt=D−1/2Topt为矩阵Lrw=D−1L的前k个特征根. 谱聚类算法(ShiandMalik,2000)给定n个点x1,...,xn,以及聚类数目k: •构建图:计算连接矩阵
W •计算Laplacian阵L=D−
W •计算广义特征根方程Lu=λDu的前k个特征向量,记为U=[u1,...,uk] •记yi为U的第i行,i=1,...,n,使用K-means算法对y1,...,yn聚类得到类C1,...,Ck •输出类A1,...,Ak,其中Ai={xj|yj∈Ci}Ng,Jordan,andWeiss(2002)给出了另外一种类似的算法. PreviousNextFirstLastBackForward 29 1.4确定类的数目 •有时候提前指定聚类的数目没有问题,例如将一个客户数据根据k个销售员聚成k个类等 •大多数情况下,聚类的确切数目是未知的.此时确定聚类的数目是很困难的一个问题(高维数据难以检查,或者难以解释类数目的合理性). •确定类的数目也是非常重要的,比如确定某种癌症有两种类型还是三种类型是差异非常大的 Silhouette(侧影)法 •KaufmanandRousseeuw(1990)提出的一种既可以评价每个点应该在当前所属类还是其他类,也可以评价整体的聚类结果效果. PreviousNextFirstLastBackForward 30 •给定观测点i,记 –a(i)为点i与其所属类Ci中其他点之间的平均相异度值–d¯(i,C)表示点i到其他类C(C̸=Ci)内的所有点之间的 平均相异度值–b(i)表示所有d¯(i,C)中的最小值 •第i个观测点的Silhouette值定义为b(i)−a(i) s(i)=max{a(i),b(i)} •平均的Silhouetter值为1∑n s¯=nswii=
1 PreviousNextFirstLastBackForward 31 •显然,−1≤s(i)≤1,s(i)靠近1需要a(i)≪b(i).由a(i)的定义知小的a(i)意味着点i匹配该类非常好,而大的b(i)意味着点i匹配其他类很差,从而s(i)靠近1表明点i的聚类合适. •s(i)靠近-1表明点i被聚类到相邻类中更合适 •s(i)靠近0表明点i在两个类的交集处,即该点属于当前类或者相邻类均合适 •KaufmanandRousseeuw建议使用评价的轮廓宽来估计数据中的类数目: –s¯>0.5表明数据聚类合适–s¯<0.2表明数据不存在聚类特征 •R的包cluster里的silhouette函数将每个类中各点的s(i)按从小到大以水平线画出. PreviousNextFirstLastBackForward 32 PreviousNextFirstLastBackForward 33 CHindex我们以K-means方法为例,大部分想法可以推广到其他方法里. •给定类数目k,K-means算法最小化类内波动(within-cluster variation): ∑k∑ W(k)= ∥xj−x¯i∥
2 i=1C(j)=i •显然W(k)随k增加而减少,W(k)越小表明类越紧凑. •类间波动性(Between-clustervariation)度量类与类之间远离 的程度: ∑kB(k)=ni∥x¯i−x¯∥
2 i=
1 •显然B(k)随k增加而增加,B(k)越大表明类与类之间界限越清晰 PreviousNextFirstLastBackForward 34 •单独使用W(k)或B(k)都是有缺点的,因此自然地使用 选择合适的k: CH(k)=B(k)/(k−1)W(k)/(n−k) kˆ=argmaxCH(k)2≤k≤Kmax PreviousNextFirstLastBackForward 35 GapStatistic •W(k)随k增加而减少,但是对每个k的减少量应该是有信息的!
•Tibshiranietal.(2001)提出的GapStatistic基于想法:比较观察到的类内波动性W(k)和W∗(k),这里W∗(k)是在零假设均匀分布(数据为一个类,且服从一个区域上的均匀分布)下得到类内波动性,通过随机模拟计算. •使用Bootstrap方法,计算 Gapn(k)=En∗log(W∗(k))−log(W(k)) 1∑ ∗ ≈ log(Wb(k))−log(W(k))
B b 以及sdk=B1∑b(Wb∗(k)−W¯∗(k))
2,其中W¯∗(k)=B1∑bWb∗(k). PreviousNextFirstLastBackForward 36 √•令sk=sdk1+1/B,最后选择类的数目为 kˆ=inf{k:Gap(k)≥Gap(k+1)−sk+1} PreviousNextFirstLastBackForward 37 1.5聚类质量的评价 •聚类性能评价方法通常分为外部评价法(externalcriterion)和内部评价法(internalcriterion). •外部评价法分析聚类结果与另一参考结果(reference,比如另一种聚类方法的结果或者真实的类别)有多么相近.例如 –Purity,F-measure,RandStatistics,Entropy等 •内部评价法来分析聚类的本质特点.内部评价法常又分为绝对和相对评价法.常用的方法有 –绝对评价法:Davis-Bouldin,Dunn,ExpectedDensityρ等–相对评价法:Elbowcriterion,GAPstatistics等 PreviousNextFirstLastBackForward 38 外部评价法 •设有n个样本点,参考(Reference)类别为C∗={C1∗,...,Cl∗}. •某种聚类结果为C={C1,...,Ck} F-measure: •精度(Precision):|Cj∩Ci∗|/|Cj|. •查全率(Recall):|Cj∩Ci∗|/|Ci∗| •计算Cj相对于Ci∗的F-measure:Fij(α)= 1+α
1 α , precision+recall (加权调和平均),α常取
1. 从而总的F-measure定义为∑l|Ci∗|max{F}nj=1,...,kij i=
1 F-measure较大时说明聚类结果满意. PreviousNextFirstLastBackForward 39 •Entropy:聚类C相对于C∗的Entropy定义为 ∑|Cj|[ ∑|Cj∩Ci∗||Cj∩Ci∗|] H(C)= − log2 C∈Cn C∩C∗̸=∅|Cj| |Cj| j ji •RandIndex考虑样本点中的点对,记 n11=♯{(xi,xj)|xi,xj∈Ci;xi,xj∈Ck∗}n00=♯{(xi,xj)|xi∈Ci1,xj∈Ci2;xi∈Ck∗1,xj∈Ck∗2}n10=♯{(xi,xj)|xi,xj∈Ci;xi∈Ck∗1,xj∈Ck∗2}n01=♯{(xi,xj)|xi∈Ci1,xj∈Ci2;xi,xj∈Ck∗2} Randindex定义为 R=n11(+)n00n2 R=0表明两种聚类没有重叠,R=1表示两个聚类完全相同.其严重依赖于聚类数目. PreviousNextFirstLastBackForward 40 •AdjustedRandIndex两种不相关随机划分的Randindex期望值并不为常数(零),HubertandArabie(1985)对Randindex进行了调整(假设超几何分布:固定列联表的边际),使得对两种独立的聚类值为
0,两种完全相同的聚类值为
1.Meila(2003)指出AjustedRandindex值可取负值. PreviousNextFirstLastBackForward 41
1 1.1简介 •将一组数据依照内在相似性划分为多个类别，使类别内的数据相似度较大而类别间的数据相似度较小。
•聚类分析假设数据的特征允许我们可以识别不同的类别，但事先并不知道数据由几个组构成，因而是一种无监督的学习。
•同义词：datasegmentation（数据挖掘领域）、classdiscovery（机器学习领域）。
•应用领域包括经济领域，生物领域，数据挖掘等等 •例如商店希望刻画顾客群的特征，区分不同的客户类，挖掘有价值的客户，以制定不同的关系管理方式，提高客户对商业活动的响应率 PreviousNextFirstLastBackForward
1 相关的研究领域 –数据挖掘:各种各种复杂形状类的识别，高维聚类等–统计学:主要集中在基于距离的聚类分析，发现球状类–机器学习:无指导学习（聚类不依赖预先定义的类）–其他领域:空间数据技术,生物学,市场营销学 什么是类?
–至今还没有普遍接受的定义：哪些特征决定了一个类。
因此，不同的聚类方法多得到不同的聚类结果。
–直观上：一个类是一组个体（对象、点等），这些个体离这个类的中心个体比较“近”（在合适的度量下）；不同类的成员之间的距离“比较远”。
PreviousNextFirstLastBackForward
2 •在2D或3D散点图中，我们很容易的发现数据中的类。
•对发现的类我们经常赋予我们认为“应该”会存在的结构或者意义。
•必须注意：“类”可能仅仅是一个聚类方法的结果 •一个“类”依赖于如何定义它以及应用背景 PreviousNextFirstLastBackForward
3 聚类与分类(clusteringandclassification) •分类： –有类别标记信息,因此是一种监督学习–根据训练样本获得分类器，然后把每个数据归结到某个 已知的类，进而也可以预测未来数据的归类。
–分类具有广泛的应用，例如医疗诊断、信用卡的信用分 级、图像模式识别。
•聚类： –无类别标记,因此是一种无监督学习–无训练样本，根据信息相似度原则进行聚类，通过聚类， 人们能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间的关系 PreviousNextFirstLastBackForward
4 •使用可视化工具探测类 –多峰性是不同类存在的标志–多种可视化技术可以使用:PCA,FA,MDS,Manifest learning,SOM等等. PreviousNextFirstLastBackForward
5 1.2距离与相异性度量 •聚类就是发现数据中具有“相似性”(similarity)的个体 •选择合适的“相似性”度量是进行聚类的关键,相似性度量函数s(·,·)一般满足 1.0≤s(x,y)≤12.s(x,x)=13.s(x,y)=s(y,x) •也可以使用相异性(dissimilarity)来度量数据之间的接近程度.下面我们以相异性为例.相异性度量和相似性度量之间一般可以相互转换. •相异性度量多为某种”距离”度量 •样本点之间的相异性(距离)函数d(·,·)一般满足 PreviousNextFirstLastBackForward
6 1..d(x,y)≥
0,等号成立当且仅当x=y2.d(x,x)=0 metricdissimilarity 3.d(x,y)=d(y,x)4.d(x,y)≤d(x,z)+d(z,y)..5.d(x,y)≤max{d(x,z),d(z,y)} .如果还满足第5条,则称d为ultrametricdissimilarity •样本点之间的相异性记x,y∈Rp为两个样本点,则距离的选择非常重要,最好的距离准则往往要基于经验,知识和运气等得到. •一般要根据数据的类型选择合适的相异性(距离)度量准则. –比例尺度(区间尺度)下的样本数据点常用距离准则 PreviousNextFirstLastBackForward
7 Minkowski: [∑p ]1/m dm(x,y)= |xk−yk|m =∥x−y∥m k=
1 Manhattan:(city-blockdistance,box-cardistance) ∑pd(x,y)=|xk−yk|=∥x−y∥1 k=
1 Euclidean:d(x,y)=∥x−y∥
2 maximum:(Chebyshevdistance) d(x,y)=max|xi−yi|=∥x−y∥∞ Canberra:(非负量)d(x,y)=∑p|xk−yk|xk+yk k=
1 PreviousNextFirstLastBackForward
8 –0-1型变量:若x,y的元素均非零即
1,则 @x@
1 0 行和 y@
1 a b a+b
0 c d c+d 列和a+cb+dn=a+b+c+d binary(ard):Czekanowski: d(x,y)=b+c←no0-0matcha+b+c d(x,y)=b+c2a+b+c ←no0-0matchdouble1-1match .其他见课本表12.1. –属性变量:若x,y为属性变量,各有p和q个不同的类别,则度量两者之间的相似性常常基于列联表度量性检验 PreviousNextFirstLastBackForward
9 中的χ2统计量进行.Coef.ofcontingency Cramer’sVcontingencycoef. (χ2)1/2sij=χ2+n ( χ
2 )1/2 sij=nmin{p−1,q−1} •变量之间的相似性样本相关系数常常用来度量变量之间的相 似性,常常使用相关系数的绝对值度量变量之间的相似性.x的 第i个分量Xi和第j个分量Xj之间的相似性: ∑n(xik−x¯i)(xjk−x¯j) 样本相关系数rij=[∑ k=
1 ∑ ]1/2 nk=1(xik−x¯i)2nk=1(xjk−x¯j)
2 ∑nxx 夹角余弦θij=[∑ k=1ikjk ∑ ]1/2 nk=1x2iknk=1x2jk PreviousNextFirstLastBackForward 10 1.3 常见的聚类方法包括 聚类方法 PreviousNextFirstLastBackForward 11 1.3.1系统聚类法 •系统聚类法(Hierarchicalclustering,也称层次聚类法)是最经典和常用的聚类方法之
一. •系统聚类法需要度量样本点之间的距离(dissimilarity)和类与类之间的联接(linkage)程度 •系统聚类法包括两种 –聚合方法(agglomerativehierarchicalmethod):(自下而上)一开始将每个样本个体作为单独的一类，然后根据类间联接程度，合并相近的类，直到所有的类合并成一个类 –分裂方法(divisivehierarchicalmethod):(自上而下)一开始将所有的样本个体置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每个样本个体单独为一个类. •我们主要介绍聚合聚类方法 PreviousNextFirstLastBackForward 12 树状图(Dendrogram) 层次聚类的结果常常使用树状图(dendrogram)来表示.•每个节点表示一个类 •每个叶子节点表示一个独点(只含一个样本点的类). •根节点是包含了所有样本点的类 •每个中间节点有两个子节点,表示其通过合并这两个子类而来 •当叶子节点调整到高度0时候,则每个中间节点的高度与其两个子节点间的相异度大小成比例 •在合适的高度上对树进行切割得到聚类结果 PreviousNextFirstLastBackForward 13 类间联系程度度量(Linkagecriteriac)lusterI•singlelinkage D(
I,J)=min{dij}i∈I,j∈
J •pletelinkage D(
I,J)=max{dij}i∈I,j∈
J •averagelinkage
1 ∑ D(
I,J)=nI+nJdij i∈I,j∈
J . PreviousNextFirstLastBackForward clusterJ14 clusterI clusterJ •centroidlinkage:D(
I,J)=∥x¯I−x¯J∥ •wardmethod:分别计算 类I和J内各点到其重心 (均值)的平方欧式距离和 (称为离差平方和),分别记 为WI和WJ;然后将所有 . 点合并为
一 个类
M,计算其离差平方和WM,最后定义类I和J之间的平方距 离为 D(
I,J)=WM−WI−WJ 离差平方和法使得两个大的类倾向于有较大的距离，因而不易合并；相反，两个小的类却因倾向于有较小的距离而易于合并。
这往往符合我们对聚类的实际要求。
PreviousNextFirstLastBackForward 15 几种联系度量的特点: •Singlelinkage下的类有串链特点.合并两个类时只看它们最近的点而不管其他点,聚出的类呈现链状.因此适合于条形甚至S形的类.其聚类结果对相异度的单调变换不变. •Completelinkage避免出现链状类,但是会导致过大的类.因为其只考虑两类最相异(远)的点,故受异常点(距离别的类比所在类的点更近)影响严重.其聚类结果对相异度的单调变换不变. •Averagelinkage是前两者的权衡.但是当相异度进行单调变换时候,基于平均距离的聚类结果会发生变化. •Centroidlinkage下的聚类树状图可能会出现逆连(中间节点的高度在两个子节点高度之间),切割树时难以确定类数目 PreviousNextFirstLastBackForward 16 聚合聚类算法1..输入所有样本点,每个点为一个类
2.计算相异度(距离)矩阵(dij)
3.合并最小链接(linkage)的两个类
4.计算新的类和其他所有类之间链接大小
5.重复3-
4,直至所有类合并为一个类或者满足停止条件
6.输出树状图,切割树状图得到聚类结果..聚合聚类方法较分裂式聚类方法更常用,分裂方法由于难以指定合适分裂方法而不太常用.cluster包里的diana函数使用分裂式层次聚类方法(KaufmanandRousseeuw,1990). PreviousNextFirstLastBackForward 17 系统聚类方法的特点 •无需事先指定类的数目 •需要确定相异度和联接度量准则 •运算量较大,适用于不太大规模的数据 •一旦一个步骤(合并或分裂)完成,就不能撤销或修正,因此产生了改进的层次聚类方法,如BRICH,BURE,ROCK,Chameleon等. PreviousNextFirstLastBackForward 18 1.3.2K-means •流行和经典的聚类方法之
一,比层次聚类法运算量小,适用于小到中大规模样本数据 •需要事先指定聚类的数目k •思想:随机选择k个样本点，每个样本点初始地代表一个类的平均值或中心,对剩余每个样本点,根据其到类中心的距离,被划分到最近的类;然后重新计算每个类的平均值.不断重复这个过程,直到所有的样本都不能再分配为止. •适用于发现球状类 •不同的初始值,结果可能不同 •有些K-means算法的结果和数据输入顺序有关 •可能会陷入局部解 PreviousNextFirstLastBackForward 19 K-means算法MacQueen(1967)提出的经典算法.核心想法是:找出k个类, 使得每个数据点到与其最近的聚类中心的平方欧式距离和最小.算法如下
1.输入数据和聚类数目k
2.执行下面二者之
一 •随机将数据分为k个类C1,...,Ck,计算每个类的中心x¯i,i=1,...,k •指定k个类的中心xi,i=1,...,k,将所有数据点划分到离其最近的类中心所在的类
3.计算每个数据点到其所属类的中心的平方距离 ∑k∑ ESS= ∥xj−x¯i∥
2 i=1j∈Ci PreviousNextFirstLastBackForward 20
4.重新将每个数据点划分到离其最近的类中心所在的类,使得ESS减少.完成后重新计算各类的中心x¯i,i=1,...,k
5.重复3和
4,直至没有点需要进行调整(ESS不能减少) K-medoids方法是对K-means方法的推广:其类似于K-means算法,区别在于 •每个类使用“代表个体”代替K-means中的类个体平均 •可以使用相异度度量,而不像K-means仅限于平方欧式距离 •需要事先指定类的个数 •相比K-means方法更加稳健(对噪音和异常点) •Rbase的kmeans函数使用K-means算法,而cluster包的pam(partitioningaroundmedoids)函数使用K-medoids算法. PreviousNextFirstLastBackForward 21 •K-means和K-medoids算法的计算复杂度高,适于小规模数据. •大规模数据可以使用CLARA(ClusteringLARgeApplications,KaufmanandRousseeuw1990)算法:随机选择一部分的样本点,使用K-medoids算法 •以及改进的CLARANS(ClusteringLargeApplicationbaseduponRANdomizedSearch,NgandHan1994)算法等. PreviousNextFirstLastBackForward 22 K-medoids算法
1.输入相异度矩阵D=(dij)和聚类数目k
2.随机选择k个样本点作为类的中心点(medoids)
3.将每个样本点关联到和其相异度最小的中心点(即所有样本点划分成k个类)
4.对第l个类(l=1,...,k),寻找类内具有最小平均相异度的点 i0: ∑ i0=argmindij i∈Cl j∈Cl 从而得到第l个类的新的中心点
5.重复3和4直至没有个体能够调整 PreviousNextFirstLastBackForward 23 1.3.3谱聚类 •两种不同的准则–紧性patness):k-means,hierarchicalclustering–相连性(connectivity):spectralclustering 谱聚类(Spectralclustering)是现代流行聚类算法之
一，较传统的K-means和层次聚类要好。
PreviousNextFirstLastBackForward 24 •基于数据之间的相似度矩阵，使用特征向量(谱). •在低维空间表达原始数据后,在低维空间使用K-means进行聚类. •常使用无向图有权图来描述 •给定样本点V=(x1,...,xn),计算其相似度(图分析中称连接阵)矩阵
W,将数据划分为k个组,使得组内的点相似,而组间的点不相似 PreviousNextFirstLastBackForward 25 –对无向图中顶点之间的权重,常用Gaussiankernel建立:∥xi−xj∥ Wij=e−2σ
2,σ2控制相邻程度 –目标:使得组内具有较高权重,区间具有较小权重 •记W(
A,B)=∑i∈A,j∈BWij表示两个顶点集A和B之间的相似程度.从而寻找一个最优的划分集A1,...,Ak,使得下式 最小化 cut(A1,...,Ak)=12∑kW(Ai,A¯i)i=
1 其中A¯表示A的补集. PreviousNextFirstLastBackForward 26 •但是这样的目标函数对异常点敏感: •其中一种解决方法(Ncut,ShiandMalik,2000): 1∑kW(Ai,A¯i) Ncut(A1,...,Ak)=
2 vol(Ai) i=
1 PreviousNextFirstLastBackForward 27 其中vol(A)=∑i∈Adi=∑i∈A∑nj=1Wij. –识别最小的Ncut(A1,...,Ak)是NP-hard.–有一些基于线性代数的有效逼近算法 –基于Laplacian矩阵,或GraphLaplacian:L=D−
W,D=diag(d1,...,dn). –对指定的k(k>2),记hij=√
1,如果xi∈Aj,否则为vol(Aj)
0.H=(hij),则: minTrace(H′LH) Am⊂inVNcut(A1,...,Ak)⇐⇒sAt1.,...,AkH′DH=Ik 替换H=D−1/2T minTrace(T′D−1/2LD−1/2T), Relaxation!
!
!
=⇒sTt∈.Rn×kT′T=Ik. –最优的Topt为矩阵Lsym=D−1/2LD−1/2的前k个特征向量. PreviousNextFirstLastBackForward 28 –最终的解Hopt=D−1/2Topt为矩阵Lrw=D−1L的前k个特征根. 谱聚类算法(ShiandMalik,2000)给定n个点x1,...,xn,以及聚类数目k: •构建图:计算连接矩阵
W •计算Laplacian阵L=D−
W •计算广义特征根方程Lu=λDu的前k个特征向量,记为U=[u1,...,uk] •记yi为U的第i行,i=1,...,n,使用K-means算法对y1,...,yn聚类得到类C1,...,Ck •输出类A1,...,Ak,其中Ai={xj|yj∈Ci}Ng,Jordan,andWeiss(2002)给出了另外一种类似的算法. PreviousNextFirstLastBackForward 29 1.4确定类的数目 •有时候提前指定聚类的数目没有问题,例如将一个客户数据根据k个销售员聚成k个类等 •大多数情况下,聚类的确切数目是未知的.此时确定聚类的数目是很困难的一个问题(高维数据难以检查,或者难以解释类数目的合理性). •确定类的数目也是非常重要的,比如确定某种癌症有两种类型还是三种类型是差异非常大的 Silhouette(侧影)法 •KaufmanandRousseeuw(1990)提出的一种既可以评价每个点应该在当前所属类还是其他类,也可以评价整体的聚类结果效果. PreviousNextFirstLastBackForward 30 •给定观测点i,记 –a(i)为点i与其所属类Ci中其他点之间的平均相异度值–d¯(i,C)表示点i到其他类C(C̸=Ci)内的所有点之间的 平均相异度值–b(i)表示所有d¯(i,C)中的最小值 •第i个观测点的Silhouette值定义为b(i)−a(i) s(i)=max{a(i),b(i)} •平均的Silhouetter值为1∑n s¯=nswii=
1 PreviousNextFirstLastBackForward 31 •显然,−1≤s(i)≤1,s(i)靠近1需要a(i)≪b(i).由a(i)的定义知小的a(i)意味着点i匹配该类非常好,而大的b(i)意味着点i匹配其他类很差,从而s(i)靠近1表明点i的聚类合适. •s(i)靠近-1表明点i被聚类到相邻类中更合适 •s(i)靠近0表明点i在两个类的交集处,即该点属于当前类或者相邻类均合适 •KaufmanandRousseeuw建议使用评价的轮廓宽来估计数据中的类数目: –s¯>0.5表明数据聚类合适–s¯<0.2表明数据不存在聚类特征 •R的包cluster里的silhouette函数将每个类中各点的s(i)按从小到大以水平线画出. PreviousNextFirstLastBackForward 32 PreviousNextFirstLastBackForward 33 CHindex我们以K-means方法为例,大部分想法可以推广到其他方法里. •给定类数目k,K-means算法最小化类内波动(within-cluster variation): ∑k∑ W(k)= ∥xj−x¯i∥
2 i=1C(j)=i •显然W(k)随k增加而减少,W(k)越小表明类越紧凑. •类间波动性(Between-clustervariation)度量类与类之间远离 的程度: ∑kB(k)=ni∥x¯i−x¯∥
2 i=
1 •显然B(k)随k增加而增加,B(k)越大表明类与类之间界限越清晰 PreviousNextFirstLastBackForward 34 •单独使用W(k)或B(k)都是有缺点的,因此自然地使用 选择合适的k: CH(k)=B(k)/(k−1)W(k)/(n−k) kˆ=argmaxCH(k)2≤k≤Kmax PreviousNextFirstLastBackForward 35 GapStatistic •W(k)随k增加而减少,但是对每个k的减少量应该是有信息的!
•Tibshiranietal.(2001)提出的GapStatistic基于想法:比较观察到的类内波动性W(k)和W∗(k),这里W∗(k)是在零假设均匀分布(数据为一个类,且服从一个区域上的均匀分布)下得到类内波动性,通过随机模拟计算. •使用Bootstrap方法,计算 Gapn(k)=En∗log(W∗(k))−log(W(k)) 1∑ ∗ ≈ log(Wb(k))−log(W(k))
B b 以及sdk=B1∑b(Wb∗(k)−W¯∗(k))
2,其中W¯∗(k)=B1∑bWb∗(k). PreviousNextFirstLastBackForward 36 √•令sk=sdk1+1/B,最后选择类的数目为 kˆ=inf{k:Gap(k)≥Gap(k+1)−sk+1} PreviousNextFirstLastBackForward 37 1.5聚类质量的评价 •聚类性能评价方法通常分为外部评价法(externalcriterion)和内部评价法(internalcriterion). •外部评价法分析聚类结果与另一参考结果(reference,比如另一种聚类方法的结果或者真实的类别)有多么相近.例如 –Purity,F-measure,RandStatistics,Entropy等 •内部评价法来分析聚类的本质特点.内部评价法常又分为绝对和相对评价法.常用的方法有 –绝对评价法:Davis-Bouldin,Dunn,ExpectedDensityρ等–相对评价法:Elbowcriterion,GAPstatistics等 PreviousNextFirstLastBackForward 38 外部评价法 •设有n个样本点,参考(Reference)类别为C∗={C1∗,...,Cl∗}. •某种聚类结果为C={C1,...,Ck} F-measure: •精度(Precision):|Cj∩Ci∗|/|Cj|. •查全率(Recall):|Cj∩Ci∗|/|Ci∗| •计算Cj相对于Ci∗的F-measure:Fij(α)= 1+α
1 α , precision+recall (加权调和平均),α常取
1. 从而总的F-measure定义为∑l|Ci∗|max{F}nj=1,...,kij i=
1 F-measure较大时说明聚类结果满意. PreviousNextFirstLastBackForward 39 •Entropy:聚类C相对于C∗的Entropy定义为 ∑|Cj|[ ∑|Cj∩Ci∗||Cj∩Ci∗|] H(C)= − log2 C∈Cn C∩C∗̸=∅|Cj| |Cj| j ji •RandIndex考虑样本点中的点对,记 n11=♯{(xi,xj)|xi,xj∈Ci;xi,xj∈Ck∗}n00=♯{(xi,xj)|xi∈Ci1,xj∈Ci2;xi∈Ck∗1,xj∈Ck∗2}n10=♯{(xi,xj)|xi,xj∈Ci;xi∈Ck∗1,xj∈Ck∗2}n01=♯{(xi,xj)|xi∈Ci1,xj∈Ci2;xi,xj∈Ck∗2} Randindex定义为 R=n11(+)n00n2 R=0表明两种聚类没有重叠,R=1表示两个聚类完全相同.其严重依赖于聚类数目. PreviousNextFirstLastBackForward 40 •AdjustedRandIndex两种不相关随机划分的Randindex期望值并不为常数(零),HubertandArabie(1985)对Randindex进行了调整(假设超几何分布:固定列联表的边际),使得对两种独立的聚类值为
0,两种完全相同的聚类值为
1.Meila(2003)指出AjustedRandindex值可取负值. PreviousNextFirstLastBackForward 41
声明：
该资讯来自于互联网网友发布，如有侵犯您的权益请联系我们。