一種基于量子進(jìn)化算法改進(jìn)的k-mean聚類算法?

張睿哲，楊照峰，趙偉艇

（1.平頂山學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，平頂山467002；2.平頂山學(xué)院軟件學(xué)院，平頂山467002）

一種基于量子進(jìn)化算法改進(jìn)的k-mean聚類算法?

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

（1.平頂山學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，平頂山467002；2.平頂山學(xué)院軟件學(xué)院，平頂山467002）

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

量子進(jìn)化算法；聚類算法；量子計(jì)算；數(shù)據(jù)挖掘；進(jìn)化優(yōu)化

1 引 言

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

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

提出了一種基于量子進(jìn)化算法的改進(jìn)的K-means聚類算法。該方法結(jié)合了兩個方法的優(yōu)點(diǎn)，用量子進(jìn)化算法進(jìn)行優(yōu)化，并且改進(jìn)了量子進(jìn)化算法中的交叉算子和更新算子，提高了基于量子進(jìn)化算法的K-means算法的局部搜索能力。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法取得了較好的效果。

2 k-mean算法簡介

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

輸入：簇的數(shù)目k和包含n個對象的數(shù)據(jù)庫。

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

方法：

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

（2）repeat

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

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

（5）until不再發(fā)生變化。

設(shè)目標(biāo)函數(shù)：

其中，聚類中心

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

N為樣本（記錄）數(shù)；

c為聚類中心數(shù)（2≤c≤N-1）。

3 基于量子進(jìn)化算法改進(jìn)的聚類算法

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

3.1 染色體構(gòu)造

用a＝（a1，a2，...，aN）表示遺傳算法的染色體結(jié)構(gòu)，用染色體來動態(tài)確定聚類數(shù)目。例如，設(shè)染色體長度為6，那么，當(dāng)染色體為｛1，2，1，3，2，1｝，聚類數(shù)目c為3；當(dāng)染色體為｛1，4，1，6，4，1｝，聚類數(shù)目c為3；當(dāng)染色體為｛1，5，1，3，2，1｝，聚類數(shù)目c為4。

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

3.2 群體初始化

群體初始化是遺傳算法最基本的步驟。從待分類的點(diǎn)中隨機(jī)選擇K個點(diǎn)作為問題的一個解并編碼為一個染色體。重復(fù)進(jìn)行這個操作，直到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 適應(yīng)度函數(shù)設(shè)計(jì)

使用類內(nèi)距與類間距之和作為目標(biāo)函數(shù)，即：

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

3.4 量子門更新策略

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

其中，Δθ為旋轉(zhuǎn)角，Δθ的具體計(jì)算如下：

其中t為進(jìn)化代數(shù)。

4 實(shí)驗(yàn)結(jié)果與分析

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

表1 數(shù)據(jù)1的實(shí)驗(yàn)結(jié)果

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

表2 數(shù)據(jù)集Iris的實(shí)驗(yàn)結(jié)果

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

5 結(jié)束語

提出了一種基于量子進(jìn)化算法的改進(jìn)的K-means聚類算法。該方法結(jié)合了兩個方法的優(yōu)點(diǎn)，用量子進(jìn)化算法進(jìn)行優(yōu)化，并且改進(jìn)了量子進(jìn)化算法中的交叉算子和更新算子，提高了基于量子進(jìn)化算法的K-means算法的局部搜索能力。實(shí)驗(yàn)結(jié)果表明改進(jìn)算法取得了較好的效果。

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

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

［3］傅濤，孫亞民.基于PSO的k-means算法及其在網(wǎng)絡(luò)入侵檢測中的應(yīng)用［J］.計(jì)算機(jī)科學(xué)，2011，38（5）：54-55，73.

［4］吳夙慧，成穎，鄭彥寧，等.K-means算法研究綜述［J］.現(xiàn)代圖書情報(bào)技術(shù)，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

河南省科技計(jì)劃重點(diǎn)項(xiàng)目（102102210416）

張睿哲（1971-），男，河南舞鋼人，講師，碩士，主研方向：計(jì)算機(jī)應(yīng)用技術(shù)、網(wǎng)絡(luò)管理體系結(jié)構(gòu)與管理機(jī)制方面的研究。

2014-01-16