【摘要】：聚類分析作為機(jī)器學(xué)習(xí)領(lǐng)域的重要研究方向之一,吸引了很多學(xué)者的關(guān)注。在聚類分析中,距離度量是影響聚類算法精度的重要因素。在傳統(tǒng)的聚類算法中,一般使用歐氏距離來度量樣本之間的相似性然后根據(jù)相似性進(jìn)行下一步簇的劃分。雖然歐氏距離容易理解和實(shí)現(xiàn),但是它假設(shè)輸入空間是各向同性的。然而各向同性的假設(shè)與現(xiàn)實(shí)社會(huì)的很多實(shí)際應(yīng)用是不吻合的,這樣歐氏距離度量便不能真實(shí)反映輸入樣本之間的相似性關(guān)系,在實(shí)際應(yīng)用中的表現(xiàn)也會(huì)受到很大限制。此外,歐氏距離在計(jì)算兩個(gè)數(shù)據(jù)樣本之間的相似性時(shí),僅僅考慮兩個(gè)樣本之間的數(shù)據(jù)信息,而忽略了所有其他樣本的信息,這就造成了數(shù)據(jù)信息的浪費(fèi)。針對(duì)這些不足,本文提出了兩種可以挖掘數(shù)據(jù)樣本之間拓?fù)浣Y(jié)構(gòu)關(guān)系的新型距離度量。具體的新型距離度量為有效距離度量和融合歐氏距離與Kendall Tau距離的距離度量。我們的新型距離度量不要求輸入空間是各向同性的,也就是我們定義的兩個(gè)樣本之間的距離可以是不對(duì)等的。本文的主要工作和創(chuàng)新點(diǎn)如下:第一,提出一種基于稀疏重構(gòu)的有效距離度量。稀疏重構(gòu)可以構(gòu)建高效的數(shù)據(jù)表示模式,通過L1范數(shù)的約束,從多個(gè)樣本中選擇相似性高的樣本用于重構(gòu)目標(biāo)樣本。本文提出的基于稀疏重構(gòu)的有效距離度量,在計(jì)算樣本集中兩個(gè)樣本之間的距離時(shí),首先利用稀疏重構(gòu)的方法得到目標(biāo)樣本以及其他所有相關(guān)樣本的相似性關(guān)系,然后通過有效距離定義計(jì)算得到樣本之間的距離。有效距離不僅考慮兩個(gè)樣本之間的關(guān)系,同時(shí)考慮目標(biāo)樣本與樣本集中其他樣本之間的拓?fù)潢P(guān)系,具有全局性�；谟行Ь嚯x度量,我們對(duì)經(jīng)典的聚類算法,如:K均值聚類算法、K中心點(diǎn)聚類算法、模糊C均值聚類算法和譜聚類算法等進(jìn)行了改進(jìn)。最后在多個(gè)UCI數(shù)據(jù)集上,驗(yàn)證了改進(jìn)后的算法的有效性。第二,提出一種新的融合歐氏距離與Kendall Tau距離的譜聚類算法。首先,我們度量樣本之間的直接歐氏距離關(guān)系以及Kendall Tau結(jié)構(gòu)拓?fù)潢P(guān)系,然后我們使用非線性的迭代擴(kuò)散融合方法融合基于歐氏距離的相似性矩陣與基于Kendall Tau距離的相似性矩陣,最后我們將得到的新的融合相似性矩陣應(yīng)用到譜聚類算法中。我們?cè)诙鄠�(gè)UCI數(shù)據(jù)集,驗(yàn)證了基于融合歐氏距離與Kendall Tau距離的譜聚類算法的有效性。實(shí)驗(yàn)結(jié)果表明,我們提出的有效距離度量和融合歐氏距離與Kendall Tau距離的距離度量能夠提高聚類算法的聚類精度。
【圖文】：

我們提出了通過概率形式反映樣本之間全局性結(jié)構(gòu)信息的有效距離度量。我們提出逡逑的有效距離依賴于數(shù)據(jù)樣本構(gòu)成的雙向網(wǎng)絡(luò)，利用概率思想，考慮了周圍其他樣本對(duì)目標(biāo)樣本逡逑的影響，從全局角度考慮了樣本之間的動(dòng)態(tài)結(jié)構(gòu)關(guān)系。詳細(xì)的有效距離展示圖如圖３．１所示。逡逑假設(shè)有Ａ、Ｂ、Ｃ、Ｄ四個(gè)數(shù)據(jù)樣本點(diǎn)。圖３．１（ａ）是四個(gè)樣本點(diǎn)之間的有向關(guān)系圖，圖中各逡逑邊所占的權(quán)重值相等。圖３．１（ｂ）中，我們通過計(jì)算概率值Ｐ丨ｎ｜ｍ）表示有向圖中兩兩樣本點(diǎn)中逡逑間的邊在與所有與它相連的邊集合中所占的比重，為了更加直觀地展示圖中邊的權(quán)重情況，我逡逑們將權(quán)重大的邊，用比較粗的寬度邊也表不。概率值表不從ｍ點(diǎn)出發(fā)到達(dá)ｎ點(diǎn)的直接逡逑路徑數(shù)與所有從ｍ點(diǎn)出發(fā)的直接路徑數(shù)的比值。例如，概率值Ｐ丨｜，表示從Ａ點(diǎn)到逡逑Ｂ點(diǎn)的概率是｜，其中４表示從４點(diǎn)出發(fā)的路徑總共有４條，，１表示其中有１條路徑可以直接逡逑到達(dá)Ｂ點(diǎn)。另外，從圖３．１（ｂ）中容易看出，從Ｂ點(diǎn)出發(fā)到達(dá)Ｄ點(diǎn)的概率（如，＝邋１逡逑）明顯大于從Ｃ點(diǎn)出發(fā)到達(dá)Ｄ點(diǎn)的概率（如

