- 相關(guān)推薦
文本聚類開題報(bào)告范文
文檔聚類可以作為多文檔自動(dòng)文摘等自然語言處理應(yīng)用的預(yù)處理步驟,可以將重要新聞文本進(jìn)行聚類處理,是一種處理文本信息的重要手段。
基于K―Mean文本聚類的研究
摘 要 文本聚類能夠把相似性大的文本聚到同一類中。K-Means常用來聚類文本,但是由于聚類中心的選取對(duì)聚類結(jié)果有影響,導(dǎo)致聚類不穩(wěn)定,因此采用一種基于聚類中心的改進(jìn)算法分析文本,通過實(shí)驗(yàn),驗(yàn)證算法的有效性。
關(guān)鍵詞 文本聚類;k-means;相似性;度量準(zhǔn)則
中圖分類號(hào):TP391 文獻(xiàn)標(biāo)識(shí)碼:B
文章編號(hào):1671-489X(20XX)18-0050-03
Research for Text Clustering based on K-Mean//ZHANG Yue, LI Baoqing, HU Lingfang, MENG Li
Abstract Text clustering can make the text similarity large clustered into the same class, K-Means usually is used in text clustering, because of impacting on the cluster center, which results in the clustering instability. Therefore, this paper uses a text analysis of improved algorithm based on the clustering center, through the experiment, it verifies the effectiveness of the improved algorithm.
Key words text clustering; k-means; similarity; measure criterion
文本聚類是把不同的文本分別聚在不同的類別中,是文本挖掘的重要技術(shù),它是一種無監(jiān)督的學(xué)習(xí)技術(shù),每個(gè)類中包含的文本之間具有較大的相似性,不同類間的文本相似性比較小。文本聚類是數(shù)據(jù)挖掘的重要分支,它應(yīng)用神經(jīng)網(wǎng)絡(luò)、機(jī)器學(xué)習(xí)等技術(shù),能夠自動(dòng)地對(duì)不同文本進(jìn)行分類。
在文本聚類分析中,文本特征表示一般采用向量空間模型[1],這種模型能更好表現(xiàn)文本。在對(duì)文本聚類的研究中,Steinbach等人研究了基于劃分的方法和基于層次的方法在文本聚類中的適用程度[2-3],得出結(jié)論:采用K-Means算法進(jìn)行聚類,不僅聚類結(jié)果較好,而且適用于數(shù)據(jù)量比較大的聚類場合。在文章中根據(jù)研究者對(duì)K-Means的發(fā)現(xiàn),結(jié)合實(shí)際研究,采用一種基于K-Means的改進(jìn)算法來聚類。Dhillod等人對(duì)文本聚類進(jìn)行研究發(fā)現(xiàn),采用余弦夾角作為相似性度量比采用歐氏距離度量的結(jié)果好很多[4]。
1 文本聚類
文本聚類的方法很多,主要分為基于層次的方法、基于劃分的方法、基于密度的方法、基于模型的方法、基于網(wǎng)格的方法[5]。在這些聚類方法中,基于劃分的K-Mean是最常用也是很多改進(jìn)方法的基礎(chǔ),文章中采取的改進(jìn)方法也是基于K-Mean的。
K-Mean首先由MacQueent[6]提出。它能在大數(shù)據(jù)集中廣泛被使用,因?yàn)樗惴ㄐ瘦^高、算法執(zhí)行過程理解容易。當(dāng)前進(jìn)行的很多研究都是以K-Mean為基礎(chǔ)開展進(jìn)行的,它的計(jì)算復(fù)雜度低,具有與文檔數(shù)量成線性關(guān)系的特性,計(jì)算效率不僅高,而且伸縮性較強(qiáng),適應(yīng)大數(shù)據(jù)集的能力也很強(qiáng)。K-Mean以k為初始聚類數(shù),然后把n個(gè)文本分到k個(gè)聚類中,這樣類內(nèi)的文本具有較高的相似度,不同類間的相似度較小。
K-Mean具體的算法過程如下:
1)首先給定n個(gè)數(shù)據(jù)文本,從其中任選k個(gè)文本,這k個(gè)數(shù)據(jù)文本初始地代表了k個(gè)類的數(shù)據(jù)中心;
2)對(duì)剩余的每個(gè)文本計(jì)算其到每個(gè)中心的距離,并把它歸到最近的中心類中;
3)重新計(jì)算已經(jīng)得到的各個(gè)類的中心,通常計(jì)算中心的準(zhǔn)則函數(shù)采用平方誤差準(zhǔn)則,這個(gè)準(zhǔn)則能夠使生成的結(jié)果類盡可能地獨(dú)立和緊湊;
4)迭代執(zhí)行第二步和第三步的動(dòng)作直至新的中心與原中心相等或小于指定閾值,直到算法結(jié)束。
具體的算法流程如圖1所示。
2 改進(jìn)的聚類算法
雖然使用K-Mean算法進(jìn)行文本聚類時(shí),具有計(jì)算復(fù)雜度低,計(jì)算效率不僅高,而且伸縮性較強(qiáng),適應(yīng)大數(shù)據(jù)集的能力也很強(qiáng)的優(yōu)點(diǎn),但是實(shí)驗(yàn)發(fā)現(xiàn),不僅初始聚類中心的選取對(duì)聚類結(jié)果有影響,孤立點(diǎn)的存在對(duì)文本的相似性的判斷也有很大的影響,這就導(dǎo)致聚類判斷不穩(wěn)定;诖耍恼虏捎靡环N改進(jìn)的方法來進(jìn)行文本聚類,改進(jìn)關(guān)鍵點(diǎn)在于聚類中心的計(jì)算,用與原聚類中心相似的文本數(shù)據(jù)來計(jì)算平均值作為該聚類中心。
改進(jìn)的K-Means算法描述如下所示:
1)首先給定n個(gè)數(shù)據(jù)文本,從其中任選k個(gè)文本,這k個(gè)數(shù)據(jù)文本初始地代表了k個(gè)類的數(shù)據(jù)中心;
2)對(duì)剩余的每個(gè)文本計(jì)算其到每個(gè)中心的距離,并把它歸到最近的中心類中,記作means;
3)選擇類中與類中心大于等于(1+a)*means的文本集合{D1,D2,...,Dk},其中a[-0.31,0.31],重新計(jì)算新文本集中的類中心;
4)迭代執(zhí)行第2步和第3步的動(dòng)作直至新的中心與原中心相等或小于指定閾值,直到算法結(jié)束。
3 相似度計(jì)算
文本聚類中涉及文本的相似性計(jì)算,只有相似性大的文本才能聚到同一類中,因此,相似性的度量對(duì)文本的聚類很關(guān)鍵。在文本聚類中,相似度度量方式一般有曼哈頓距離、Cosine距離、歐式距離,其中Cosine距離更能體現(xiàn)文本的相似性。本文主要采用Cosine距離,當(dāng)兩個(gè)文本之間的文本相似度越大,它們之間的相關(guān)性越強(qiáng)。文本集用向量空間模型表示后,文本的相似度采用向量之間距離表示:
4 評(píng)價(jià)標(biāo)準(zhǔn)
文本聚類的有效性需要進(jìn)行驗(yàn)證,文章中主要采用F度量、平均純度來對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià)。
1)F度量。F度量把召回率和評(píng)價(jià)標(biāo)準(zhǔn)準(zhǔn)確率結(jié)合在一起。
準(zhǔn)確率:P(i,r)=nir/nr (2)
召回率:R(i,r)=nir/ni (3)
其中nir是類別r中包含類別i中的文本的個(gè)數(shù),nr是類別r中實(shí)際文本的數(shù)目,ni是原本類別i中應(yīng)有的文本數(shù),F(xiàn)值的計(jì)算公式:
(4)
由公式(4)最后得到評(píng)價(jià)函數(shù)為:
(5)
其中n為文本的總數(shù)。從公式看出F值越高,聚類效果越好。
2)平均純度。除了用F度量來評(píng)價(jià)聚類,文章中還使用平均純度來度量文本聚類質(zhì)量好壞[7]。設(shè)類ci的大小為ni,則該類的純度為:
(6)
其中nj表示類ci與第j類的交集大小,則平均純度公式為:
(7)
其中k為最終的聚類數(shù)目。一般說來純度越高聚類效果越好。
5 聚類實(shí)驗(yàn)結(jié)果分析
文章中采用的實(shí)驗(yàn)數(shù)據(jù)主要是搜狗語料庫。搜狗語料庫主要包括10種文本類別:軍事、招聘、IT、文化、健康、汽車、體育、旅游、財(cái)經(jīng)、教育。搜狗語料庫包含了每一類的文件夾,在文件夾中都是txt文本。為了驗(yàn)證改進(jìn)后的算法比原算法更有效,進(jìn)行了多次實(shí)驗(yàn),最終選取了其中一次實(shí)驗(yàn)結(jié)果為例子,對(duì)兩種算法的F度量和純度進(jìn)行比較,分別如表1和表2所示。
從表1可以看出,改進(jìn)聚類中心的K-Means算法在純度方面相對(duì)有一些提高;從表2可以看到F值提高明顯;從兩個(gè)表中的實(shí)驗(yàn)結(jié)果可以看到改進(jìn)的算法是有效的。
6 結(jié)論
基于文本的聚類分析能夠?qū)Υ罅康奈谋具M(jìn)行聚類,分析中采用的聚類算法的改進(jìn)能在很大程度上提高聚類的準(zhǔn)確性。實(shí)驗(yàn)證明達(dá)到設(shè)計(jì)的效果,同時(shí)也為后期的各種數(shù)據(jù)挖掘工作打下基礎(chǔ)。
參考文獻(xiàn)
[1]Salton G, Wong A, Yang C S. A vector space model for automatic indexing[J].Comm. ACM,1975,18(11):613-620.
[2]Steinbach M, KaryPis G, Kumar V. A comparison of document clustering techniques[C].Proceedings of KDD 2000 Workshop on Text Mining.2000:1-20.
[3]Ying Zhao, KaryPis G. Hierarchical Clustering Algorithms for Document Datasets[J].Proceedings of Data Mining and Knowledge Discovery,2005,10(2):141-168.
[4]Dhillon I S, Modha D S. Concept decompositions for large sparse text data using clustering[J].Machine Learning,2001,
42(1):143-175.
[5]邵峰晶,于忠清.數(shù)據(jù)挖掘原理與算法[M].北京:中國水利水電出版社,2003.
[6]MacQueen J. Some methods for classification and analysis
of multivariate observations[C]//Proceedings of 5th Berkeley
Symposium on Mathematics. Statistics and Science.1967:281-
296.
[7]Hammouda K, Kamel M. Collaborative document clu-stering[C]//2006 SIAM Conference on Data Mining (SDM06).
2006:453-463.
【文本聚類開題報(bào)告】相關(guān)文章:
化學(xué)類的開題報(bào)告03-18
建筑、工程類論文開題報(bào)告12-04
醫(yī)學(xué)類畢業(yè)開題報(bào)告11-30
建筑工程類論文開題報(bào)告02-28
醫(yī)學(xué)類開題報(bào)告的基本寫法11-21
醫(yī)學(xué)類開題報(bào)告基本寫法03-19
翻譯類英語論文開題報(bào)告11-19
基于網(wǎng)格的聚類方法研究03-13