商务智能pptCh6V2 聚类分析.pptx
《商务智能pptCh6V2 聚类分析.pptx》由会员分享,可在线阅读,更多相关《商务智能pptCh6V2 聚类分析.pptx(53页珍藏版)》请在三一文库上搜索。
1、第6章 聚类分析Chapter6:Clustering主要内容6.1 概述6.2 相似度衡量方法6.3 k均值方法6.4 层次聚类方法6.5 DBSCAN方法6.6 聚类效果衡量方法6.1 概述编号账户余额年龄收入性别子女个数100很低151967男0200高258453男1300中326125女2400低202167男1500低552439女4 聚类(clustering):实现将对象自动分组的一种方法 无监督学习 物以类聚应用 CRM中的客户分群:customer segmentation Insurance保险:Identifying groups of motor insurance
2、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)基本概念基本概念 根据簇之间的关系-划分型聚类:属于各个簇的对象之间没有交集,即CiCj=-层次型聚类:簇之间只具有包含关系,如CiCj-重叠聚类:簇之间只具有重叠关系,即CiCj
3、根据数据集D与簇之间的关系-完全聚类:D=C1C2Ck,所有对象都被分配都簇中-部分聚类:DC1C2Ck 孤立点(outlier):那些未被分到任一个簇中的对象聚类方法分类 划分法(Partitioning approach):-k均值(k-means)、k中心点(k-medoids)等方法。层次法(Hierarchical approach):-凝聚层次聚类(agglomerative hierarchical clustering)和分裂层次聚类(divisive hierarchical clustering)-Diana、Agnes、BIRCH、ROCK、CAMELEON等。基于密度的
4、方法(Density-based approach)-DBSCAN、OPTICS和 DenClue等。基于模型的方法(Model-based)-EM、SOM和COBWEB等6.2 相似度衡量方法6.2 相似度衡量方法6.2.1 数据类型6.2.2 基于内容的相似度衡量6.2.3 基于链接的相似度衡量数据类型 定量属性-标称(nominal)属性、序数(ordinal)属性、二值属性(binary)-二值属性:对称属性(symmetric)和非对称属性(asymmeric)性别是对称属性,医学检查结果为非对称属性 定量属性-区间属性(interval)和比率属性(ratio)区间属性:加和减操作
5、有意义,可以比较取值的差别,乘除运算没有意义,即两个取值之间的比率关系不成立。摄氏温度比率属性既可以加减也可以乘除。绝对温度基于内容的相似度衡量 基于距离的相似度度量 余弦相似度 基于相关性的相似度度量 Jaccard系数 异种属性相似度的综合度量距离度量 明可夫斯基距离Minkowski distance:-i=(xi1,xi2,xim)和j=(xj1,xj2,xjm)-明可夫斯基距离又称为Lp范式(Lp范式),p=1时对应曼哈顿距离,又称L1范式;p=2时对应欧式距离,又称L2范式。p=时称为切比雪夫距离(Chebyshev distance)111(,)lim(|)max|mppijik
6、jkk mikjkpkd o oxxxx-距离公式 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|.|),(2211jmxixjxixjxixjoiod-基于距离的相似度(,)(,)ijijs o od o o-1(,)1(,)ijijs o od o o(,)(,)ijd o oijs
7、o oe-余弦相似度 假设两个对象oi和oj对应的向量分别为x=(xi1,xi2,xim)和y=(xj1,xj2,xjm),则余弦相似度cos(oi,oj)的计算公式-相似度忽略了向量的大小,即各个属性取值的绝对大小,这是与距离不同的。-两个向量中,只要有一个对象在某维度(属性)的取值为0,则该维度相当于被忽略,因为乘积为0。这使得该相似度特别适合于具有大量零值维度的情况12211(,)|mikjkkijmmikjkkkxxxycos o oxyxx基于相关性的相似度度量 对象oi=(xi1,xi2,xim)和oj=(xj1,xj2,xjm)的皮尔森相关系数corr(oi,oj)的计算公式如下
8、 corr(oi,oj)的取值范围为-1,1。取值为1时说明两个对象正相关,也最相似,取值为-1时说明两个对象负相关,也最不相似122111()()1(,)11()()11mikijkjkijmmikijkjkkxxxxmcorr o oxxxxmm-11miikkxxm11mjjkkxxm Jaccard系数 适合于用非对称二值属性描述的对象间的相似度衡量。-对于非对称二值属性,假设重要的取值用1代表,不重要的用0代表,对象oi=(xi1,xi2,xim)和oj=(xj1,xj2,xjm)的m个二值属性取值中,假设两个对象取值都为1的属性个数为n11,取值都为0的属性个数为n00,取值一个为
9、1另一个为0的属性个数为n10,取值一个为0另一个为1的属性个数为n0111111001(,)ijns o onnn简单匹配系数(simple matching coefficient)对于用对称二值属性描述的对象间的相似度可以利用简单匹配系数进行衡量。111100100100(,)ijnns o onnnn二值属性 列联表 Simple matching coefficient(对称属性):Jaccard distance(非对称属性)Jaccard coefficient pdbcasumdcdcbabasum0101cbacb jid),(Object iObject j(,)as i
10、j abc(,)a ds i j a b c d Jaccard系数 Y,P:1;N:02(,)0.6731(,)0.3331(,)0.254sjack m arysjackjimsjim m ary(,)as i j abc异种属性相似度的综合度量 标称属性:假设对象oi=(xi1,xi2,xim)和oj=(xj1,xj2,xjm)的第k个属性是标称属性,则基于此属性的两对象相似度,记为sk(oi,oj)序数属性:假设对象oi=(xi1,xi2,xim)和oj=(xj1,xj2,xjm)的第k个属性是序数属性,有p个不同取值,首先将其取值排序,按照顺序映射为整数0(p-1),并用此序号代替原
11、来的取值,则基于此属性的两对象相似度,sk(oi,oj)1 =(,)0 ikjkkijxxs o o若否则|(,)1p 1ikjkkijxxs o o-异种属性相似度的综合度量 区间属性或比率属性可以通过取值的差来衡量相异度,假设对象oi=(xi1,xi2,xim)和oj=(xj1,xj2,xjm)的第k个属性是数值属性,则基于此属性的两对象相似度,sk(oi,oj),对于非对称二值属性,如果采用标称属性的处理方法,则有可能使得不重要的0值左右了相似度,因此,如果两个对象的非对称属性的两个取值均为0,则在衡量相似度时忽略,否则:1(,)1|kijikjks o oxx-1 =(,)0 ikjk
12、kijxxs 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步;否则,按照标称属性处理;-若为对称二值属性,按照标称属性处理;-对于标称属性,直接计算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若
13、否则|(,)1p 1ikjkkijxxs o o-1(,)1|kijikjks o oxx-基于链接的相似度衡量 对于结点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 a基于链接的相似度衡量 s
14、imRank-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(,)(),()|()|()|jiI vI vkikqiljqlijCsvvsIvIvI vI v 基于链接的相似度衡量 用于二部图
15、-初始化:s(a,a)=1,s(a,b)=0-C:衰减因子(0,1)(1)(11)(),()()(),(BOjjiAOiBOAOsBOAOCBAs)(1)(12)(),()()(),(dIjjicIidIcIsdIcICdcs基于链接的相似度衡量 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)(),()()(),(BOjjiAOiBOAOsBOAOC
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 商务智能pptCh6V2 聚类分析 商务 智能 pptCh6V2
链接地址:https://www.31doc.com/p-21712400.html