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

TextClusteringIIWangJiminNov25,2005Outline

引言文本间距离与文本类间的距离

聚类方法层次方法划分方法

SOM方法聚类结果的评价聚类聚类是对数据对象进行划分的一种过程，与分类不同的是，它所划分的类是未知的，故此，这是一个“无指导的学习”过程，它倾向于数据的自然划分。文本聚类（Textclustering）:将文本集合分组成多个类或簇，使得在同一个簇中的文本内容具有较高的相似度，而不同簇中的文本内容差别较大。它是聚类分析技术在文本处理领域的一种应用。层次聚类方法凝聚的方法(agglomerative)，也称自底向上（bottom-up）

分裂的方法（divisive），也称自顶向下（top-down）还有许多变形（改进）方法，如BIRCH,CURE等Outline

引言文本间距离与文本类间的距离

聚类方法层次方法划分方法

SOM方法聚类结果的评价划分方法对包含n个文档的文本集合，划分将生成k个分组，k<=n，每一个分组代表一个聚类聚类的准则函数通常选用平方误差准则典型的划分方法（Partitioningmethods）:k-平均方法k-中心点方法TheK-MeansClusteringMethod

Example012345678910012345678910012345678910012345678910K=2ArbitrarilychooseKobjectasinitialclustercenterAssigneachobjectstomostsimilarcenterUpdatetheclustermeansUpdatetheclustermeansreassignreassignk-平均算法step1.任意选择k个对象作为初始的类的中心step2.repeatstep3.根据类中文档的平均值,将每个文档(重新)赋给最相近的类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需要分情况考虑替换的代价。PAMPAM对非代表对象Oj来说，上图给出了Oh替代Oi所化的代价。遍历所有j即得到总交换代价TCih

。该代价函数反映了替换前后平方误差值之间的差别。

若总代价为负，Oh可以替代Oi，否则说明当前的中心点是可接受的，在本次迭代中不发生变化。k-中心点（k-modoid）算法step1.任意选择k个对象作为初始的类的中心点step2.repeatstep3.指派每个剩余对象给离它最近的中心点step4.随机选择一个非中心点Ohstep5.计算用Oh代替中心点Oi的总代价Sstep6.ifS<0,thenOh代替中心点Oi

形成新的k个中心点集合until不再发生变化。Example?5个节点，熟悉其实际计算过程Exercise?算法性能有效消除了对孤立点数据的敏感性。比k-means方法更健壮，不易受极端数据的影响。PAM对小数据集非常有效（如100个对象聚成5类），但对大数据集效率较低。可扩展性差。PAM算法的改进:CLARA

CLARA（ClusterLARgerApplication）:基于k-medoid类型的算法，能处理较大的数据集合。

首先进行随机抽样，用PAM方法从样本中选择中心点。如果样本是以非常随机的方式选取的，它应该足以代表原来的数据集合。从中选出的中心点很可能与从整体集合中选出的非常近似。

CLARACLARA可以抽取多个样本，对每个样本应用PAM算法，返回最好的聚类结果。复杂度是O（ks2+k(n-k)）,其中s是样本大小。如果样本发生倾斜，基于样本的一个好的聚类不一定代表整个数据集合的一个好的聚类。特别地，如果任何取样得到的中心点不包含最佳的中心点，CLARA算法不能得到最佳聚类。Outline

引言文本间距离与文本类间的距离

聚类方法层次方法划分方法

SOM方法聚类结果的评价WEBSOMWEBSOMisamethodforautomaticallyorganizingcollectionsoftextdocumentsandforpreparingvisualmapsofthemtofacilitatetheminingandretrievalofinformation.Thedocumentsareinthepoints,or"pigeon-holes",ofthemap,andtheircontentscanbebrowsedbyclickingthepointsvisibleonthelowestlevelofthemapdisplay.YoucanuseafulltextsearchtofindaninterestingstartingpointforbrowsingOvermilliondocumentsfromover80UsenetnewsgroupsWebsomWebsomWebsom自组织映射(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)为训练参数,0<a(t)<1，t为训练次数5．如果训练次数t的值达到预设次数T，则停止训练，否则减少a(t)的值，重复2—4步。注：在训练过程中，随着训练次数t的增加，a(t)和领域都不断变小。

神经元间的不同拓扑结构：矩形结构（网格结构）六角形结构

随机拓扑结构

神经元之间的距离欧几里德距离、位置向量之间距离、Manhattan距离等。一个例子:matlabp=rands(2,1000);plot(p(1,:),p(2,:),'+r');net=newsom([01;01],[56]);holdon;net.trainParam.epochs=1;net=train(ne