基于近鄰關(guān)系的稀有類挖掘.pdf

1、在現(xiàn)實生活中，我們常常會要處理一些不平衡的數(shù)據(jù)集，其中主要類的數(shù)據(jù)樣本占據(jù)了數(shù)據(jù)集的絕大多數(shù)，而稀有類只擁有極少數(shù)的數(shù)據(jù)樣本。與主要類相比，數(shù)據(jù)集中的稀有類在許多情況下往往是我們最為感興趣的。例如，在網(wǎng)絡(luò)入侵檢測中，雖然絕大多數(shù)的網(wǎng)絡(luò)訪問都屬于正常訪問，但是也有少數(shù)訪問屬于我們需要關(guān)注的惡意攻擊行為;在金融安全中，雖然絕大多數(shù)的金融交易都是合法的，但是也有少量交易屬于危害極大的違法操作。因此，如何挖掘出這些數(shù)據(jù)集中的稀有類具有較高的研究

2、價值與現(xiàn)實意義。
　　 在現(xiàn)有文獻中，稀有類挖掘的任務(wù)分為兩大類，即(1)為每個稀有類發(fā)現(xiàn)至少一個數(shù)據(jù)樣本，以證明該稀有類的存在;(2)為每個稀有類找出全部的數(shù)據(jù)樣本，以更好地理解該稀有類的性質(zhì)。其中，第一類任務(wù)通常被稱作“稀有類檢測”，又可進一步分為“基于先驗知識的稀有類檢測”和“無先驗知識的稀有類檢測”;而第二類任務(wù)包括“稀有類分類”、“稀有類聚類”、以及本文提出的“稀有類勘探”。
　　 本文圍繞稀有類挖掘的兩大任務(wù)

3、，分別研究了基于先驗知識的稀有類檢測問題、無先驗知識的稀有類檢測問題，并首次提出了“稀有類勘探”的研究問題，給出了相應(yīng)的挖掘算法。本文的主要貢獻有:
　　 (1)針對基于先驗知識的稀有類檢測問題，提出了首個具有密度不敏感特性的稀有類檢測算法，即RADAR算法。該算法通過利用數(shù)據(jù)樣本之間的反向k近鄰關(guān)系來發(fā)現(xiàn)稀有類的邊界點，從而達到發(fā)現(xiàn)稀有類數(shù)據(jù)樣本的目的。大量實驗證明，與現(xiàn)有方法相比，RADAR算法受稀有類密度的影響極小，更適合

4、于處理包含多密度稀有類的數(shù)據(jù)集。另外，提出了RADAR算法改進版本，即CATION算法。該算法通過考察稀有類邊界附近數(shù)據(jù)樣本的反向k近鄰個數(shù)上的變化，重新設(shè)計了選取稀有類邊界點的方法，以幫助用戶選取那些更為靠近稀有類內(nèi)部的稀有類邊界點，從而進一步提高發(fā)現(xiàn)稀有類數(shù)據(jù)樣本的概率。大量實驗證明，CATION算法的稀有類檢測性能明顯優(yōu)于現(xiàn)有算法。
　　 (2)針對無先驗知識的稀有類檢測問題，鑒于現(xiàn)有方法的時間復(fù)雜度普遍偏高，提出了一種快

5、速的解決方案，即CLOVER算法。該算法通過利用數(shù)據(jù)樣本之間的互k近鄰關(guān)系，將稀有類的數(shù)據(jù)樣本與其他類型的數(shù)據(jù)樣本區(qū)分開來。大量實驗證明，相較現(xiàn)有方法，CLOVER算法有效地減少了運行時間，且在稀有類檢測性能上具有明顯優(yōu)勢。
　　 (3)針對稀有類挖掘的第二大任務(wù)，即找出每個稀有類的全體數(shù)據(jù)樣本，鑒于現(xiàn)有的稀有類分類與稀有類聚類技術(shù)在應(yīng)用時的制約與局限，本文首次提出“稀有類勘探”(RareCategoryExploration)

6、這一新問題，即在給定一個已發(fā)現(xiàn)稀有類數(shù)據(jù)樣本的基礎(chǔ)上，如何準(zhǔn)確找出該稀有類余下的數(shù)據(jù)樣本。稀有類勘探的提出使得稀有類挖掘的兩大任務(wù)之間形成了連續(xù)的應(yīng)用場景，即稀有類檢測幫助用戶發(fā)現(xiàn)一個稀有類數(shù)據(jù)樣本后，再由稀有類勘探來完成尋找該稀有類余下數(shù)據(jù)樣本的工作。
　　 (4)針對稀有類勘探問題，本文提出了一種簡單而性能優(yōu)良的解決方案，即FRANK算法。該算法通過在給定的數(shù)據(jù)集上構(gòu)造k近鄰圖，將稀有類勘探問題轉(zhuǎn)化為從一個起始頂點出發(fā)、尋找