一種基于量子進化算法改進的k-mean聚類算法?

張睿哲，楊照峰，趙偉艇

（1.平頂山學院計算機科學與技術學院，平頂山467002；2.平頂山學院軟件學院，平頂山467002）

一種基于量子進化算法改進的k-mean聚類算法?

張睿哲1，楊照峰2，趙偉艇2

（1.平頂山學院計算機科學與技術學院，平頂山467002；2.平頂山學院軟件學院，平頂山467002）

聚類分析是模式識別中的一個重要問題，是非監督學習的重要方法。K-means算法是其中最經典的聚類算法之一。但是這種方法面對大規模數據的時候工作量非常巨大，并且保證不了聚類結果的最優性。提出了一種基于量子進化算法的改進的K-means聚類算法。該方法結合了兩個方法的優點，用量子進化算法進行優化，并且改進了量子進化算法中的交叉算子和更新算子，提高了基于量子進化算法的K-means算法局部搜索能力。實驗結果表明，改進算法取得了較好的效果。

量子進化算法；聚類算法；量子計算；數據挖掘；進化優化

1 引 言

聚類分析是模式識別中的一個重要問題，是非監督學習的重要方法［1］。聚類分析的目標是將一個數據集劃分成若干個簇.使同一個簇中的對象盡可能地相似，而不同簇對象間的差異盡可能的大。聚類分析是通過無監督訓練將樣本按相似性分類［2］。

聚類分析根據基因功能對其進行分類以獲得對人群中所固有結構更深入的了解。可以幫助市場人員發現顧客群中存在不同特征的組群［3］。聚類還可以從地球觀測數據庫中幫助識別具有相似土地使用情況的區域。聚類分析是一種典型的組合優化問題，目前已有很多種聚類算法，主要分為［4］：劃分聚類、基于密度的聚類以及基于網格的聚類、層次聚類。劃分聚類中的K-means算法是其中最經典的聚類算法之一。該聚類算法首先根據一定的經驗準則選取某些聚類參數，但是這種方法面對大規模數據的時候工作量非常巨大，并且保證不了聚類結果的最優性。所以需要尋找一種能克服K—mean對初始化敏感這一缺點的全局優化算法。

提出了一種基于量子進化算法的改進的K-means聚類算法。該方法結合了兩個方法的優點，用量子進化算法進行優化，并且改進了量子進化算法中的交叉算子和更新算子，提高了基于量子進化算法的K-means算法的局部搜索能力。實驗結果表明，改進算法取得了較好的效果。

2 k-mean算法簡介

首先，隨機地選擇k個對象，每個對象初始地代表了一個簇的平均值或中心。對剩余的每個對象，根據其與各個簇中心的距離，將它賦給最近的簇。采用平方誤差函數的k-mean算法流程如下：

輸入：簇的數目k和包含n個對象的數據庫。

輸出：k個簇，是平方誤差函數最小。

方法：

（1）任意選擇k個對象作為初始簇中心；

（2）repeat

（3）根據簇中對象的平均值，將每個對象重新賦給最類似的簇；

（4）更新簇的平均值，即計算每個簇中對象的平均值；

（5）until不再發生變化。

設目標函數：

其中，聚類中心

nr為屬于r類的樣本（記錄）個數；

N為樣本（記錄）數；

c為聚類中心數（2≤c≤N-1）。

3 基于量子進化算法改進的聚類算法

近幾年來，一些學者研究將量子計算的概念引入進化算法和多目標進化算法中，從而提出諸多量子進化算法（Quantum-inspired Evolutionary Algorithms，QEA）［5-6］。

3.1 染色體構造

用a＝（a1，a2，...，aN）表示遺傳算法的染色體結構，用染色體來動態確定聚類數目。例如，設染色體長度為6，那么，當染色體為｛1，2，1，3，2，1｝，聚類數目c為3；當染色體為｛1，4，1，6，4，1｝，聚類數目c為3；當染色體為｛1，5，1，3，2，1｝，聚類數目c為4。

Step 0：設置遺傳算法的相關參數，max_gen：最大迭代次數；pop_size：群體大小；l_chrom：染色體長度；pc：交叉概率；pm：變異概率；c：初始聚類數目；w：在評價函數中的參數；gen＝0。

3.2 群體初始化

群體初始化是遺傳算法最基本的步驟。從待分類的點中隨機選擇K個點作為問題的一個解并編碼為一個染色體。重復進行這個操作，直到pop_size（種群的大小）個染色體全部被初始化。

Step 1：群體初始化

for i＝1 to pop_size do

for j＝1 to l_chrom do

染色體ai的第j位等位基因＝random（0，c）；

