【正文】 .....................................11 第三章 k均值聚類算法 .............................................................................................. 12 K均值聚類算法的思想 ........................................................................................ 12 K均值聚類算法的基本思想 ............................................................................. 12 K均值聚類算法的算法流程 ............................................................................. 12 K均值算法的優(yōu)缺點(diǎn)分析 ................................................................................. 13 K均值聚類算法的改進(jìn) ................................................................... 15 K均值聚類算法 ..................................................... 16 本章小結(jié) ................................................................................................................ 17 第四章 SOM 聚類算法 ................................................................................................... 18 SOM 聚類算法的網(wǎng)絡(luò)特性與基本流程 ................................................................. 18 基于文本 的 聚類算法研究 SOM網(wǎng)絡(luò)的特性 ................................................................................................ 18 SOM網(wǎng)絡(luò)聚類的基本流程 .................................................................................. 19 SOM網(wǎng)絡(luò)聚類的優(yōu)點(diǎn)及存在的問題 .................................................................... 19 SOM 聚類方法 ............................................................................................. 20 ......................................................................................... 20 ...................................................... 21 ................................................................................................ 22 .............................................................................. 22 .................................................................................. 23 ................................................................................................................. 25 參 考 文 獻(xiàn) .................................................................................................................. 26 致 謝 ........................................................................................................................ 28 基于文本的聚類算法研究 1 第一章 緒 論 課題研究的背景 隨著 Inter 的迅猛發(fā)展，信息的爆炸式增加，信息超載問題變的越來越嚴(yán)重，信息的更新率也越來越高，用戶在信息海洋里查找信息就像大海撈針一樣。 作 者 簽 名： 日 期： 指導(dǎo)教師簽名： 日 期： 使用授權(quán)說明 本人完全了解 大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計(jì)（論文）的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版本；學(xué)校有權(quán)保 存畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)?？梢圆捎糜坝?、縮印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)?？梢怨颊撐牡牟糠只蛉?jī)?nèi)容。其目的是要使同一類別的文本間的相似度盡可能大，而不同類別的文本間的相似度盡可能的小。本文主 要 研究的聚類主要方法是 k均值和 SOM算法，介紹 了兩種算法的基本思想和實(shí)現(xiàn)步驟，并分析兩種算法的聚類效果。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方 式標(biāo)明。那么 ，如何從中獲取特定內(nèi)容的信息和知識(shí)成為擺在人們面前的一道難題。 隨著人們對(duì) 聚 類問題更加深入地了解和重視，國(guó)內(nèi)外大量學(xué)者不斷投身到該項(xiàng)目研究，聚類主要工作集中在尋找針對(duì)大型數(shù)據(jù)庫(kù)的聚類方法和世界的聚類分析方法上，使得各種成果不斷涌現(xiàn)，各個(gè)領(lǐng)域的聚類分析算法層出不窮。近年來，文檔聚類算法還在文檔分析處理領(lǐng)域中一個(gè)新的應(yīng)用方向話題檢測(cè)與跟蹤中得到了進(jìn)一步研究與應(yīng)用。聚類流程三個(gè)步驟的實(shí)際處理內(nèi)容為： (1)文本聚類分析首先將文本表示成機(jī)器可計(jì)算的形式。不同的算法對(duì)參數(shù)的敏感性不同，但是基本上參數(shù)的好壞對(duì)結(jié)果的影響都比較顯著。特征的權(quán)重定義及特征結(jié)構(gòu)上的相似度度量可以選取不同的模型，如向量空間模型、概率模型、語(yǔ)言模型等。經(jīng)典布爾模型中查詢與文檔的相關(guān)性只能是 0或者 1，滿足查詢query 中的所有邏輯表達(dá)式的文檔被判定相關(guān)，不滿足的被判定為不相關(guān)。每個(gè)文檔可以用文檔中的詞來表示，這些詞及其對(duì)應(yīng)的權(quán)重構(gòu)成一個(gè)向量。如果兩文本之間相似度為 1，則說明這兩個(gè)文本對(duì)象完全相同；反之，則說明兩文本沒有相似之處。為了衡量文本集合之間的相似度，常見的方法有：最小距離、最大距離、平均距離、質(zhì)心法、離差平方和等。為了對(duì)大規(guī)模的數(shù)據(jù)集進(jìn)行聚類，以及處理復(fù)雜形狀的聚類，各類改進(jìn)的劃分算法逐漸增多。使用該算法可以得到較好的聚類結(jié)果，而且該方法無需用戶輸入?yún)?shù)；但是層次聚類算法的時(shí)間復(fù)雜度比較高，達(dá)到了 O(n2)，對(duì)于大規(guī)模的文本集合，有其不適用性。 基于密度的聚類算法在當(dāng)前的文獻(xiàn)中較少被用于文本聚類中。代表算法有統(tǒng)計(jì)信息網(wǎng)格法 STING 算法、聚類高維空間法 CLIQUE 算法、基于小波變換的聚類法 WAVECLUSTER 算法。 基于模型的方法 基于模型的算法（ ModelBased Clustering Method）試圖優(yōu)化給定的數(shù)據(jù)和某些數(shù)學(xué)模型之間的適應(yīng)性。如基于 SOM 的文檔聚類方法在數(shù)字圖書館等領(lǐng)域得到了較好的應(yīng)用。該算法首先隨機(jī)選取 k個(gè)數(shù)據(jù)點(diǎn)作為 n個(gè) 簇的初始簇中心，集合中每個(gè)數(shù)據(jù)點(diǎn)被劃分到與其距離最近的簇中心所在的類簇之中，形成了 k 個(gè)聚類的初始分布。具體流程如下 : [Stepl][初始化 l隨機(jī)指定 k 個(gè)聚類中心 (ml， m2， ?? mk)。然而這些技術(shù)并沒有得到廣泛認(rèn)可，在許多實(shí)際應(yīng)用中還是反復(fù)利用 K均值聚類算法來解決問題。 K均值聚類算法隨機(jī)的選取 K個(gè)初始簇中心點(diǎn)，并針對(duì)這 K個(gè)簇中心點(diǎn)進(jìn)行迭代運(yùn)算，即重新分配數(shù)據(jù)點(diǎn)和重新計(jì)算簇中心的運(yùn)算，直到所有的數(shù)據(jù)點(diǎn)位置不再變化或聚類誤差準(zhǔn)則函數(shù)不再變化。 (5)K均值聚類算法不適用于大數(shù)據(jù)量的聚類問題。 基于 K均值聚類算法的改進(jìn)，國(guó)內(nèi)外的專家學(xué)者做了大量的研究工作，主要 基于文本的聚類算法研究 16 總結(jié)如下。 (6)聚類問題解出 k 類問題的中心。它是由多個(gè)細(xì)胞聚合而成的，在接受外界刺激后，它們會(huì)自動(dòng)形成。遺憾的是，網(wǎng)絡(luò)在高維映射到低維時(shí)會(huì)發(fā)生畸變，而且壓縮比越大，畸變?cè)酱?。鄰域半徑 Nbo. 步驟 2:取樣對(duì)所有輸入樣本執(zhí)行步驟 3 一步驟 6. 步驟 3:確定獲勝神經(jīng)元。 ③ 具有可視化的優(yōu)點(diǎn) 。相反有些神經(jīng)元因?yàn)楂@勝次數(shù)過多，出現(xiàn)神經(jīng)元過度利用的問題，也會(huì)影響網(wǎng)絡(luò)的學(xué)習(xí)效果。近 年來，有些學(xué)者針對(duì)神經(jīng)元欠利用和過度利用的問題，提出了許多改進(jìn)的學(xué)習(xí)策略，代表性的有 SOMCV、 SOMC、 ESOM、 TASOM、 DSOM。 以上算法對(duì)神經(jīng)元的獲勝策略進(jìn)行了改進(jìn)，在一定程度上解決了神經(jīng)元欠利用和過度利用 的問題，可以得到較好質(zhì)量的聚類結(jié)果。 (3)改進(jìn)算法的基本流程 根據(jù)等類內(nèi)離差準(zhǔn)則，希望所有分割區(qū)域的類內(nèi)離差相等，即要求所有的D(S、 )(i， 2，? K)相等。如果采用歐氏距離，按連接權(quán)向量與輸入樣本之間的距離值最小的神經(jīng)元是獲勝神經(jīng)元。 初始化連接權(quán)值 初始權(quán)的設(shè)置，對(duì)于網(wǎng)絡(luò)的收斂狀況和收斂速度都是有影響的。一般情況下，輸入學(xué)習(xí)模式只處于整個(gè)模式空間的有限位置，如果對(duì) 連接權(quán)值隨機(jī)初始化，則在權(quán)值矢量會(huì)廣泛地分布于各個(gè)隨機(jī)方向上，一定會(huì)有大量的連接基于文本的聚類算法研究 23 權(quán)矢量與輸入模式方向差異很大，甚至方向相反。進(jìn)行特征抽取以后，一個(gè)單詞可能映射到輸入空間的多個(gè)維上 ，使這種確定初始連接權(quán)值的方法變得非常困難。 圖 1 密集區(qū)域探測(cè) 步驟 2:按照這些密集 小區(qū)域的得分 (Score)為這個(gè)鏈表進(jìn)行排序。對(duì)所有輸入樣本執(zhí)行步驟 7一步驟 10。 步驟 10:返回步驟 6，直至算法收斂或達(dá)到最大迭代次數(shù)為為止。按本文更新獲勝神經(jīng)元及其鄰域內(nèi)所有神經(jīng)元的連接權(quán)值，而鄰域外的神經(jīng)元的連接權(quán)值保持不變。至此，獲得了 K個(gè)中心。選出的這 K個(gè)數(shù)據(jù)點(diǎn)應(yīng)該屬于不同的模式 類別為好，且這 K個(gè)數(shù)據(jù)點(diǎn)應(yīng)盡量靠近該類別的中心，這是我們初始化連接權(quán)時(shí)要達(dá)到的目標(biāo)。 (3)從輸入空間中任意選取 K 個(gè)矢量對(duì)權(quán)值矢量進(jìn)行初始化， K是輸出層神經(jīng)元結(jié)點(diǎn)的個(gè)數(shù)。 已有的初始化連接權(quán)的方法 網(wǎng)絡(luò)的訓(xùn)練主要是通過對(duì)連接權(quán)的調(diào)整實(shí)現(xiàn)的，當(dāng)連接權(quán)不再變化或者變化很少時(shí)，網(wǎng)絡(luò)訓(xùn)練就完成了，達(dá)到了一個(gè)收斂的狀態(tài)。鄰域半徑也隨著學(xué)習(xí)代數(shù)的增加而遞減，最后只有獲勝結(jié)點(diǎn)在學(xué)習(xí)。鄰 域半徑 Nb。來表示。 (4)TASOM 該種 學(xué)習(xí)策略中，每個(gè)神經(jīng)元都有自己的學(xué)習(xí)率和鄰域函數(shù)，并且能 根據(jù)學(xué)習(xí)時(shí)間自動(dòng)地調(diào)整學(xué)習(xí)率和鄰域的大小。 改進(jìn)的 SOM 聚類方法 已有的學(xué)習(xí)策略改進(jìn) 就具體的學(xué)習(xí)策略來說，自組織特征映射神經(jīng)網(wǎng)絡(luò)采用的是“勝者全得”的競(jìng)爭(zhēng)學(xué)習(xí)算法，就是在競(jìng)爭(zhēng)學(xué)習(xí)時(shí)網(wǎng)絡(luò)的各輸出神經(jīng)元相互競(jìng)爭(zhēng)，最后只有一個(gè)最強(qiáng)神經(jīng)元獲勝 。輸出層結(jié)點(diǎn)的初始拓?fù)浣Y(jié)構(gòu)與輸入模式在在原始數(shù)據(jù)空間中的拓?fù)浣Y(jié)構(gòu)一致時(shí)，網(wǎng)絡(luò)才會(huì)達(dá)到好的學(xué)習(xí)效果。調(diào)整學(xué)習(xí)率和鄰域半徑，為了保證算法的收斂，學(xué)習(xí)率的取值一般在 O到 1之間，且隨著學(xué)習(xí)代數(shù)的增加而遞減 。一般可以這樣說， SOM網(wǎng)絡(luò)的權(quán)矢量收斂到所代表的輸入矢量的平均值，它反映了輸入數(shù)據(jù)的統(tǒng)計(jì)特性。 SOM 網(wǎng)絡(luò)是輸入樣本通過競(jìng)爭(zhēng)學(xué)習(xí)后，功能相同的輸入靠得比較近，不同的分得比較開，以此將一些無規(guī)則的輸入自動(dòng)排開，在連接權(quán)的調(diào)整過程中，使權(quán)的分布與輸入域可逐步縮小，使區(qū)域的劃分越來越明顯。除了以上列出的初始中心點(diǎn)的選取方法以外，還有很多對(duì) K均值聚類算法的初始中心點(diǎn)的改進(jìn)算法，在這里由于篇幅的關(guān)系我們沒有一一列出。 (4)采用基于數(shù)據(jù)采樣的方法。而 K均值聚類算法采取隨機(jī)選取初始簇 中心點(diǎn)，這樣，初始中心點(diǎn)的不同或數(shù)據(jù)輸入順序的不同都有可能導(dǎo)致聚類結(jié)果的不穩(wěn)定性，且無法得到全局最優(yōu)解而陷入局部最優(yōu)解。在 K均值聚類算法中，每次對(duì)于簇中心的重新計(jì)算，都是通過對(duì)每一個(gè)類簇 中所有數(shù)據(jù)點(diǎn)求均值，這樣，當(dāng)數(shù)據(jù)集中存在噪音點(diǎn)數(shù)據(jù)時(shí)，均值點(diǎn)的計(jì)算將導(dǎo)致聚類中心 (即簇中心偏離數(shù)據(jù)真正密集的區(qū)域，而趨向噪音點(diǎn)數(shù)據(jù)歹這樣導(dǎo)致聚類結(jié)果的不準(zhǔn)確。從 K均值聚類算法的算法流程中可以看出， K