商务智能课件：第6章 聚类分析.ppt

1、Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 1Introduction to商务智能方法与应用第6章 聚类分析Chapter6: ClusteringPrinciples and Applications of Business IntelligenceChap 6 ： 聚类分析 2主要内容 6.1 概述 6.2 相似度衡量方法 6.3 k均值方法 6.4 层次聚类方法 6.5 DBSCAN方法 6.6 聚类效果衡量方法Principles and Applications of Business Inte

2、lligenceChap 6 ： 聚类分析 36.1 概述编号账 户余额年龄收入性别子女个数100 很低151967男0200 高258453男1300 中326125女2400 低202167男1500 低552439女4 聚类（clustering）：实现将对象自动分组的一种方法 无监督学习 物以类聚Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 4应用 CRM中的客户分群: customer segmentation Insurance保险: Identifying groups of motor ins

3、urance policy holders with a high average claim cost 高索赔额的汽车保险的投保人 City-planning: Identifying groups of houses according to their house type, value, and geographical location WWW: 根据 Weblog 数据发现相似的访问模式 生物: 动植物分类（taxonomy）Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 5基本概念Principl

4、es and Applications of Business IntelligenceChap 6 ： 聚类分析 6基本概念 根据簇之间的关系- 划分型聚类：属于各个簇的对象之间没有交集，即CiCj=- 层次型聚类：簇之间只具有包含关系，如CiCj- 重叠聚类: 簇之间只具有重叠关系，即CiCj 根据数据集D与簇之间的关系- 完全聚类: D= C1C2Ck，所有对象都被分配都簇中- 部分聚类: DC1C2Ck 孤立点(outlier)：那些未被分到任一个簇中的对象Principles and Applications of Business IntelligenceChap 6 ： 聚类分析

5、 7聚类方法分类 划分法（Partitioning approach）：- k均值（k-means）、k中心点（k-medoids）等方法。 层次法（Hierarchical approach）：- 凝聚层次聚类（agglomerative hierarchical clustering）和分裂层次聚类（divisive hierarchical clustering）- Diana、 Agnes、BIRCH、 ROCK、CAMELEON等。 基于密度的方法（Density-based approach）- DBSCAN、OPTICS和 DenClue等。 基于模型的方法（Model-base

6、d）- EM、SOM和COBWEB等Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 86.2 相似度衡量方法Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 96.2 相似度衡量方法 6.2.1 数据类型 6.2.2 基于内容的相似度衡量 6.2.3 基于链接的相似度衡量Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 10数据类型 定量属性- 标称

7、（nominal）属性、序数（ordinal）属性、二值属性（binary）- 二值属性：对称属性（symmetric）和非对称属性（asymmeric）性别是对称属性，医学检查结果为非对称属性 定量属性- 区间属性（interval）和比率属性（ratio）区间属性：加和减操作有意义，可以比较取值的差别，乘除运算没有意义，即两个取值之间的比率关系不成立。摄氏温度比率属性既可以加减也可以乘除。绝对温度Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 11基于内容的相似度衡量 基于距离的相似度度量 余弦相似度 基于

8、相关性的相似度度量 Jaccard系数 异种属性相似度的综合度量Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 12距离度量 明可夫斯基距离Minkowski distance: - i = (xi1, xi2, , xim) 和j = (xj1, xj2, , xjm)- 明可夫斯基距离又称为Lp范式(Lp范式) ，p=1时对应曼哈顿距离，又称L1范式；p=2时对应欧式距离，又称L2范式。p=时称为切比雪夫距离（Chebyshev distance）111( ,)lim(| )max|mppijikjkk m

