汪凌

1.北京交通大學(xué)中國產(chǎn)業(yè)安全研究中心，北京 100044

2.固體廢物處理與環(huán)境安全教育部重點實驗室，北京 100084

一種基于改進粒子群的連續(xù)屬性離散化算法

汪凌

1.北京交通大學(xué)中國產(chǎn)業(yè)安全研究中心，北京 100044

2.固體廢物處理與環(huán)境安全教育部重點實驗室，北京 100084

1 引言

決策系統(tǒng)中的連續(xù)屬性離散化在機器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域具有十分重要的作用。粗糙集理論只能處理離散型數(shù)據(jù)，而樣本數(shù)據(jù)大多為連續(xù)屬性。因此，離散化是粗糙集理論處理連續(xù)問題的關(guān)鍵，離散化結(jié)果直接關(guān)系到后續(xù)的數(shù)據(jù)挖掘。目前，國內(nèi)外學(xué)者提出了多種屬性離散化算法。如文獻[1]給出了基于屬性重要性的啟發(fā)式離散化算法；文獻[2]給出了基于信息熵的離散化算法；上述方法都充分考慮了決策表的不相容性，但算法時間復(fù)雜度較大；文獻[3]給出了基于遺傳算法的離散化方法，該方法計算速度較慢，且局部搜索能力差；文獻[4]給出了基于聚類分析的連續(xù)屬性離散化算法，該算法對于決策系統(tǒng)中數(shù)據(jù)量較大時存在計算復(fù)雜度較大、離散化效率較低等缺點。鑒于上述分析，本文將集群智能優(yōu)化理論和粗糙集理論相結(jié)合，提出一種基于改進粒子群的連續(xù)屬性離散化算法。算法分析和實驗結(jié)果表明，該算法具有較好的離散化效果，能使決策系統(tǒng)的信息損失降低到最小，并可獲取更為簡潔的決策規(guī)則。

2 數(shù)據(jù)一致性度量

為了使離散化后保持決策系統(tǒng)中原有數(shù)據(jù)信息，可采用粗糙集理論對決策系統(tǒng)中數(shù)據(jù)進行一致性度量（或辨識函數(shù)）LC(D)=γC(D)，其中γC(D)為粗糙集決策屬性D對條件屬性C的依賴度，也稱為分類質(zhì)量，即

其中，POSC(D)為D的C正域，-CX為X的下近似集。數(shù)據(jù)一致性是屬性離散化和屬性選取的一個有效度量，反映了決策系統(tǒng)中根據(jù)條件屬性C的信息對所有實例關(guān)于決策屬性D的等價類的分辨能力，當(dāng)γC(D)=1時稱決策系統(tǒng)是相容的或協(xié)調(diào)的。因此，粗糙集中的連續(xù)屬性離散化可以根據(jù)離散化后數(shù)據(jù)“一致性”值逐次調(diào)整終止條件，直至不一致性為零（最?。?，其目的是保持原有數(shù)據(jù)的分辨能力。

3 粒子群算法及其改進

3.1 基本粒子群算法

粒子群優(yōu)化算法[5]（Particle Swarm Optimization）是Eberhart和Kennedy于1995年提出的一種基于集群智能優(yōu)化算法，主要適用于求解非線性、不可微等復(fù)雜優(yōu)化問題。由于PSO算法具有簡單、計算速度快、易于獲得全局最優(yōu)解等優(yōu)點，現(xiàn)已廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練及模糊系統(tǒng)控制等領(lǐng)域，但是該算法存在收斂精度較低，且易陷入局部最優(yōu)等缺點。

3.2 改進的粒子群算法

為了防止陷入局部極值，有效提高粒子群算法的精度和全局收斂性能，本文對基本PSO算法進行以下改進，以便更好地進行連續(xù)屬性離散化處理。

（1）初始化的改進：基本粒子群算法中一般粒子群的初始化均采用隨機方法產(chǎn)生，如文獻[7]提出均勻設(shè)計的方法產(chǎn)生的分割點集構(gòu)成的初始群體比隨機產(chǎn)生的初始群體更能從統(tǒng)計意義上反映出目標(biāo)函數(shù)的特性。本文提出利用符合均勻分布的隨機數(shù)來初始化粒子群體的位置，以此優(yōu)化全局尋優(yōu)效果。

