基于量子C均值聚類分析的數(shù)據(jù)異常檢測方法

李萍

摘要：數(shù)據(jù)庫海量數(shù)據(jù)集需要數(shù)據(jù)異常檢測方法具有高效的數(shù)據(jù)挖掘能力，基于聚類的異常數(shù)據(jù)檢測中聚類算法對初始聚類中心較為敏感，算法穩(wěn)定性差.針對以上問題，提出了基于量子c均值聚類分析的異常數(shù)據(jù)檢測方法。算法引入量子機制的高效并行計算能力，將其與C-means聚類算法相結(jié)合應用于數(shù)據(jù)點異常檢測中，不僅克服了聚類算法對初始聚類中心敏感的問題，還具有量子模式的高效運算能力；仿真實驗表明，算法在檢測異常數(shù)據(jù)的準確性和效率上均優(yōu)于傳統(tǒng)基于聚類的異常檢測算法。

關鍵詞：量子；C均值；聚類分析；數(shù)據(jù)異常檢測

中圖分類號：TP18；TP301.6 文獻標識碼：A 文章編號：1009-3044（2018）06-0198-02

大數(shù)據(jù)和云計算技術尤其是云存儲發(fā)展，使得數(shù)據(jù)庫中的信息量成指數(shù)的增長，數(shù)據(jù)庫的重要性和價值也日益體現(xiàn)。數(shù)據(jù)庫海量數(shù)據(jù)中只有部分數(shù)據(jù)有意義和價值，甚至會存在極少數(shù)的異常數(shù)據(jù)，這些異常數(shù)據(jù)可能對所屬數(shù)據(jù)集的價值造成不可預估的危害，因此，異常數(shù)據(jù)的挖掘成了數(shù)據(jù)庫及數(shù)據(jù)挖掘領域的具有重要意義的研究方向，受到了大量的學者和研究人員的廣泛關注。

異常數(shù)據(jù)挖掘發(fā)展至今，出現(xiàn)了許多經(jīng)典方法。Breunig在文獻提出一種基于密度對異常點進行檢測的LOF（LocalOut-her Factor）算法。算法賦予每一個數(shù)據(jù)點一個離群因子，用來衡量數(shù)據(jù)的偏離水平進而表征一個數(shù)據(jù)對象偏離度的數(shù)值，缺點是對序列數(shù)據(jù)和低密度數(shù)據(jù)對象不能很好的度量。在鄧玉潔等人提出一種基于聚類分析的異常點檢測方法中，存在對初值敏感并易陷入局部最優(yōu)的缺點。針對以上問題，本文結(jié)合數(shù)據(jù)庫數(shù)據(jù)規(guī)模大、要求異常數(shù)據(jù)挖掘高效的特點，在基于聚類的數(shù)據(jù)異常檢測的基礎上，結(jié)合量子機制改進聚類算法的聚類性能，提出了基于量子K均值聚類分析的數(shù)據(jù)異常發(fā)現(xiàn)方法。仿真實驗表明，算法在異常數(shù)據(jù)挖掘的準確性和效率上均優(yōu)于傳統(tǒng)的聚類異常數(shù)據(jù)檢測算法。

1聚類數(shù)據(jù)庫異常檢測原理

基于聚類分析的異常數(shù)據(jù)檢測中，要求相同特征的數(shù)據(jù)對象聚集在一起形成數(shù)據(jù)簇，簇與簇之間盡量不相似。聚類的目的是尋找具有相同特征、緊密相關的數(shù)據(jù)，而異常數(shù)據(jù)檢測則要找到與大多數(shù)據(jù)對象偏離的數(shù)據(jù)，因此將基于聚類的異常數(shù)據(jù)檢測方法定義為：通過聚類將數(shù)據(jù)對象按特征值分成很多簇，然后將那些偏離任何一個簇的數(shù)據(jù)對象定義為異常點。

基于聚類的異常數(shù)據(jù)檢測的主要思想在于偏離其他簇的小規(guī)模簇的異常點的定義。因此，必須要明確定義異常點簇與其他簇的遠離程度以及小規(guī)模簇的具體規(guī)模。在這個過程中，首先確定一個最小距離，然后嚴格按照這個距離對數(shù)據(jù)對象進行聚類，如果當前聚類中存在大于該距離的數(shù)據(jù)，那偏離數(shù)據(jù)簇，即是異常點。其次，再根據(jù)聚類結(jié)果構(gòu)造出最小掃描樹，作為森林的一員。當聚類規(guī)模較少時，生成樹的節(jié)點也比較少，這部分樹就稱為異常點。

