基于遺傳聚類算法的出行行為分析
2009-01-01 00:00:00鮮于建川雋志才
計算機應用研究 2009年3期
(上海交通大學 安泰經濟與管理學院， 上海 200052)
摘 要：針對K中心點聚類算法對分類數據聚類的有效性和遺傳算法良好的自組織、自適應和自學習能力，提出了基于遺傳聚類算法的出行行為分析方法。該方法采用整數編碼，用活動模式間的匹配度度量模式對象之間的相異度，以各活動模式與最近聚類中心點之間相異度的總和為適應度函數，探討了K中心聚類與遺傳算法相結合完成分類對象聚類分析的方法；通過算法在不同數據量和不同參數設定下仿真結果的比較，提出了關鍵參數的推薦值。研究表明，新方法不僅能很好地解決孤立點和局部最優的問題，同時還提高了算法的收斂速度，降低了計算成本，能很好地解決分類數據的聚類問題。
關鍵詞：聚類分析； 遺傳算法； K中心點聚類； 活動模式
中圖分類號：TP183 文獻標志碼：A
文章編號：10013695(2009)03083604
Travel behavior analysis using genetic clustering algorithm
XIANYU Jianchuan， JUAN Zhicai
(College of Antai Economics Management， Shanghai Jiaotong University， Shanghai 200052， China)
Abstract:Based on the good performance of Kmedoids clustering algorithm for categorical data and the nice selforganization， selfadaptation and selflearning of genetic algorithm， this paper aimed to develop a methodology for the clustering of activity patterns with a genetic algorithm based clustering method. The proposed method used integer coded chromosome. The dissimilarity measure between two activity patterns was defined as the total number of mismatches of activity types at a corresponding time index and the fitness function was defined as the sum of dissimilarities of all objects to their nearest medoids. The results for different sizes of data sets and for different parameter settings were compared and based on this recommended parameter settings were provided. It is demonstrated that the algorithm is good at preventing premature convergence， decreasing the sensitivity to outliers and that it is fast converging and is a good solution for categorical data clustering analysis.
Key words：cluster analysis; genetic algorithm; Kmedoids clustering algorithm; activity pattern
將基于活動的分析方法與微觀仿真方法相結合分析出行行為、預測出行需求、評價出行需求管理策略已成為交通規劃管理領域的研究熱點。這一研究過程的關鍵是以活動模式特征分析為基礎，將出行者劃分為不同類別，得到各個群體的代表性活動模式，然后通過仿真分析為各類出行者分配具體活動出行屬性特征[1]。上述研究屬于特征子集選擇問題，可用聚類分析完成，即將出行者活動模式數據集劃分為若干組或類，使得同一組內的活動模式對象具有較高的相似度，而不同組中的活動模式對象則不相似。
由于對活動模式的聚類涉及分類數據（不同活動類型），包括K均值聚類、分層聚類在內的一些基于歐式距離和需要計算聚類對象均值的聚類方法都不再適用[2]。為了適應對不同數據類型聚類分析的需要，研究人員改進K均值聚類，提出了K中心聚類[3]。與K均值聚類不同，K中心聚類不采用均值作為聚類中心，而是采用數據集中的實際對象作為聚類中心，能很好解決K均值對孤立點敏感的問題，極大提高了聚類精度。但該方法受初值影響很大，有收斂到局部最優、不易得到全局最優解的問題[2]。
遺傳算法起源于對生物系統所進行的計算機模擬研究，是一種借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法。與傳統搜索算法不同，遺傳算法不依賴于梯度信息，而是通過模擬自然進化過程來搜索最優解，廣泛應用于數據分析、動態處理、模式識別、人工智能、生產調度等許多學科[4~6]；也有嘗試用遺傳算法進行聚類分析[7， 8]，但往往計算量大、效果有限，研究表明K均值與遺傳算法相結合的聚類分析雖然有一定效果，但仍然不能很好解決孤立點和局部最優的問題[9]。為此，針對孤立點對聚類的影響和算法過早收斂到局部最優的問題，本文將K中心點聚類與遺傳算法相結合研究出行活動模式聚類問題，研究表明，基于遺傳算法和K中心聚類的方法不僅能很好地解決孤立點和局部最優的問題，還可以加快遺傳算法的收斂速度、減少計算量、縮短求解時間。
1 數據
對數據結構的認識和了解有助于對算法特點和性能的評價，本文采用合成數據而非直接觀察結果進行分析。
1.1 活動模式表達
活動類型的判定是出行者活動模式聚類的前提。通勤者活動出行是日常出行需求的最重要組成部分，本文將著重分析通勤者活動模式的特點和聚類分析方法。考慮到工作活動在活動開始時刻、持續時間，以及工作地點和家庭居住地點在空間上的相對固定性，在很大程度上制約和限制著對其他出行和活動的安排。研究中將活動劃分為四類：a）在家活動，指在家的時段中所完成的各種活動；b）工作活動，指工作及工作相關活動；c）休閑娛樂活動，包括以娛樂、放松、消遣為主要目的的活動；d）生活活動，指除休閑娛樂活動外，諸如就餐、存取款、郵寄東西、購物等日常生活活動。
對活動模式作離散化表示：對每個被調查出行者，以10 min為間隔，記錄其每個時間區間內進行的活動類型，得到長度為144的活動類型序列作為日活動模式。序列中各分量為1~4的整數，為對應時間間隔下的活動類型編碼，是分類變量，無數值含義。
1.2 數據合成
研究中采用結構已知的合成數據。為了使合成的活動模式數據能夠代表實際情況，參考已有研究結果[10， 11]，合成數據主要來自五類活動計劃。a)標準工作模式（SW）。這類個體一般有8 h的工作活動時間。早上（7~9點）離開家去單位上班，一些人中午還會安排外出就餐，傍晚（17~18點）下班后回家。b)高強度工作模式（PW）。這類個體的活動安排與SW組類似，但工作活動時間更長，平均日工作時間在10 h左右。c)生活工作模式（LW）。這類個體的日平均工作時間也在8 h左右，活動安排與SW組類似。但通常工作開始時間較晚，在中午12點以后。d)工作—休閑娛樂模式（WD）。這類個體上下班時間和工作持續時間相似，但通常會在工作結束后安排一些娛樂活動。部分出行者選擇下班后直接去娛樂場所，另一些則是先回家然后再去。e)短時多樣模式（VS）。這類個體的工作開始、結束和持續時間都非常靈活，通常還會參加生活和娛樂活動。從五類活動模式中各取一個樣本，如圖1所示。
2 K中心聚類算法
活動模式的分類問題可描述為如下的K中心點聚類問題：假設由N個活動模式對象組成集合S={S1，S2，…，SN}，對象Si是一個長度144的向量，各分量為對應時間間隔的活動類型，通過K中心聚類算法從這N個對象中找出K個具有代表性的典型模式，并按選定的相異度定義將其他對象分配到最近的代表性模式。算法的流程如下：a)從N個數據對象中任意選擇K個對象作為初始聚類中心點(m1，m2，…，mK)；b)按最小差異度原則，將余下的對象分配到以上述中心點為代表的各個類；c)對于任意類i，順序選擇對象mr，計算用mr代替 mi后各個對象到距離最近的代表性對象差異度之和FK的取值，選擇FK取值最小的mr來代替mi；d)循環b)c)，直到K個中心點都固定下來。函數FK的數學表示如下：
Fk=∑Ni=1 mint=1，…，K d(Si，mt)
(1)
其中：K< 在聚類算法中，歐式距離是兩個對象間差異度的常用度量方法，但不適用于對分類數據的分析。本文參考Huang[12]的研究，對活動模式對象間的差異度定義如下：活動模式S1與S2之間的相異度d(S1，S2)為對應時間間隔不匹配活動類型的個數，即 d(S1，S2)=∑｜Si｜j=1 δ(S1(j)，S2(j)) δ(S1(j)，S2(j))=0 S1(j)=S2(j)1 S1(j)≠S2(j)(2) 其中:｜Si｜=144，為活動模式對象Si的長度；d(S1，S2)的取值是[0，144]上的整數。 3 基于遺傳算法和K中心聚類的新算法 遺傳算法的本質是一種高效、并行、全局的搜索和優化方法，能在搜索過程中自動獲取和積累有關搜索空間的知識，并自適應地控制搜索過程以求得最優解，在許多領域都得到了廣泛應用。將遺傳算法與K中心聚類相結合應用于分類數據的聚類分析，不僅能夠很好地解決局部最優和孤立點的問題，還能加快求解過程、減少計算成本。 算法首先隨機產生遺傳算法的第一代并開始選擇；然后在每一步的進化中對所有被選中個體計算以其為初始值的K中心算法的局部最優解，以局部最優結果替換原有個體；繼續進化過程直到到達最大遺傳代數或符合要求為止。算法的偽碼如下： for t=1:GN P(t) forj=1:NP/2-1 P1=P2j+1(t) P2=P2j+2(t) {C1，C2} {C′1，C′2} append{C′1，C′2，} to matrix C next create matrix M including both P and C binary tournament selection matrix M next 其中：GN為最大遺傳代數；NP為初始種群規模；P(t)為t時的種群；Pi為母體i；Cj為子代個體j。 3.1 染色體編碼和初始種群生成 用遺傳算法分析聚類問題，對染色體可以有不同的編碼方法[12~14]。考慮到與所研究問題的相關性，最終借鑒Lucasius等人[15]的研究，采用整數編碼。每條染色體長度為K（聚類數），各元素代表數據集中的對象，該數據對象對應一個聚類中心，且取值為(1，N)上的均勻分布。例如研究中K＝5，而中心點對應模式編號為7、13、39、54、82，則得到的染色體可表示為向量[7 13 39 54 82]。用整數編碼可以極大減少染色體的長度，提高遺傳算法的收斂速度；計算目標函數時省去從基因型到表現型的轉換，減少了計算成本。 初始種群隨機生成，得到一個初始種群矩陣P(0)。其中每一行代表一個個體，行中的一個元素代表一個聚類中心。矩陣的行數為種群規模，列數為聚類數。一個種群規模為N、待聚類數為K的種群可表示為如下矩陣： O11O12…O1KO21O22…O2KON1ON2…ONK 3.2 適應度函數 遺傳算法在處理過程中以適應度函數為依據，利用種群中每個個體的適應度值進行搜索，故適應度函數的選取將直接影響到算法的收斂速度。考慮到活動模式對象的分類取值特性，采用對象間差異度之和FK=∑Ni=1mint=1，…，K d(Si，mt)作為適應度函數，函數定義同式(1)(2)。 3.3 選擇算子 遺傳算法用選擇算子對群體中的個體進行優勝劣汰的選擇操作，體現了“適者生存”的原則：適應度越高的個體被遺傳進入到子代群體中的概率越大，而適應度低的個體被遺傳到下一代中去的概率較小。已有研究多采用按比例適應度分配方法計算個體被選中概率，然后用輪盤賭方法進行個體的選擇[15，16]。從理論分析和前期實驗結果來看，二進制隨機競賽選擇方式（binary tournament selection， BTS）較輪盤賭方法更具優勢，本文采用BTS方法。首先隨機地從種群中挑選一定數目（tour）的個體，然后選擇最好的個體作為母個體，并將此過程反復進行直至選出足夠的個體。其中競爭規模tour為待設定參數。BTS算子的選擇規模與選擇強度（selInt）之間的關系及選擇過程中多樣化損失（lossDiv）的計算如下： selInttour(tour)=2(log(tour)-log4.14 log(tour)) lossDivtour(tour)=tour-1/(tour-1)-tour-tour/(tour-1) 3.4 交叉算子 交叉算子通過把兩個母個體的部分結構加以替換重組而生成新的個體。交叉操作的目的是為了在下一代中產生不同于母代的新個體，通過交叉操作，遺傳算法的搜索能力得以大幅度提高。針對均勻交叉等標準交叉算子可能帶來不可行個體的問題，本文選擇random respectful recombination(R3)算子[17]作為交叉算子。R3算子的基本原理與均勻交叉相似，但通過算法保證了兩個母體所共有的基因一定會遺傳到子代，能夠保證所得到的個體是可行的，且具有保持相似性、遺傳性和適當變異的特點，使得交叉模式的任意兩個體產生的新個體是模式的實例，能保證子個體中的模式均來自于母個體，且兩個相似相容模式的實例之間進行交叉產生的子個體仍是兩模式的一個實例。 3.5 變異算子 在變異算子的作用下，經交叉算子作用的子代個體除了繼承母代個體的信息外，還將以一定的概率發生轉變，體現了生物遺傳的多樣性。變異操作本身是一種局部隨機搜索過程，與選擇算子和交叉算子結合在一起，則能夠保證遺傳算法的有效性和種群的多樣性，防止出現非成熟的過早收斂。在變異操作中，變異率的選取非常重要，通常在0.0001~0.1內選擇。當變異率大于0.5時，遺傳算法退化為隨機搜索，失去了算法所具有的一些數學特性和搜索能力[18]。 4 分析及結果 算法用MATLAB[19]實現。由于遺傳算法的隨機性，同樣的算法在每次得到的結果都是不同的。為此在算法的每一設定參數下重復進行10次，下面所給出的結果都是10次重復計算的平均值。仿真實驗中嘗試了不同的初始種群規模、變異率、迭代次數和最大遺傳代數對聚類效果的影響，結果如表1~3所示。其中：NP為初始種群規模；FP為終止種群規模；iter為迭代次數；GN為最大遺傳代數；PM為變異率；fit為平均適應度函數值；T為計算時間。 表中結果按適應度函數從低到高的順序排列。研究發現，變異率控制著變異操作被使用的頻度，當變異率很小時，解群體的穩定性很好，但一旦進入局部極值就很難跳出，容易產生未成熟收斂；對變異率稍做增加，可破壞解群體的同化，保持解空間的多樣性，使搜索過程跳出局部最優，收斂到全局最優；而當變異率取值過大時，雖能產生較多的個體，增加了群體的多樣性，但有可能破壞掉很多好的模式，使遺傳算法近似于隨機搜索算法的性能。對于本文所研究的問題，變異率宜控制在0.05~0.1，而在0.05附近取值的性能更優。另外，初始種群規模的大小直接影響到遺傳算法的收斂速度和效率，規模過小，容易收斂到局部最優；規模過大又會影響計算速度。研究表明，初始種群規模設定在20或30時，能兼顧算法的收斂速度和性能；迭代次數可以在5~7內變化，而最大遺傳代數設為50或60時有較好的效果。并且，所有參數的取值均與待聚類數據量的大小有關，當數據量較大時，各參數值也應進行相應擴大。 5 結束語 聚類分析是模式識別中非監督學習的一種，方法將多維空間中表示對象的特征向量按某種相似度度量劃分為若干集合，使同一集合中對象間差異度較小，而不同集合中的對象間差異度較大。但聚類方法大都對孤立點敏感、容易陷入局部最優解，用遺傳算法模擬生物進化過程，有很好的自組織能力，在求解大規模優化問題的全局最優解方面表現出了顯著優勢。本文以適用于分量數據聚類的K中心聚類算法為指導，通過對活動模式進行整數編碼，然后選擇適宜的選擇算子、交叉算子和變異算子，以模式匹配度作為不同模式間相異度的度量，以各模式向量與最近聚類中心點相異度的總和為適應度函數，提出了一種基于遺傳算法的新的聚類方法。通過在不同數據量和不同設定參數下仿真結果的比較，得出了參數設定的推薦值。研究表明，新的聚類算法吸收了K中心聚類和遺傳算法的優點，能較好解決孤立點和局部最優的問題，同時還加快了收斂速度、減少了計算成本，能很好地解決分類樣本的聚類問題，具有普遍適用性。為了更客觀地評價所提出的算法、對算法作進一步的優化，后續準備在與解決同類問題的其他算法的分析比較上進行深入研究[20]；另一方面，將考慮將研究所提出的方法擴展到在最小化聚類數的同時最優化適應度函數的多目標聚類問題上。 參考文獻： ［1］PRIBYL O， GOULIAS K G. Simulation of daily activity patterns incorporating interactions within households: algorithm overview and performance[J]. Journal of Trans on Research Board， 2005，1926(1):135141. [2]EVERITT B S， LANDAU S， LEESE M. Cluster analysis[M]. London: Hodder Arnold， 2001. [3]KAUFMAN L，ROUSSEEUW P J. Finding groups in data: an introduction to cluster analysis[M]. New York: Wiley， 1990. [4]陳群， 姚加林， 晏克非. 基于遺傳算法的通道上停車換乘量確定方法[J]. 計算機工程， 2008， 34(4):201206. [5]王烜， 段常貴. 改進遺傳算法在燃氣管網布局優化中的應用[J]. 哈爾濱工業大學學報， 2006，38(1):4648. [6]WANG H，XUE D. An intelligent zonebased delivery scheduling approach[J].Computers in Industry， 2002，48(2):109125. [7]張偉， 廖曉峰， 吳中福. 一種基于遺傳算法的聚類新方法[J]. 計算機科學， 2002， 29(6):114116. [8]張強， 李淼. 基于遺傳算法和遺傳模糊聚類的混合聚類算法[J]. 計算機工程與應用， 2007， 43(3):164166. [9]劉婷， 郭海湘，諸克軍，等. 一種改進的遺傳Kmeans聚類算法[J]. 數學的實踐與認識， 2007， 37(8):106111. [10]SCHWANEN T， DIJST M. Time window in workers’ activity patterns: empirical evidence from the Netherlands[J]. Transportation， 2003， 30(3):261283. [11]邵昀泓. 基于活動的出行需求分析及信息影響研究[D]. 南京: 東南大學， 2006. [12]HUANG Zhexue. Clustering large data sets with mixed numeric and categorical values[C]//Proc of the 1st PacificAsia Conference on Knowledge Discovery and Data Mining. 1997:283304. [13]ZHOU Enwang， KHOTANZAD A. Fuzzy classifier design using genetic algorithms[J]. Pattern Recognition， 2007，40(12):34013414. [14]MAULIK U， BANDYOPADHYAY S. Genetic algorithmbased clustering technique[J]. Pattern Recognition， 2000，33(9):18831893. [15]LUCASIUS C B， DANE A D，KATEMAN G. On Kmedoid clustering of large data sets with the aid of genetic algorithm: background， feasibility and comparison[J]. Analytica Chimica Acta， 1993，282(3):647669. [16]傅景廣， 許剛， 王裕國. 基于遺傳算法的聚類分析[J]. 計算機工程， 2004， 30(4):122124. [17]ESTVILLCASTRO V， MURRAY A T. Spatial clustering for data mining with genetic algorithms[C]//Proc of the International ICSC Symposium on Engineering of Intelligent Systems. 1998:39. [18]王小平， 曹立明. 遺傳算法：理論、應用及軟件實現[M]. 西安: 西安交通大學出版社， 2002. [19]雷英杰， 張善文，李續武，等. MATLAB遺傳算法工具箱及應用[M]. 西安: 西安電子科技大學出版社， 2006. [20]PRINZIE A，POEL A V D. Incorporating sequential information into traditional classification models by using an element/positionsensitive SAM[J]. Decision Support Systems， 2006，42(2):508526.
