基于成對(duì)約束的半監(jiān)督聚類算法研究及其并行化實(shí)現(xiàn)

《基于成對(duì)約束的半監(jiān)督聚類算法研究及其并行化實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、國內(nèi)圖書分類號(hào)：TP301.6密級(jí)：公開國際圖書分類號(hào)：681.14西南交通大學(xué)研究生學(xué)位論文基于成對(duì)約束的半監(jiān)督聚類算法研究及其并行化實(shí)現(xiàn)年級(jí)二〇一〇級(jí)姓名林超申請(qǐng)學(xué)位級(jí)別碩士專業(yè)計(jì)算機(jī)應(yīng)用技術(shù)指導(dǎo)老師楊燕教授二零一三年五月ClassifiedIndex:TP301.6U.D.C:681.14SouthwestJiaotongUniversityMasterDegreeThesisSEMI-SUPERVISEDCLUSTERINGALGORITHMBASEDONPAIRWISECONSTRAINTSA

2、NDITSPARALLELIMPLEMENTATIONGrade:2010Candidate:LinChaoAcademicDegreeAppliedfor:MasterSpeciality:ComputerApplicationSupervisor:Prof.YangYanMay,2013西南交通大學(xué)學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)西南交通大學(xué)可以將本論文的全部或部分

3、內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)印手段保存和匯編本學(xué)位論文。本學(xué)位論文屬于1．保密□，在年解密后適用本授權(quán)書；2．不保密□，使用本授權(quán)書。（請(qǐng)?jiān)谝陨戏娇騼?nèi)打“√”）學(xué)位論文作者簽名：指導(dǎo)老師簽名：日期：日期：西南交通大學(xué)碩士學(xué)位論文主要工作（貢獻(xiàn)）聲明本人在學(xué)位論文中所做的主要工作或貢獻(xiàn)如下：(1)針對(duì)半監(jiān)督聚類算法Cop-Kmeans中的約束違反問題，提出了一種全新的改進(jìn)方案。該方案不僅能夠使程序在迭代過程中完全避免約束違反，在算法運(yùn)行時(shí)間效率上也明顯優(yōu)于傳統(tǒng)的改進(jìn)方案。(2)

4、針對(duì)成對(duì)約束自身特征在半監(jiān)督聚類算法中給聚類結(jié)果可能造成的不良影響，進(jìn)一步提出了相應(yīng)的改進(jìn)方案。即分別為Must-Link和Cannot-Link約束組制定了新的分配規(guī)則，能夠最大限度的削弱成對(duì)約束的這種不良影響，進(jìn)而能夠在一定程度上提高聚類結(jié)果的精度。(3)利用MapReduce計(jì)算模型對(duì)改進(jìn)的半監(jiān)督聚類算法進(jìn)行并行化實(shí)現(xiàn)，并在Hadoop搭建的并行處理平臺(tái)上處理大數(shù)據(jù)集，大大提高了聚類效率。本人鄭重聲明：所呈交的學(xué)位論文，是在導(dǎo)師指導(dǎo)下獨(dú)立進(jìn)行研究工作所得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不

5、包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫過的研究成果。對(duì)本文的研究做出貢獻(xiàn)的個(gè)人和集體，均已在文中作了明確說明。本人完全了解違反上述聲明所引起的一切法律責(zé)任將由本人承擔(dān)。學(xué)位論文作者簽名：日期：西南交通大學(xué)碩士研究生學(xué)位論文第III頁摘要作為數(shù)據(jù)挖掘領(lǐng)域中的一種重要方法，聚類分析能夠發(fā)現(xiàn)數(shù)據(jù)對(duì)象自然的分布結(jié)構(gòu)。它根據(jù)數(shù)據(jù)對(duì)象之間的相似性，把數(shù)據(jù)對(duì)象分割成簇，并保證同一簇內(nèi)中數(shù)據(jù)的相似性盡可能大，而不同簇間數(shù)據(jù)的相似性盡可能小。從機(jī)器學(xué)習(xí)的角度來看，聚類分析是一種無監(jiān)督的學(xué)習(xí)方法，它按照一定的優(yōu)化準(zhǔn)則對(duì)數(shù)據(jù)進(jìn)

6、行分割，對(duì)數(shù)據(jù)的分析不需要知道其相關(guān)的背景知識(shí)。但是，現(xiàn)實(shí)生活中我們對(duì)數(shù)據(jù)的信息并不是一無所知，并且我們發(fā)現(xiàn)通過這些少量的已知信息能夠找到數(shù)據(jù)對(duì)象標(biāo)識(shí)或相互之間的約束信息。半監(jiān)督聚類就是在傳統(tǒng)的無監(jiān)督聚類算法中引入先驗(yàn)知識(shí)來指導(dǎo)聚類過程，提高聚類結(jié)果精度。本文選擇引入成對(duì)約束作為先驗(yàn)知識(shí)來協(xié)助指導(dǎo)聚類過程，分別建立了Must-Link和Cannot-Link約束組，用以描述兩個(gè)樣本數(shù)據(jù)間的關(guān)系。其中，Must-Link代表兩個(gè)樣本數(shù)據(jù)必須被分配到同一劃分，而Cannot-Link則代表兩個(gè)樣本數(shù)據(jù)必須被

7、分配到不同的劃分。詳細(xì)介紹了基于成對(duì)約束的半監(jiān)督聚類算法Cop-Kmeans，對(duì)算法比較常見的約束違反的問題，提出了全新的改進(jìn)方法，在解決約束違反的同時(shí)，算法的運(yùn)行時(shí)間效率也優(yōu)于傳統(tǒng)的改進(jìn)方案。此外，針對(duì)成對(duì)約束自身特征可能給聚類性能帶來的不良影響，進(jìn)一步提出了相應(yīng)的改進(jìn)方案，能夠最大限度的削弱這種不良影響，從而能夠在一定程度上改善聚類結(jié)果精度?？紤]到當(dāng)聚類對(duì)象是一個(gè)大數(shù)據(jù)集或者高維數(shù)據(jù)類型時(shí)，傳統(tǒng)的單機(jī)串行聚類算法無論是在內(nèi)存或者運(yùn)算能力都無法滿足實(shí)際需求。本文選擇運(yùn)用“云計(jì)算”思想，采用并行處理方式

8、處理大規(guī)模的數(shù)據(jù)集。我們利用MapReduce計(jì)算模型對(duì)改進(jìn)的半監(jiān)督聚類算法進(jìn)行并行化實(shí)現(xiàn)，并在Hadoop搭建的并行處理平臺(tái)上處理大數(shù)據(jù)集。實(shí)驗(yàn)結(jié)果表明，采用并行計(jì)算方式能夠顯著提高聚類效率。關(guān)鍵詞：半監(jiān)督聚類；成對(duì)約束；并行計(jì)算；MapReduce西南交通大學(xué)碩士研究生學(xué)位論文第III頁AbstractAsanimportantmethodinthefieldofdatamining,clusteranalysisisabletofin