白 寧

(山西警官高等專科學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)系，山西 太原 030021)

0 引言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，以及人們管理和知識(shí)水平的提高，對(duì)于客觀世界事物的描述更加全面，現(xiàn)實(shí)世界中需要存儲(chǔ)和處理的數(shù)據(jù)量也越來越大，但如何從這些海量復(fù)雜數(shù)據(jù)中提取異常但對(duì)于用戶重要的信息，依然是一個(gè)亟待解決的問題。數(shù)據(jù)挖掘［1］就是從大規(guī)模的、不完整的、有噪聲的、模糊的、隨機(jī)的復(fù)雜數(shù)據(jù)集中提取隱含的、潛在有用的信息或知識(shí)。異常檢測(cè)是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要研究方向，其主要用來檢測(cè)數(shù)據(jù)集中偏離正常分布模式的異常數(shù)據(jù)。目前常采用的異常檢測(cè)技術(shù)包括監(jiān)督的、半監(jiān)督的和無監(jiān)督的異常檢測(cè)方法。

基于監(jiān)督的異常檢測(cè)技術(shù)通過給出帶標(biāo)簽的正常數(shù)據(jù)集和異常數(shù)據(jù)集來構(gòu)成整個(gè)訓(xùn)練集，常用的基于監(jiān)督的異常檢測(cè)技術(shù)包括:基于概率統(tǒng)計(jì)的方法［2］、基于數(shù)據(jù)挖掘的方法［3］、基于神經(jīng)網(wǎng)絡(luò)［4］的方法等?；诎氡O(jiān)督的異常檢測(cè)技術(shù)只給出部分有標(biāo)記的正常數(shù)據(jù)構(gòu)成訓(xùn)練集，而沒有異常數(shù)據(jù)的標(biāo)記。在半監(jiān)督異常檢測(cè)過程中，通過正常數(shù)據(jù)的標(biāo)記來挖掘異常數(shù)據(jù)信息。李和平等［5］通過自動(dòng)選擇正常行為模式建立正常模型，提出一種基于半監(jiān)督學(xué)習(xí)的異常檢測(cè)方法，具有較高的可靠性;Hu等人［6］提出一個(gè)自組織層次神經(jīng)網(wǎng)絡(luò)模型，并通過軌跡分布模式來檢測(cè)局部可能的異?，F(xiàn)象;Zhang等人［7］通過正常數(shù)據(jù)集對(duì)正常模型進(jìn)行建模，然后不斷迭代使用貝葉斯自適應(yīng)的隱馬爾可夫模型判斷異常。

盡管基于監(jiān)督學(xué)習(xí)的異常檢測(cè)方法雖然能夠通過建立準(zhǔn)確的正常模型來進(jìn)行異常檢測(cè)，但是需要對(duì)數(shù)據(jù)進(jìn)行手工標(biāo)記來獲取足夠的訓(xùn)練樣本，成本較大，因此人們提出了基于無監(jiān)督的異常檢測(cè)方法?；跓o監(jiān)督學(xué)習(xí)的異常檢測(cè)方法從無標(biāo)簽樣本集中提取有用的信息，該方法具有代價(jià)小、適用范圍廣、適時(shí)性好、可獨(dú)立于數(shù)據(jù)工作等優(yōu)點(diǎn)。

聚類作為一種典型的無監(jiān)督數(shù)據(jù)挖掘方法，目前已在異常檢測(cè)領(lǐng)域得到成功應(yīng)用。常見的聚類模型包括:劃分聚類、層次聚類、密度聚類、網(wǎng)格聚類、概率聚類和譜聚類等。Yasami等人［8］提出了基于決策樹算法的無監(jiān)督異常檢測(cè)算法，該方法分別從聚類算法和ID3決策樹算法中提取異常分?jǐn)?shù)，結(jié)合起來生成最終的異常評(píng)分值進(jìn)行異常檢測(cè);Park等人［9］通過建立用戶連續(xù)活動(dòng)的數(shù)據(jù)流，采用基于數(shù)據(jù)流分析的聚類算法對(duì)用戶的正常行為建模來實(shí)現(xiàn)異常檢測(cè);李娜等人［10］結(jié)合信息熵理論提出了一種基于層次聚類的無監(jiān)督異常檢測(cè)算法;周亞建等人［11］提出了基于CURE聚類算法的無監(jiān)督異常檢測(cè)方法以迅速、準(zhǔn)確地檢測(cè)出入侵行為。

