量子k-means算法

劉雪娟,袁家斌,許 娟,段博佳

(南京航空航天大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,南京210016)

0 引 言

近年來,越多越多的學(xué)者將量子計算應(yīng)用于數(shù)據(jù)挖掘領(lǐng)域[1]。Anguita等[2]提出利用Grover量子搜索算法[3]優(yōu)化支持向量機SVM的訓(xùn)練過程用于解決SVM的訓(xùn)練效率問題。Rebentrost等[4]提出量子SVM,利用量子計算解決訓(xùn)練數(shù)據(jù)的內(nèi)積計算,即利用量子計算求解矩陣的偏跡得到訓(xùn)練數(shù)據(jù)的歸一化核矩陣。Lu等[5]提出量子決策樹算法,利用量子態(tài)之間的保真度作為訓(xùn)練數(shù)據(jù)之間相似度的度量,依此將訓(xùn)練集劃分成子類,并引入量子信息熵作為選擇決策節(jié)點的依據(jù)建立量子決策樹。阮越等[6]提出了量子PCA算法并用于人臉識別中,用量子態(tài)表示人臉特征,將Grover量子搜索算法用于人臉識別的過程達(dá)到二次加速的效果。徐永振等[7]提出基于一維三態(tài)離散量子游走的聚類算法,將數(shù)據(jù)點看作游走粒子,執(zhí)行三態(tài)量子游走,根據(jù)粒子的測量結(jié)果更新數(shù)據(jù)點的屬性值并依此進(jìn)行聚類。Elhaddad等[8]從并行計算和優(yōu)化計算兩個方面分別分析了量子計算對人工智能和數(shù)據(jù)挖掘領(lǐng)域所帶來的影響。

聚類作為一種無監(jiān)督的機器學(xué)習(xí)技術(shù),其依據(jù)給定的相似性度量將數(shù)據(jù)劃分成若干個類,使得同一類內(nèi)的數(shù)據(jù)相似度較高,而不同類間的數(shù)據(jù)相似度較低[9]。聚類算法被廣泛應(yīng)用于圖像識別、社交網(wǎng)絡(luò)、商業(yè)智能等領(lǐng)域中[10,11]。k-means是一種經(jīng)典的聚類算法,被譽為數(shù)據(jù)挖掘領(lǐng)域的十大算法之一,自提出以來就得到了廣泛的應(yīng)用[12-14]。然而大數(shù)據(jù)時代,巨大的數(shù)據(jù)量為kmeans聚類的速度帶來了巨大的挑戰(zhàn),利用基于云計算的大規(guī)模集群進(jìn)行并行聚類成了較為普遍的應(yīng)對策略;但是大規(guī)模集群所產(chǎn)生的巨大的能量消耗問題又帶來新的挑戰(zhàn)[15,16]。而量子計算不但具有超強的并行計算能力,又因計算的可逆性使其不會面臨能量消耗的問題,故已有學(xué)者研究利用量子計算的相關(guān)理論對k-means算法進(jìn)行聚類加速。因量子態(tài)之間的信息保真度與傳統(tǒng)相似度度量中的余弦相似度相似,A?meur等[17]提出利用量子信息保真度代替k-means算法中數(shù)據(jù)之間的相似度量,并利用受控交換門Control-Swap計算量子信息保真度,但k-means算法的其他步驟并沒有引入量子計算。隨后A?meur等[18,19]又提出了利用Grover算法的擴展算法量子最小值查找算法作為一個量子子程序去加速經(jīng)典k-means算法中的一個步驟,但算法的計算復(fù)雜度并沒有降低。k-means算法對初始聚類中心的選擇比較敏感,不同的聚類中心其聚類效果可能不同,故Lloyd等[20]提出利用量子絕熱算法選擇合適的初始聚類中心點后,再利用kmeans算法進(jìn)行聚類,聚類的計算過程中并未引入量子計算。

綜上所述,有關(guān)量子計算與k-means算法相結(jié)合的工作中,大多是利用量子計算對算法中的某一個步驟進(jìn)行了加速,但是算法整體的計算復(fù)雜度并未降低。本文給出的量子k-means算法將對聚類的主要步驟進(jìn)行加速,使算法整體計算復(fù)雜度得到降低。

