自組織神經(jīng)網(wǎng)絡(luò)-北京大學(xué)Text+Clustering+2課件

TextClusteringIIWangJiminNov25,2005Outline

引言文本間距離與文本類間的距離

聚類方法層次方法劃分方法

SOM方法聚類結(jié)果的評(píng)價(jià)聚類聚類是對(duì)數(shù)據(jù)對(duì)象進(jìn)行劃分的一種過(guò)程，與分類不同的是，它所劃分的類是未知的，故此，這是一個(gè)“無(wú)指導(dǎo)的學(xué)習(xí)”過(guò)程，它傾向于數(shù)據(jù)的自然劃分。文本聚類（Textclustering）:將文本集合分組成多個(gè)類或簇，使得在同一個(gè)簇中的文本內(nèi)容具有較高的相似度，而不同簇中的文本內(nèi)容差別較大。它是聚類分析技術(shù)在文本處理領(lǐng)域的一種應(yīng)用。層次聚類方法凝聚的方法(agglomerative)，也稱自底向上（bottom-up）

分裂的方法（divisive），也稱自頂向下（top-down）還有許多變形（改進(jìn)）方法，如BIRCH,CURE等Outline

引言文本間距離與文本類間的距離

聚類方法層次方法劃分方法

SOM方法聚類結(jié)果的評(píng)價(jià)TheK-MeansClusteringMethod

Example012345678910012345678910012345678910012345678910K=2ArbitrarilychooseKobjectasinitialclustercenterAssigneachobjectstomostsimilarcenterUpdatetheclustermeansUpdatetheclustermeansreassignreassignk-平均算法step1.任意選擇k個(gè)對(duì)象作為初始的類的中心step2.repeatstep3.根據(jù)類中文檔的平均值,將每個(gè)文檔(重新)賦給最相近的類step4.更新類的平均值，step5.until不再發(fā)生變化,即沒(méi)有對(duì)象進(jìn)行被重新分配時(shí)過(guò)程結(jié)束。

有多種變形形式k-平均方法有多種變形形式，不同改進(jìn)在于：初始k個(gè)平均值的選擇相異度的計(jì)算計(jì)算類平均值產(chǎn)生較好聚類結(jié)果的一個(gè)有趣策略：首先用層次聚類方法決定結(jié)果簇的個(gè)數(shù)，并找到初始的聚類然后用迭代重定位來(lái)改進(jìn)聚類結(jié)果。k-中心點(diǎn)（k-modoid）方法PAM（partitioningaroundmedoid）是最早提出的k-中心點(diǎn)方法之一。它選用簇中位置最靠近中心的對(duì)象作為代表對(duì)象（中心點(diǎn)），試圖對(duì)n個(gè)對(duì)象給出k個(gè)劃分。最初隨機(jī)選擇k個(gè)對(duì)象作為中心點(diǎn)，該算法反復(fù)用非代表對(duì)象（非中心點(diǎn)）代替中心點(diǎn)，試圖找出更好的中心點(diǎn)，以改進(jìn)聚類結(jié)果的質(zhì)量。k-中心點(diǎn)（k-modoid）方法在每次迭代中，所有可能的對(duì)象對(duì)被分析，每個(gè)對(duì)中的一個(gè)對(duì)象是中心點(diǎn)，而另一個(gè)是非中心點(diǎn)。對(duì)所有可能的組合，估算聚類結(jié)果的質(zhì)量。一個(gè)對(duì)象Oi被可以使最大平方誤差減少的對(duì)象代替。在一次迭代中產(chǎn)生的最佳對(duì)象集合成為下次迭代的中心點(diǎn)。判定一個(gè)對(duì)象Oh是否是當(dāng)前一個(gè)代表對(duì)象Oi的好替代，對(duì)每一個(gè)非代表對(duì)象Oj需要分情況考慮替換的代價(jià)。PAM對(duì)非代表對(duì)象Oj來(lái)說(shuō)，上圖給出了Oh替代Oi所化的代價(jià)。遍歷所有j即得到總交換代價(jià)TCih

。該代價(jià)函數(shù)反映了替換前后平方誤差值之間的差別。

若總代價(jià)為負(fù)，Oh可以替代Oi，否則說(shuō)明當(dāng)前的中心點(diǎn)是可接受的，在本次迭代中不發(fā)生變化。k-中心點(diǎn)（k-modoid）算法step1.任意選擇k個(gè)對(duì)象作為初始的類的中心點(diǎn)step2.repeatstep3.指派每個(gè)剩余對(duì)象給離它最近的中心點(diǎn)step4.隨機(jī)選擇一個(gè)非中心點(diǎn)Ohstep5.計(jì)算用Oh代替中心點(diǎn)Oi的總代價(jià)Sstep6.ifS<0,thenOh代替中心點(diǎn)Oi

