基于偏離度的孤立點檢測算法在聚類分析的應(yīng)用①

,

(1.東北石油大學(xué)計算機與信息技術(shù)學(xué)院,黑龍江 大慶 163318;2.大慶市讓湖路區(qū)政府，黑龍江 大慶 163712)

0 引 言

孤立點檢測是數(shù)據(jù)挖掘中一個重要的研究方向，尤其在金融欺詐、入侵檢測等應(yīng)用中[1]。查找數(shù)據(jù)集中明顯不同于其他數(shù)據(jù)的對象，進而分析其產(chǎn)生的原因和來源，是客觀存在還是因錯產(chǎn)生，這是孤立點檢測的主要應(yīng)用[2]。目前國內(nèi)外有很多文獻資料進行孤立點的檢測和應(yīng)用。文獻[3]提出基于相似孤立系數(shù)的孤立點檢測算法解決了一般檢測算法結(jié)果比較粗糙，不夠準確的問題。文獻[4]解決了傳統(tǒng)的RAIM算法可以很快地檢測出單個孤立點，但經(jīng)常會漏掉多個異常點。文獻[5、6]設(shè)計出一個混合數(shù)據(jù)孤立點檢測算法。文獻[7]通過優(yōu)化數(shù)據(jù)對象鄰域查詢過程，提出兩階段的改進算法解決了LOF時間復(fù)雜度高的問題。文獻[8]提出一種基于Akaike信息規(guī)則的算法，并應(yīng)用于大麥秸稈燃燒產(chǎn)生的灰分含量的實驗數(shù)據(jù)。文獻[9]提出基于聚類的兩段式孤立點檢測算法，用DBSCAN聚類算法產(chǎn)生可疑孤立點集合,然后進行剪枝、排序取交集的方法獲得孤立點。有很多類似的文獻對孤立點進行檢測和研究，主要是提出一種基于偏離度的孤立點檢測算法。

為準確掌握學(xué)生的學(xué)習(xí)情況或教師的授課狀況，常采用問卷調(diào)查、測試、專題考核、學(xué)生或?qū)＜以u教等方法。從這些方法整理出的最終數(shù)據(jù)有可能是真實的、大量的、連續(xù)的，或者可能是不完整的、模糊的、隨機的，甚至是刻意的、惡意的。管理者要從這些數(shù)據(jù)中挖掘有用的信息和數(shù)據(jù)，轉(zhuǎn)換為能直觀表征學(xué)生學(xué)習(xí)或教師授課的總體狀況，為教學(xué)和教學(xué)管理提供可靠依據(jù)。采用基于偏離度的孤立點檢測聚類分析算法對教務(wù)管理中的異常數(shù)據(jù)進行分析。然后對查找的孤立點進行聚類分析，找出這些孤立點的來源。這在實際應(yīng)用中是很有用的，保證教學(xué)管理的準確性。

1 基于偏離度的孤立點檢測算法

2000年提出的基于距離的孤立點檢測算法中最新的孤立點的定義是[10]：數(shù)據(jù)集U中，至少有p部分對象與對象O的距離大于d，那么對象O就是一個帶參數(shù)p和d的基于距離的孤立點，記為DB(p,d)。

1.1 基本概念

定義1 對象偏離度[11]對象xi,m(維數(shù)為m)的偏離度。

(1)

其中

(2)

定義2 孤立點 數(shù)據(jù)集U中對象xi,m的偏離度pi>0，則對象xi就是基于偏離度的孤立點,記為G(pi,m)。

1.2 基于偏離度的孤立點檢測算法

采用一個基于偏離度的孤立點檢測算法。算法如下：

初始化，數(shù)據(jù)集U中，t表示孤立點個數(shù)，t=0

For i=1 to n

計算hi,然后計算s=s+hi

Next

For i=1 to n

如果pi>0則G(pi,m),t++,然后，A={xi,m}

Next

輸出A和t。

對數(shù)據(jù)集A進行聚類分析。

算法結(jié)束。

通常，數(shù)據(jù)挖掘需要剔除孤立點[12]，需要k均值算法對這些孤立點進行聚類分析，查找出孤立點的類別，進行分析找出異常的來源。

2 異常應(yīng)用檢測

教學(xué)管理數(shù)據(jù)由于獲取手段、方式不一致，表示結(jié)果有所不同，往往會使測試結(jié)果帶有一定的異?；蛘咴胍?。在利用這些數(shù)據(jù)進行教學(xué)管理的時候，由于數(shù)據(jù)本身存在的異?；蛘咴肼?，就可能會出現(xiàn)掩蓋了數(shù)據(jù)本身的真實情況，結(jié)果造成錯誤的決策和管理[13]。利用孤立點的檢測方法對教務(wù)管理系統(tǒng)中積累的數(shù)據(jù)進行分析，發(fā)現(xiàn)那些值得注意的異?，F(xiàn)象，從而為教學(xué)管理者提供有利的決策支持。

2.1 學(xué)生成績管理異常檢測

實驗所用數(shù)據(jù)為5個專業(yè)各6個班的數(shù)據(jù)，共1207個數(shù)據(jù)。便于對后面的各個專業(yè)的班級提高參考。為了便于實驗，將獲得的數(shù)據(jù)進行標準化處理得到一個樣本集。其中部分數(shù)據(jù)如下：

表1 標準化后的部分數(shù)據(jù)

依照定義1，可以計算出每個學(xué)生的距離和，同時距離和均值為216，得到每個對象的偏離度。

表2 部分對象的計算屬性表

依據(jù)定義2，從上表中可以看出，序號為2、5、6、8、10、11、15、18等共有127名學(xué)生成績出現(xiàn)異常，即疑似為孤立點。

從實際數(shù)據(jù)可以看出，使用對象的偏離度計算的孤立點基本符合實際結(jié)果。說明基于偏離度檢測孤立點的算法能很好的對成績中的孤立點進行查找。說明算法是可行的。

2.2 孤立點異常分析

基于偏離度檢測孤立點的算法能發(fā)現(xiàn)孤立點，但最終目的是要查找這些孤立點的來源。因此需要進行孤立點的分類，下面對這些孤立點進行k均值聚類分析。

表3 k均值算法執(zhí)行參數(shù)

根據(jù)實驗數(shù)據(jù)，采用基于聚類的孤立點聚類分析，大致得到5類異常的孤立點。

(1)噪聲數(shù)據(jù)。在記錄成績過程中會出現(xiàn)人為的或教務(wù)系統(tǒng)的等多種影響，例如記錄中筆誤、度量標準不統(tǒng)一、測試手段不一致等造成隨機出現(xiàn)的異?，F(xiàn)象等都將遮蔽學(xué)生成績的本質(zhì)特征。如序號為13{13|77,68,106,63,78,77}的學(xué)生三級英語成績?yōu)?06，這在百分制中是不可能的。對于噪聲這類異常數(shù)據(jù)可以不予考慮，畢竟，手誤或者筆誤是沒法預(yù)料的，只需在以后工作中注意細節(jié)即可。

(2)成績不穩(wěn)定。這類孤立點數(shù)據(jù)是我們要從數(shù)據(jù)集中挖掘處理的重要異常之一。如序號為10{10|45,56,61,40,60,0}和15{15|60,67,81,72,63,41}的學(xué)生。對于成績不穩(wěn)定這類數(shù)據(jù)，就是成績挖掘處理的重要異常之一。對這類學(xué)生，觀察出一有異常波動就要做工作，使之能夠保持好成績。

(3)成績下滑。這類孤立點數(shù)據(jù)是教學(xué)管理的常見情況。如序號為8和18的學(xué)生。{8|82,71,61,60,51,43}，{18|79,70,64,60,60,0}。對于成績時時下滑的這類學(xué)生，要多關(guān)注多勸導(dǎo)。

(4)努力。這類孤立點一般還可以分2小類。即是努力有成績和努力成績小。如序號為2、14、5的學(xué)生。2{2|56,64,68,65,60,0}，{14|45,57,61,63,65,51}，{5|32,45,56,60,55,0}。對于很努力的這類學(xué)生，例如數(shù)據(jù)中序號為2和14的學(xué)生是屬于努力且有成績的，而序號為5的是努力成績小。對這種知道自己努力類的學(xué)生要給予及時的鼓勵。只要有進步了，就表揚和鼓勵使之不放松前進。同時，在其它課程中也要進行鼓勵。多個老師同時進行鼓勵，可能效果更好。

(5)作弊嫌疑。這類孤立點是常用的情況之一。一般以英語四級和六級見多。如序號為6、11的學(xué)生。{6|56,78,72,60,90,8}、{11|70,56,68,54,58,90}。對于有作弊嫌疑的這類學(xué)生，各門課程的考核中尤其要注意，能使之改正過來是最好的。

基于聚類分析找出異常數(shù)據(jù)，可以看出這些數(shù)據(jù)代表不同的聚類。在此基礎(chǔ)上，可以得出實際中的學(xué)生例如英語學(xué)習(xí)的指導(dǎo)意見。

3 結(jié) 論

使用給出孤立點的定義，然后提出基于偏離度檢測孤立點的算法，并使用真實數(shù)據(jù)有效地挖掘出異常數(shù)據(jù)。目前這種算法只能檢測數(shù)值型數(shù)據(jù)，而且更深入的分析孤立點的來源和更深入的應(yīng)用，有待進一步研究。