1 經(jīng)典k-means算法

給定數(shù)據(jù)集X＝{x1,x2,…,x n},n為數(shù)據(jù)集的規(guī)模,x i為第i個數(shù)據(jù)點,每個數(shù)據(jù)點的特征維度為d,x ir表示第i個數(shù)據(jù)點的第r個特征值;數(shù)據(jù)集被劃分為k個類別,聚類中心為c＝{c1,c2,…,c k}。k-means算法的聚類過程如下:

(1)隨機從數(shù)據(jù)集X中選取k條記錄作為初始聚類中心c。

(2)對每一數(shù)據(jù)點x i,計算其到k個聚類中心的相似度。

(3)將數(shù)據(jù)點x i歸于相似度最大的那個聚類中心所屬的類。

(4)數(shù)據(jù)集中的所有數(shù)據(jù)經(jīng)過步驟(2)(3)計算后,根據(jù)數(shù)據(jù)集的類別標(biāo)號重新計算新的聚類中心。

(5)判斷是否達(dá)到聚類結(jié)束的條件,若達(dá)到,聚類結(jié)束;否則回到步驟(1)。

k-means算法的主要聚類步驟和計算量集中在第(2)(3)步,即對每個數(shù)據(jù)點計算其到k個聚類中心的相似度,并將其歸于相似度最大的聚類中心所屬的類別。

2 本文算法

量子k-means算法將量子計算的相關(guān)理論引入到聚類的主要步驟,主要分成3個階段完成該步驟的任務(wù):第一,先將待聚類的數(shù)據(jù)點和k個聚類中心點制備成量子態(tài);第二,利用受控交換門Control-Swap計算任一數(shù)據(jù)點x i和k個聚類中心c＝{c1,c2,…,c k}的相似度,并利用相位估計算法將相似度存儲在量子比特上;第三,對所求出的k個相似度利用最小值查找量子搜索算法求出最相似的聚類中心點c j。

2.1 量子態(tài)制備

k-means算法中需要計算每一個數(shù)據(jù)點與k個聚類中心的相似度,所以需要將其制備成量子態(tài)。量子態(tài)制備之前先將所有的數(shù)據(jù)進(jìn)行歸一化處理。假設(shè)任一聚類數(shù)據(jù)點x i用具有d個特征值的向量來表示,以待聚類的數(shù)據(jù)點x0為例,將數(shù)據(jù)點x0制備成如式(1)所示的量子態(tài):

式中:x0j為第0個數(shù)據(jù)點的第j個特征值。

將k個聚類中心c＝{c1,c2,…,c k}制備成如式(2)所示的量子態(tài):

式中:c ij表示第i個聚類中心點的第j個特征值。

設(shè)2m＝k,2n＝d,量子態(tài)|c〉的制備過程如下:

(1)初始輸入為|0〉?m|0〉?n|1〉|0〉,利用H門得到量子態(tài):

(2)將量子黑箱Oracle作用到式(3)上得到:

量子黑箱Oracle定義為:

(3)利用一個繞Y軸旋轉(zhuǎn)的酉操作作用到式(4)中的最后一個量子比特上得到:

(4)利用第(2)步的量子黑箱Oracle的逆操作清除式(5)中的|c ij〉,得到如式(2)所示的量子態(tài)|c〉。

利用同樣的方法制備如式(1)所示的量子態(tài)|x0〉。由上述量子態(tài)的制備過程可以得到,制備量子態(tài)|c〉需要3次Oracle操作,制備|x0〉與|c0〉則需要6次Oracle操作。

2.2 相似性計算

計算量子態(tài)|x0〉與|c〉的相似度,并利用相位估計算法將相似度存儲在量子比特中。對于相似度的計算,仍然采用文獻(xiàn)[17]中的方法:即采用控制交換門Control-Swap計算量子態(tài)之間的保真度用于估計相似度。

用于計算量子態(tài)|x0〉與|c〉相似度的控制交換門Control-Swap如圖1所示,輸入的第1個量子比特位經(jīng)過一個H門后用作控制位,當(dāng)其為1時實現(xiàn)交換操作。計算的過程如下:

