基于近鄰關系的稀有類挖掘.pdf

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

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

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

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

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

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