文本挖掘技术 Text Mining 05-聚类


1 文本自动聚类技术 杨建武 Email:yangjw@pku.edu.cn 第五章: 北京大学计算机科学技术研究所 文本挖掘技术(2012春) 2 簇Cluster  簇Cluster: 数据对象的集合 在同一个簇中,数据对象是相似的 不同簇之间的对象是不相似的 3 聚类分析 聚类分析是按照一定的规律和要求对事 物进行簇划分的过程,在这一过程中没有 任何关于簇划分的先验知识,没有指导, 仅靠事物间的相似性作为簇划分的准则。 将一个数据集合划分成多个簇; 聚类分析是一种无监督分类,没有预定义的类 4 无标记的 样本集 空间划分 空间覆盖 聚类分析:数据集的划分 5 聚类分析的数学描述  聚类分析(Clustering): 给 定 数 据 样 本 集 X {X1,X2,…,Xn},根据数据点间的相似程度将 数据集合分成k簇{C1,C2,…,Ck}的过程称为聚 类分析。  簇记为Ci={Xj1 i,Xj2 i,…,Xjni i}  Ci(i=1,…,k)是X的子集,且满足:  C1∪C2∪…∪Ck=X  Ci∩Cj=ф,i≠j。  相似样本在同一簇中,相异样本在不同簇中。 6 文本聚类  Document Clustering (DC) is partitioning a set of documents into groups or clusters  Clusters should be computed to  Contain similar documents  Separate as much as possible different documents  For instance, if similarity between documents is defined to capture semantic relatedness, documents in a cluster should deal with the same topics, and topics in each cluster should be different. 7 文本聚类的应用  Guiding the organization of a document collection (e.g. [Sahami 98])  Progressively clustering groups of documents allow to build a topic hierarchy  Supporting browsing and interactive retrieval  Grouping retrieved documents to allow a faster relevant documents selection process  Some search engines (Vivisimo)  Pre-processing for other tasks, e.g.  To detect the main semantic dimensions of the text collection and to support a kind of concept indexing [Karypis & Han 00]  For text summarization 8 9 文本聚类基本步骤  As other text processing tasks, DC has several steps Document representation Dimensionality reduction Applying a clustering algorithm Evaluating the effectiveness of the process  文档表示  聚类算法  可视化 abc efghi [-,-,-,-,] [-,-,-,-,] [-,-,-,-,] 10 评价指标 11 聚类结果的评价  「准确率」(P, precision)  「召回率」(R, recall)  F-Measure   RP F 111 1    RP PRF  2 1 12 聚类结果的评价  所有类的总体评价 ii ii i RP RPF  2 1  宏平均 Macro  微平均 Micro       m i i m i ii n Fn FMicro 1 1 )(    m i iFmFMacro 1 1   ii i RP F 111 1     误差平方和准则 (sum-of-squared-error criterion): 其中X∈Ci,mi是Ci的质心 Je即所有样本的平方误差和。 13 聚类的准则函数 2 1 || i iCX k i e mXJ    14 聚类算法的评价  聚类算法的好坏:该算法是否能发现某些或所 有的隐含模式;  一个好的聚类算法要能产生高质量的聚类结 果——簇,这些簇要具备以下两个特点:  高的簇内相似性;  低的簇间相似性。  聚类结果的好坏取决于:  聚类算法采用的相似性评估方法;  该算法的具体实现。 15 聚类算法的评价  可伸缩性  能发现任意形状的簇  参数输入的时候,尽量不需要特定的领域知识;  对输入数据对象的顺序不敏感  能够处理噪声和异常  能够处理不同类型的属性  能处理高维数据  能产生一个好的、满足用户指定约束的聚类结果  结果是可解释的、可理解的和可用的 16 聚类算法 17 文档间距离  向量空间模型(Vector Space Model) M个无序标引项ti (特征),词根/词/短语 /其他 每个文档dj可以用标引项向量来表示 •(a1j,a2j,…,aMj) 权重计算,N个训练文档 •AM*N= (aij) 相似度计算 • Cosine计算 • 内积计算 T3 T1 T2 D1 = 2T1+ 3T2 + 5T3 D2 = 3T1 + 7T2 + T3 Q = 0T1 + 0T2 + 2T3 7 3 2 5 18 簇间距离 簇Gp与簇Gq之间的距离Dpq (d(xi,xj)表示点xi∈ Gp和xj ∈ Gq之间的距离) min ( , )pq i jD d x x 最短距离法: 最长距离法: 重心法: 离差平方和:(Wald) 簇平均法: max ( , )pq i jD d x x min ( , )pq p qD d x x 12 1 (,) i p j q pq i j x G x G D d x xnn    )(')(1 pi Gx pi xxxxD pi    )(')(2 qj Gx qj xxxxD pj    )(')(21 xxxxD k GGx k ppk     2121 DDDD pq   19 聚类方法  划分方法  层次方法  基于密度的方法  基于网格的方法  在线聚类方法 20 划分方法 21 划分方法  将文档集D={d1, … ,di , … ,dn} 分割为的若干类, 具体过程: 1. 确定要生成的类的数目k; 2. 按照某种原则生成k个聚类中心作为聚类的种子 S={s1, … ,sj , … ,sk}; 3. 对D中的每一个文档di ,依次计算它与各个种子sj的相 似度sim(di , sj ); 4. 选取具有最大的相似度的种子 arg max sim(di , sj ), 将di归入以sj 为聚类中心的类Cj ,从而得到D的一个聚 类C={c1, … ,ck}; 5. 重复步骤2~4若干次,以得到较为稳定的聚类结果。 22 k-means(k-均值)(MacQueen’67)  1.选择一个含有随机样本的k个簇的初始划分, 计算这些簇的质心。  2.根据欧氏距离把剩余的每个样本分配到距离 它最近的簇质心的一个划分。  3.计算被分配到每个簇的样本的均值向量,作 为新的簇的质心。  4.重复2,3直到k个簇的质心点不再发生变化或 准则函数收敛。 23 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Arbitrarily assign each objects to k initial cluster Update the cluster means Update the cluster means reassign reassign k-means算法示例 K=2 24 k-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}。 (请大家练习完成后续的步骤) 25 k-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};  样本初始随机分布之后,方差是: e1 2 = [(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; e2 2=8.12;  总 体 平 方 误 差 是:E2 =e1 2+e2 2 =19.36+8.12= 27.48(公式) 2 1 || i iCX k i e mXJ    26 k-means算法示例  第2步:按与质心(M1或M2)间距离关系,选择最小 距离分配所有样本,簇内样本的重新分布如下: d(M1,X1)=(1.662+1.342)1/2=2.14 d(M2,X1)=3.40 ==>X1∈C1; d(M1,X2)=1.79 和 d(M2,X2)=3.40 ==>X2∈C1 d(M1,X3)=0.83 和 d(M2,X3)=2.01 ==>X3∈C1 d(M1,X4)=3.41 和 d(M2,X4)=2.01 ==>X4∈C2 d(M1,X5)=3.60 和 d(M2,X5)=2.01 ==>X5∈C2  新簇C1={X1,X2,X3}和C2={X4,X5} 27 k-means算法示例  第3步:计算新的质心: M1={0.5,0.67}; M2={5.0,1.0}。  相应的方差及总体平方误差分别是: e1 2=4.17; e2 2=2.00; E=6.17;  可以看出第一次迭代后,总体误差显著减小(从值 27.48到6.17)。  在这个简单的例子中,第一次迭代同时也是最后一次 迭代,因为如果继续分析新中心和样本间的距离,样 本将会全部分给同样的簇,不将重新分配,算法停止。  时间代价? 28 k-means算法分析  Strength: Relatively efficient: O(tkn), where n is # objects, k is # clusters, and t is # iterations. Normally, k, t << n. • Comparing: PAM: O(k(n-k)2 ), CLARA: O(ks2 + k(n-k))  Comment: Often terminates at a local optimum. The global optimum may be found using techniques such as: deterministic annealing and genetic algorithms(确定性退火和遗传算法) 29 k-means的缺陷  要求用户必须事先给出要生成的簇的数目,选择初始划 分的最佳方向、更新和停止准则  难以处理大小很不相同的簇或具有凹状的簇。  算法只有在簇的平均值被定义的情况下才能使用,这不 适涉及有分类属性的数据。  k-prototypes算法对数值与离散两种混合的数据聚类, k- modes方法对离散属性  对噪音和异常点非常敏感 方法速度快,但k要预先确定,种子选取难 30 k-mediods(k-中心点)方法  基本策略:  不采用簇中样本的平均值作为参照点,  选用簇中位置最中心的对象――中心点作为参照点。  PAM(Partitioning Around Medoids围绕中心点划分)  最早提出的k-中心点算法之一(1987) ;  基本思想:最初随机选择k个中心点后,反复尝试 找更好的中心点 31 PAM算法(1987)  1.随机选择k个代表对象作为初始的中心点。  2.repeat  3.指派每个剩余对象给离它最近的中心点所代 表的簇;  4.随机的选择一个非中心点对象Orandom  5.计算用Orandom代替Oj的总代价  6.if s为负,则Orandom代替Oj,形成新的k个中心 点的集合  7.Until不发生变化 32 Typical k-medoids algorithm (PAM) 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Total Cost = 20 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 K=2 Arbitrary choose k object as initial medoids Assign each remainin g object to nearest medoids Randomly select a nonmedoid object,Oramdom Compute total cost of swapping 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Total Cost = 26 Swapping O and Oramdom If quality is improved. Do loop Until no change 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 33 PAM算法分析  PAM is more robust than k-means in the presence of noise and outliers because a medoid is less influenced by outliers or other extreme values than a mean  PAM works efficiently for small data sets but does not scale well for large data sets.  O(k(n-k)2 ) for each iteration where n is # of data, k is # of clusters Sampling based method, CLARA(Clustering LARge Applications) 34 CLARA (1990)  CLARA (Clustering Large Applications)  (Kaufmann and Rousseeuw in 1990)  It draws multiple samples of the data set, applies PAM on each sample, and gives the best clustering as the output  Strength: deals with larger data sets than PAM  Weakness:  Efficiency depends on the sample size  A good clustering based on samples will not necessarily represent a good clustering of the whole data set if the sample is biased (偏倚) 35 CLARANS (1994)  CLARANS (A Clustering Algorithm based on Randomized Search) (Ng and Han’94)  CLARANS draws sample of neighbors dynamically  The clustering process can be presented as searching a graph where every node is a potential solution, that is, a set of k medoids  If the local optimum is found, CLARANS starts with new randomly selected node in search for a new local optimum  It is more efficient and scalable than both PAM and CLARA 36 层次聚类 37 层次聚类  自底向上的聚类(凝聚)  每一项自成一类  迭代,将最近的两类合为一类  自顶向下的聚类(分裂)  将所有项看作一类  找出最不相似的项分裂出去成为两类 Step 0 Step 1 Step 2 Step 3 Step 4 b d c e a a b d e c d e a b c d e Step 4 Step 3 Step 2 Step 1 Step 0 agglomerative (AGNES) divisive (DIANA) 38 凝聚层次聚类  将文档集D={d1, … ,di , … ,dn} 中的每一个文档di 看作是一个具有单个成员的簇Ci={di},这些簇构 成了D的一个聚类C={c1, … ,ci , … ,cn};  计算C中每对簇( ci , cj )之间的相似度 sim(ci , cj );  选取相似度最大的簇对 arg max sim(ci , cj ), 并将ci 和cj合并为一个新的簇ck=ci∪cj ,从而构成 D的一个新的聚类C={c1, … ,cn-1}  重复上述步骤,直到C中只剩下一个簇为止 39 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 AGNES (1990)  AGNES (Agglomerative Nesting)  Kaufmann and Rousseeuw (1990)  Use the Single-Link method and the dissimilarity matrix.  Merge nodes that have the least dissimilarity  Go on in a non-descending fashion  Eventually all nodes belong to the same cluster 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 40 AGNES (1990)  1.单连接算法(single-linkage)(最近邻Nearest Neighbor):  基本思想:两个簇之间的距离用从两个簇中抽取的 每对样本的最小距离  作为距离度量,一旦最近的两个簇的距离超过某个 任意给定的阈值,算法就自动结束。  2.全连接算法  3.平均连接算法 ),(min ji CCD 41 Single Link 42 Complete Link 43 单连接算法  先将每个样本都分别看成是一个簇,最靠近的两个簇是 3和4,因为他们具有最小的簇间距离  D(3,4)=5.0。 第一步:合并簇3和4,得到新簇集合1,2,(34),5 44 单连接算法  更新距离矩阵:  D(1,(34)) = min(D(1,3),D(1,4)) = min(20.6, 22.4) = 20.6;  D(2,(34)) = min(D(2,3),D(2,4)) = min(14.1, 11.2) = 11.2;  D(5,(34)) = min(D(3,5),D(4,5)) = min(25.0, 25.5) = 25.0.  原有簇1,2,5间的距离不变,修改后的距离矩阵 如图所示,在四个簇1,2,(34),5中,最靠近的两 个簇是1和5,它们具有最小簇间距离D(1,5) =7.07。 45 单连接算法 46 单连接算法 47 AGNES算法分析  Major weakness of agglomerative clustering methods  do not scale well: time complexity of at least O(n2), where n is the number of total objects  can never undo what was done previously 48 更多的层次聚类算法  BIRCH(1996)是一个综合的层次聚类方法,它引 入了两个概念:聚类特征和聚类特征树(CF树)  CURE(1998)采用了一种新颖的层次聚类算法, 该算法选择基于质心和基于代表对象方法之间 的中间策略。  ROCK方法是一个适用于分类属性层次聚类算法  Chameleon(变色龙)(1999)是一个在层次聚类 中采用动态模型的层次聚类算法 49 BIRCH (1996)  Birch: Balanced Iterative Reducing and Clustering using Hierarchies  by Zhang, Ramakrishnan, Livny (SIGMOD‟96)  Incrementally construct a CF (Clustering Feature) tree, a hierarchical data structure for multiphase clustering  Phase 1: scan DB to build an initial in-memory CF tree (a multi-level compression of the data that tries to preserve the inherent clustering structure of the data) (用树状结构将对象进行层次划分)  Phase 2: use an arbitrary clustering algorithm to cluster the leaf nodes of the CF-tree (其它算法对叶节点进 行聚类) 50 CF-Tree in BIRCH  CF is a compact storage for data on points in a cluster  Has enough information to calculate the intra-cluster distances  summary of the statistics for a given subcluster.  Additivity theorem allows us to merge sub-clusters Clustering Feature: CF = (N, LS, SS) N: Number of data points LS: N i=1Xi SS: N i=1Xi 2 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 CF = (5, (16,30),(54,190)) (3,4) (2,6) (4,5) (4,7) (3,8) 51 CF Tree CF1 child1 CF3 child3 CF2 child2 CF6 child6 CF1 child1 CF3 child3 CF2 child2 CF5 child5 CF1 CF2 CF6 prev next CF1 CF2 CF4 prev next Root Non-leaf node Leaf node Leaf node 52 CF-Tree in BIRCH  A CF tree is a height-balanced tree that stores the clustering features for a hierarchical clustering  新数据项总是插入到树中与该数据距离最近的叶子中。  如果插入后使得该叶子的直径大于“类直径”,则把 该叶子节点分裂。  两个约束: • 叶子节点中数据个数不超过“类直径”; • 每个非叶子节点的子女个数不大于“分枝因子”。  聚类特征树可以动态构造,因此不要求所有数据 读入内存,而可以在外存上逐个读入。  算法可以通过改变“类直径”修改特征树大小, 控制其占内存容量。 53 BIRCH优缺点  Scales linearly: finds a good clustering with a single scan and improves the quality with a few additional scans  Weakness: handles only numeric data, and sensitive to the order of the data record. 54 CURE (1998)  CURE (Clustering Using REpresentatives )  by Guha, Rastogi & Shim, 1998  Shrink the multiple representative points towards the gravity center by a fraction of .  Multiple representatives capture the shape of the cluster 55 CURE 算法  从源数据对象中抽取一个随机样本S  将样本分割为一组划分p (size s/p)  对每个划分局部地聚成 s/pq个 clusters  随机取样剔除孤立点,去掉增长较慢的类  对局部的簇进行聚类 落在每个新形成的簇中的代表点根据用户定 义的收缩因子a收缩或向中心移动,这些代表 点可捕捉到簇的形状  用相应的簇标签来标记数据 56 样本数: s = 50 划分组数:p = 2 每组样本:s/p = 25 x x x y y y y x y x 每组簇数:s/pq = 5 CURE 算法示例 57  Shrink the multiple representative points towards the gravity center by a fraction of .  Multiple representatives capture the shape of the cluster x y x y CURE收缩代表点 58 CURE 算法  CURE算法将传统对类的表示方法进行了改进:  从每一个类中抽取固定数量、分布较好的点作为描 述此类的代表点; • 回避了用所有点或用中心和半径来表示一个类。  将这些点乘以一个适当的收缩因子,使它们更靠近 类的中心点。 • 将一个类用代表点表示,使得类的外延可以向非球形的形 状扩展,从而可调整类的形状以表达那些非球形的类。 • 收缩因子的使用减小了嗓音对聚类的影响。  CURE算法采用随机抽样与分割相结合的办法 来提高算法的空间和时间效率,并且在算法中 用了堆和K-d树结构来提高算法效率。 59 DIANA (1990)  DIANA (Divisive Analysis)  Kaufmann and Rousseeuw (1990)  Inverse order of AGNES  Eventually each node forms a cluster on its own 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 60 基于密度的方法 61 基于密度的方法  基于样本之间的距离的聚类方法只能发现球状的簇;  基于密度的方法可用来过滤“噪声”孤立点数据,以 发现任意形状的簇。  主要思想:只要临近区域的密度(样本的数目)超过 某个阈值则继续聚类。即对于给定簇中的每个样本, 在一个给定范围的区域中必须至少包含某个数目的样 本。 62 基于密度的方法  Clustering based on density (local cluster criterion), such as density-connected points  Major features: Discover clusters of arbitrary shape Handle noise One scan Need density parameters as termination condition  Several interesting studies: DBSCAN: Ester, et al. (KDD‟96) OPTICS: Ankerst, et al (SIGMOD‟99). DENCLUE: Hinneburg & D. Keim (KDD‟98) CLIQUE: Agrawal, et al. (SIGMOD‟98) 63 基于密度聚类的相关定义  1.给定对象半径ε内的区域称为该对象的 ε-邻域。  2.如果一个对象的ε-邻域至少包含最小 数目MinPts个对象,则称该对象为核心 对象。  3.给定一个对象集合D,如果p是在q的ε -邻域内,而q是一个核心对象,则称对 象p从对象q出发是直接密度可达的。 p q MinPts = 5 Eps = 1 cm 64 基于密度聚类的相关定义  4.如果存在一个对象链p1,p2,…,pn,p1=q,pn= p,对pi∈D(1<=i<=n),pi+1是从pi关于ε和 MinPts直接密度可达的,则对象p是从对象q关 于ε和MinPts密度可达的。  5.如果对象集合D中存在一个对象o,使得对象 p和q是从o关于ε和MinPts密度可达的,那么对 象p和q是关于ε和MinPts密度相连的。 p q o 65 DBSCAN (KDD-96)  DBSCAN (Density-Based Spatial Clustering of Applications with Noise)  基于高密度连接区域的密度聚类方法  Martin Ester,KDD-96 66 DBSCAN算法的相关定义  簇:基于密度可达性的最大的密度相连 对象的集合  噪音:不在任何簇中的对象  边界对象:不是核心对象,但在簇中, 即至少从一个核心对象直接可达 核心对象 边界对象 噪音  = 1cm MinPts = 5 67 DBSCAN算法  1)任意选择没有加簇标签的点 p  2)找到p 的ε-邻域( |N(q)| 个)  3)如果|N(q)|MinPts ,则p是核心对象,形成一 个新的簇,给簇内所有的对象点加簇标签  4)否则处理数据集的下一点  5)重复上述过程,直到所有的点处理完毕  = 1cm MinPts = 5 68 DBSCAN算法的不足和改进  只能发现密度相仿的簇  对用户定义的参数( and MinPts)敏感  计算复杂度为O(n2)  采用R-树等空间索引技术,计算复杂度为 o(nlogn) 69 OPTICS (SIGMOD‟99)  OPTICS: Ordering Points To Identify the Clustering Structure(通过对象排序识别 聚类结构)  by Mihael Ankerst. ACM SIGMOD‟99  对DBSCAN的改进 对输入参数不敏感 可以发现不同密度的簇 用图表等可视化的方式来表示 按可达距离排序 可自动挖掘,也可与用户交互 70 OPTICS 引入两个新概念  p为对象, D为数据集,为距离值,MinPts为最 小对象数,N(p)为邻域对象数  p的核心距离:  使得P成为核心对象的最小  若|(N(p)| MinPts,即p不是核心对象,则无定义, 即无穷大  p关于对象q的可达距离:p的核心距离和p,q的欧 氏距离之间的较大值  Max(核心距离,|(p,q)|)  若|N(p)| MinPts,即p不是核心对象,则无定义 71 OPTICS 概念图示  核心距离  可达距离 72 OPTICS算法  1.计算数据点p的核心距离和可达距离  2.如果p为核心对象,找到所有它的关于 和MinPts的直接密度可达点,按可达距 离排序并插入队列。  3.处理下一个数据点 Complexity: O(kN2) 73 参数的影响  减小,则可达距离为无穷大的点增多;  MinPts减小,核心对象增多,图象更尖锐 可达距离 对象的簇次序 74 基于网格的方法 75 主要思想  数据空间区域被划分为矩形单元  对应于不同级别的分辨率,存在着不同级别的 矩形单元:高层的每个单元被分为多个低一层 的单元。  每个网格单元的统计信息被预先计算和存储, 以供处理查询之用 76 CLIQUE(1998)  CLIQUE:Clustering In QUEst,1998  给定多维数据集合,数据点在数据空间 中不是均衡分布的。  如果一个单元中的包含数据点超过了某 个输入模型参数,则该单元是密集的。  簇:相连的密集单元的最大集合 77 CLIQUE主要步骤  1.将数据空间划分为互不相交的长方形单元, 记录每个单元里的对象数  2.用先验性质识别包含簇的子空间  3.识别簇:  在符合兴趣度的子空间中找出密集单元  在符合兴趣度的子空间中找出相连的密集单元  4.识别密集单元  先验性质:如果一个K维单元是密集的,那么它在 k-1空间上的投影也是密集的。  即给定一个k维的侯选密集单元,如果检查它的k-1 维投影空间,发现任何一个不是密集的,那么知道 第k维的单元也不可能是密集的。 78 Salary (10,000) Vacation (week) 20 30 40 50 60 age 5 4 3 1 2 6 7 0 20 30 40 50 60 age 5 4 3 1 2 6 7 0 age Vacation 30 50  = 3 关于age对salary和 vacation维的密集单元, 这些密集单元相交形成 更高维度密集单元的一 个侯选搜索空间 79 CLIQUE有效性和缺点  自动地发现最高维的子空间,高密度聚 类存在于这些子空间中。  对元组的输入顺序不敏感,无需假设任 何规范的数据分布  随输入数据的大小线形地扩展,当数据 的维数增加时具有良好的可伸缩性  聚类结果的准确度较低 80 On-line clustering 81 On-line clustering  Web Search Results: multiple sub-topics are mixed together for the given query.  Organizing Web search results into clusters facilitates users' quick browsing. 82 On-line clustering  Zamir and Etzioni‟95:  clustering algorithm should take the document snippets instead of the whole documents as input, since the downloading of original documents is time-consuming;  the clustering algorithm should be fast enough for online calculation  the generated clusters should have readable descriptions for quick browsing by users.  Zamir and Etzioni presented a Suffix Tree Clustering (STC) ‟95 ( Web Document Clustering: A Feasibility Demonstration)  first identifies sets of documents that share common phrases,  then create clusters according to these phrases 83 Suffix Tree Clustering (STC)  STC is a linear time clustering algorithm that is based on a suffix tree which efficiently identifies sets of documents that share common phrases.  STC satisfies the key requirements:  STC treats a document as a string, making use of proximity information between words.  STC is novel, incremental, and O(n) time algorithm.  STC succinctly summarizes clusters‟ contents for users.  Quick because of working on smaller set of documents, incrementality  … 84 后缀树  一棵后缀树包含了一个或者多个字符串的 所有后缀。空字符串也算其中一个后缀。  对于字符串banana,其所有后缀为: banana anana nana ana na a 空。  通常为了更清楚地表示出后缀,在字符串 末尾添加一个特殊字符作为结束标记($)。  后缀树可以用O(n)的算法构造出来。 85 后缀树  banana所对应的后缀树如下: 86 STC算法  Step1: Document “cleaning” Html -> plain text Words stemming Mark sentence boundaries Remove non-word tokens  Step 2: Identifying Base Clusters  Step3: Combining Base Clusters * STC treats a document as a set of strings… 87 Ex. A Suffix Tree of Strings  Document1: “cat ate cheese”,  Document2: “mouse ate cheese too”  Document3: “cat ate mouse too” Document No, Term No 88 Base clusters Base clusters corresponding to the suffix tree nodes 89 Base Cluster Graph Node: cluster Edge: similarity between two clusters > 1 What if “ate” is in the stop word list? 90 Cluster score  s(B) = |B| * f(|P|) |B| is the number of documents in base cluster B |P| is the number of words in P that have a non-zero score • zero score words: stopwords, too few(<3) or too many( >40%) 91 Step 3: Combining Base Clusters  Merge base clusters with a high overlap in their document sets documents may share multiple phrases.  Similarity of Bm and Bn (0.5 is paramter) 1 iff | Bm  Bn| / | Bm | > 0.5 = and | Bm  Bn| / | Bn | > 0.5 0 otherwise 92 Evaluation-Precision 93 Snippets vs. Whole Document 94 Execution time 95 STC  STC – an incremental, o(n) time clustering algorithm  STC allows cluster overlap a document often has 1+ topics STC allows a document to appear in 1+ clusters, since documents may share 1+ phrases with other documents But not too similar to be merged into one cluster..  A clustering algorithms on Web search engine results 96 A paper: Cluster Web Search Results, 2004  Learning to Cluster Web Search Results.  Hua-Jun Zeng, etc. (Microsoft research, Asia) , SIGIR‟04, 2004  These traditional clustering techniques generate clusters with poor readable names. 97 A paper: Cluster Web Search Results, 2004  Zeng‟s method reformalize the clustering problem as a salient phrase ranking problem. First extracts and ranks salient phrases as candidate cluster names, based on a regression model learned from human labeled training data. The documents are assigned to relevant salient phrases to form candidate clusters. The final clusters are generated by merging these candidate clusters. 98 Salient Phrases Extraction  Denote: the current phrase (an n-gram) as w, the set of documents that contains w as D(w).  Five properties which are calculated during the document parsing.  Phrase Frequency / Inverted Document Frequency  Phrase Length  Intra-Cluster Similarity  Cluster Entropy  Phrase Independence  Phrase Frequency / Inverted Document Frequency  Phrase Length: the count of words in a phrase. a longer name is preferred for users„ browsing. LEN = n  Intra-Cluster Similarity (ICS):is calculated as the average cosine similarity between the documents and the centroid. 99 Salient Phrases Extraction 100 Salient Phrases Extraction  Cluster Entropy (CE) :represent the distinctness of a phrase.  Phrase Independence (IND):a phrase is independent when the entropy of its context is high (i.e. the left and right contexts are random enough). 101 Experimental Results ----Property Comparison 102 Experimental Results ---- Learning Methods Comparison  The coefficients of one of the linear regression models, as follows 103 Example Queries 伊拉克 104 小结  聚类概述  聚类算法 划分方法 层次方法 密度方法 网格方法 在线聚类 105
还剩104页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf