關(guān)聯(lián)子空間離群點挖掘研究.pdf

1、傳統(tǒng)的基于全維空間的離群點挖掘技術(shù)受“維災(zāi)”影響，不再適用于高維數(shù)據(jù)。為了從高維數(shù)據(jù)中發(fā)現(xiàn)有意義的離群點，學(xué)者們提出將高維空間的數(shù)據(jù)投影到子空間上進(jìn)行離群點挖掘。子空間離群點挖掘目的是在任何可能的屬性子集中檢測離群點，對于高維數(shù)據(jù)而言窮舉所有可能的子空間進(jìn)行離群點挖掘是不可行的。事實上，并非所有子空間都存在離群點，如果子空間中數(shù)據(jù)隨機均勻分布，則該子空間不存在離群點，就可在離群點挖掘過程中忽略處理。關(guān)聯(lián)子空間離群點挖掘正是在這個基礎(chǔ)上提

2、出的，旨在搜尋分布不均的、更可能存在離群點的、關(guān)聯(lián)性高的子空間進(jìn)行離群點挖掘。
　　已有的局部關(guān)聯(lián)子空間離群點挖掘方法的主要局限是:(1)無法反映子空間的關(guān)聯(lián)程度，對子空間是否關(guān)聯(lián)進(jìn)行0-1判斷導(dǎo)致子空間選取不準(zhǔn)確，且采用類似窮舉的方式搜索子空間導(dǎo)致時間復(fù)雜度高。(2)未考慮大量不大可能構(gòu)成數(shù)據(jù)點關(guān)聯(lián)子空間的屬性的影響，在全維屬性集合中搜索子空間，導(dǎo)致不必要的時間開銷，且所得子空間質(zhì)量降低致使離群點挖掘精度降低。
　　針對上

3、述問題，本文采用數(shù)據(jù)點及其鄰域在各維屬性投影上的最大非均勻分布程度衡量子空間的關(guān)聯(lián)性，采用自底向上的方式搜索子空間。為了進(jìn)一步提高算法的有效性，根據(jù)數(shù)據(jù)點及其局部鄰域在屬性投影上的取值分布計算屬性的局部信息熵，只選取局部信息熵高的屬性構(gòu)成候選屬性集合，并基于該候選屬性集合搜索子空間。論文主要工作如下:
　　(1)提出局部關(guān)聯(lián)子空間離群點挖掘算法RSOM(Outlier Mining in RelevantSubspaces)。采用

4、數(shù)據(jù)點及其鄰域在各維屬性投影上的最大非均勻分布程度衡量子空間的關(guān)聯(lián)程度，以增加子空間選取的魯棒性，進(jìn)而提高離群點挖掘精度;采用自底向上的方式搜索子空間，以降低子空間搜索的時間復(fù)雜度。實驗結(jié)果表明，RSOM大大降低了時間開銷，顯著地提高了離群點挖掘精度。
　　(2)提出基于局部信息熵的關(guān)聯(lián)子空間離群點挖掘算法LERSOM(LocalInformation Entropy based Outlier Mining in Relevan

5、t Subspaces)。從信息熵的角度考慮離群點在某些屬性上取值的不確定性，根據(jù)數(shù)據(jù)點及其局部鄰域在屬性投影上的取值分布計算屬性的局部信息熵，只選局部信息熵高的屬性構(gòu)成數(shù)據(jù)點的候選屬性集合進(jìn)行離群點挖掘，減少了需要處理的子空間數(shù)量并提高了所得子空間的質(zhì)量。實驗結(jié)果表明，LERSOM獲得較高的挖掘精度，且時間開銷減半。
　　(3)采用模塊化的設(shè)計方式，設(shè)計并實現(xiàn)了關(guān)聯(lián)子空間離群點挖掘原型系統(tǒng)，在可視化環(huán)境下進(jìn)行實驗操作，以便檢驗本