由于實(shí)際問題中用戶行為的多樣性和不可預(yù)知性，以及人工標(biāo)注的代價(jià)較大，傳統(tǒng)異常檢測(cè)方法通過提前設(shè)定正常模式的方式進(jìn)行學(xué)習(xí)變得異常困難。針對(duì)這個(gè)問題，本文提出一種基于k-均值聚類的自動(dòng)異常檢測(cè)方法(OD_KC方法)。該方法通過對(duì)無標(biāo)簽的樣本集進(jìn)行k-均值聚類，通過調(diào)整不同的聚類個(gè)數(shù)，衡量聚類結(jié)果的抱團(tuán)性和分離性，以獲得最佳的聚類結(jié)果，同時(shí)自動(dòng)地得到那些被劃分為很小規(guī)模的類的樣本作為異常模式樣本。基于k-均值的異常檢測(cè)方法具有很強(qiáng)的自主性和自適應(yīng)性，特別地，當(dāng)樣本分布模式發(fā)生變化時(shí)，算法的檢測(cè)結(jié)果也能隨之而自動(dòng)更新，因此具有較好的異常檢測(cè)能力。

1 傳統(tǒng)k-均值聚類方法

在眾多聚類方法中，k-均值聚類是一種最為經(jīng)典使用最為廣泛的劃分聚類方法［12-13］。k-均值聚類方法以各類樣本的質(zhì)量中心代表該類進(jìn)行迭代，從而通過不斷地動(dòng)態(tài)調(diào)整各類中心進(jìn)行聚類。

設(shè)聚類樣本集為X= {xi，i=1，…，n }且 xi∈Rd，k為初始聚類個(gè)數(shù)參數(shù)。傳統(tǒng)k-均值聚類方法首先從n個(gè)樣本中隨機(jī)選擇k個(gè)樣本作為初始聚類中心，然后根據(jù)其他樣本與已得到的聚類中心的相似度分別分配到最相似的類中心所屬類中。2個(gè)樣本xi與xj的相似度定義如下:

本文結(jié)合k-均值聚類方法能夠根據(jù)樣本相似度進(jìn)行自適應(yīng)聚類的特性，提出一種基于k-均值聚類的自動(dòng)異常檢測(cè)方法。通過對(duì)樣本集進(jìn)行多次不同k值的k-均值聚類，通過構(gòu)造測(cè)度函數(shù)衡量聚類結(jié)果的抱團(tuán)性和分離性，以獲得最佳的聚類結(jié)果，同時(shí)自動(dòng)得到那些被劃分為很小規(guī)模類的樣本作為異常模式樣本。

2 基于k-均值聚類的異常檢測(cè)方法

其中，d為樣本維度，ni為聚類結(jié)果中第i個(gè)類的類內(nèi)樣本個(gè)數(shù)，k為聚類參數(shù)。然后逐次改變聚類參數(shù)k值，觀測(cè)評(píng)測(cè)指標(biāo)J的變化，從而自動(dòng)地得到較為合理的聚類結(jié)果，以發(fā)現(xiàn)數(shù)據(jù)中的異常模式。

基于k-均值聚類的異常檢測(cè)算法具體過程如下:

算法1 基于k-均值聚類的異常檢測(cè)算法

Step2 對(duì)樣本集X進(jìn)行k-均值聚類，得到初始聚類結(jié)果，具體過程如下:

Step2.1 從樣本集X中隨機(jī)選擇k(t)個(gè)樣本構(gòu)造初始聚類中心集

Step2.2 根據(jù)式(1)計(jì)算樣本集中每個(gè)樣本xi(i=1，…，n)與所有不同類心之間的相似度S，并分別將每個(gè)xi歸為與其最相似的類中心所屬的類;

Step2.4 觀測(cè)更新前后的聚類中心集合C(t)是否一致，若不一致，則返回Step2.2繼續(xù)執(zhí)行，直到更新前后的聚類中心一致為止;若一致，則得到本論聚類的聚類結(jié)果X→。

Step5 算法結(jié)束，輸出異常模式樣本。

3 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證本文提出的基于k-均值聚類的異常檢測(cè)方法的有效性，本文在4個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)在1臺(tái)PC機(jī)(2Ghz CPU，4G內(nèi)存)上進(jìn)行，實(shí)驗(yàn)平臺(tái)是Matlab 2008。實(shí)驗(yàn)采用的標(biāo)準(zhǔn)數(shù)據(jù)集［14］見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集