（2）對最優(yōu)粒子和最差粒子的處理：PSO算法中，每個粒子都是隨機運動的，當(dāng)最優(yōu)粒子飛行到某一步時，若適應(yīng)度變差，則下一步就會從變差的位置繼續(xù)飛行，因而不能充分發(fā)揮最優(yōu)粒子應(yīng)有的優(yōu)勢功能。為了有效更新粒子群體中粒子的速度和位置，對于每一步最優(yōu)粒子的飛行，現(xiàn)采用試探方法使其朝著適應(yīng)度變優(yōu)的方向飛行，即最優(yōu)粒子飛行一步后，若適應(yīng)度變好，則從新的位置繼續(xù)飛行；若適應(yīng)度變差，則返回原位置重新搜索。同時，對于每一步最差的粒子的飛行，應(yīng)用該步的歷史全局最優(yōu)粒子取代。

（3）慣性權(quán)重w的取值：在粒子群體優(yōu)化過程中，合理控制全局搜索和局部搜索的能力對于有效尋求最優(yōu)解是非常關(guān)鍵的。從公式（2）可以看出，慣性權(quán)重w決定了粒子在上一個位置的速度對目前位置粒子的影響。因而，通過控制慣性權(quán)重w的值可以維護局部搜索和全局搜索的平衡，準(zhǔn)確高效地搜索全局最優(yōu)解。當(dāng)w較大時，粒子有能力擴展搜索空間，全局搜索能力較強，但是收斂性相對下降；當(dāng)w較小時，粒子可在特定區(qū)域內(nèi)精細搜索，局部搜索能力較強。為了克服基本PSO算法固定參數(shù)不足的缺點，本文擬采用自適應(yīng)MPSO算法調(diào)整w的策略，即讓w隨算法的迭代進行線性的減少。慣性權(quán)重w調(diào)整方法如式（4）所示：

其中，wmax、wmin分別為慣性權(quán)重的最大值與最小值，iter為當(dāng)前迭代次數(shù)，itermax為最大迭代次數(shù)。

4 改進粒子群的屬性離散化算法

4.1 初始分割點集選取

4.2 初始分割點集編碼

為了簡化問題的描述，本文擬采用二進制編碼方式對決策系統(tǒng)中連續(xù)屬性初始分割點集編碼。用長度為P的二進制串來表示一個個體，該串由M個子串組成，每個子串對應(yīng)決策系統(tǒng)中一個條件屬性的初始分割點集，每一位對應(yīng)一個分割點。其值“1”和“0”分別代表該分割點的“取”和“舍”。

4.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用來確定群體中個體的適應(yīng)度值，而適應(yīng)度值是粒子群算法中區(qū)分個體“好壞”的唯一標(biāo)準(zhǔn)，也是更新粒子群的唯一依據(jù)。由分割點選取的合理性衡量標(biāo)準(zhǔn)可知，個體的適應(yīng)度主要取決于兩個方面：一是所包含的分割點數(shù)應(yīng)該盡可能少；二是利用該分割點進行離散化后應(yīng)保持決策系統(tǒng)的一致性。因此適應(yīng)度函數(shù)由分割點數(shù)和分辨關(guān)系兩者共同確定。綜合起來，適應(yīng)度函數(shù)可定義為：

其中，x為個體所表示的分割點集，P表示個體的二進制串長度，即初始總分割點數(shù)，Lx為個體所包含的分割點數(shù)目，γC(D)為粒子所包含的分割點劃分后的決策系統(tǒng)中決策屬性對條件屬性的依賴度，α、β為權(quán)重調(diào)節(jié)因子。顯然，分割點數(shù)目越小，粒子的適應(yīng)度值越大；分類質(zhì)量越大，決策系統(tǒng)一致性越高，適應(yīng)度值越大。

4.4 算法步驟

步驟1初始化算法參數(shù)。設(shè)定粒子群體規(guī)模M、學(xué)習(xí)因子c1和c2、慣性權(quán)重w的上下限及粒子更新的速度限值等，設(shè)置最大迭代次數(shù)itermax，設(shè)定迭代次數(shù)iter=0，隨機產(chǎn)生M個粒子，按均勻分布函數(shù)初始化粒子的初始位置xi，粒子的初始速度νi設(shè)為0，個體極值pbest，i，全局極值gbest。

步驟2根據(jù)每個粒子i表示的分割點集將初始決策系統(tǒng)DS轉(zhuǎn)化成離散化的決策系統(tǒng)DSP，計算離散化后分割點數(shù)和決策系統(tǒng)中決策屬性對條件屬性的依賴度γC(D)，作為每個粒子的適應(yīng)度值Fitness(i)。

步驟3對群體中的每個粒子i，執(zhí)行以下操作步驟：

（1）根據(jù)公式（5）計算各粒子i的適應(yīng)度值Fitness(i)；

（2）若Fitness(i)優(yōu)于此前的個體極值pbest，i，則將其設(shè)為pbest，i；若最佳的pbest，i優(yōu)于此前的全局極值gbest，則將其設(shè)為gbest。

步驟4根據(jù)公式（2）～（4）更新每個粒子的速度νi和位置xi；若νi〉νmax，則取νi=νmax，若νi〈νmin，則取νi=νmin。

步驟5根據(jù)每個粒子i表示的分割點集將初始決策系統(tǒng)DS轉(zhuǎn)化成離散決策系統(tǒng)DSP；然后根據(jù)公式（1）計算決策屬性對條件屬性集的依賴度γC(D)，調(diào)整粒子的適應(yīng)度值Fitness(i)。

步驟6對每一步的最優(yōu)粒子和最差粒子進行處理。

步驟7若迭代次數(shù)達到itermax，則轉(zhuǎn)入步驟9，否則轉(zhuǎn)入步驟8。

步驟8判斷γC(D)是否等于1，若是轉(zhuǎn)入步驟9，否則iter=iter+1，自適應(yīng)調(diào)整慣性權(quán)重w，轉(zhuǎn)回步驟3繼續(xù)迭代。

步驟9輸出適應(yīng)度值最優(yōu)的粒子(gbest)作為最優(yōu)分割點集對決策系統(tǒng)進行離散化。

連續(xù)屬性離散化的改進PSO算法流程如圖1所示。

4.5 算法復(fù)雜度分析

設(shè)決策系統(tǒng)的實例數(shù)為N，粒子群體大小為M，條件屬性分割點數(shù)為R，最大迭代次數(shù)為L。本算法的計算復(fù)雜度主要由步驟2～步驟9所決定的。

步驟2中計算離散化的決策系統(tǒng)DSP，時間復(fù)雜度為O(N2)；

步驟3中計算適應(yīng)度函數(shù)Fitness(i)，計算量為M×R× N2，由于粒子群體大小M、條件屬性分割點數(shù)R都是常量，與決策系統(tǒng)實例數(shù)N相比可以忽略，因此計算適應(yīng)度函數(shù)的時間復(fù)雜度為O(N2)；

圖1 連續(xù)屬性離散化的改進PSO算法流程圖

步驟4～步驟9計算最優(yōu)分割點集，其計算量為L×O(N2)，L為有限常量，因此算法時間復(fù)雜度為O(N2)。

綜上所述，本算法總的時間復(fù)雜度為O(N2)，是一個比較有效的屬性離散化算法。

5 實驗結(jié)果及分析

為了驗證改進的PSO離散化算法的有效性及性能，從UCI機器學(xué)習(xí)數(shù)據(jù)庫中選取5組數(shù)據(jù)集進行離散化。為便于比較，將改進的PSO離散化算法實驗結(jié)果和基于屬性重要性的離散化算法、基于信息熵的離散化算法、遺傳算法進行性能對比實驗。實驗基本配置CPU為3 GHz，內(nèi)存為512 MB，仿真軟件為Matlab7.0。改進的粒子群算法的基本參數(shù)設(shè)置：粒子群規(guī)模30，學(xué)習(xí)因子c1=c2=2.0，慣性因子wmax=1.2、wmin=0.4，粒子速度在[-4，4]間變化，最大迭代次數(shù)為itermax=50。

