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

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

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

【參考文獻】

相關期刊論文 前2條

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

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

相關博士學位論文 前1條

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

本文編號：2537326