發(fā)布時(shí)間：2017-10-11 21:33

  本文關(guān)鍵詞：改進(jìn)的支持向量聚類算法及其應(yīng)用研究

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

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

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

【參考文獻(xiàn)】

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

1 紀(jì)秋穎;林健;;基于核方法的聚類算法及其應(yīng)用[J];北京航空航天大學(xué)學(xué)報(bào);2006年06期

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

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

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

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

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

7 王英奇;;支持向量聚類算法的研究與改進(jìn)[J];湛江師范學(xué)院學(xué)報(bào);2008年06期

8 劉務(wù)華;羅鐵堅(jiān);王文杰;;文本聚類算法的質(zhì)量評(píng)價(jià)[J];中國(guó)科學(xué)院研究生院學(xué)報(bào);2006年05期

9 王書舟;傘冶;;支持向量機(jī)的訓(xùn)練算法綜述[J];智能系統(tǒng)學(xué)報(bào);2008年06期

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

1 周昭濤;文本聚類分析效果評(píng)價(jià)及文本表示研究[D];中國(guó)科學(xué)院研究生院（計(jì)算技術(shù)研究所）;2005年

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

，

本文編號(hào)：1014877