實驗過程根據(jù)以下四個步驟進行：（1）從數(shù)據(jù)庫中隨機抽取70%的數(shù)據(jù)作為訓(xùn)練集，30%的數(shù)據(jù)作為測試集；（2）采用本算法對訓(xùn)練集進行離散化，得到離散化后的分割點集；（3）用訓(xùn)練集的分割點集對相應(yīng)的測試集進行離散化；（4）用C5.0算法從訓(xùn)練集中獲取分類規(guī)則對測試集進行判斷獲得平均分類精度。所有實驗結(jié)果均為10次實驗平均值。其中，表1給出了各數(shù)據(jù)集的基本信息，表2給出了四種離散化算法實驗結(jié)果的相應(yīng)數(shù)據(jù)。

表1 數(shù)據(jù)集基本信息

表2 四種離散化算法的實驗結(jié)果比較

從實驗結(jié)果可以看出：

（1）在對初始分割點進行篩選的四種算法中，改進PSO算法的初始分割點數(shù)明顯少于其他三種算法的初始分割點數(shù)。這主要是因為改進PSO算法屬全局尋優(yōu)離散化算法，考慮了屬性之間的依賴關(guān)系和決策系統(tǒng)的一致性等情況；而其他三種離散化算法僅考慮屬性重要性或分割點重要性等。這表明，對于相同的一組實例數(shù)據(jù)，改進的PSO離散化算法可以對特定屬性空間實現(xiàn)更簡單的離散劃分。

（2）與其他三種算法相比，本文提出的改進PSO離散化算法能大幅度提高規(guī)則的分類精度。由于改進PSO算法結(jié)合了粗糙集理論的思想，考慮了屬性間的相互影響，從而產(chǎn)生了比較合理的分割點，提高了規(guī)則的分類精度；而其他三種離散化算法的分類精度主要來源于評價標(biāo)準(zhǔn)值的計算。

（3）在計算時間上，改進PSO離散化算法和遺傳算法的計算時間比其他兩種算法在相應(yīng)數(shù)據(jù)集上的計算時間大。這是由于改進的PSO算法和遺傳算法都屬全局離散化算法，在初始分割點選擇、樣本數(shù)和迭代次數(shù)等方面都影響算法的計算時間。此外，改進的PSO離散化算法中，glass數(shù)據(jù)集的計算時間最高，這是因為glass數(shù)據(jù)集的決策分類最多，而改進PSO算法要考慮條件屬性和決策屬性之間的依賴關(guān)系。

（4）四種算法在數(shù)據(jù)集glass上的結(jié)果分割點數(shù)最多，這是因為數(shù)據(jù)集glass的決策分類數(shù)較多，從而導(dǎo)致glass數(shù)據(jù)集的分割點數(shù)最多。另外，四種算法在glass數(shù)據(jù)集上的測試精度也較低，這也與glass數(shù)據(jù)集的決策分類數(shù)較多等有關(guān)。由此可見，在數(shù)據(jù)集的樣本數(shù)和連續(xù)屬性數(shù)不變的條件下，決策分類越多，則分割點數(shù)越多，測試精度越低，計算時間越長。

6 結(jié)束語

決策系統(tǒng)中連續(xù)屬性離散化是壓縮數(shù)據(jù)、提取決策規(guī)則的有效手段。針對當(dāng)前屬性離散化算法中分割點選取存在的數(shù)量及選取合理性等問題，本文結(jié)合粗糙集理論和集群智能優(yōu)化理論，提出一種基于改進粒子群的連續(xù)屬性離散化算法，并以UCI機器學(xué)習(xí)數(shù)據(jù)庫作為測試集，進行了仿真實驗。算法分析和實驗結(jié)果表明，本文算法具有較好的離散化效果，能使決策系統(tǒng)的信息損失降低到最小，并可獲取更為簡潔的決策規(guī)則。

[1]侯利娟，王國胤，聶能，等.粗糙集理論中的離散化問題[J].計算機科學(xué)，2000，27（12）：89-94.

[2]謝宏，程浩忠，牛曉東.基于信息熵的粗糙集連續(xù)屬性離散化算法[J].計算機學(xué)報，2005，28（9）：1570-1574.

[3]趙衛(wèi)東，戴偉輝，蔡斌.遺傳算法在決策表連續(xù)屬性離散化中的應(yīng)用研究[J].系統(tǒng)工程理論與實踐，2003（1）：62-67.