形成新的k個(gè)中心點(diǎn)集合until不再發(fā)生變化。算法性能有效消除了對(duì)孤立點(diǎn)數(shù)據(jù)的敏感性。比k-means方法更健壯，不易受極端數(shù)據(jù)的影響。PAM對(duì)小數(shù)據(jù)集非常有效（如100個(gè)對(duì)象聚成5類），但對(duì)大數(shù)據(jù)集效率較低?？蓴U(kuò)展性差。PAM算法的改進(jìn):CLARA

CLARA（ClusterLARgerApplication）:基于k-medoid類型的算法，能處理較大的數(shù)據(jù)集合。

首先進(jìn)行隨機(jī)抽樣，用PAM方法從樣本中選擇中心點(diǎn)。如果樣本是以非常隨機(jī)的方式選取的，它應(yīng)該足以代表原來(lái)的數(shù)據(jù)集合。從中選出的中心點(diǎn)很可能與從整體集合中選出的非常近似。

CLARACLARA可以抽取多個(gè)樣本，對(duì)每個(gè)樣本應(yīng)用PAM算法，返回最好的聚類結(jié)果。復(fù)雜度是O（ks2+k(n-k)）,其中s是樣本大小。如果樣本發(fā)生傾斜，基于樣本的一個(gè)好的聚類不一定代表整個(gè)數(shù)據(jù)集合的一個(gè)好的聚類。特別地，如果任何取樣得到的中心點(diǎn)不包含最佳的中心點(diǎn)，CLARA算法不能得到最佳聚類。Outline

引言文本間距離與文本類間的距離

聚類方法層次方法劃分方法

SOM方法聚類結(jié)果的評(píng)價(jià)WEBSOMWEBSOMisamethodforautomaticallyorganizingcollectionsoftextdocumentsandforpreparingvisualmapsofthemtofacilitatetheminingandretrievalofinformation.Thedocumentsareinthepoints,or"pigeon-holes",ofthemap,andtheircontentscanbebrowsedbyclickingthepointsvisibleonthelowestlevelofthemapdisplay.YoucanuseafulltextsearchtofindaninterestingstartingpointforbrowsingOvermilliondocumentsfromover80UsenetnewsgroupsWebsomWebsom自組織映射(SOM)SOM（self-organizingmap）神經(jīng)網(wǎng)絡(luò)是一種基于模型的聚類方法。

SOM是由芬蘭赫爾辛基大學(xué)神經(jīng)網(wǎng)絡(luò)專家Kohonen教授在1981年提出的競(jìng)爭(zhēng)式神經(jīng)網(wǎng)絡(luò)，它模擬大腦神經(jīng)系統(tǒng)自組織特征映射的功能，在訓(xùn)練中能無(wú)監(jiān)督地進(jìn)行自組織學(xué)習(xí)。由于它的強(qiáng)大功能，多年來(lái)，網(wǎng)絡(luò)在數(shù)據(jù)分類、知識(shí)獲取、過(guò)程監(jiān)控、故障識(shí)別等領(lǐng)域中得到了廣泛應(yīng)用。SOM組成SOM神經(jīng)網(wǎng)絡(luò)由輸入層和競(jìng)爭(zhēng)層組成。輸入層由N個(gè)神經(jīng)元組成，競(jìng)爭(zhēng)層由M個(gè)神經(jīng)元組成。為可視化表示結(jié)果，常將M表示為一個(gè)二維平面陣列M=s*t，當(dāng)然,一維或多維也是允許的。SOM組成典型的SOM聚類算法

1.初始化，用較小的隨機(jī)數(shù)對(duì)競(jìng)爭(zhēng)層各個(gè)神經(jīng)元的每一個(gè)權(quán)向量賦初值。2．用文本集合中選擇選擇一個(gè)訓(xùn)練向量Xi進(jìn)行輸入3．比較競(jìng)爭(zhēng)層中所有神經(jīng)元，尋找神經(jīng)元j，使它的突融權(quán)重向量Wj最接近Xi，即|Xi--Wj|=min{|Xi–Wk|,k=1，…，M}。4.修改神經(jīng)元j及其鄰居神經(jīng)元，更新它的突融權(quán)重

