本文關鍵詞：改進的支持向量聚類算法及其應用研究

  更多相關文章： 支持向量聚類 最小閉包球 鄰接矩陣 文本聚類 主成分分析

【摘要】： 21世紀是知識經(jīng)濟時代,知識發(fā)現(xiàn)已受到日益廣泛的關注。聚類分析是知識發(fā)現(xiàn)中一個極為重要的分支,幾乎可用于社會生活的各個方面。而核聚類算法由于具有許多經(jīng)典聚類算法無法比擬的優(yōu)勢,逐漸成為聚類算法研究領域的一大熱點。本文主要研究的支持向量聚類(Support Vector Clustering, SVC)算法就是一種典型的核聚類算法。 與其他聚類算法相比,SVC算法具有兩大顯著優(yōu)勢：一是不需要事先確定簇的數(shù)目,且能產(chǎn)生任意形狀的簇邊界；二是能分析噪聲數(shù)據(jù)點且能分離相互交錯的簇。SVC算法分為兩個階段：SVC訓練階段和聚類分配階段。這兩個階段分別需要計算Lagrange乘子和鄰接矩陣,而這兩個計算問題可能導致算法具有較高的時間復雜性。正是針對這兩個問題,本文提出一種改進的SVC (Improved SVC, ISVC)算法。 在SVC訓練階段,提出一種基于熵的最小閉包球(Minimal Enclosing Sphere, MES)算法。可以證明,這種方法能有效減少計算Lagrange乘子的時間。在聚類分配階段,首先利用核矩陣提供的信息對數(shù)據(jù)點進行初始分類,然后用計算初始類的中心點集上的鄰接矩陣代替經(jīng)典SVC算法中計算整個數(shù)據(jù)集上的鄰接矩陣。這種方法能有效減少鄰接矩陣的規(guī)模,從而提高鄰接矩陣的計算效率。因此,ISVC算法對經(jīng)典SVC算法的兩個瓶頸問題都進行了改進。數(shù)值實驗表明,ISVC算法不僅顯著改善了經(jīng)典SVC算法的時間性能,在聚類精度上也有一定程度的提高。 之后將ISVC算法應用于文本聚類。選擇復旦大學整理的小規(guī)模語料庫中的100篇文本進行實驗。首先對實驗文本集進行預處理,依次為：切分文本集；利用向量空間模型(Vector Space Model, VSM)將切分后的文本集表示成矩陣形式；利用主成分分析(Principal Component Analysis, PCA)技術對文本集進行降維。然后利用ISVC算法將預處理后的文本數(shù)據(jù)聚類,并對聚類結果進行描述。最后對比了ISVC、k-均值和層次聚類中的凝聚算法(DHCA)三種算法在實驗文本集上的聚類結果,發(fā)現(xiàn)ISVC算法具有較高的精度。這說明本文的ISVC算法在一定程度上提高了文本聚類的效率。
【關鍵詞】：支持向量聚類 最小閉包球 鄰接矩陣 文本聚類 主成分分析
【學位授予單位】：大連理工大學
【學位級別】：碩士
【學位授予年份】：2010
【分類號】：F062.3;F224
【目錄】：

• 摘要4-5
• Abstract5-9
• 1 緒論9-18
• 1.1 問題提出9-10
• 1.2 國內(nèi)外研究現(xiàn)狀10-16
• 1.2.1 核聚類算法的國內(nèi)外研究現(xiàn)狀10-15
• 1.2.2 文本聚類算法的國內(nèi)外研究現(xiàn)狀15-16
• 1.3 研究內(nèi)容及思路16
• 1.4 內(nèi)容安排16-18
• 2 支持向量機簡介18-26
• 2.1 支持向量分類和回歸簡介18-22
• 2.1.1 結構風險最小化原則18-19
• 2.1.2 支持向量分類簡介19-21
• 2.1.3 支持向量回歸簡介21-22
• 2.2 支持向量聚類算法簡介22-26
• 2.2.1 SVC訓練23-24
• 2.2.2 聚類分配24
• 2.2.3 SVC算法評價24-26
• 3 ISVC算法及數(shù)值實驗26-38
• 3.1 ISVC算法26-34
• 3.1.1 SVC訓練26-29
• 3.1.2 聚類分配29-31
• 3.1.3 ISVC算法的具體步驟31-32
• 3.1.4 ISVC算法的復雜性32-34
• 3.2 數(shù)值實驗34-38
• 3.2.1 ISVC算法與經(jīng)典SVC算法的比較34-37
• 3.2.2 ISVC算法與經(jīng)典聚類算法的比較37-38
• 4 ISVC算法應用于文本聚類38-49
• 4.1 實驗數(shù)據(jù)與環(huán)境38
• 4.2 實驗設計38-48
• 4.2.1 文本預處理39-45
• 4.2.2 實驗結果描述及評價45-48
• 4.3 與經(jīng)典文本聚類算法的比較48-49
• 結論49-51
• 參考文獻51-54
• 攻讀碩士學位期間發(fā)表學術論文情況54
• 攻讀碩士學位期間參加科研項目情況54-55
• 致謝55-57

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前9條

1 紀秋穎;林健;;基于核方法的聚類算法及其應用[J];北京航空航天大學學報;2006年06期

2 呂佳;;核聚類算法及其在模式識別中的應用[J];重慶師范大學學報(自然科學版);2006年01期

3 郭崇慧,陸玉昌;預測型數(shù)據(jù)挖掘中的優(yōu)化方法[J];工程數(shù)學學報;2005年01期

4 張勝;;數(shù)據(jù)挖掘中聚類算法的研究[J];軟件導刊;2008年06期

5 孫德山;李海清;;基于線性規(guī)劃的支持向量聚類算法[J];計算機工程與設計;2010年06期

6 伍忠東,高新波,謝維信;基于核方法的模糊聚類算法[J];西安電子科技大學學報;2004年04期

7 王英奇;;支持向量聚類算法的研究與改進[J];湛江師范學院學報;2008年06期

8 劉務華;羅鐵堅;王文杰;;文本聚類算法的質量評價[J];中國科學院研究生院學報;2006年05期

9 王書舟;傘冶;;支持向量機的訓練算法綜述[J];智能系統(tǒng)學報;2008年06期

中國碩士學位論文全文數(shù)據(jù)庫 前2條

1 周昭濤;文本聚類分析效果評價及文本表示研究[D];中國科學院研究生院（計算技術研究所）;2005年

2 姚清耘;基于向量空間模型的中文文本聚類方法的研究[D];上海交通大學;2008年

，

本文編號：1014877