[4]韓秋明，趙軼群.Rough Set中基于聚類的連續(xù)屬性離散化方法[J].計算機工程，2003（3）：81-87.

[5]Kennedy J，Eberhart R C.Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks.Piscataway：IEEE Press，1995：1942-1948.

[6]Maurice C，Kennedy J.Τhe particle swarm explosion，stability，and convergence in a multidimensional complex space[J].IEEE Τransactions on Evolutionary Computation，2002，6（1）：58-73.

[7]張騰飛，王錫淮，肖鍵梅.基于微粒群優(yōu)化的連續(xù)屬性離散化[J].計算機工程，2006，32（3）：44-46.

[8]劉業(yè)政，楊善林，鐘金宏.基于粗集理論的冗余分割點約簡[J].計算機工程，2002（8）：17-19.

[9]陳國初，俞金壽.增強型微粒群優(yōu)化算法及其在軟測量中的應(yīng)用[J].控制與決策，2005，20（4）：377-381.

[10]Shi Y，Eberhart R.A modified particle swarm optimizer[C]// Proceedings of IEEE International Conference on Evolutionary Computation，1998：69-73.

[11]王立宏，吳彥，吳耿鋒.離散化的一種啟發(fā)式搜索算法[J].計算機應(yīng)用，2004，24（8）：41-43.

[12]王立宏，孫立民，孟佳娜.數(shù)值離散化中粒度熵與分類精度的相關(guān)性[J].重慶大學(xué)學(xué)報，2008，31（1）：57-61.

[13]Nguyen H S.Discretization of real value attributes：a boolean reasoning approach[D].Warsaw：Computer Science Department，University of Warsaw，1997.

[14]Nguyen H S，Skowron A.Quantization of real values attributes[C]//Proc of the 2nd Joint Annual Conference on Information Science，Wrightsville Beach，North Carolina，1995：34-37.

[15]姚耀如，徐玉如.粒子群優(yōu)化算法分析[J].哈爾濱工程大學(xué)學(xué)報，2007，28（11）：1242-1246.

[16]Eberhart R C，Shi Y.Particle Swarm Optimization：developments，applications and resources[C]//Proceedings of the IEEE Congresss on Evolutionary Computation.Piscataway，NJ：IEEE Service Center，2001：81-86.

WANG Ling

1.China Center for Industrial Security Research,Beijing Jiaotong University,Beijing 100044,China
2.Key Lab for Solid Waste Management and Environment Safety,Ministry of Education of China,Beijing 100084,China

An algorithm of continuous attribute discretization based on improved particle swarm is proposed.Τhe algorithm combines intelligent optimization theory and rough sets theory.Each attribute discretization points are initialized to particle group, seeking the optimal discretization points through the interaction between particles.Discretization algorithm is applied to the UCI data sets in the experiment,and the experimental results show that,the algorithm can make the loss of information decision system reduce to the minimum,and get more concise decision rules.

improved particle swarm;intelligent optimization;rough sets;continuous attribute discretization

提出一種基于改進粒子群的連續(xù)屬性離散化算法。該算法結(jié)合集群智能優(yōu)化理論和粗糙集理論，將各屬性離散化分割點初始化為粒子群體，通過粒子間的相互作用尋求最優(yōu)離散化分割點。將提出的離散化算法應(yīng)用于UCI數(shù)據(jù)集實驗中，實驗結(jié)果表明，該算法能使決策系統(tǒng)的信息損失降低到最小，并可獲取更為簡潔的決策規(guī)則。

改進粒子群；智能優(yōu)化；粗糙集；連續(xù)屬性離散化

A

ΤP311

10.3778/j.issn.1002-8331.1305-0492

WANG Ling.Algorithm of continuous attribute discretization based on improved particle swarm.Computer Engineering and Applications,2013,49（21）：29-32.

教育部人文社會科學(xué)研究青年基金項目（No.11YJC630195）；安徽省高校省級自然科學(xué)研究重點項目（No.KJ2012A076）；固體廢物處理與環(huán)境安全教育部重點實驗室開放基金項目（No.SWMES 2011-05）。

汪凌（1976—），男，博士后，研究方向：粗集決策分析、數(shù)據(jù)挖掘、智能交通等。E-mail：tcwling@126.com

2013-06-04

2013-08-30

1002-8331（2013）21-0029-04