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

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

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

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

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

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

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