自组织神经网络-北京大学Text+Clustering+2

TextClusteringIIWangJiminNov25,2005信息科学技术学院·网络研究所Outline引言文本间距离与文本类间的距离聚类方法层次方法划分方法SOM方法聚类结果的评价信息科学技术学院·网络研究所聚类聚类是对数据对象进行划分的一种过程，与分类不同的是，它所划分的类是未知的，故此，这是一个“无指导的学习”过程，它倾向于数据的自然划分。文本聚类（Textclustering）:将文本集合分组成多个类或簇，使得在同一个簇中的文本内容具有较高的相似度，而不同簇中的文本内容差别较大。它是聚类分析技术在文本处理领域的一种应用。信息科学技术学院·网络研究所层次聚类方法凝聚的方法(agglomerative)，也称自底向上（bottom-up）分裂的方法（divisive），也称自顶向下（top-down）还有许多变形（改进）方法，如BIRCH,CURE等信息科学技术学院·网络研究所Outline引言文本间距离与文本类间的距离聚类方法层次方法划分方法SOM方法聚类结果的评价信息科学技术学院·网络研究所划分方法对包含n个文档的文本集合，划分将生成k个分组，k=n，每一个分组代表一个聚类聚类的准则函数通常选用平方误差准则典型的划分方法（Partitioningmethods）:k-平均方法k-中心点方法21||ikiipCEpm信息科学技术学院·网络研究所TheK-MeansClusteringMethodExample012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2ArbitrarilychooseKobjectasinitialclustercenterAssigneachobjectstomostsimilarcenterUpdatetheclustermeansUpdatetheclustermeansreassignreassign信息科学技术学院·网络研究所k-平均算法step1.任意选择k个对象作为初始的类的中心step2.repeatstep3.根据类中文档的平均值,将每个文档(重新)赋给最相近的类step4.更新类的平均值，step5.until不再发生变化,即没有对象进行被重新分配时过程结束。信息科学技术学院·网络研究所K-Means特点该算法试图找出使平方误差值最小的k个划分。当结果簇是密集的，而簇与簇之间区分明显时，它的效果较好。算法复杂度O（nkt），其中t是迭代次数。因此其可扩展性较好，对大数据集处理有较高的效率。算法常以局部最优结束。全局最优要穷举所有可能的划分。缺点：不适合发现非凸面状的簇。不适合大小差别较大的簇。对于噪声和孤立点是敏感的，由于少量的该类数据对平均值产生较大的]影响。信息科学技术学院·网络研究所有多种变形形式k-平均方法有多种变形形式，不同改进在于：初始k个平均值的选择相异度的计算计算类平均值产生较好聚类结果的一个有趣策略：首先用层次聚类方法决定结果簇的个数，并找到初始的聚类然后用迭代重定位来改进聚类结果。信息科学技术学院·网络研究所k-中心点（k-modoid）方法PAM（partitioningaroundmedoid）是最早提出的k-中心点方法之一。它选用簇中位置最靠近中心的对象作为代表对象（中心点），试图对n个对象给出k个划分。最初随机选择k个对象作为中心点，该算法反复用非代表对象（非中心点）代替中心点，试图找出更好的中心点，以改进聚类结果的质量。信息科学技术学院·网络研究所k-中心点（k-modoid）方法在每次迭代中，所有可能的对象对被分析，每个对中的一个对象是中心点，而另一个是非中心点。对所有可能的组合，估算聚类结果的质量。一个对象Oi被可以使最大平方误差减少的对象代替。在一次迭代中产生的最佳对象集合成为下次迭代的中心点。判定一个对象Oh是否是当前一个代表对象Oi的好替代，对每一个非代表对象Oj需要分情况考虑替换的代价。信息科学技术学院·网络研究所PAM信息科学技术学院·网络研究所PAM对非代表对象Oj来说，上图给出了Oh替代Oi所化的代价。遍历所有j即得到总交换代价TCih。该代价函数反映了替换前后平方误差值之间的差别。若总代价为负，Oh可以替代Oi，否则说明当前的中心点是可接受的，在本次迭代中不发生变化。信息科学技术学院·网络研究所k-中心点（k-modoid）算法step1.任意选择k个对象作为初始的类的中心点step2.repeatstep3.指派每个剩余对象给离它最近的中心点step4.随机选择一个非中心点Ohstep5.计算用Oh代替中心点Oi的总代价Sstep6.ifS0,thenOh代替中心点Oi形成新的k个中心点集合until不再发生变化。信息科学技术学院·网络研究所Example?5个节点，熟悉其实际计算过程Exercise?信息科学技术学院·网络研究所算法性能有效消除了对孤立点数据的敏感性。比k-means方法更健壮，不易受极端数据的影响。PAM对小数据集非常有效（如100个对象聚成5类），但对大数据集效率较低。可扩展性差。信息科学技术学院·网络研究所PAM算法的改进:CLARACLARA（ClusterLARgerApplication）:基于k-medoid类型的算法，能处理较大的数据集合。首先进行随机抽样，用PAM方法从样本中选择中心点。如果样本是以非常随机的方式选取的，它应该足以代表原来的数据集合。从中选出的中心点很可能与从整体集合中选出的非常近似。信息科学技术学院·网络研究所CLARACLARA可以抽取多个样本，对每个样本应用PAM算法，返回最好的聚类结果。复杂度是O（ks2+k(n-k)）,其中s是样本大小。如果样本发生倾斜，基于样本的一个好的聚类不一定代表整个数据集合的一个好的聚类。特别地，如果任何取样得到的中心点不包含最佳的中心点，CLARA算法不能得到最佳聚类。信息科学技术学院·网络研究所Outline引言文本间距离与文本类间的距离聚类方法层次方法划分方法SOM方法聚类结果的评价信息科学技术学院·网络研究所WEBSOMWEBSOMisamethodforautomaticallyorganizingcollectionsoftextdocumentsandforpreparingvisualmapsofthemtofacilitatetheminingandretrievalofinformation.Thedocumentsareinthepoints,orpigeon-holes,ofthemap,andtheircontentscanbebrowsedbyclickingthepointsvisibleonthelowestlevelofthemapdisplay.YoucanuseafulltextsearchtofindaninterestingstartingpointforbrowsingOvermilliondocumentsfromover80Usenetnewsgroups信息科学技术学院·网络研究所Websom信息科学技术学院·网络研究所Websom信息科学技术学院·网络研究所Websom信息科学技术学院·网络研究所自组织映射(SOM)SOM（self-organizingmap）神经网络是一种基于模型的聚类方法。SOM是由芬兰赫尔辛基大学神经网络专家Kohonen教授在1981年提出的竞争式神经网络，它模拟大脑神经系统自组织特征映射的功能，在训练中能无监督地进行自组织学习。由于它的强大功能，多年来，网络在数据分类、知识获取、过程监控、故障识别等领域中得到了广泛应用。信息科学技术学院·网络研究所SOM的基础SOM的基础:尽管大脑具有大量的细胞，但生物学研究表明作用并不同。在空间中处于不同位置的脑细胞控制着人体不同部位的运动。同样，处于不同区域的脑细胞对来自某一方面的刺激信号的敏感程度也不一样。这种特定细胞对特定信号的特别反映能力似乎是由后来的经历和训练形成的。Kohonen根据人脑的这一原理提出了自组织映射。信息科学技术学院·网络研究所SOM组成SOM神经网络由输入层和竞争层组成。输入层由N个神经元组成，竞争层由M个神经元组成。为可视化表示结果，常将M表示为一个二维平面阵列M=s*t，当然,一维或多维也是允许的。信息科学技术学院·网络研究所SOM组成信息科学技术学院·网络研究所典型的SOM聚类算法1.初始化，用较小的随机数对竞争层各个神经元的每一个权向量赋初值。2．用文本集合中选择选择一个训练向量Xi进行输入3．比较竞争层中所有神经元，寻找神经元j，使它的突融权重向量Wj最接近Xi，即|Xi--Wj|=min{|Xi–Wk|,k=1，…，M}。4.修改神经元j及其邻居神经元，更新它的突融权重其中，a(t)为训练参数,0a(t)1，t为训练次数5．如果训练次数t的值达到预设次数T，则停止训练，否则减少a(t)的值，重复2—4步。注：在训练过程中，随着训练次数t的增加，a(t)和领域都不断变小。(1)()(())kkikwtwttXWt信息科学技术学院·网络研究所神经元间的不同拓扑结构：矩形结构（网格结构）六角形结构随机拓扑结构信息科学技术学院·网络研究所神经元之间的距离欧几里德距离、位置向量之间距离、Manhattan距离等。信息科学技术学院·网络研究所一个例子:matlabp=rands(2,1000);plot(p(1,:),p(2,:),'+r');net=newsom([01;01],[56]);holdon;net.trainParam.epochs=1;net=train(net,p);plotsom(net.iw{1,1},net.layers{1}.distances)holdoff;信息科学技术学院·网络研究所一个例子:matlab信息科学技术学院·网络研究所一个具体应用SOM文档信息地图：把语义相近的文档聚集在一起，并为每个类目自动地分配一个标签来说明这个类目的主题。XiaLin（1991）ASelf-organizingSemanticMapforInformationRetrieval信息科学技术学院·网络研究所一个具体应用信息科学技术学院·网络研究所类似应用信息科学技术学院·网络研究所SOMSOM类似于大脑的信息处理过程。它能把任意维的输入信号变换到一维或二维的离散网格上，并保持一定的拓扑有序性。SOM通过对输入向量的反复学习，其权向量的空间分布能反映输入向量的统计特征。训练结束后，状态相同或相近的输入向量在竞争层网络上所处位置相邻近，因此，该方法可以正确显示SOM的聚类训练结果。信息科学技术学院·网络研究所SOM不足网络连接权向量初值的选取对网络收敛性影响很大。训练时间过长对大集合处理困难。信息科学技术学院·网络研究所Outline引言文本间距离与文本类间的距离聚类方法层次方法划分方法SOM方法聚类结果的评价信息科学技术学院·网络研究所聚类结果的评测因为没有训练文档集合，所以评测聚类效果是比较困难的。常用的方法是：选择人工已经分好类或者做好标记的文档集合作为测试集合，聚类结束后，将聚类结果与已有的人工分类结果进行比较。信息科学技术学院·网络研究所文档关联评测及其指标所谓文档关联，是指属于同一个类别的任意两个文档之间所形成的“文档对”关系。基于文档关联的聚类评测方法，其考察的基本对象就是“文档对”。各种不同情况下的“文档对”数据主要有：Pt:文档集合中所有可能的文档对的数量。设文档总数为n，则Pt=Cn2=n*