動點聚類算法及其量子化研究.pdf

1、數(shù)據(jù)聚類是模式識別的重要分支，它在模式分析、數(shù)據(jù)挖掘、信息獲取、圖像分割、決策等領(lǐng)域都有重要的應(yīng)用。而這些領(lǐng)域的問題，通常都沒有關(guān)于數(shù)據(jù)的先驗知識可供利用。正是由于實際問題存在這些難以逾越的限制條件，因此，數(shù)據(jù)聚類應(yīng)運而生，它特別適合對未標(biāo)記數(shù)據(jù)點間的關(guān)系進行探索。數(shù)據(jù)聚類就是研究如何對未標(biāo)記的數(shù)據(jù)進行分組或分類的學(xué)科，它不需要事先提供任何標(biāo)記的樣本，聚類的任務(wù)就是找出大量數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，將這些未標(biāo)記的數(shù)據(jù)點聚合成有意義的類別，以對它們

2、的結(jié)構(gòu)進行評價。在典型的聚類算法中，用于聚類的數(shù)據(jù)點是固定不動的，通過設(shè)計函數(shù)找到聚類中心或邊界。然而，近年來，一些研究者提出動點聚類的新思想，他們將數(shù)據(jù)點考慮為自身可移動的Agent，通過設(shè)計簡單規(guī)則，讓數(shù)據(jù)點自動完成聚類。
　　 另一方面，量子計算的研究方興未艾，在過去十年間，量子計算取得了一系列驚人的成就，以奇特的量子效應(yīng)，如量子內(nèi)在并行性、量子糾纏等為基礎(chǔ)的量子算法，已經(jīng)提供了量子計算可能比經(jīng)典計算更強大的有力證據(jù)。如S

3、hor的大數(shù)質(zhì)因子分解量子算法，將經(jīng)典計算中的NP完全問題轉(zhuǎn)化為一個P問題，以多項式時間完成經(jīng)典算法指數(shù)時間才能完成的任務(wù)。這些成就讓我們意識到量子算法可能比已知最好的經(jīng)典算法更快更好地解決問題，甚至解決某些經(jīng)典計算無法有效解決的問題。更重要的是，它提供了一條尋找潛在算法加速的新途徑。
　　 本文的研究主要分為兩個部分：(1)經(jīng)典世界中的動點聚類算法。受近年來興起的動點聚類思想的啟發(fā)，本文提出基于改進隨機游動模型，基于復(fù)雜網(wǎng)絡(luò)上

4、的Flocking，基于演化網(wǎng)絡(luò)上的博弈等幾種動點聚類算法。(2)量子世界中的聚類算法。受量子計算已取得的驚人成就的鼓舞，本文將數(shù)據(jù)聚類問題與量子計算結(jié)合起來，提出基于量子隨機游動和基于量子博弈的聚類算法，它們也可以看作是本文提出的兩種經(jīng)典世界中的動點聚類算法的量子化。本文的主要研究內(nèi)容概括如下：
　　 (1)基于改進隨機游動模型的聚類算法。隨機游動是一類特殊的隨機過程，本文提出一種改進的隨機游動模型，并基于此模型建立聚類算法，

5、并證明了算法的收斂性。算法中，數(shù)據(jù)點既是圖的頂點，又是可移動的粒子，因而數(shù)據(jù)點形成的圖的形狀將隨時間變化。每個移動的數(shù)據(jù)點又可以看作是一個局域控制系統(tǒng)，通過控制器調(diào)整轉(zhuǎn)移概率并確定下一步的轉(zhuǎn)移方向。當(dāng)數(shù)據(jù)點根據(jù)簡單規(guī)則在空間中作隨機游動時，相似的數(shù)據(jù)點逐漸游動到同一個位置，并穩(wěn)定下來形成一個聚類，而不同的聚類則相互遠離。最后，當(dāng)算法收斂時，聚類也就自動形成。
　　 (2)基于復(fù)雜網(wǎng)絡(luò)上的Flocking聚類算法。復(fù)雜網(wǎng)絡(luò)是近年提

6、出的一種描述社會網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，本文將數(shù)據(jù)點考慮為可移動的Agent，并且為每個Agent添加長程鏈接，從而將它們之間的關(guān)系用一個時變的復(fù)雜網(wǎng)絡(luò)來表示。由此，將經(jīng)典Flocking模型推廣到復(fù)雜網(wǎng)絡(luò)拓撲上，進而研究了一種基于復(fù)雜網(wǎng)絡(luò)上的Flocking聚類算法。復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)不僅為數(shù)據(jù)聚類提供了新的拓撲，更重要的是，復(fù)雜網(wǎng)絡(luò)中的長程鏈接還為數(shù)據(jù)點提供了無法直接感知的隱含信息，并且加快了算法的收斂速度。最后，數(shù)據(jù)點會在算法收斂時，自動形成

7、分離的群落，每個群落對應(yīng)一個聚類。
　　 (3)基于演化網(wǎng)絡(luò)上的博弈聚類算法。演化博弈理論植根于對生物界中動植物的競爭與合作現(xiàn)象的研究，本文將數(shù)據(jù)點看作有一定決策能力的博弈參與人，提出一種基于演化網(wǎng)絡(luò)上的博弈聚類算法。每個博弈參與人的目的都是使自己的收益最大化，通過觀察周圍鄰居的收益，斷掉與低收益鄰居的連邊，而重新與有高收益的鄰居相連，從而使得網(wǎng)絡(luò)開始演化。在博弈參與人不斷調(diào)整自己連邊的過程中，某些策略會在網(wǎng)絡(luò)中傳播，并最終成為

8、演化穩(wěn)定策略。聚類在參與人博弈的過程中自然涌現(xiàn)，最后，采用相同演化穩(wěn)定策略的數(shù)據(jù)點被分為一類，演化穩(wěn)定策略的個數(shù)對應(yīng)了聚類的類數(shù)。
　　 (4)基于量子隨機游動的聚類算法。量子隨機游動是經(jīng)典隨機游動的量子模擬，本文將量子隨機游動與數(shù)據(jù)聚類結(jié)合起來，提出一種基于量子隨機游動的聚類算法。量子隨機游動與經(jīng)典隨機游動的區(qū)別在于，它的演化是酉的和可返的，而且，可能的經(jīng)典路徑在量子隨機游動中產(chǎn)生相干。這就使得在量子隨機游動中，粒子位置的概率

9、分布與經(jīng)典情況完全不同，這就為量子聚類算法得到更好的結(jié)果提供了機會。本文首先研究了兩個基于一維量子隨機游動的聚類算法，然后將一維量子隨機游動推廣到高維，從而建立基于高維隨機游動的聚類算法，最后討論了參數(shù)對聚類算法的影響。
　　 (5)基于量子博弈的聚類算法。量子博弈是經(jīng)典博弈的量子模擬，在提出的基于量子博弈的聚類算法中，數(shù)據(jù)點作為可以使用量子策略的博弈參與人與對手進行2×2量子博弈。量子博弈利用量子糾纏態(tài)，使得博弈雙方在使用量子