基于量子計(jì)算加速的DDC算法

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

?

基于量子計(jì)算加速的DDC算法

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

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京，210016)

考慮到量子計(jì)算具有超強(qiáng)的并行計(jì)算能力，擬引入量子計(jì)算以降低局部密度和delta距離度量的聚類算法(DDC)計(jì)算復(fù)雜度。DDC算法的局部密度求解過程是計(jì)數(shù)算法，提出利用量子計(jì)數(shù)算法加速局部密度的求解；delta距離是最小值查找的過程，提出利用最小值查找量子算法加速delta距離的求解。研究結(jié)果表明：利用量子計(jì)算對(duì)DDC聚類算法進(jìn)行加速，能夠使算法的執(zhí)行效率獲得顯著提升。

局部密度；delta距離；聚類算法；量子計(jì)算；加速

聚類作為一種常見的數(shù)據(jù)分析處理技術(shù)，依據(jù)一定的相似性度量將數(shù)據(jù)劃分成若干類，以發(fā)現(xiàn)其中潛在的規(guī)律[1]，其廣泛應(yīng)用于圖像處理、模式識(shí)別和社交網(wǎng)絡(luò)等領(lǐng)域。常見的聚類算法或存在易陷于局部極值、對(duì)初始值敏感、不能自動(dòng)確定簇的數(shù)量或存在嚴(yán)重依賴數(shù)據(jù)分布等缺點(diǎn)[2]，如k-means，F(xiàn)CM和DBSCAN等。RODRIGUEZ等[3]提出一種基于局部密度和delta距離度量的聚類算法(density & distance clustering，DDC)。與其他聚類算法相比較，DDC聚類算法具有數(shù)據(jù)分布自適應(yīng)、無需設(shè)置初始值且能自動(dòng)識(shí)別簇的數(shù)量等優(yōu)點(diǎn)，其一經(jīng)提出便得到聚類研究者的極大關(guān)注及廣泛應(yīng)用。CHENG等[4]將DDC算法用于超網(wǎng)絡(luò)中的社群檢測中，通過利用DDC算法計(jì)算超網(wǎng)絡(luò)中各節(jié)點(diǎn)的密度和距離來構(gòu)建一種稱為密度排序樹的結(jié)構(gòu)(density-ordered tree, DOT)以表示原始數(shù)據(jù)，使社群檢測問題轉(zhuǎn)換成DOT劃分問題。CHEN等[5]將DDC算法應(yīng)用于面部年齡的估計(jì)中，先將面部特征轉(zhuǎn)換為LBP 集合，利用DDC算法從LBP集合中發(fā)現(xiàn)每個(gè)年齡組的密度峰值，根據(jù)到密度峰值的距離來估計(jì)每張面部圖片的年齡。WANG等[6]將DDC算法用于社交網(wǎng)絡(luò)，利用DDC算法計(jì)算社交網(wǎng)絡(luò)中每個(gè)用戶的距離和密度以發(fā)現(xiàn)其所屬的社交圈。在現(xiàn)今的大數(shù)據(jù)時(shí)代，巨大的數(shù)據(jù)量為聚類的速度帶來了巨大的挑戰(zhàn)，為應(yīng)對(duì)這種挑戰(zhàn)，目前較為普遍的策略是采用云計(jì)算的模式對(duì)大數(shù)據(jù)進(jìn)行并行聚類[7]?？墒牵朴?jì)算的硬件基礎(chǔ)設(shè)施所產(chǎn)生的巨大的能量消耗問題又帶來新的挑戰(zhàn)[8?9]。考慮到量子計(jì)算具有超強(qiáng)的并行計(jì)算能力，計(jì)算的可逆性也不會(huì)帶來面臨能量消耗問題[10]，近年來，量子計(jì)算受到研究者越來越多的關(guān)注，并被應(yīng)用到各個(gè)領(lǐng)域以達(dá)到加速的目的[11?15]。DDC作為一種具有全新的、聚類效果優(yōu)良的算法，目前為止仍未檢索到量子計(jì)算對(duì)其加速的研究，本文提出利用量子計(jì)算的相關(guān)理論加速DDC算法。提出分別利用量子計(jì)數(shù)算法和最小值量子查找算法去加速DDC算法中的局部密度和delta距離這2個(gè)參數(shù)的計(jì)算，使其在大數(shù)據(jù)環(huán)境下不但聚類效果優(yōu)良，且聚類速度更快。

1 基礎(chǔ)知識(shí)

1.1 DDC算法

1.2 量子算法

接下來迭代執(zhí)行以下4步，迭代過程稱之為Grover迭代：

1) 應(yīng)用量子黑箱；

2) 應(yīng)用Hadamard變換后得到

2 量子計(jì)算加速DDC算法

本節(jié)給出量子計(jì)算加速DDC算法的方案，即對(duì)每個(gè)數(shù)據(jù)點(diǎn)提出利用量子計(jì)數(shù)算法加速求解其局部密度，利用最小值查找量子算法加速求解其delta距離。

2.1 量子計(jì)數(shù)算法加速求解局部密度

圖2 兩比特量子尋址方案

算法1：求解局部密度的量子計(jì)數(shù)算法

2) 量子黑箱Oracle1。

過程：

2.2 最小值查找量子算法加速求解delta距離

最小值查找量子算法通常利用保存搜索問題的解空間；但是在DDC算法中，delta距離的解由

算法2：求解delta距離的最小值查找量子算法

3) 量子黑箱Oracle2。

輸出：測量第四寄存器的值。

過程：

3 算法分析

3.1 量子計(jì)數(shù)算法加速求解局部密度的算法分析

