TextMining05-聚类

1文本自动聚类技术杨建武Email:[e-mail]第五章：北京大学计算机科学技术研究所文本挖掘技术(2012春)2簇Cluster簇Cluster:数据对象的集合在同一个簇中，数据对象是相似的不同簇之间的对象是不相似的3聚类分析聚类分析是按照一定的规律和要求对事物进行簇划分的过程，在这一过程中没有任何关于簇划分的先验知识，没有指导，仅靠事物间的相似性作为簇划分的准则。将一个数据集合划分成多个簇；聚类分析是一种无监督分类，没有预定义的类4无标记的样本集空间划分空间覆盖聚类分析：数据集的划分5聚类分析的数学描述聚类分析(Clustering)：给定数据样本集X｛X1,X2,…,Xn｝，根据数据点间的相似程度将数据集合分成k簇｛C1,C2,…,Ck｝的过程称为聚类分析。簇记为Ci＝｛Xj1i,Xj2i,…,Xjnii｝Ci（i＝1,…,k）是X的子集，且满足：C1∪C2∪…∪Ck＝XCi∩Cj＝ф，i≠j。相似样本在同一簇中，相异样本在不同簇中。6文本聚类DocumentClustering(DC)ispartitioningasetofdocumentsintogroupsorclustersClustersshouldbecomputedtoContainsimilardocumentsSeparateasmuchaspossibledifferentdocumentsForinstance,ifsimilaritybetweendocumentsisdefinedtocapturesemanticrelatedness,documentsinaclustershoulddealwiththesametopics,andtopicsineachclustershouldbedifferent.7文本聚类的应用Guidingtheorganizationofadocumentcollection(e.g.[Sahami98])ProgressivelyclusteringgroupsofdocumentsallowtobuildatopichierarchySupportingbrowsingandinteractiveretrievalGroupingretrieveddocumentstoallowafasterrelevantdocumentsselectionprocessSomesearchengines(Vivisimo)Pre-processingforothertasks,e.g.Todetectthemainsemanticdimensionsofthetextcollectionandtosupportakindofconceptindexing[Karypis&Han00]Fortextsummarization89文本聚类基本步骤Asothertextprocessingtasks,DChasseveralstepsDocumentrepresentationDimensionalityreductionApplyingaclusteringalgorithmEvaluatingtheeffectivenessoftheprocess文档表示聚类算法可视化abcefghi[-,-,-,-,][-,-,-,-,][-,-,-,-,]10评价指标11聚类结果的评价「准确率」（P,precision）「召回率」（R,recall）F－MeasureRPF1111RPPRF2112聚类结果的评价所有类的总体评价iiiiiRPRPF21宏平均Macro微平均MicromiimiiinFnFMicro11)(miiFmFMacro11iiiRPF1111误差平方和准则(sum-of-squared-errorcriterion）:其中X∈Ci，mi是Ci的质心Je即所有样本的平方误差和。13聚类的准则函数21||iiCXkiemXJ14聚类算法的评价聚类算法的好坏：该算法是否能发现某些或所有的隐含模式；一个好的聚类算法要能产生高质量的聚类结果——簇，这些簇要具备以下两个特点：高的簇内相似性；低的簇间相似性。聚类结果的好坏取决于：聚类算法采用的相似性评估方法；该算法的具体实现。15聚类算法的评价可伸缩性能发现任意形状的簇参数输入的时候，尽量不需要特定的领域知识；对输入数据对象的顺序不敏感能够处理噪声和异常能够处理不同类型的属性能处理高维数据能产生一个好的、满足用户指定约束的聚类结果结果是可解释的、可理解的和可用的16聚类算法17文档间距离向量空间模型(VectorSpaceModel)M个无序标引项ti(特征)，词根/词/短语/其他每个文档dj可以用标引项向量来表示•(a1j,a2j,…,aMj)权重计算，N个训练文档•AM*N=(aij)相似度计算•Cosine计算•内积计算T3T1T2D1=2T1+3T2+5T3D2=3T1+7T2+T3Q=0T1+0T2+2T3732518簇间距离簇Gp与簇Gq之间的距离Dpq(d(xi,xj)表示点xi∈Gp和xj∈Gq之间的距离)min(,)pqijDdxx最短距离法:最长距离法:重心法:离差平方和:(Wald)簇平均法:max(,)pqijDdxxmin(,)pqpqDdxx121(,)ipjqpqijxGxGDdxxnn)(')(1piGxpixxxxDpi)(')(2qjGxqjxxxxDpj)(')(21xxxxDkGGxkppk2121DDDDpq19聚类方法划分方法层次方法基于密度的方法基于网格的方法在线聚类方法20划分方法21划分方法将文档集D={d1,…,di,…,dn}分割为的若干类，具体过程：1.确定要生成的类的数目k；2.按照某种原则生成k个聚类中心作为聚类的种子S={s1,…,sj,…,sk}；3.对D中的每一个文档di，依次计算它与各个种子sj的相似度sim(di,sj)；4.选取具有最大的相似度的种子argmaxsim(di,sj),将di归入以sj为聚类中心的类Cj，从而得到D的一个聚类C={c1,…,ck}；5.重复步骤2~4若干次，以得到较为稳定的聚类结果。22k-means（k-均值）(MacQueen’67)1.选择一个含有随机样本的k个簇的初始划分，计算这些簇的质心。2.根据欧氏距离把剩余的每个样本分配到距离它最近的簇质心的一个划分。3.计算被分配到每个簇的样本的均值向量，作为新的簇的质心。4.重复2,3直到k个簇的质心点不再发生变化或准则函数收敛。23012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910ArbitrarilyassigneachobjectstokinitialclusterUpdatetheclustermeansUpdatetheclustermeansreassignreassignk-means算法示例K=224k-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｝。（请大家练习完成后续的步骤）25k-means算法示例这两个簇的质心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｝；样本初始随机分布之后，方差是：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（公式）21||iiCXkiemXJ26k-means算法示例第2步：按与质心（M1或M2）间距离关系，选择最小距离分配所有样本，簇内样本的重新分布如下：d(M1,X1)=(1.662+1.342)1/2=2.14d(M2,X1)=3.40==X1∈C1；d(M1,X2)=1.79和d(M2,X2)=3.40==X2∈C1d(M1,X3)=0.83和d(M2,X3)=2.01==X3∈C1d(M1,X4)=3.41和d(M2,X4)=2.01==X4∈C2d(M1,X5)=3.60和d(M2,X5)=2.01==X5∈C2新簇C1＝｛X1,X2,X3｝和C2＝｛X4,X5｝27k-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）。在这个简单的例子中，第一次迭代同时也是最后一次迭代，因为如果继续分析新中心和样本间的距离，样本将会全部分给同样的簇，不将重新分配，算法停止。时间代价？28k-means算法分析Strength:Relativelyefficient:O(tkn),wherenis#objects,kis#clusters,andtis#iterations.Normally,k,tn.•Comparing:PAM:O(k(n-k)2),CLARA:O(ks2+k(n-k))Comment:Oftenterminatesatalocaloptimum.Theglobaloptimummaybefoundusingtechniquessuchas:deterministicannealingandgeneticalgorithms（确定性退火和遗传算法）29k-means的缺陷要求用户必须事先给出要生成的簇的数目，选择初始划分的最佳方向、更新和停止准则难以处理大小很不相同的簇或具有凹状的簇。算法只有在簇的平均值被定义的情况下才能使用，这不适涉及有分类属性的数据。k－prototypes算法对数值与离散两种混合的数据聚类，k－modes方法对离散属性对噪音和异常点非常敏感方法速度快，但k要预先确定，种子选取难30k-mediods(k-中心点)方法基本策略：不采用簇中样本的平均值作为参照点，选用簇中位置最中心的对象――中心点作为参照点。PAM(PartitioningAroundMedoids围绕中心点划分)最早提出的k-中心点算法之一(1987)；基本思想：最初随机选择k个中心点后，反复尝试找更好的中心点31PAM算法(1987)1.随机选择k个代表对象作为初始的中心点。2.repeat3.指派每个剩余对象给离它最近的中心点所代表的簇；4.随机的选择一个非中心点对象Orandom5.计算用Orandom代替Oj的总代价6.ifs为负，则Orandom代替Oj，形成新的k个中心点的集合7.Until不发生变化32Typicalk-medoidsalgorithm(PAM)012345678910012345678910TotalCost=20012345678910012345678910K=2Arbitrarychoosekobjectasinitialmedoids012345678910012345678910Assigneachremaining