endfor

endfor

3.3 適應度函數設計

使用類內距與類間距之和作為目標函數，即：

其中，w為權重，它反映決策者的偏好。當w變大時，聚類數目c也增大；反之，c將減小。算法的目的是搜索J值最小的聚類中心，因此適應度函數為：1／J。

3.4 量子門更新策略

算法中采用量子旋轉門U（Δθ）更新個體，U（Δθ）定義如下［7］：

其中，Δθ為旋轉角，Δθ的具體計算如下：

其中t為進化代數。

4 實驗結果與分析

為了驗證上述算法的有效性，實驗數據分為兩組，第一組為某一數據庫中的記錄，第二組為Fisher的Iris植物樣本數據。對兩組數據分別使用K-mean算法和本文提出的遺傳聚類算法進行實驗。改進的算法有關參數設置如下：初始 c＝12、a＝0.2、pop_size＝30、k1＝k3＝0.9、k2＝k4＝0.1、gen_max＝1000。運行100次的平均收斂代數分別為163代和372代。實驗結果如表1所示。

表1 數據1的實驗結果

第二組數據是Fisher的Iris植物樣本數據，該數據由分別屬于三種植物的150個樣本組成，每個樣本均為四維模式向量，代表了植物的四種特征數據。用兩種算法分別做了3次實驗，實驗中遺傳算法的pop_size＝100，每次實驗的迭代次數為100次，其他參數不變，實驗結果如表2所示。

表2 數據集Iris的實驗結果

可以看出普通的K-mean算法對初值敏感，并且在三次運行中均收斂于不同的局部極優點。而本文改進的K-mean算法每次均能收斂到全局最優點。這表明了本文改進的K-mean算法與普通的K均值算法相比，具有較強的全局收斂性能。

5 結束語

提出了一種基于量子進化算法的改進的K-means聚類算法。該方法結合了兩個方法的優點，用量子進化算法進行優化，并且改進了量子進化算法中的交叉算子和更新算子，提高了基于量子進化算法的K-means算法的局部搜索能力。實驗結果表明改進算法取得了較好的效果。

［1］於躍成，王建東，鄭關勝，等.基于約束信息的并行k-means算法［J］.東南大學學報（自然科學版），2011，41（3）：505-508.

［2］陸林華，王波.一種改進的遺傳聚類算法［J］.計算機工程與應用，2007，43（21）：170-172.

［3］傅濤，孫亞民.基于PSO的k-means算法及其在網絡入侵檢測中的應用［J］.計算機科學，2011，38（5）：54-55，73.

［4］吳夙慧，成穎，鄭彥寧，等.K-means算法研究綜述［J］.現代圖書情報技術，2011，205（5）：30-35.

［5］Tony H.Quantum computing：all introduction［J］.Computing＆Control Engineering Journal，1996，10（3）：105-112.

［6］Narayanan A，Moore M.Quantum-inspired genetic algorithm［A］.Proc of IEEE International Conference on Evolutionary Computation［C］.Piscataway：IEEE Press，1996：61-66.

［7］Kuk-Hyun Han，Jong-Hwan Kim.Genetic Quantum Algorithmand its Application to Combinatorial Optimization Problem［C］.Proceedings of the 2000 Congress on Evolutionary Computation，2000：1354-l360.

An Im proved K-mean Clustering Algorithm Based on Quantum Evolutionary Algorithm

ZHANG Rui-zhe1，YANG Zhao-feng2，ZHAOWei-ting2
（1.Computer Science and Technology Academy，Pingdingshan University，Pingdingshan 467002，China；2.School of Software Engineering，Pingdingshan University，Pingdingshan 467002，China）

The cluster analysis is a key point in pattern recognition and an important method of unsupervised learning.The K-means algorithm is one of themost classical clustering algorithms，which produces huge workload from themassive data and cannot ensure the optimality of the clustering results.This paper proposes a quantum evolutionary algorithm based on improved K-means clustering algorithm which combining such advantages as optimized quantum evolutionary algorithm，the improved crossover operator and update operator in quantum evolutionary algorithm for improving the quantum evolutionary algorithm based on K-means algorithm local search ability.The experimental results show that the improved algorithm achieves good effect.

Quantum evolutionary algorithm；Clustering algorithm；Quantum computing；Data mining；Evolutionary optimization

10.3969／j.issn.1002-2279.2014.04.023

TP393

：A

：1002-2279（2014）04-0071-03

河南省科技計劃重點項目（102102210416）

張睿哲（1971-），男，河南舞鋼人，講師，碩士，主研方向：計算機應用技術、網絡管理體系結構與管理機制方面的研究。

2014-01-16