將式(5)與(8)代入式(7)可以得到

3.2 最小值查找量子算法加速求解delta距離的算法分析

4 結(jié)論

1) 利用量子計(jì)算的相關(guān)算法對(duì)這一新穎的、可以自動(dòng)識(shí)別簇?cái)?shù)且數(shù)據(jù)分布自適應(yīng)的DDC算法進(jìn)行加速，對(duì)算法的2個(gè)主要參數(shù)即局部密度和delta距離的計(jì)算過程給出了量子計(jì)算的加速方案，利用量子計(jì)數(shù)算法加速求解局部密度，利用最小值查找量子算法加速求解delta距離。

2) 經(jīng)過量子計(jì)算加速后，DDC算法的執(zhí)行效率顯著提升。

[1] JAIN A K, DUBES R C. Algorithms for clustering data[M]. New Jersey: Prentice-Hall, Englewood Cliffs, 1988: 45?46.

[2] XU Dongkuan, TIAN Yingjie. A comprehensive survey of clustering algorithms[J]. Annals of Data Science, 2015, 2(2): 165?193.

[3] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492?1496.

[4] CHENG Qing, LIU Zhong, HUANG Jincai, et al. Community detection in hypernetwork via Density-Ordered Tree partition[J]. Applied Mathematics and Computation, 2016, 276: 384?393.

[5] CHEN Yewang, LAI Dehe, QI Han, et al. A new method to estimate ages of facial image for large database[J]. Multimedia Tools and Applications, 2016, 75(5): 2877?2895.

[6] WANG Mengmeng, ZUO Wanli, WANG Ying. An improved density peaks-based clustering method for social circle discovery in social networks[J]. Neurocomputing, 2016, 179: 219?227.

[7] GHULIA P, SHUKLAA A, KIRANA R, et al. Multidimensional canopy clustering on iterative MapReduce framework using Elefig tool[J]. IETE Journal of Research 2015, 61(1): 14?21.

[8] 丁有偉, 秦小麟, 劉亮, 等. 一種異構(gòu)集群中能量高效的大數(shù)據(jù)處理算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(2): 377?390. DING Youwei, QIN Xiaolin, 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.

[9] FORREST W. How to cut data centre carbon emissions 2008 [EB/OL]. [2014?12?08]. http//www.computerweekly.com/ Articles/ 2008/12/05/233748/how-tocut-data-centre carbon—emissions. htm.

[10] Nielsen M A, Chuang I L. Quantum computation and quantum information[M]. Cambridge, UK: Cambridge University Press, 2010: 221?263.

[11] ANGUITA D, RIDELLA S, RIVIECCIO F, et al. Quantum optimization for training support vector machines[J]. Neural Networks, 2003, 16(5): 763?770.

[12] REBENTROST P, MOHSENI M, LLOYD S. Quantum support vector machine for big data classification[J]. Physical review letters, 2014, 113(13): 130503.

[13] YOO S, BANG J, LEE C, et al. A quantum speedup in machine learning: finding an N-bit Boolean function for a classification[J]. 2014, 16(10): 103014?103028.

[14] LU S, BRAUNSTEIN S L. Quantum decision tree classifier[J]. Quantum information processing, 2014, 13(3): 757?770.

[15] 阮越, 陳漢武, 劉志昊, 等. 量子主成分分析算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(3): 666?676.RUAN Yue, CHEN Hanwu, LIU Zhihao, et al. Quantum principal component analysis algorithm[J]. Chinese Journal of Computers, 2014, 37(3): 666?676.

[16] GROVER L K. A fast quantum mechanical algorithm for database search[C]// Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. ACM. Philadelphia, Pennsylvania , USA, 1996: 212?219.

[17] BOYER M, BRASSARD G, H?YER P, et al. Tight bounds on quantum searching[J]. Progress of Physics, 1998, 46(4/5): 493?505.

[18] DURR C, HOYER P. A quantum algorithm for finding the minimum[EB/OL]. [1999?01?07]. https://arxiv.org/pdf/quant- ph/9607014.pdf.

[19] BRASSARD G, HOYER P, TAPP A. Quantum counting[C]// International Colloquium on Automata, Languages, and Programming. Berlin Heidelberg: Springer, 1998: 820?831.

Speed up DDC based on quantum computing

LIU Xuejuan, YUAN Jiabin, XU Juan, DUAN Bojia

(College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)

The purpose was to improve the efficiency of local density and delta distance based clustering (DDC) by using the quantum computation, which was characterized by the great performance of the parallel computation. First, the quantum counting algorithm was developed to accelerate the processing of local density for each data point. Then, the quantum algorithm for finding the minimum was incorporated to find each point’s delta distance. The results show that the efficiency of DDC can be improved significantly by using quantum computation to accelerate DDC algorithm.

localdensity; delta distance; clustering algorithm; quantum computation; speed up

10.11817/j.issn.1672-7207.2018.07.014

TP387

A

1672?7207(2018)07?1677?06

2017?07?04；

2017?09?17

國家自然科學(xué)基金資助項(xiàng)目(61571226，61572053，61701229，61702367)；江蘇省自然科學(xué)基金資助項(xiàng)目(BK20170802，BK20140823) (Projects(61571226, 61572053, 61701229, 61702367) supported by the National Natural Science Foundation of China; Projects(BK20170802, BK20140823) supported by the National Science Foundation of Jiangsu Province, China)

劉雪娟，博士研究生，從事量子計(jì)算、機(jī)器學(xué)習(xí)等研究；E-mail: liu_juanjuan80@126.com

(編輯 楊幼平)