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

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

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

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