(1)|0〉|x0〉|c〉 ∥ 初態(tài)。

圖1 控制交換門Fig.1 Control-Swap gate

由此得到控制交換門的輸出結(jié)果為:

設(shè)測量算子M1＝|1〉〈1|,并且有,則:

由p(m)可以得到第一位量子比特為1的概率為,由于量子態(tài)c是k個聚類中心點量子態(tài)c i的疊加,則〈x0|c〉為x0與c i的余弦值,這里定義為s(x0,c i),用于描述x0與c i的相似度,當(dāng)s(x0,c i)值越小,其x0與c i的余弦值〈x0|c〉就越大,兩者就越相似。由此,控制交換門的輸出可以表示為:

接下來將相位估計算法作用在φ上,使相似度信息存儲在量子比特上[21]。相位估計算法用于求解給定向量的相位,其實現(xiàn)原理主要是基于量子Fourier變換技術(shù)。量子Fourier主要是實現(xiàn)如下形式的變換:

將量子態(tài)φ作為相位估計算法的輸入,可以得到:

由此可將c i與x0之間的相似度存儲于量子比特上,即越小,兩者之間的相似度越大;同理越大,兩者的相似度越小。由于相位估計的過程主要是Grover迭代的過程,即需要相應(yīng)的Oracle操作,其計算量與估計的精度有關(guān);當(dāng)精度值確定后,其計算量則為常數(shù),這里假設(shè)其需要的Oracle操作的次數(shù)為R′。

2.3 相似度最大值查找

量子態(tài)α中保存的k個值,可以看作是一個規(guī)模為k的無序數(shù)據(jù)庫的疊加態(tài),其中使達(dá)到最小的c i便是與x0最為相似的聚類中心,即兩者之間的相似度最大。如果利用經(jīng)典查找算法查找與x0最相似的c i,需要的時間復(fù)雜度為O(k)。而最小值查找量子算法作為Grover算法的一個擴展算法,其可以的時間復(fù)雜度從無序數(shù)據(jù)庫中查找出最小值[22]。

利用量子最小值查找算法從量子態(tài)α中查找最小值的步驟如下:首先隨機選取一個聚類中心c j作為初始值,然后重復(fù)以下步驟次:

(1)制備初始值c j的量子態(tài)為β。

(2)α、β作為輸入,b作為控制輸入,利用Grover算法查找到。

圖2 查找最相似的聚類中心Fig.2 Find the maximum of similarity to cluster center

相應(yīng)的量子搜索算法模型如圖2所示。此時找到的c j為與x0最近的聚類中心點,將x0歸于c j所屬的類別。

3 算法復(fù)雜度分析

兩種算法的時間復(fù)雜度和空間復(fù)雜度對比結(jié)果如表1所示。

表1 兩種算法的復(fù)雜度比較Table 1 Comparison of complexity of two algorithms

3.1 時間復(fù)雜度

經(jīng)典k-means算法中的主要計算步驟為第(2)(3)步。其中第(2)步,即對于每一個具有d個特征值的數(shù)據(jù)點x i,都要計算其與k個聚類中心的相似度,該步計算的時間復(fù)雜度為O(kd)。算法第(3)步是從k個相似度中查找最大值,其時間復(fù)雜度為O(k),文獻(xiàn)[23,24]主要是對該步驟利用量子搜索算法對其加速,使該步驟的時間復(fù)雜度降到,但是該步驟的加速并不會使整個算法的時間復(fù)雜度提高。對于數(shù)據(jù)規(guī)模為n需要迭代t次的聚類過程,經(jīng)典k-means算法的時間復(fù)雜度為O(tnkd)。

