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

李萍

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

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

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

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

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

1聚類數據庫異常檢測原理

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

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

2量子C均值聚類數據異常檢測方法

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

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

上述量子C均值聚類算法中需要調節的參數有兩個σ和ε，其中σ是一個需要多次實驗選取的經驗值，滿足ε∈[0，2]，ε是一個精度調節參數。

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

3實驗分析

采用傳統聚類挖掘算法和CQC算法對相同的數據集進行異常數據點挖掘實驗，實驗結果如表2所述。表中實驗a數據來源于Ecoli數據集，包含8個異常數據。實驗b數據來源wine數據集包含6個異常數據。

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

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

從執行結果可以發現，數據量較低（少于30000）時，兩種算法的執行時間均不超過2MS，但是隨著數據規模的增長（數據量達到90000條時），CQC算法執行效率明顯優于傳統聚類算法。

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

4結論

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