邐６３．１３邐７１．２３邐８４．９０邐７３．５０邐７６．６４逡逑一個(gè)箱形對(duì)應(yīng)的橫線從下到上依次為：下邊緣線、下四分位線、中位數(shù)線、上四分位線以及上逡逑邊緣線。從圖３．２可以明顯看出，所有的基于有效距離的算法的各條線都比傳統(tǒng)的聚類算法的逡逑對(duì)應(yīng)線要高，表明新的算法明顯優(yōu)于傳統(tǒng)算法。逡逑８０－邐＝ｆ＝邐邐逡逑？邋一逡逑曹邋？邋一＾ｎ邐ｔ邐逡逑ｕ邐——逡逑＜邋６０－￣—邐逡逑｜邋ｉ邐＾邐＾邐＾逡逑？邋５０邋—邋—邐邐邐邐邐？邐■—逡逑°邐ｕ邋－邋ｕ邐ｕ逡逑圳４邐＇ｉ１邐＾邐ｙ邐Ｔ逡逑３０ｌ邐１邐＾邐１邐１邐＊邐—＊—＝丨逡逑Ｋ－ｍｅａｎｓ邐ＥＫ－ｍｅａｎｓ邐Ｋ－ｒａｅｄｏｉｄｓ邐ＥＫ－ｍｅｄｏｉｄｓ邐ＦＣＭ邐ＥＦＣＭ逡逑Ｃｌｕｓｔｅｒｉｎｇ邋Ａｌｇｏｒｉｔｈｍｓ逡逑圖３．２邐聚類算法結(jié)果對(duì)比圖逡逑正如前面第二章聚類算法的評(píng)估標(biāo)準(zhǔn)章節(jié)所介紹的，聚類算法的性能度量不僅能用聚類逡逑精度：來評(píng)估還可以使用Ｊａｃｃａｒｄ系數(shù)（ＪＣ）、ＦＭ指數(shù)（ＦＭＩ）和Ｒａｎｄ指數(shù)（ＲＩ）等指標(biāo)描逡逑述，這些性能度量的結(jié)果值均在［０，１］區(qū)間內(nèi)，并且值越大越好。所以我們?cè)趦蓚�(gè)數(shù)據(jù)集上就逡逑上述性能指標(biāo)進(jìn)行計(jì)算。圖３．３中，我們?cè)敿?xì)描述了在Ｓｏｎａｒ數(shù)據(jù)集和Ｈａｂｅｍｉａｎ數(shù)據(jù)集上，逡逑ＥＫ－ｍｅａｎｓ邋與邋Ｋ－ｍｅａｎｓ、ＥＫ－ｍｅｄｏｉｄｓ邋與邋Ｋ－ｍｅｄｏｉｄｓ、ＥＦＣＭ邋與邋ＦＣＭ：等各種：算法在每個(gè)指標(biāo)下逡逑的性能度量結(jié)果值。從圖３．３上可以看出，我們提出的基于有效距離的聚類算法在ＪＣ、ＦＭＩ逡逑以及ＲＩ等各個(gè)指標(biāo)上的結(jié)果值都要高于對(duì)應(yīng)的傳統(tǒng)算法的結(jié)果值。實(shí)驗(yàn)結(jié)果表明
【學(xué)位授予單位】：南京航空航天大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP311.13;TP181

【參考文獻(xiàn)】

相關(guān)期刊論文 前2條

1 呂清秀;李弼程;高毫林;;基于距離度量學(xué)習(xí)的DCT域JPEG圖像檢索[J];太赫茲科學(xué)與電子信息學(xué)報(bào);2014年01期

2 張煥炯,王國勝,鐘義信;基于漢明距離的文本相似度計(jì)算[J];計(jì)算機(jī)工程與應(yīng)用;2001年19期

相關(guān)博士學(xué)位論文 前1條

1 梅江元;基于馬氏距離的度量學(xué)習(xí)算法研究及應(yīng)用[D];哈爾濱工業(yè)大學(xué);2016年

本文編號(hào)：2537326