本文提出的量子k-means算法,將被聚類的每一個數(shù)據(jù)點x i與k個聚類中心制備成相應(yīng)的量子疊加態(tài),需要的Oracle操作次數(shù)為6次。由于量子計算其內(nèi)生的計算并行性,則對于每一個數(shù)據(jù)點x i,利用控制交換門計算其與k個聚類中心的相似度,只需要一步計算即可得到。得到的相似度只是作為一個中間值,并不會對其直接測量,而是利用相位估計算法將其存儲于量子比特中,該步的結(jié)果被直接用于查找與x i相似度最大的聚類中心點。相位估計算法需要的Oracle操作次數(shù)為常數(shù)R′,查找最相似的聚類中心需要的時間復(fù)雜度為。設(shè)6＋R′＝R,則量子k-means算法主要步驟的計算復(fù)雜度為,整個量子k-means算法的時間復(fù)雜度為。對比兩種算法的時間復(fù)雜度,可以得到:當(dāng)時,即時,量子k-means算法的計算速度快,且k和d越大,這種效果就越明顯,量子k-means算法的時間復(fù)雜度就越低。

3.2 空間復(fù)雜度

在經(jīng)典k-means算法中,對于任意數(shù)據(jù)點x i,假設(shè)一個特征值需要占據(jù)一個字節(jié)的內(nèi)存空間,則x i需要的內(nèi)存空間為d字節(jié);由于要計算其與k個聚類中心的距離,那么其需要的內(nèi)存應(yīng)該為(k＋1)d字節(jié)＝8(k＋1)d比特。而對于量子k-means算法,任一數(shù)據(jù)點x i的量子態(tài)所需要的內(nèi)存為(2＋log2d)比特,k個聚類中心的量子態(tài)所需要的內(nèi)存為(2＋log2d＋log2k)比特,即第一步總共需要的最大內(nèi)存為(4＋2 log2d＋log2k) 比特。對比8(k＋1)d和(4＋2 log2d＋log2k)可以看到,量子算法的空間復(fù)雜度達(dá)到指數(shù)級降低。

4 結(jié)束語

本文在k-means算法的主要步驟中引入量子計算相關(guān)理論,得到k-means算法的量子化版本。首先給出了任一聚類數(shù)據(jù)x i和k個聚類中心的量子態(tài)制備過程,然后給出了x i和這k個聚類中心距離的相似度計算過程,并利用相位估計算法將相似度轉(zhuǎn)換成量子比特,最后,利用最小值查找量子算法查找出最相似的聚類中心點并將其歸于所屬的類別。對兩種算法的時間復(fù)雜度進(jìn)行理論分析和比較可以得到,在k和d比較大的情況下,量子k-means算法相對經(jīng)典算法的時間復(fù)雜度得到降低,且k和d越大,這種效果越明顯;而量子k-means的空間復(fù)雜度相對經(jīng)典算法則可以達(dá)到指數(shù)級降低。

[1]王書浩,龍桂魯.大數(shù)據(jù)與量子計算[J].科學(xué)通報,2015,60(5):499-508.Wang Shu-hao,Long Gui-lu.Big data and quantum computation[J].Chin Sci Bull,2015,60(5):499-508.

[2]Anguita D,Ridella S,Rivieccio F,et al.Quantum optimization for training support vector machines[J].Neural Networks,2003,16(5/6):763-770.

[3]Grover L K.A fast quantum mechanical algorithm for database search[C]∥Proc 28th Ann ACM Symp Theory of Computing,New York,USA,1996:212-219.

[4]Rebentrost P,Mohseni M,Lloyd S.Quantum support vector machine for big data classification[J].Physical Review Letters,2014,113(13):130503.

[5]Lu S,Braunstein S L.Quantum decision tree classifier[J].Quantum Information Processing,2014,13(3):757-770.

[6]阮越,陳漢武,劉志昊,等.量子主成分分析算法[J].計算機學(xué)報,2014,37(3):666-676.Ruan Yue,Chen Han-wu,Liu Zhi-hao,et al.Quantum principal component analysis algorithm[J].Chinese Journal of Computers,2014,37(3):666-676.

[7]徐永振,郭躬德,蔡彬彬,等.基于一維三態(tài)量子游走的量子聚類算法[J].計算機科學(xué),2016,43(3):80-83.Xu Yong-zhen,Guo Gong-de,Cai Bin-bin,et al.Quantum clustering algorithm based on one-dimensional three-state quantum walk[J].Computer Science,2016,43(3):80-83.