2量子C均值聚類數(shù)據(jù)異常檢測方法

算法基本思想：對大型數(shù)據(jù)集進行聚類，C均值算法能夠進行高效分類，性能明顯優(yōu)于層次聚類算法，但是C均值算法具有聚類算法的通病，即對初始聚類中心敏感，而且易陷入局部最優(yōu)，算法不穩(wěn)健。而量子計算用于高效并行計算能力，量子計算模式在計算速度上大大超越了圖靈機模型，適合于海量數(shù)據(jù)的處理。因此，結(jié)合量子計算的高性能和c均值聚類的優(yōu)點，提出量子C均值聚類算法，并將其應用與異常數(shù)據(jù)的檢測。

C-means聚類算法對初始聚類中心非常敏感，結(jié)合David提出的量子聚類算法中量子機制對初始數(shù)據(jù)不敏感的特性，將其引入到C-means聚類算法中，形成量子C-means聚類算法（CQC），并將該算法運用到海量數(shù)據(jù)下的異常數(shù)據(jù)挖掘中，基于量子機制的C均值聚類算法描述如下。在傳統(tǒng)聚算法中，與聚類中心屬于一簇的數(shù)據(jù)樣本是采用歐式距離來度量的，為了統(tǒng)一樣本各維的單位，消除量綱的影響，采用馬氏距離（馬氏距離消除了量綱的影響）來度分類。馬氏距離定義如下其中S為數(shù)據(jù)樣本的協(xié)方差矩陣。CQC算法描述如下：

上述量子C均值聚類算法中需要調(diào)節(jié)的參數(shù)有兩個σ和ε，其中σ是一個需要多次實驗選取的經(jīng)驗值，滿足ε∈[0，2]，ε是一個精度調(diào)節(jié)參數(shù)。

在得到數(shù)據(jù)的聚類結(jié)果后，根據(jù)基于聚類的異常數(shù)據(jù)檢測的主要思想，與實現(xiàn)定義的異常點簇與其他簇的遠離程度以及小規(guī)模簇的具體規(guī)模進行比較分析，挖掘、檢測出數(shù)據(jù)異常點。

3實驗分析

采用傳統(tǒng)聚類挖掘算法和CQC算法對相同的數(shù)據(jù)集進行異常數(shù)據(jù)點挖掘?qū)嶒灒瑢嶒灲Y(jié)果如表2所述。表中實驗a數(shù)據(jù)來源于Ecoli數(shù)據(jù)集，包含8個異常數(shù)據(jù)。實驗b數(shù)據(jù)來源wine數(shù)據(jù)集包含6個異常數(shù)據(jù)。

從表2檢測結(jié)果可以看出，與傳統(tǒng)聚類算法檢測異常數(shù)據(jù)相比，CQC算法對異常數(shù)據(jù)的檢測準確率較高，且挖掘速度較快。

為了研究CQC算法針對不同規(guī)模數(shù)據(jù)集時的異常數(shù)據(jù)的檢測性能，將傳統(tǒng)聚類算法與CQC檢測算法對實驗1中包含10000到90000條規(guī)模數(shù)據(jù)集進行實驗，各算法的執(zhí)行時間對比如下：

從執(zhí)行結(jié)果可以發(fā)現(xiàn)，數(shù)據(jù)量較低（少于30000）時，兩種算法的執(zhí)行時間均不超過2MS，但是隨著數(shù)據(jù)規(guī)模的增長（數(shù)據(jù)量達到90000條時），CQC算法執(zhí)行效率明顯優(yōu)于傳統(tǒng)聚類算法。

上述實驗數(shù)據(jù)均表明：基于C均值聚類分析的數(shù)據(jù)異常檢測算法挖掘準確度高，效率性高。

4結(jié)論

本文采用量子機制與C-means聚類算法融合形成量子C均值聚類算法，并其代替C均值算法用于異常數(shù)據(jù)點的檢測。該算法利用量子計算的高效并行計算能力以及對數(shù)據(jù)初始聚類中心不敏感的特征，解決了C-means聚類算法聚類時對初始數(shù)據(jù)中心敏感、穩(wěn)定性差等問題。仿真結(jié)果表明，該算法較基于傳統(tǒng)聚類算法的異常數(shù)據(jù)檢測方法在異常數(shù)據(jù)點挖掘準確率和效率上均有一定的優(yōu)勢。