李萍

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

關(guān)鍵詞：量子；C均值；聚類(lèi)分析；數(shù)據(jù)異常檢測(cè)

中圖分類(lèi)號(hào)：TP18；TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）06-0198-02

大數(shù)據(jù)和云計(jì)算技術(shù)尤其是云存儲(chǔ)發(fā)展，使得數(shù)據(jù)庫(kù)中的信息量成指數(shù)的增長(zhǎng)，數(shù)據(jù)庫(kù)的重要性和價(jià)值也日益體現(xiàn)。數(shù)據(jù)庫(kù)海量數(shù)據(jù)中只有部分?jǐn)?shù)據(jù)有意義和價(jià)值，甚至?xí)嬖跇O少數(shù)的異常數(shù)據(jù)，這些異常數(shù)據(jù)可能對(duì)所屬數(shù)據(jù)集的價(jià)值造成不可預(yù)估的危害，因此，異常數(shù)據(jù)的挖掘成了數(shù)據(jù)庫(kù)及數(shù)據(jù)挖掘領(lǐng)域的具有重要意義的研究方向，受到了大量的學(xué)者和研究人員的廣泛關(guān)注。

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

1聚類(lèi)數(shù)據(jù)庫(kù)異常檢測(cè)原理

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

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

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

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

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

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

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

3實(shí)驗(yàn)分析

采用傳統(tǒng)聚類(lèi)挖掘算法和CQC算法對(duì)相同的數(shù)據(jù)集進(jìn)行異常數(shù)據(jù)點(diǎn)挖掘?qū)嶒?yàn)，實(shí)驗(yàn)結(jié)果如表2所述。表中實(shí)驗(yàn)a數(shù)據(jù)來(lái)源于Ecoli數(shù)據(jù)集，包含8個(gè)異常數(shù)據(jù)。實(shí)驗(yàn)b數(shù)據(jù)來(lái)源wine數(shù)據(jù)集包含6個(gè)異常數(shù)據(jù)。

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

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

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

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

4結(jié)論

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