表2列出了基于k-均值聚類的異常檢測(cè)方法所得到的檢測(cè)結(jié)果。實(shí)驗(yàn)中，4個(gè)數(shù)據(jù)集上的初始聚類參數(shù)k值分別根據(jù)樣本規(guī)模的大小依次取20，50，200和 25。實(shí)驗(yàn)中的聚類結(jié)束參數(shù) ε取 1.5。

表2 OD_KC算法的異常檢測(cè)結(jié)果

綜上可看出，本文提出的基于k-均值聚類的異常檢測(cè)方法具有很強(qiáng)的自主性和自適應(yīng)性，特別地，當(dāng)樣本分布模式復(fù)雜時(shí)，也能得到較為優(yōu)秀的檢測(cè)結(jié)果，因此具有較好的異常檢測(cè)能力。

4 結(jié)束語

針對(duì)傳統(tǒng)異常檢測(cè)方法需要提前設(shè)定正常模式的缺陷，本文提出一種基于k-均值聚類的自適應(yīng)異常檢測(cè)方法。該方法通過對(duì)無標(biāo)簽的樣本集進(jìn)行k-均值聚類，通過調(diào)整不同的聚類個(gè)數(shù)，通過構(gòu)造測(cè)度函數(shù)，以衡量聚類結(jié)果的抱團(tuán)性和分離性，從而獲得最佳的聚類結(jié)果，同時(shí)自動(dòng)得到那些被劃分為很小規(guī)模的類的樣本作為異常模式樣本。在今后工作中，筆者將進(jìn)一步結(jié)合并行計(jì)算方法探討基于k-均值聚類方法在大規(guī)模異常檢測(cè)問題中的應(yīng)用。

［1］苗奪謙，王國胤，劉清，等.粒計(jì)算:過去、現(xiàn)在與展望［M］.北京:科學(xué)出版社，2007.

［2］Staniford S，Hoagland J，McAlerney J.Practical automated detection of stealthy portscans［J］.Journal of Computer Security，2002，10(2):105-136.

［3］Bridges S，Vaughn R.Fuzzy data mining and genetic algorithms applied to intrusion detection［C］//Proceedings 23rd National Information Systems Security Conference.Baltimore，2000:13-31.

［4］Sung A，Mukkamala S.Identify important features for intrusion detection using support vector machines and neural networks［C］//IEEE Proceedings of the 2003 Symposium on Application and the Internet.2003:209-216.

［5］李和平，胡占義，吳毅紅.基于半監(jiān)督學(xué)習(xí)的行為建模與異常檢測(cè)［J］.軟件學(xué)報(bào)，2007，18(3):527-537.

［6］Hu W M，Xie D，Tan T N.A hierarchical self-organizing approach for learning the patterns of motion trajectories［J］.IEEE Transactions on Neural Networks，2004，15(1):135-144.

［7］Zhang D，Gatica-Perez D，Bengio S，et al.Semi-supervised adapted HMMs for unusual event detection［C］//Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.2005:611-618.

［8］Yasami Y，Mozaffari S P.A novel unsupervised classification approach for network anomaly detection by k-means clustering and ID3 decision tree learning method［J］.ACM Journal of Supercomputing，2010，53(11):231-245.

［9］Park N H，Oh S H，Lee W S.Anomaly intrusion detection by clustering transactional audit streams in a host computer［J］.Information Sciences，2010，180(12):2375-2389.

［10］李娜，鐘誠.基于劃分和凝聚層次聚類的無監(jiān)督異常檢測(cè)［J］.計(jì)算機(jī)工程，2008，34(2):120-123.

［11］周亞建，徐晨，李繼國.基于改進(jìn)CURE聚類算法的無監(jiān)督異常檢測(cè)方法［J］.通信學(xué)報(bào)，2010，31(7):19-23，32.

［12］Elkan C.Using the triangle inequality to accelerate kmeans［C］//Proceedings of the Twentieth International Conference on Machine Learning.2003:147-153.

［13］曹文平.一種有效k-均值聚類中心的選取方法［J］.計(jì)算機(jī)與現(xiàn)代化，2008(3):95-97.

［14］UCIrvine.UCI Machine Learning Repository［DB/OL］.http://archive.ics.uci.edu/ml/，2013-08-13.