信息科学技术学院.ppt

《信息科学技术学院.ppt》由会员分享，可在线阅读，更多相关《信息科学技术学院.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Text Clustering IText Clustering IWang Wang JiminJiminNov 11,2005 Nov 11,2005 信息科学技术学院信息科学技术学院 网络研究所网络研究所Outlineoo 引言引言oo文本间距离与文本类间的距离文本间距离与文本类间的距离 oo聚类方法聚类方法n n层次方法层次方法层次方法层次方法n n划分方法划分方法划分方法划分方法 oo聚类结果的评价聚类结果的评价ooOn-line clustering On-line clustering ooVisualization via embeddingVisualization via

2、embedding信息科学技术学院信息科学技术学院 网络研究所网络研究所引言oo聚聚类类是是对对数数据据对对象象进进行行划划分分的的一一种种过过程程，与与分分类类不不同同的的是是，它它所所划划分分的的类类是是未未知知的的，故故此此，这这 是是 一一 个个“无无 指指 导导 的的 学学 习习”（unsupervisedunsupervisedlearninglearning）过过程程，即即聚聚类类算算法法不不需需要要“教教师师”的的指指导导，不不需需要要提提供供训训练练数数据据，它它倾倾向向于于数数据据的自然划分。的自然划分。oo文文本本聚聚类类（TextTextclusteringcluste

3、ring）:将将文文本本集集合合分分组组成成多多个个类类或或簇簇，使使得得在在同同一一个个簇簇中中的的文文本本内内容容具具有有较较高高的的相相似似度度，而而不不同同簇簇中中的的文文本本内内容容差差别别较较大大。它它是是聚聚类类分分析析技技术术在在文文本本处处理理领领域域的的一种应用。一种应用。信息科学技术学院信息科学技术学院 网络研究所网络研究所引言oo在在IRIR中中的的应应用用：早早期期主主要要是是为为了了提提高高系系统统的的查查准准率率与查全率，并被用于寻找给定文本的相近文本。与查全率，并被用于寻找给定文本的相近文本。oo目目前前主主要要用用于于浏浏览览文文本本、显显示示文文本本集集合合

4、、组组织织搜搜索索引引擎擎的的返返回回结结果果，如如VivisimoVivisimo的的结结果果聚聚类类，这这有有利利于于用户快速定位自己需要的信息。用户快速定位自己需要的信息。oo其其他他应应用用：如如帮帮助助市市场场分分析析人人员员从从客客户户信信息息中中发发现现不不同同的的用用户户群群，并并且且用用购购买买模模式式来来刻刻画画不不同同的的用用户户群的特征。群的特征。oo文文本本聚聚类类的的主主要要方方法法:基基于于划划分分的的、层层次次的的、自自组组织织特征映射、遗传算法等。特征映射、遗传算法等。信息科学技术学院信息科学技术学院 网络研究所网络研究所Requirements of Clu

5、steringRequirements of ClusteringooScalabilityScalabilityooAbility to deal with different types of attributesAbility to deal with different types of attributesooDiscovery of clusters with arbitrary shapeDiscovery of clusters with arbitrary shapeooMinimal requirements for domain knowledge to determin

6、e input Minimal requirements for domain knowledge to determine input parametersparametersooAble to deal with noise and outliersAble to deal with noise and outliersooInsensitive to order of input recordsInsensitive to order of input recordsooHigh dimensionalityHigh dimensionalityooIncorporation of us

7、er-specified constraintsIncorporation of user-specified constraintsooInterpretability and usabilityInterpretability and usability信息科学技术学院信息科学技术学院 网络研究所网络研究所Text clusteringText clusteringooTwo example:nVivisimo SE http:/www.VnMicrosoft Research Asia a group on search and mining信息科学技术学院信息科学技术学院 网络研究所网

8、络研究所Vivisimo Vivisimo SESE信息科学技术学院信息科学技术学院 网络研究所网络研究所Vivisimo Vivisimo SE SE信息科学技术学院信息科学技术学院 网络研究所网络研究所Microsoft Research Asia信息科学技术学院信息科学技术学院 网络研究所网络研究所Microsoft Research Asia信息科学技术学院信息科学技术学院 网络研究所网络研究所文本间距离与文本类间的距离文本间距离与文本类间的距离 oo为了度量文本间的接近或相似程度，需要定义一些用于划分类别的计量指标。oo常用的统计指标有距离和相似系数。“距离”属于相异性测度指标，“相

