量子k-means算法

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

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

0 引 言

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

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

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

1 經典k-means算法

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

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

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

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

(4)數據集中的所有數據經過步驟(2)(3)計算后,根據數據集的類別標號重新計算新的聚類中心。

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

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

2 本文算法

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

2.1 量子態制備

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

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

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

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

設2m＝k,2n＝d,量子態|c〉的制備過程如下:

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

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

量子黑箱Oracle定義為:

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

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

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

2.2 相似性計算

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

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

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

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

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

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

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

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

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

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

2.3 相似度最大值查找

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

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

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

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

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

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

3 算法復雜度分析

兩種算法的時間復雜度和空間復雜度對比結果如表1所示。

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

3.1 時間復雜度

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

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

3.2 空間復雜度

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

4 結束語

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

[1]王書浩,龍桂魯.大數據與量子計算[J].科學通報,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].計算機學報,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]徐永振,郭躬德,蔡彬彬,等.基于一維三態量子游走的量子聚類算法[J].計算機科學,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]許美慧,尹建芹,張玲,等.可處理暗腔的日冕物質拋射檢測新方法[J].光學精密工程,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].中國光學,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-均值聚類算法的行駛工況構建方法[J].吉林大學學報:工學版,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]趙文昌,李忠木.融合改進人工蜂群和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]丁有偉,秦小麟,劉亮,等.一種異構集群中能量高效的大數據處理算法[J].計算機研究與發展,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].系統工程與電子技術,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].東南大學學報:自然科學版,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.