【正文】 步驟 10:返回步驟 6，直至算法收斂或達到最大迭代次數(shù)為為止。按本文更新獲勝神經(jīng)元及其鄰域內(nèi)所有神經(jīng)元的連接權(quán)值，而鄰域外的神經(jīng)元的連接權(quán)值保持不變。對所有輸入樣本執(zhí)行步驟 7一步驟 10。至此，獲得了 K個中心。 圖 1 密集區(qū)域探測 步驟 2:按照這些密集 小區(qū)域的得分 (Score)為這個鏈表進行排序。選出的這 K個數(shù)據(jù)點應(yīng)該屬于不同的模式 類別為好，且這 K個數(shù)據(jù)點應(yīng)盡量靠近該類別的中心，這是我們初始化連接權(quán)時要達到的目標。進行特征抽取以后，一個單詞可能映射到輸入空間的多個維上 ，使這種確定初始連接權(quán)值的方法變得非常困難。 (3)從輸入空間中任意選取 K 個矢量對權(quán)值矢量進行初始化， K是輸出層神經(jīng)元結(jié)點的個數(shù)。一般情況下，輸入學(xué)習(xí)模式只處于整個模式空間的有限位置，如果對 連接權(quán)值隨機初始化，則在權(quán)值矢量會廣泛地分布于各個隨機方向上，一定會有大量的連接基于文本的聚類算法研究 23 權(quán)矢量與輸入模式方向差異很大，甚至方向相反。 已有的初始化連接權(quán)的方法 網(wǎng)絡(luò)的訓(xùn)練主要是通過對連接權(quán)的調(diào)整實現(xiàn)的，當(dāng)連接權(quán)不再變化或者變化很少時，網(wǎng)絡(luò)訓(xùn)練就完成了，達到了一個收斂的狀態(tài)。 初始化連接權(quán)值 初始權(quán)的設(shè)置，對于網(wǎng)絡(luò)的收斂狀況和收斂速度都是有影響的。鄰域半徑也隨著學(xué)習(xí)代數(shù)的增加而遞減，最后只有獲勝結(jié)點在學(xué)習(xí)。如果采用歐氏距離，按連接權(quán)向量與輸入樣本之間的距離值最小的神經(jīng)元是獲勝神經(jīng)元。鄰 域半徑 Nb。 (3)改進算法的基本流程 根據(jù)等類內(nèi)離差準則，希望所有分割區(qū)域的類內(nèi)離差相等，即要求所有的D(S、 )(i， 2，? K)相等。來表示。 以上算法對神經(jīng)元的獲勝策略進行了改進，在一定程度上解決了神經(jīng)元欠利用和過度利用 的問題，可以得到較好質(zhì)量的聚類結(jié)果。 (4)TASOM 該種 學(xué)習(xí)策略中，每個神經(jīng)元都有自己的學(xué)習(xí)率和鄰域函數(shù)，并且能 根據(jù)學(xué)習(xí)時間自動地調(diào)整學(xué)習(xí)率和鄰域的大小。近 年來，有些學(xué)者針對神經(jīng)元欠利用和過度利用的問題，提出了許多改進的學(xué)習(xí)策略，代表性的有 SOMCV、 SOMC、 ESOM、 TASOM、 DSOM。 改進的 SOM 聚類方法 已有的學(xué)習(xí)策略改進 就具體的學(xué)習(xí)策略來說，自組織特征映射神經(jīng)網(wǎng)絡(luò)采用的是“勝者全得”的競爭學(xué)習(xí)算法，就是在競爭學(xué)習(xí)時網(wǎng)絡(luò)的各輸出神經(jīng)元相互競爭，最后只有一個最強神經(jīng)元獲勝 。相反有些神經(jīng)元因為獲勝次數(shù)過多，出現(xiàn)神經(jīng)元過度利用的問題，也會影響網(wǎng)絡(luò)的學(xué)習(xí)效果。輸出層結(jié)點的初始拓撲結(jié)構(gòu)與輸入模式在在原始數(shù)據(jù)空間中的拓撲結(jié)構(gòu)一致時，網(wǎng)絡(luò)才會達到好的學(xué)習(xí)效果。 ③ 具有可視化的優(yōu)點 。調(diào)整學(xué)習(xí)率和鄰域半徑，為了保證算法的收斂，學(xué)習(xí)率的取值一般在 O到 1之間，且隨著學(xué)習(xí)代數(shù)的增加而遞減 。鄰域半徑 Nbo. 步驟 2:取樣對所有輸入樣本執(zhí)行步驟 3 一步驟 6. 步驟 3:確定獲勝神經(jīng)元。一般可以這樣說， SOM網(wǎng)絡(luò)的權(quán)矢量收斂到所代表的輸入矢量的平均值，它反映了輸入數(shù)據(jù)的統(tǒng)計特性。遺憾的是，網(wǎng)絡(luò)在高維映射到低維時會發(fā)生畸變，而且壓縮比越大，畸變越大 。 SOM 網(wǎng)絡(luò)是輸入樣本通過競爭學(xué)習(xí)后，功能相同的輸入靠得比較近，不同的分得比較開，以此將一些無規(guī)則的輸入自動排開，在連接權(quán)的調(diào)整過程中，使權(quán)的分布與輸入域可逐步縮小，使區(qū)域的劃分越來越明顯。它是由多個細胞聚合而成的，在接受外界刺激后，它們會自動形成。除了以上列出的初始中心點的選取方法以外，還有很多對 K均值聚類算法的初始中心點的改進算法，在這里由于篇幅的關(guān)系我們沒有一一列出。 (6)聚類問題解出 k 類問題的中心。 (4)采用基于數(shù)據(jù)采樣的方法。 基于 K均值聚類算法的改進，國內(nèi)外的專家學(xué)者做了大量的研究工作，主要 基于文本的聚類算法研究 16 總結(jié)如下。而 K均值聚類算法采取隨機選取初始簇 中心點，這樣，初始中心點的不同或數(shù)據(jù)輸入順序的不同都有可能導(dǎo)致聚類結(jié)果的不穩(wěn)定性，且無法得到全局最優(yōu)解而陷入局部最優(yōu)解。 (5)K均值聚類算法不適用于大數(shù)據(jù)量的聚類問題。在 K均值聚類算法中，每次對于簇中心的重新計算，都是通過對每一個類簇 中所有數(shù)據(jù)點求均值，這樣，當(dāng)數(shù)據(jù)集中存在噪音點數(shù)據(jù)時，均值點的計算將導(dǎo)致聚類中心 (即簇中心偏離數(shù)據(jù)真正密集的區(qū)域，而趨向噪音點數(shù)據(jù)歹這樣導(dǎo)致聚類結(jié)果的不準確。 K均值聚類算法隨機的選取 K個初始簇中心點，并針對這 K個簇中心點進行迭代運算，即重新分配數(shù)據(jù)點和重新計算簇中心的運算，直到所有的數(shù)據(jù)點位置不再變化或聚類誤差準則函數(shù)不再變化。從 K均值聚類算法的算法流程中可以看出， K 值作為一個需要預(yù)先確定的參數(shù)，在已知的前提下才能執(zhí)行 K均值聚類算法，而在實際應(yīng)用中，需要聚類的數(shù)據(jù)究竟要分成多少個類別，往往不是被用戶所知的。然而這些技術(shù)并沒有得到廣泛認可，在許多實際應(yīng)用中還是反復(fù)利用 K均值聚類算法來解決問題。 K均值算法的優(yōu)缺點分析 K均值算法是一種基于劃分的聚類算法，它通過不斷的迭代過程來進行聚類，當(dāng)算法收斂到一個結(jié)束條件時就終止迭代過程，輸出聚類結(jié)果。具體流程如下 : [Stepl][初始化 l隨機指定 k 個聚類中心 (ml， m2， ?? mk)。 K均值聚類算法的算法流程 原始的 K均 值聚類算法 : 輸入 :數(shù)據(jù)集 x={x1， x2， ?? xn}，聚類數(shù)目 k。該算法首先隨機選取 k個數(shù)據(jù)點作為 n個 簇的初始簇中心，集合中每個數(shù)據(jù)點被劃分到與其距離最近的簇中心所在的類簇之中，形成了 k 個聚類的初始分布。 本章小結(jié) 本章主要介紹了影響文本聚類結(jié)果的三方面主要因素：文本表示模型、相似度計算方法及聚類算法。如基于 SOM 的文檔聚類方法在數(shù)字圖書館等領(lǐng)域得到了較好的應(yīng)用?；谀Ｐ偷乃惴ㄖ饕袃深?，分別為統(tǒng)計學(xué)方法和神經(jīng)網(wǎng)絡(luò)方法。 基于模型的方法 基于模型的算法（ ModelBased Clustering Method）試圖優(yōu)化給定的數(shù)據(jù)和某些數(shù)學(xué)模型之間的適應(yīng)性。 CLIQUE（ Clustering in Quest）是一種將基于密度的方法與基于網(wǎng)格的方法相結(jié) 合的算法，能有效處理大型數(shù)據(jù)庫的高維數(shù)據(jù)。代表算法有統(tǒng)計信息網(wǎng)格法 STING 算法、聚類高維空間法 CLIQUE 算法、基于小波變換的聚類法 WAVECLUSTER 算法。 基于網(wǎng)格的方法 基于網(wǎng)格的算法（ GridBased Clustering Method）把對象空間量化為有限數(shù)目的單元，形成了一個網(wǎng)絡(luò)結(jié)構(gòu)。 基于密度的聚類算法在當(dāng)前的文獻中較少被用于文本聚類中。為此，提出了基于密度的聚類算法（ DensityBased Clustering Method），其主要思想是：只要鄰近區(qū)域的對象或數(shù)據(jù)點的數(shù)目超過某個閾值，就繼續(xù)聚類。使用該算法可以得到較好的聚類結(jié)果，而且該方法無需用戶輸入?yún)?shù)；但是層次聚類算法的時間復(fù)雜度比較高，達到了 O(n2)，對于大規(guī)模的文本集合，有其不適用性。 基于層次的方法 基于層次的聚類算法（ Hierarchical Method）又叫“分級聚類算法”或“樹聚類”，它通過分解給定的數(shù)據(jù)對象集來創(chuàng)建一個層次。為了對大規(guī)模的數(shù)據(jù)集進行聚類，以及處理復(fù)雜形狀的聚類，各類改進的劃分算法逐漸增多。方法將數(shù)據(jù)集合分成若干個子集，它根據(jù)設(shè)定的劃分數(shù)目 k 選出 k 個初始聚類中心，得到一個初始劃分，然后采用迭代重定位技術(shù)，反復(fù)在 k 個簇之間重新計算每個簇的 聚類中心，并重新分配每個簇中的對象，以改進劃分的質(zhì)量。為了衡量文本集合之間的相似度，常見的方法有：最小距離、最大距離、平均距離、質(zhì)心法、離差平方和等。 在文本相似度計算中，我們也可以用兩個文本之間的距離來度量文本之間 的相似程度。如果兩文本之間相似度為 1，則說明這兩個文本對象完全相同；反之，則說明兩文本沒有相似之處。一個文本聚類分析過程的質(zhì)量取決于對度量標準的選擇。每個文檔可以用文檔中的詞來表示，這些詞及其對應(yīng)的權(quán)重構(gòu)成一個向量。 向量空間模型將文檔表示成一個向量，向量的每一維表示一個特征，這個特征可以是一個字、一個詞、一個 ngram或某個復(fù)雜的結(jié)構(gòu)。經(jīng)典布爾模型中查詢與文檔的相關(guān)性只能是 0或者 1，滿足查詢query 中的所有邏輯表達式的文檔被判定相關(guān)，不滿足的被判定為不相關(guān)。關(guān)于特征定義與篩選可以參考自然語言處理領(lǐng)域中的相關(guān)研究，這里不詳細介紹。特征的權(quán)重定義及特征結(jié)構(gòu)上的相似度度量可以選取不同的模型，如向量空間模型、概率模型、語言模型等。在經(jīng)典的研究中通常利用特征 (Term，包括字、詞、詞組等 )的詞頻信息建立文本向量，通過文本向量與文本向量之間 的相似度來進行聚類分析。不同的算法對參數(shù)的敏感性不同，但是基本上參數(shù)的好壞對結(jié)果的影響都比較顯著。聚類分析算法可以從不同的角度進行比較，比如是否產(chǎn)生層次聚類結(jié)構(gòu)、是否需要參數(shù)、是否能夠產(chǎn)生模糊聚類、能否識別出不規(guī)則形狀的簇等等。聚類流程三個步驟的實際處理內(nèi)容為： (1)文本聚類分析首先將文本表示成機器可計算的形式。因此，需要對文本聚類分析結(jié)果的質(zhì)量進行評價，利用這種評價機制來指導(dǎo)算法設(shè)計、算法選擇、算法效能分析、參數(shù) 優(yōu)化等。近年來，文檔聚類算法還在文檔分析處理領(lǐng)域中一個新的應(yīng)用方向話題檢測與跟蹤中得到了進一步研究與應(yīng)用。關(guān)于文本數(shù)據(jù)上的聚類分析研究，較早的綜合性介紹可以追溯到 Rijsbergen 在 IR 領(lǐng)域的經(jīng)典書籍《 InformationRetrieval》 中提到的利用文本聚類分析技術(shù)來提高信息檢索系統(tǒng)的準確率，但近年來此類研究已不多見。 隨著人們對 聚 類問題更加深入地了解和重視，國內(nèi)外大量學(xué)者不斷投身到該項目研究，聚類主要工作集中在尋找針對大型數(shù)據(jù)庫的聚類方法和世界的聚類分析方法上，使得各種成果不斷涌現(xiàn)，各個領(lǐng)域的聚類分析算法層出不窮。 聚類作為一種只是發(fā)現(xiàn)的重要方法，是數(shù)據(jù)挖掘中一項重要的研究課題，它廣泛地與中文信息處理技術(shù)相結(jié)合，應(yīng)用于網(wǎng)絡(luò)信息處理中以滿足用戶快捷地從互聯(lián)網(wǎng)獲得自己需要的信息資源，文本聚類則是聚類問題在文本挖掘中的有效應(yīng)用，是文本挖掘的重要內(nèi)容之一。那么 ，如何從中獲取特定內(nèi)容的信息和知識成為擺在人們面前的一道難題。 涉密論文按學(xué)校規(guī)定處理。對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方 式標明。對本研究提供過幫助和做出過貢獻的個人或集體，均已在文中作了明確的說明并表示了謝意。本文主 要 研究的聚類主要方法是 k均值和 SOM算法，介紹 了兩種算法的基本思想和實現(xiàn)步驟，并分析兩種算法的聚類效果。文本聚類是聚類問題在文本挖掘中的有效應(yīng)用，它根據(jù)文本數(shù)據(jù)的不同特征，按照文本間的相似性，將其分為不同的文本簇。其目的是要使同一類別的文本間的相似度盡可能大，而不同類別的文本間的相似度盡可能的小。同時介紹了兩種算法的改進算法。 作 者 簽 名： 日 期： 指導(dǎo)教師簽名： 日 期： 使用授權(quán)說明 本人完全了解 大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計（論文）的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計（論文）的印刷本和電子版本；學(xué)校有權(quán)保 存畢業(yè)設(shè)計（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)?？梢圆捎糜坝?、縮印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)?？梢怨颊撐牡牟糠只蛉績?nèi)容。本人完全意識到本聲明的法律后果由本人承擔(dān)。 作者簽名： 日期： 年 月 日 導(dǎo)師簽名： 日期： 年 月 日 指導(dǎo)教師評閱書 指導(dǎo)教師評價： 一、撰寫（設(shè)計）過程 學(xué)生在論文（設(shè)計）過程中的治學(xué)態(tài)度、工作精神 □ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格 學(xué)生掌握專業(yè)知識、技能的扎實程度 □ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格 學(xué)生綜合運用所學(xué)知識和專業(yè)技能分析和解決問題的能力 □ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格 研究方法 的科學(xué)性；技術(shù)線路的可行性；設(shè)計方案的合理性 □ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格 完成畢業(yè)論文（設(shè)計）期間的出勤情況 □ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格 二、論文（設(shè)計）質(zhì)量 論文（設(shè)計）的整體結(jié)構(gòu)是否符合撰寫規(guī)范？ □ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格 是否完成指定的論文（設(shè)計）任務(wù)（包括裝訂及附件）？ □ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格 三、論文（設(shè)計）水平 論文（設(shè)計）的理論意義或?qū)鉀Q實際問題的指導(dǎo)意義 □ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格 論文的觀念是否有新意？設(shè)計是否有創(chuàng)意？ □ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格 論文（設(shè)計說明書）所體現(xiàn)的整體水平 □ 優(yōu)