其中，a(t)為訓(xùn)練參數(shù),0<a(t)<1，t為訓(xùn)練次數(shù)5．如果訓(xùn)練次數(shù)t的值達(dá)到預(yù)設(shè)次數(shù)T，則停止訓(xùn)練，否則減少a(t)的值，重復(fù)2—4步。注：在訓(xùn)練過(guò)程中，隨著訓(xùn)練次數(shù)t的增加，a(t)和領(lǐng)域都不斷變小。

神經(jīng)元間的不同拓?fù)浣Y(jié)構(gòu)：矩形結(jié)構(gòu)（網(wǎng)格結(jié)構(gòu)）六角形結(jié)構(gòu)

隨機(jī)拓?fù)浣Y(jié)構(gòu)

神經(jīng)元之間的距離歐幾里德距離、位置向量之間距離、Manhattan距離等。一個(gè)例子:matlabp=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;一個(gè)例子:matlab一個(gè)具體應(yīng)用

SOM文檔信息地圖：把語(yǔ)義相近的文檔聚集在一起，并為每個(gè)類目自動(dòng)地分配一個(gè)標(biāo)簽來(lái)說(shuō)明這個(gè)類目的主題。XiaLin（1991）ASelf-organizingSemanticMapforInformationRetrieval一個(gè)具體應(yīng)用類似應(yīng)用SOMSOM類似于大腦的信息處理過(guò)程。它能把任意維的輸入信號(hào)變換到一維或二維的離散網(wǎng)格上，并保持一定的拓?fù)溆行蛐浴OM通過(guò)對(duì)輸入向量的反復(fù)學(xué)習(xí)，其權(quán)向量的空間分布能反映輸入向量的統(tǒng)計(jì)特征。訓(xùn)練結(jié)束后，狀態(tài)相同或相近的輸入向量在競(jìng)爭(zhēng)層網(wǎng)絡(luò)上所處位置相鄰近，因此，該方法可以正確顯示SOM的聚類訓(xùn)練結(jié)果。SOM不足網(wǎng)絡(luò)連接權(quán)向量初值的選取對(duì)網(wǎng)絡(luò)收斂性影響很大。

訓(xùn)練時(shí)間過(guò)長(zhǎng)對(duì)大集合處理困難。Outline

引言文本間距離與文本類間的距離

聚類方法層次方法劃分方法

SOM方法聚類結(jié)果的評(píng)價(jià)聚類結(jié)果的評(píng)測(cè)因?yàn)闆](méi)有訓(xùn)練文檔集合，所以評(píng)測(cè)聚類效果是比較困難的。常用的方法是：

選擇人工已經(jīng)分好類或者做好標(biāo)記的文檔集合作為測(cè)試集合，聚類結(jié)束后，將聚類結(jié)果與已有的人工分類結(jié)果進(jìn)行比較。

文檔關(guān)聯(lián)評(píng)測(cè)及其指標(biāo)所謂文檔關(guān)聯(lián)，是指屬于同一個(gè)類別的任意兩個(gè)文檔之間所形成的“文檔對(duì)”關(guān)系。基于文檔關(guān)聯(lián)的聚類評(píng)測(cè)方法，其考察的基本對(duì)象就是“文檔對(duì)”。各種不同情況下的“文檔對(duì)”數(shù)據(jù)主要有：Pt:文檔集合中所有可能的文檔對(duì)的數(shù)量。設(shè)文檔總數(shù)為n，則Pt=Cn2=n*(n-1)/2.Tm:人工分類中所有可能的文檔對(duì)的數(shù)量。Ta:聚類結(jié)果中所有可能的文檔對(duì)的數(shù)量。Ei:錯(cuò)誤關(guān)聯(lián)，指在聚類結(jié)果中出現(xiàn)，而在人工分類中沒(méi)有出現(xiàn)的文檔對(duì)的數(shù)量。Em:遺漏關(guān)聯(lián)，指在人工分類中出現(xiàn)，而在聚類結(jié)果中沒(méi)有出現(xiàn)的文檔對(duì)的數(shù)量。評(píng)測(cè)指標(biāo)聚類錯(cuò)誤率CE=(錯(cuò)誤關(guān)聯(lián)+遺漏關(guān)聯(lián))/文檔集合中所有可能的文檔對(duì)的數(shù)量=(Ea+Em)/Pt聚類全面率CR=正確關(guān)聯(lián)數(shù)/人工分類中文檔對(duì)的數(shù)量=（Ta--Ei）