9、似系数”属于相似性测度指标。oo距 离 和 相 似 系 数 成 反 比，如sim(i,j)=1/(1+dij)。信息科学技术学院信息科学技术学院 网络研究所网络研究所文本间的距离文本间的距离 信息科学技术学院信息科学技术学院 网络研究所网络研究所文本间的距离文本间的距离信息科学技术学院信息科学技术学院 网络研究所网络研究所文本间的距离文本间的距离信息科学技术学院信息科学技术学院 网络研究所网络研究所文本间的相似系数文本间的相似系数 oo对于有n个特征属性的文档集合来说，m个文档可以看作n维空间中的m个向量。oo为此，我们可以用相似系数来度量它们之间的相近程度，用sim(i,j)表示第i个向量与

10、第j个向量之间的相似系数，则我们有：信息科学技术学院信息科学技术学院 网络研究所网络研究所几种常见的文本间相似系数几种常见的文本间相似系数 信息科学技术学院信息科学技术学院 网络研究所网络研究所文本类间的距离文本类间的距离 为了度量两个文本类间的关联或相似程度，在实际应用中有多种定义形式。为了度量两个文本类间的关联或相似程度，在实际应用中有多种定义形式。为了度量两个文本类间的关联或相似程度，在实际应用中有多种定义形式。为了度量两个文本类间的关联或相似程度，在实际应用中有多种定义形式。信息科学技术学院信息科学技术学院 网络研究所网络研究所文本类间的距离文本类间的距离信息科学技术学院信息科学技术学

11、院 网络研究所网络研究所数据的标准化数据的标准化oo选选用用的的度度量量单单位位将将直直接接影影响响聚聚类类分分析析的的结结果果，如如将将高高度度由由“米米”改改为为“厘厘米米”，重重量量由由“克克”改改为为“千千克克”，就就可可能能产产生生非非常常不不同同的的聚类结果聚类结果oo为为了了避避免免对对度度量量单单位位的的依依赖赖，数数据据应应当当进进行行标标准准化化，有有多多种种方方法法，在在此此我我们们介介绍绍三三种种方方法法n n最小最小-最大规范化最大规范化n nZ-scoreZ-score规范化规范化n n按小数定标规范化按小数定标规范化 信息科学技术学院信息科学技术学院 网络研究所网

12、络研究所数据的标准化数据的标准化信息科学技术学院信息科学技术学院 网络研究所网络研究所Outlineoo 引言引言oo文本间距离与文本类间的距离文本间距离与文本类间的距离 oo聚类方法聚类方法n n层次方法层次方法层次方法层次方法n n划分方法划分方法划分方法划分方法 oo聚类结果的评价聚类结果的评价ooOn-line clustering On-line clustering ooVisualization via embeddingVisualization via embedding信息科学技术学院信息科学技术学院 网络研究所网络研究所基于层次的文本聚类方法基于层次的文本聚类方法 oo层

13、次聚类法（Hierarchicalmethods）将文本集合进行层次分解，组成一颗凝聚树。根据层次的形成方式可以分为两类n n 凝凝聚聚的的方方法法(agglomerative)agglomerative)，也也称称自自底底向向上上（bottom-bottom-upup）n n 分裂的方法（分裂的方法（divisivedivisive），），也称自顶向下（也称自顶向下（top-downtop-down）信息科学技术学院信息科学技术学院 网络研究所网络研究所凝聚的层次聚类方法凝聚的层次聚类方法(agglomerative)oo采用自底向上（采用自底向上（bottom-upbottom-up）的策

14、略首先将每个文档看作一个类，的策略首先将每个文档看作一个类，然后相继合并相近的文本类，直到所有的文档合并为一个类，或然后相继合并相近的文本类，直到所有的文档合并为一个类，或者达到某个终止条件，如希望得到的类的个数或者两个相近的类者达到某个终止条件，如希望得到的类的个数或者两个相近的类超过了某一个阈值。超过了某一个阈值。信息科学技术学院信息科学技术学院 网络研究所网络研究所分裂的层次聚类方法（分裂的层次聚类方法（divisive）oo它它首首先先将将所所有有的的文文档档看看作作一一个个类类，然然后后逐逐渐渐细细分分为为越越来来越越小小的的类类，直直到到每每个个文文档档自自成成一一类类，或或者者达