9、ikjkpkd o oxxxx -Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 13距离公式 If q = 1, d is 曼哈顿距离Manhattan distance, L1 If q = 2, d is 欧式距离Euclidean distance: L2- 性质：d(oi,oj) 0d(oi, oi) = 0d(oi,oj) = d(oj,oi)d(oi,oj) doi,ok) + d(ok,oj)|.|(|),(2222211jmximxjxixjxixjoiod-|m|.|),(2211jmxix

10、jxixjxixjoiod-Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 14基于距离的相似度( ,)( ,)ijijs o od o o -1( ,)1( ,)ijijs o od o o(,)( ,)ijd o oijs o oe-Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 15余弦相似度 假设两个对象oi和oj对应的向量分别为x= (xi1, xi2, xim)和y=(xj1, xj2, xjm)，则余弦相似度cos

11、(oi, oj)的计算公式- 相似度忽略了向量的大小，即各个属性取值的绝对大小，这是与距离不同的。- 两个向量中，只要有一个对象在某维度（属性）的取值为0，则该维度相当于被忽略，因为乘积为0。这使得该相似度特别适合于具有大量零值维度的情况12211( ,)| |mikjkkijmmikjkkkxxxycos o oxyxxPrinciples and Applications of Business IntelligenceChap 6 ： 聚类分析 16基于相关性的相似度度量 对象oi=(xi1, xi2, xim)和oj=(xj1, xj2, xjm)的皮尔森相关系数corr(oi, oj

12、)的计算公式如下 corr(oi, oj)的取值范围为-1，1。取值为1时说明两个对象正相关，也最相似，取值为-1时说明两个对象负相关，也最不相似122111() ()1( ,)11()()11mikijkjkijmmikijkjkkxxxxmcorr o oxxxxmm-11miikkxxm11mjjkkxxm Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 17Jaccard系数 适合于用非对称二值属性描述的对象间的相似度衡量。- 对于非对称二值属性，假设重要的取值用1代表，不重要的用0代表，对象oi=(x

13、i1, xi2, xim)和oj=(xj1, xj2, xjm)的m个二值属性取值中，假设两个对象取值都为1的属性个数为n11，取值都为0的属性个数为n00，取值一个为1另一个为0的属性个数为n10，取值一个为0另一个为1的属性个数为n0111111001( ,)ijns o onnnPrinciples and Applications of Business IntelligenceChap 6 ： 聚类分析 18简单匹配系数(simple matching coefficient) 对于用对称二值属性描述的对象间的相似度可以利用简单匹配系数进行衡量。111100100100( ,)ijn

14、ns o onnnnPrinciples and Applications of Business IntelligenceChap 6 ： 聚类分析 19二值属性 列联表 Simple matching coefficient (对称属性): Jaccard distance (非对称属性) Jaccard coefficient pdbcasumdcdcbabasum0101cbacb jid),(Object iObject j( , )as i j abc(, )a ds i j a b c d Principles and Applications of Business Intel

15、ligenceChap 6 ： 聚类分析 20Jaccard系数2(,)0.6731(,)0.3331(,)0.254sjack m arysjackjimsjim m ary Y , P: 1; N : 0( , )as i j abcPrinciples and Applications of Business IntelligenceChap 6 ： 聚类分析 21异种属性相似度的综合度量 标称属性：假设对象oi=(xi1, xi2, xim)和oj=(xj1, xj2, xjm)的第k个属性是标称属性，则基于此属性的两对象相似度，记为sk(oi, oj) 序数属性：假设对象oi=(xi

16、1, xi2, xim)和oj=(xj1, xj2, xjm)的第k个属性是序数属性，有p个不同取值，首先将其取值排序，按照顺序映射为整数0(p-1），并用此序号代替原来的取值，则基于此属性的两对象相似度，sk(oi, oj)1 =( ,)0 ikjkkijxxs o o若否则 |( ,)1p 1ikjkkijxxs o o- -Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 22异种属性相似度的综合度量 区间属性或比率属性可以通过取值的差来衡量相异度，假设对象oi=(xi1, xi2, xim)和oj=(xj

17、1, xj2, xjm)的第k个属性是数值属性，则基于此属性的两对象相似度，sk(oi, oj)， 对于非对称二值属性，如果采用标称属性的处理方法，则有可能使得不重要的0值左右了相似度，因此，如果两个对象的非对称属性的两个取值均为0，则在衡量相似度时忽略，否则：1( ,) 1 |kijikjks o oxx-1 =( ,)0 ikjkkijxxs o o若否则 oi=(xi1, xi2, xim), oj=(xj1, xj2, xjm)1. k=1，c=0，s(oi, oj)=0;2. 按照第k个属性的类型分别进行如下计算。- 对于非对称二值属性，若xik= xjk=0，转至第3步； 否则，按

18、照标称属性处理；- 若为对称二值属性，按照标称属性处理；- 对于标称属性， 直接计算sk(oi, oj)；- 若为序数属性 ，用序号代替原值；- 若为数值属性，计算sk(oi, oj)； c=c+1，s(oi, oj)=s(oi, oj)+ sk(oi, oj)3. 若k0时 s(oi, oj)=s(oi, oj)/c；返回s(oi, oj)；1 =( ,)0 ikjkkijxxs o o若否则 |( ,)1p 1ikjkkijxxs o o- -1( ,) 1 |kijikjks o oxx-Principles and Applications of Business Intelligen

19、ceChap 6 ： 聚类分析 24基于链接的相似度衡量 对于结点viV，从vi指出的边称为出边，指向vi的边为入边。由vi指向的结点称为vi的外邻居（out-neighbor）, vi的外邻居的集合由O（vi）代表，其中Oj(vi)表示vi的第j个外邻居。指向vi的结点称为vi的内邻居（in-neighbor）, vi的内邻居的集合由I（vi）代表，Ij(vi)表示vi的第j个内邻居。 vi的外邻居的个数称为vi的出度，即出度=|O(vi)|；vi的内邻居的个数称为vi的入度,即入度=|I(vi)|。b e d c aPrinciples and Applications of Busine

20、ss IntelligenceChap 6 ： 聚类分析 25基于链接的相似度衡量 simRank- Two objects are similar if they are referenced by similar objects- A object is maximally similar to itself (score=1) 两个结点vi与vj间相似度s(vi, vj)的公式如下| ()| ( )|111 ()( , )( ( ), ( ) ()| ( )| ( )|jiijI vI vijqiljijqlijvvs v vCs I vI vvvI vI v | ()| ()|1j11

21、(,)(),()|() |() |jiI vI vkikqiljqlijCsvvsIvIvI vI v Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 26基于链接的相似度衡量 用于二部图- 初始化: s(a,a) = 1, s(a,b)=0 - C: 衰减因子(0,1)(1)(11)(),()()(),(BOjjiAOiBOAOsBOAOCBAs)(1)(12)(),()()(),(dIjjicIidIcIsdIcICdcsPrinciples and Applications of Business Int

22、elligenceChap 6 ： 聚类分析 27基于链接的相似度衡量 O(A)=c,d,e, O1(A)=c, O2(A)=d, O3(A)=e O(B)=d,e,f, I(c )=A, I(d)=A,B C1=C2=0.5 s1(A, B) =0.51/31/3(0+0+0+1+0+0+0+1+0)=1/9 s1 (c,d) =0.51/2(1+1/9)=5/18)(1)(11)(),()()(),(BOjjiAOiBOAOsBOAOCBAs)(1)(12)(),()()(),(dIjjicIidIcIsdIcICdcscdefPrinciples and Applications of

23、Business IntelligenceChap 6 ： 聚类分析 28基于链接的相似度衡量: referencesGlen Jeh & Jennifer Widom. SimRank: A Measure of Structural-Context Similarity. SIGKDD02D. Lizorkin, et al. Accuracy estimate and optimization techniques for simrank computation. PVLDB, 1(1):422433, 2008.Pei Li, Hongyan Liu, et al. Fast Sing

24、le-Pair SimRank Computation. SIAM International conference on Data Mining. SDM 2010 (Best paper award)Yuanzhe Cai, Gao Cong, Xu Jia, Hongyan Liu, Jun He, Jiaheng Lu and Xiaoyong Du. Efficient Algorithms for Computing Link-based Similarity in Real World Networks. IEEE International Conference on Data

25、 Mining. ICDM 2009Pei Li, Yuanzhe Cai, Hongyan Liu, Jun He, and Xiaoyong Du. Exploiting the block structure of link graph for efficient similarity computation. PAKDD2009.Hongyan Liu, Jun He, Dan Zhu, Xiaofeng Ling, Xiaoyong Du. Measuring Similarity Based on Link Information: A Comparative Study” . I

26、EEE Transactions on Knowledge and Data Engineering(TKDE)Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 296.3 k均值方法 （k-means) 输入：数据集D由n个对象，D=oi=(xi1, xi2, xim)，i=1,2, , n ，簇的个数k，主要步骤如下:- 从n个对象中随机选取k个分别作为k个簇的初始质心（centroid），质心是每个簇的代表，通常是靠近簇中心位置的点。- 对于D中每个对象通过计算与每个质心的欧式距离，选择距离最近的质心，将其

27、分配到此质心代表的簇中；- 重新计算每个簇的质心- 若新得到的质心与上一次迭代得到的质心完全相同，则迭代停止；否则，转至步骤2Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 30质心（Centroid）0123456789100123456789101|liijljoCiyxCPrinciples and Applications of Business IntelligenceChap 6 ： 聚类分析 31The K-Means Clustering Method Example01234567891001

28、2345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2Arbitrarily choose K object as initial cluster centerAssign each objects to most similar centerUpdate the cluster means012345678910012345678910Update the cluster meansreassignreassignPrinciples and Applications of B

29、usiness IntelligenceChap 6 ： 聚类分析 32示例 10 objects: (1,2)、( 1,3 )、 ( 2,2 )、( 2,3 )、 ( 3,4)、 ( 4,2 )、 ( 4,3 )、( 4,4 )、 ( 5,1 )、( 5,3 ), K=2 1st round: Centroid: (9/5=1.8, 14/5=2.8) (22/5=4.4, 13/5=2.6) 2nd round: Weka: - cluster-simpleKMeans: numClusters簇个数Principles and Applications of Business Intel

30、ligenceChap 6 ： 聚类分析 33K均值1(,)jikjiioCSSDd oc Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 34k均值的特点 优点：快速 缺点：- 适用范围：categorical data?- k-modes及k-prototype- 噪音数据 和 孤立点：k-medoid- 非凸的形状（non-convex shapes）- kPrinciples and Applications of Business IntelligenceChap 6 ： 聚类分析 356.4 层次聚

31、类方法Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 36层次聚类（Hierarchical Clustering） 层次聚类产生具有层次关系的簇 不需要指定簇的个数kStep 0Step 1Step 2Step 3Step 4bdceaa bd ec d ea b c d eStep 4Step 3Step 2Step 1Step 0凝聚凝聚(agglomerative)(AGNES)分裂(divisive)(DIANA)Principles and Applications of Business Inte

32、lligenceChap 6 ： 聚类分析 37AGNES (Agglomerative Nesting) Kaufmann and Rousseeuw (1990) 假设有n个对象进行聚类，初始时每个单个对象被看作一个簇，即n个簇；接着，将最相似的两个簇合并为一个簇，产生共（n-1）个簇；然后继续合并最相似的两个簇，直至所有对象被合并到一个簇中 采用单链接Single-Link 方法衡量簇之间的相似度Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 38簇之间的相似度的衡量方法 最小距离(minimum dis

33、tance)，即单链接Single link: 基于来自两个簇中的结点之间的最小距离来衡量两个簇的相似度, 即, dis(Ci, Cj) = min(oip, ojq)Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 39簇之间的相似度的衡量方法 最大距离(maximum distance)，即全链接complete link: 基于来自两个簇中的结点之间的最大距离来衡量两个簇的相似度, 即, dis(Ci, Cj) = max(oip, ojq)Principles and Applications of Bu

34、siness IntelligenceChap 6 ： 聚类分析 40簇之间的相似度的衡量方法 平均距离(average distance)，即单链接Single link: 基于来自两个簇中的结点之间的平均距离来衡量两个簇的相似度, 即, dis(Ci, Cj) = avg(oip, ojq)Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 41簇之间的相似度的衡量方法 平均距离(average distance)，即单链接Single link:计算两个簇的质心之间的距离来衡量两个簇的相似度, 即, dis(

35、Ci, Cj) = dis(ci, cj)Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 42分裂层次聚类：DIANA Kaufmann and Rousseeuw (1990) 与AGNES的过程相反 Cluster is split, according to some principle, e.g, the maximum Euclidean distance between the closest neighboring objects in the cluster. Principles and Ap

36、plications of Business IntelligenceChap 6 ： 聚类分析 436.5 DBSCAN方法Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 44基于密度的聚类方法 DBSCAN(Density-Based Spatial Clustering of Applications with Noise) 给定包含n个对象的数据集D，D=oi|i=1,2, n ，以及两个参数：和minPts，其中是半径，minPts是半径区域内的点的个数的最小值，即密度阈值，DBSCAN发现D中满足参

37、数的高密度区域对应的簇 DBSCAN的优点：不需要指定簇的个数，可以发现任意形状的簇 缺点是对于高维数据，鉴于采用距离的度量带来的后果，聚类效果不好Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 45基本概念 邻居：给定半径，一个对象o的 邻居集，记为neighbor(o, )，是一个对象的集合，其中每个对象到o的距离不大于半径，称为对象o的 邻居。 邻域：以对象o为中心的半径的区域称为此对象的 邻域。 集合neighbor(o, )包含的对象的个数，即对象o 的邻域内对象的个数称为对象o的密度。 给定半径，如

38、果一个对象的密度不小于给定最小密度阈值minPts，则称该对象为一个核心点（core point）Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 46给定数据集D、半径和密度阈值minPts，DBSCAN的主要步骤： 初始时将n个对象的状态都标记为0，i=1; 从D中随机选取一个状态为0的对象p，并将其状态更改为1； 如果对象p的密度不小于minPts，则创建一个新的簇Ci并把p加入到此簇中，令集合N=neighbor(p, )。对于N中的每个对象q，做如下二步操作：- 若q的状态为0，改为1，若q是个核心点，

39、将其所有的 邻居加入集合N。- 如果q不属于已有的任何一个簇Cj，1 ji，将q放入Ci。 如果对象p的密度小于minPts，标记p的状态为3； 如果所有对象的状态都为1，则输出所有簇，不属于任何簇的对象为噪音，停止，否则，令i=i+1，转至步骤2。Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 47示例 假设半径=1，密度阈值minPts=3处理对象a(1,2) 处理对象b(3,4)处理对象c(4,3)Principles and Applications of Business IntelligenceCh

40、ap 6 ： 聚类分析 48参数的设定 对于二维数据集来说，MinPts=4比较合适。 和minPts的设定可以借助k距离 一个对象o的k距离定义为与其第k个近邻的距离。 给定k，将数据集D中所有对象的k距离计算后，根据k距离降序排列各点，并以结点序号为x轴，k距离为y轴绘图，此图称为k距离图。 根据此图，找到第一个谷点在k距离=2.24处。这样，将半径设为2.24，minPts设为k的值4。Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 496.6 聚类效果衡量方法 Cohesion(凝聚度):衡量簇内各对象

41、紧密程度 Separation(分离度):衡量簇间各对象的相异程度 silhouette coefficient(轮廓系数): combining cohesion and separationPrinciples and Applications of Business IntelligenceChap 6 ： 聚类分析 50Cohesion C=C1, C2, Ck ci is the centroid of cluster Ci |Ci|: number of objects of cluster Ci11, 11()()(,)|iijikkiijiioCoCiicohesion Cco

42、hesion Csimilarity ooCC11()()(,)jikkijiiioCcohesion Ccohesion Csimilarity oc Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 51Separation C=C1, C2, Ck ci is the centroid of cluster Ci c is the centroid of all objects1()|(, )kiiiseparation CCsimilarity cc1, ,()(,)kiljkklioCoCjisepar

43、ation Csimilarity ooPrinciples and Applications of Business IntelligenceChap 6 ： 聚类分析 52silhouette coefficient Suppose oi belongs to cluster Ci n为对象的总个数 轮廓系数的取值范围是-1，1 当ai=0时，轮廓系数取最大值1。 轮廓系数越大越好。将所有点的轮廓系数求平均可以用于衡量聚类质量1,()max(, )1(,)|1(,)|1jjjijiiiiiikiijjji oCiiijoCooibasc obabd oonCad ooC-Principles and Applications of Business IntelligenceChap 6 ： 聚类分析 53