高維空間中的離群點發(fā)現(xiàn)

《高維空間中的離群點發(fā)現(xiàn)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、1000-9825/2002/13(02)0280-11?2002JournalofSoftware軟件學(xué)報Vol.13,No.2高維空間中的離群點發(fā)現(xiàn)?魏藜,宮學(xué)慶,錢衛(wèi)寧,周傲英(復(fù)旦大學(xué)計算機科學(xué)與工程系,上海200433)E-mail:{lwei,xqgong,wnqian,ayzhou}@fudan.edu.cnhttp://www.fudan.edu.cn摘要:在許多KDD(knowledgediscoveryindatabases)應(yīng)用中,如電子商務(wù)中的欺詐行為監(jiān)測,例外情況或離群點的發(fā)現(xiàn)比常規(guī)知識

2、的發(fā)現(xiàn)更有意義.現(xiàn)有的離群點發(fā)現(xiàn)大多是針對數(shù)值屬性的,而且這些方法只能發(fā)現(xiàn)離群點,不能對其含義進行解釋.提出了一種基于超圖模型的離群點(outlier)定義,這一定義既體現(xiàn)了“局部”的概念,又能很好地解釋離群點的含義.同時給出了HOT(hypergraph-basedoutliertest)算法,通過計算每個點的支持度、隸屬度和規(guī)模偏差來檢測離群點.該算法既能夠處理數(shù)值屬性,又能夠處理類別屬性.分析表明,該算法能有效地發(fā)現(xiàn)高維空間數(shù)據(jù)中的離群點.關(guān)鍵詞:數(shù)據(jù)挖掘;離群點;超圖模型;聚類中圖法分類號:TP311文獻

3、標識碼:AKDD(knowledgediscoveryindatabases)是從大量數(shù)據(jù)中發(fā)現(xiàn)正確的、新穎的、潛在有用并能夠被理解的[1]知識的過程.現(xiàn)有的KDD研究大多集中于發(fā)現(xiàn)適用于大部分數(shù)據(jù)的常規(guī)模式.但在一些應(yīng)用中,如電子商務(wù)和金融服務(wù)領(lǐng)域中的欺詐等犯罪行為監(jiān)測,有關(guān)例外情況的信息比常規(guī)模式更有價值.目前,這樣的研究正得到越來越多的重視.[2][3][4][5][6][7][8]KDD中多數(shù)聚類算法(CLARANS,DBSCAN,BIRCH,STING,WaverCluster,DenClue,CLIQ

4、UE)能夠發(fā)現(xiàn)一些例外情況.但是,因為聚類算法的主要目標是發(fā)現(xiàn)簇,而不是發(fā)現(xiàn)離群點(outlier),聚類算法或者對這些例外情況不敏感,或者忽視這些例外情況.最近,有一些研究是專門針對離群點發(fā)現(xiàn)的,例如文獻[9~13].現(xiàn)有的離群點發(fā)現(xiàn)方法大多是針對數(shù)值屬性的,而且只能發(fā)現(xiàn)離群點,不能對其含義進行解釋.本文提出了一種基于超圖模型的離群點檢測方法HOT(hypergraph-basedoutliertest),它具有如下特點：·既能夠處理數(shù)值屬性,又能夠處理類別(categorical)屬性；·能有效并且高效地處理

5、高維數(shù)據(jù)；·離群點是在“窗口”中定義的,而窗口中的其他點與該點有許多相似之處,既體現(xiàn)了數(shù)據(jù)的局部性,又體現(xiàn)了屬性的局部性,同時也能很好地解釋離群點的物理含義——正是窗口規(guī)定的這些屬性造成了它的離群.本文第1節(jié)簡單介紹了超圖聚類,傳統(tǒng)的離群點發(fā)現(xiàn)方法和針對高維數(shù)據(jù)的離群點發(fā)現(xiàn)方法.第2節(jié)詳細描述了發(fā)現(xiàn)離群點的問題,并給出了支持度、隸屬度和規(guī)模偏差的定義.尋找離群點的具體算法步驟及算法復(fù)雜度分析在第3節(jié)中給出.第4節(jié)討論HOT算法的特點.第5節(jié)總結(jié)全文,并給出了本文的后續(xù)工作.?收稿日期:2001-04-20;修改日

6、期:2001-09-20基金項目:國家自然科學(xué)基金資助項目(60003016;60003008);國家重點基礎(chǔ)研究發(fā)展規(guī)劃973資助項目(G1998030404)作者簡介:魏藜(1978－),女,江西南昌人,碩士生,主要研究領(lǐng)域為數(shù)據(jù)挖掘技術(shù);宮學(xué)慶(1974－),男,黑龍江饒河人,講師,主要研究領(lǐng)域為WEB數(shù)據(jù)管理,數(shù)據(jù)挖掘;錢衛(wèi)寧(1976－),男,浙江上虞人,博士生,主要研究領(lǐng)域為數(shù)據(jù)挖掘,Web數(shù)據(jù)管理;周傲英(1965－),男,安徽人,博士,教授,博士生導(dǎo)師,主要研究領(lǐng)域為Web數(shù)據(jù)管理,數(shù)據(jù)挖掘.魏藜

7、等:高維空間中的離群點發(fā)現(xiàn)2811相關(guān)工作1.1超圖模型聚類文獻[14]提出了一種基于超圖(hypergraph)模型的,對高維空間數(shù)據(jù)進行聚類的方法.該方法將數(shù)據(jù)集中的每一條記錄看作超圖中的一個點,把具有公共頻繁項集的點歸結(jié)到一條超邊中,并用基于關(guān)聯(lián)規(guī)則的概念來衡量超邊的權(quán)重.因此,該方法能夠?qū)?shù)據(jù)之間的關(guān)系映射到超圖上,其中超邊表示數(shù)據(jù)點之間的關(guān)系,超邊的權(quán)重反映這種關(guān)系的強弱.建立了超圖模型以后,使用超邊分割方法,每次打斷權(quán)重最小的超邊,直到每個分割中的數(shù)據(jù)都密切相關(guān)為止,最終得到的分割就是聚類的結(jié)果.在進

8、行超邊分割的同時,用點與簇之間的連通度來評價得到的簇,因此可以有效地排除噪聲數(shù)據(jù)對聚類結(jié)果的影響.1.2傳統(tǒng)的尋找離群點的方法[15]到目前為止,離群點還沒有一個正式的、為人們普遍接受的定義.Hawkin的定義揭示了離群點的本質(zhì):“離群點的表現(xiàn)與其它點如此不同,不禁讓人懷疑它們是由另外一種完全不同的機制產(chǎn)生的.”(“Anoutlierisanobservationthat