亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于量子計算加速的DDC算法

        2018-08-08 08:28:04劉雪娟袁家斌許娟段博佳
        中南大學學報(自然科學版) 2018年7期
        關(guān)鍵詞:利用

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

        ?

        基于量子計算加速的DDC算法

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

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

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

        局部密度;delta距離;聚類算法;量子計算;加速

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

        1 基礎(chǔ)知識

        1.1 DDC算法

        1.2 量子算法

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

        1) 應用量子黑箱;

        2) 應用Hadamard變換后得到

        2 量子計算加速DDC算法

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

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

        圖2 兩比特量子尋址方案

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

        2) 量子黑箱Oracle1。

        過程:

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

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

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

        3) 量子黑箱Oracle2。

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

        過程:

        3 算法分析

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

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

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

        4 結(jié)論

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

        2) 經(jīng)過量子計算加速后,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]. 計算機研究與發(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]. 計算機學報, 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

        國家自然科學基金資助項目(61571226,61572053,61701229,61702367);江蘇省自然科學基金資助項目(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)

        劉雪娟,博士研究生,從事量子計算、機器學習等研究;E-mail: liu_juanjuan80@126.com

        (編輯 楊幼平)

        猜你喜歡
        利用
        利用min{a,b}的積分表示解決一類絕對值不等式
        利用倒推破難點
        如何利用基本不等式比較大小
        利用一半進行移多補少
        利用口訣算除法
        利用數(shù)的分解來思考
        Roommate is necessary when far away from home
        利用
        回收木再利用——Piet Hein Eek
        低丘緩坡未利用地的開發(fā)利用探討
        河北遙感(2015年4期)2015-07-18 11:05:06
        中文字幕国产亚洲一区| 国产a级精精彩大片免费看| 免费人人av看| 成人做爰黄片视频蘑菇视频| 四虎国产成人永久精品免费| 色视频www在线播放国产人成| 国产肉体XXXX裸体784大胆| 亚洲天堂av在线一区| 国产在线无码精品无码| 国产情侣久久久久aⅴ免费| 99久久综合九九亚洲| 一区二区在线观看日本免费| 97色伦图片97综合影院| 成年无码av片完整版| 久久99精品中文字幕在| 综合成人亚洲网友偷自拍| 久久久久亚洲av综合波多野结衣| 国产乱妇乱子视频在播放| 深夜福利国产| 日本在线观看一二三区| 久久天堂综合亚洲伊人hd妓女| 亚洲色图+国产精品| 97人妻蜜臀中文字幕| 免费在线观看视频播放| 色八区人妻在线视频免费| 丰满少妇爆乳无码专区| 99久久精品人妻一区二区三区 | 亚洲av成人无遮挡网站在线观看| 综合三区后入内射国产馆| 国产av大片在线观看| 一区二区亚洲精品在线| 精品9e精品视频在线观看| 国产精品无码专区综合网| 好看的中文字幕中文在线| 无码熟妇人妻av在线影片最多| 亚洲暴爽av天天爽日日碰| 国产福利一区二区三区视频在线看| 一区二区三区四区中文字幕av| 天天天天躁天天爱天天碰2018| 国产成人亚洲精品77| 日本女优久久精品久久|