基于連通性的離群檢測與聚類研究.pdf

1、離群檢測和聚類是數(shù)據(jù)挖掘的兩個重要研究領(lǐng)域。雖然其相關(guān)技術(shù)已經(jīng)非常成熟,但仍然有許多難題未能較好解決。本課題希望通過基礎(chǔ)理論的研究繼續(xù)推進離群檢測和聚類的發(fā)展,并解決當(dāng)前研究和應(yīng)用中的部分難題。具體的工作為:從數(shù)據(jù)關(guān)系描述出發(fā),研究離群檢測和聚類的數(shù)學(xué)模型,進一步論證和優(yōu)化其解方案。數(shù)據(jù)關(guān)系描述是數(shù)據(jù)挖掘領(lǐng)域中的基礎(chǔ)性研究。在實際應(yīng)用中,關(guān)系描述的好壞往往直接影響數(shù)據(jù)挖掘的結(jié)果。因此,首先研究了關(guān)系描述----不相似性度量,并完善了相關(guān)

2、理論。歐式距離是最為常用的不相似性度量。然而,此度量無法準(zhǔn)確描述數(shù)據(jù)之間的不相似性,甚至有時候會給出錯誤的不相似性描述。在此基礎(chǔ)上,本文提出了基于鄰域的不相似性度量以及基于連通性的不相似性度量。新度量分別綜合了密度信息和連通性信息,能較好地反映數(shù)據(jù)之間的不相似性。為便于使用,文中還對基于鄰域的不相似性度量進行了理論分析,獲得其均勻分布估計值;對連通不相似性進行理論推導(dǎo),獲得了基于最小生成樹路徑不相似性描述。
　　本文基于連通性考慮

3、,提出了基于第k個最相似鄰居的離群檢測算法,即根據(jù)第k相似鄰居的連通性度量離群程度。此第k相似鄰居的連通性對應(yīng)遞閉包不相似性第k小值;通過證明,該第k小值也等于Prim最小生成樹算法的第k個被合并點的連通性。所以,將離群性定義為考察點與第k相似鄰居之間的最小生成樹路徑上的最大邊。另外,提出的離群檢測算法還考慮了密度因素,因此適用于任意密度、任意形狀的數(shù)據(jù),且在局部離群點和簇離群點檢測方面表現(xiàn)出較好性能。連通性也是聚類需要考慮的重要因素。