15、达到到某某个个终终止止条条件件，如如希希望望得得到到的的类类的的个个数数或或者者两个相近的类超过了某一个阈值。两个相近的类超过了某一个阈值。oo相关问题：相关问题：n n缺缺点点：一一旦旦一一个个步步骤骤（合合并并或或分分裂裂）完完成成就就不不能能修修正正。现现在在已已有多种改进方法，如凝聚层次的聚类与迭代重定位的集成等有多种改进方法，如凝聚层次的聚类与迭代重定位的集成等n n时时间间复复杂杂度度O(nO(n2 2)，n n为为文文档档数数。层层次次聚聚类类算算法法实实质质上上是是一一种种贪贪心算法。心算法。n n软件包软件包matlab matlab 已经实现了层次聚类方法已经实现了层次聚类

16、方法信息科学技术学院信息科学技术学院 网络研究所网络研究所聚类结果的树状图表示聚类结果的树状图表示信息科学技术学院信息科学技术学院 网络研究所网络研究所简单实例：聚类简单实例：聚类天网点击日志天网点击日志oo每天用户访问量每天用户访问量2020余万，用户点击记录余万，用户点击记录1010余万条余万条 oo天网天网用户点击日志的一个记录用户点击日志的一个记录 MonSep100:00:002003MonSep100:00:002003 /点击时间点击时间202.206.202.206.xxxxxx.xxxxxx /用户用户IPIP成人高考成人高考 /查询词查询词http:/ /点击的点击的URL

17、URLoo1616 /点击页面的排序点击页面的排序信息科学技术学院信息科学技术学院 网络研究所网络研究所点击点击URL的聚类分析的聚类分析oo构造数据矩阵，统计一个时间段内的用户点击日志，构造以查询词为行，以点击URL为列数据矩阵H，oo对数据进行标准化处理oo对行向量进行相似性分析，通过给定聚类结果的数目，得到相似查询词。信息科学技术学院信息科学技术学院 网络研究所网络研究所查询词聚类查询词聚类oo类别结果1：mp3mp3免费下载mp3下载歌曲下载免费mp3下载oo类别结果2：美女写真人体艺术美女性感oo类别结果3：列车时刻表火车火车时刻表信息科学技术学院信息科学技术学院 网络研究所网络研究

18、所点击点击URL聚类聚类oo类别结果类别结果1 1：http:/www.http:/ httpttp:/www.:/ 2http:/www.china.org.http:/cn/chinesechinese/zhuantizhuanti/224196./224196.htmhtmhttp:/www.http:/ 网络研究所网络研究所ReferenceReferenceooJ.HanandM.J.HanandM.KambrKambr,Datamining:conceptsandtechniques.,Datamining:conceptsandtechniques.Highereducation

19、press,2001.Highereducationpress,2001.www.www.cscs.uiucuiuc.eduedu/hanjhanjoSoumenChakrabarti.2003.MiningtheWeb:DiscoveringKnowledgefromHypertextData.Amsterdam:MorganKaufmann.oPierreBaldi,PaoloFrasconiandPadhraicSmyth.2003.ModelingtheInternetandtheWeb:ProbabilisticMethodsandAlgorithms.Wiley.信息科学技术学院信

20、息科学技术学院 网络研究所网络研究所Outlineoo 引言引言oo文本间距离与文本类间的距离文本间距离与文本类间的距离 oo聚类方法聚类方法n n层次方法层次方法层次方法层次方法n n划分方法划分方法划分方法划分方法 oo聚类结果的评价聚类结果的评价ooOn-line clustering On-line clustering ooVisualization via embeddingVisualization via embedding信息科学技术学院信息科学技术学院 网络研究所网络研究所Thank you!信息科学技术学院信息科学技术学院 网络研究所网络研究所基于划分的文本聚类方法基于划

21、分的文本聚类方法oo对包含n个文档的文本集合，划分将生成k个分组，k=n，每一个分组代表一个聚类。oo典型的划分方法（Partitioningmethods）:n nk-k-平均方法平均方法n n k-k-中心点方法中心点方法信息科学技术学院信息科学技术学院 网络研究所网络研究所k-平均算法平均算法oostep1.任意选择k个对象作为初始的类的中心oostep2.repeatoostep3.根据类中文档的平均值,将每个文档(重新)赋给最相近的类oostep4.更新类的平均值，oostep5.until不再发生变化。信息科学技术学院信息科学技术学院 网络研究所网络研究所The K-Means Clustering Method ooExample012345678910012345678910012345678910012345678910K=2Arbitrarily choose K object as initial cluster centerAssign each objects to most similar centerUpdate the cluster meansUpdate the cluster meansreassignreassign