[8]Elhaddad M E,Mohammed S A O.Analysing the impact of quantum computing using system dynamics[C]∥Engineering&MIS(ICEMIS),IEEE,2016:1-5.

[9]Jain A K,Murty M N,Flynn P J.Data clustering:a review[J].ACM Computing Surveys(CSUR),1999,31(3):264-323.

[10]許美慧,尹建芹,張玲,等.可處理暗腔的日冕物質(zhì)拋射檢測新方法[J].光學(xué)精密工程,2016,24(10s):591-599.Xu Mei-hui,Yin Jian-qin,Zhang Ling,et al.New detection method for coronal mass ejection capable of dark cavity processing[J].Optics and Precision Engineering,2016,24(10s):591-599.

[11]王麗.融合底層和中層字典特征的行人重識別[J].中國光學(xué),2016,9(5):540-546.Wang Li.Pedestrian re-identification based on fusing low-level and mid-level features[J].Chinese Optics,2016,9(5):540-546.

[12]Wu X,Kumar V,Quinlan J R,et al.Top 10 algorithms in data mining[J].Knowledge and Information Systems,2008,14(1):1-37.

[13]秦大同,詹森,漆正剛,等.基于K-均值聚類算法的行駛工況構(gòu)建方法[J].吉林大學(xué)學(xué)報:工學(xué)版,2016,46(2):383-389.Qin Da-tong,Zhan Sen,Qi Zheng-gang,et al.Driving cycle construction using K-means clustering method[J].Journal of Jilin University(Engineering and Technology Edition),2016,46(2):383-389.

[14]趙文昌,李忠木.融合改進(jìn)人工蜂群和K均值聚類的圖像分割[J].液晶與顯示,2017,32(9):726-735.Zhao Wen-chang,Li Zhong-mu.Image segmentation algorithm based on improved artificial bee colony and K-mean clustering[J].Chinese Journal of Liquid Crystals and Displays,2017,32(9):726-735.

[15]丁有偉,秦小麟,劉亮,等.一種異構(gòu)集群中能量高效的大數(shù)據(jù)處理算法[J].計算機研究與發(fā)展,2015,52(2):377-390.Ding You-wei,Qin Xiao-lin,Liu Liang,et al.An energy efficient algorithm for big data processing in heterogeneous cluster[J].Journal of Computer Research and Development,2015,52(2):377-390.

[16]Forrest W.How to cut datacentre carbon emissions?[EB/OL].[2014-12-08].http∥www.computerweekly.com/Articles/2008/12/05/233748/how-tocut-data-centre carbon－emissions.htm

[17]A?meur E,Brassard G,Gambs S.Machine learning in a quantum world[J].Advances in Artificial Intelligence,2006,4013:431-442.

[18]A?meur E,Brassard G,Gambs S.Quantum clustering algorithms[C]∥Proceedings of the 24th International Conference on Machine Learning,2007:1-8.[19]A?meur E,Brassard G,Gambs S.Quantum speed-up for unsupervised learning[J].Machine Learning,2013,90(2):261-287.

[20]Lloyd S,Mohseni M,Rebentrost P.Quantum algorithms for supervised and unsupervised machine learning[J].ar Xiv,2013:1307.0411.

[21]Brassard G,Hoyer P,Mosca M,et al.Quantum amplitude amplification and estimation[J].Contemporary Mathematics,2002,305:53-74.

[22]Durr C,Hoyer P.A quantum algorithm for finding the minimum[J/OL].[2016-07-11].https:∥arxiv.org/abs/quant-ph/9607014.

[23]李強,蔣靜坪.量子K最近鄰算法[J].系統(tǒng)工程與電子技術(shù),2008,30(5):940-943.Li Qiang,Jiang Jing-ping.Quantum K nearest neighbor algorithm[J].Systems Engineering and Electronics,2008,30(5):940-943.

[24]陳漢武,高越,張軍.量子K-近鄰算法[J].東南大學(xué)學(xué)報:自然科學(xué)版,2015,45(4):647-651.Chen Han-wu,Gao Yue,Zhang Jun.Quantum K-nearest neighbor algorithm[J].Journal of Southeast University(Natural Science Edition),2015,45(4):647-651.