今日頭條
官方微信
官方抖音
案例頻道
劉強（1979－）
男，遼寧工業大學研究生，（遼寧工業大學信息科學與工程學院，遼寧 錦州 121001 ）,研究方向為智能控制。
摘要：論文基于免疫網絡理論和克隆選擇原理，建立了一種人工免疫數據聚類分析算法，并詳細闡述了聚類算法在城市交通時段自動劃分中的具體應用。實例分析表明，該算法可以有效減少聚類數據的冗余信息，特別適合于解決分級聚類等傳統方法不適應的大數據量聚類問題，對解決城市交通時段的自動劃分等數據聚類問題是可行的和有效的。
關鍵詞：聚類；人工免疫系統；模式識別；交通控制
Abstract: An artificial immune algorithm for data clustering is proposed in this paper. This work is mainly based on the immune network theory and the clone selection principle extracted from vertebrate immune systems. Experiments show that the given clustering algorithm can effectively reduce the redundant information of data, and thus, especially fit to the mass data clustering applications where hierarchical clustering algorithm or other traditional clustering algorithms may be ineffective.
Key words: clustering；artificial immune system；pattern recognition；traffic signal control
1 引言
目前城市交通信號控制應用較為普遍的是多時段定時控制方案。多時段定時控制(time of day，TOD)是根據車流量等交通信息把一天劃分為若干個時間段，不同的時段采用不同的信號優化控制方案。TOD控制的前提是交通時段的合理劃分。傳統上，交通工程技術人員根據收集到的交通流量，繪制流量時間曲線圖，根據曲線的特征人工劃分交通時段。傳統方法具有很大的主觀性，極易產生不合理的時段劃分，難以滿足現代城市交通模式快速變化的需求。
以生物免疫系統為基礎的人工免疫系統(artificial immune systems, AIS) [1]已成為目前國內外計算智能領域一個新的研究熱點。本文在詳細研究生物免疫學和AIS的最新研究成果的基礎上，建立了一種人工免疫數據聚類分析算法，該算法可以有效減少聚類數據的冗余信息，特別適合于解決分級聚類等傳統聚類方法不適應的大數據量聚類問題。論文把建立的人工免疫算法用于城市交通時段的自動劃分[2]，克服了人工時段劃分的不合理性，為TOD交通時段的劃分及城市交通控制方案的制定提供了一條新的思路[3]。
2 免疫系統的基本理論
生物免疫系統是一個由細胞、分子和器官組成的復雜系統，其主要功能是限制異物對肌體的侵害[4]。免疫系統抵御外部入侵，使其機體免受病原侵害的應答反應稱為免疫(immunity)。外部有害病原入侵機體并激活免疫細胞，誘導其發生反應的過程稱為免疫應答。誘導免疫系統產生免疫應答的物質稱為抗原(antigen,簡稱Ag)，能與抗原進行特異性結合的免疫細胞稱為抗體(antibody, 簡稱Ab)。抗原與抗體的結合強度用親和度（affinity）度量。AIS主要涉及T細胞和B細胞的相關免疫特性。B細胞的作用是識別抗原和分泌抗體，T細胞能夠促進和抑制B細胞的產生與分化。免疫系統的結構示意如圖1所示。生物免疫學的研究成果是AIS的理論基礎。本文給出的數據聚類算法，主要基于生物免疫隱喻的克隆選擇理論[5]和免疫網絡理論[6]。當淋巴細胞實現對抗原的識別，即抗體與抗原的親和度(affinity)超過一定閾值后，B細胞被激活并增殖復制產生細胞克隆。由于遺傳和免疫細胞在增殖中的基因突變，形成了免疫細胞的多樣性。當每一種抗原侵入機體后都能在機體內選擇出能識別和消滅相應抗原的免疫細胞克隆，使之激活、分化和增殖，進行免疫應答以最終清除抗原。克隆選擇的主要特征是免疫細胞在抗原刺激下產生克隆擴增，隨后通過遺傳變異分化為多樣性效應細胞和記憶細胞。
圖1 免疫系統的基本結構
3 人工免疫聚類分析算法
AIS借鑒了一些生物免疫系統的功能、原理和模型，使用學習、記憶和關聯檢索來完成識別與分類任務，具有強大的和魯棒的信息處理能力，是一種有效的數據聚類分析方法[7]。AIS將待分析的數據作為抗原，通過抗體對抗原的學習、記憶過程來識別、分類不同數據，并從中找出數據間的相關性能。
假設標稱為[0，1]下的Q個輸入數據集構成抗原Ag，聚類分析的目的就是要通過免疫學習，尋找記憶數據集M作為輸入數據的聚類。
為描述算法的方便，定義如下變量：
Ag：輸入抗原，即待聚類的輸入數據集合，或研究問題的論域：
（1）
Ab：抗體，即N個初始網絡細胞：
（2）
M：記憶數據集，即nt個網絡記憶細胞：
（3）
：所有抗體與抗原Agj的距離度量矢量和親和力矢量；
：M中抗體的相似度矢量；
Nc：激發細胞產生的克隆細胞數量；
Cj：激發細胞產生的克隆細胞群體，親和力成熟后變為C。
基于免疫網絡理論和克隆選擇原理的人工免疫聚類算法由如下步驟構成[5，6，7，8］：
Step1 隨機初始化N個抗體Ab，作為初始網絡細胞。
Step2 設定循環控制參數。
Step3 輸入待聚類數據作為抗原，對抗原Agj(j=1，2,…,Q)進行如下操作：
Step3.1 計算距離度量矢量Dj和親和力矢量AFj：
抗原與抗體之間的距離用歐幾里德距離定義，即
（4）
根據聚類分析的特點，抗原與抗體之間的親和力采用式(5)定義：
(5)
于是
(6)
(7)
Step3.2按照opR(optimal selecting Rate)的比率從Ab中選擇n個與Agj具有最高親和力的抗體進行克隆擴增，產生對應的克隆細胞集合Cj。根據克隆選擇原理，抗體與抗原的親和力越大，抗體產生的克隆細胞數量越多。對n個選擇細胞按親和力從小到大的順序排序，克隆細胞的數量按下式計算。
(8)
式中：Nc為n個抗體產生的克隆細胞總數；α為乘數因子，用于控制克隆群體的規模；Int(.)為取整函數。
Step3.3 應用式(9)對克隆的抗體進行隨機變異操作，實現親和力的成熟，產生具有更高親和力的抗體細胞C。
（9）
式中：rand(CR，NR)為隨機函數，表示從CR中隨機抽取NR個變量；μ為抗體的變異率。生物免疫系統抗體變異的實質是基因片斷的重組，使得子代抗體與抗原的親和力得以迅速提高，而且與抗原具有較大親和力的抗體具有較小的變異率?？贵w的變異率按式(10)確定：
(10)
式中：AFv為抗體親和力的標稱值，k為比例因子，η為衰減控制系數。k與η的合理取值可以保證變異個體在其允許的域值范圍[0，1]之內。
Step3.4 計算C的抗體細胞與抗原Agj的親和力矢量AFc j。
Step3.5 按照rsR(re-selecting Rate)的比率，選擇C中若干個與抗原Agj具有最高親和力的抗體，作為部分記憶細胞Mp 。
Step3.6 去除Mp中相似度sij小于閾值σd的抗體，產生新的記憶集Mk ，實現免疫系統克隆抑制的效果。抗體的相似度sij用抗體間的歐幾里德距離描述，即：
(11)
Step3.7 把部分記憶細胞Mk合并到記憶細胞集合M(M [M;Mk])。
Step4 計算M中各記憶細胞的相似度矢量S，去除M中相似度sij低于閾值σs的抗體，實現不同克隆集的網絡抑制。sij按式(11)計算。
Step5 按照wsR(worst selecting Rate)的比率，隨機產生若干個抗體替換原抗體中親和力較低的個體，體現免疫系統的自組織功能。
Step6 變量替換，返回Step3，進行下一代的網絡學習，直到達到要求的學習代數，或滿足設定的聚類迭代要求（如迭代達到了預定的記憶細胞的個數或抗原與記憶細胞的平均親和力達到了預定的誤差范圍等）。
學習過程結束后，算法的輸出M為聚類數據的記憶數據集，S為記憶數據集各抗體之間的相似度。根據待聚類數據與各記憶細胞的距離，或抗原與記憶細胞的親和度，可方便的實現對抗原數據的聚類。上述聚類算法的核心是保持網絡抗體代克隆、變異及抑制的操作，最終產生記憶數據集。
調節抑制閾值σs可以控制網絡的學習規模和性能，閾值越大，得到的免疫記憶數據越多，分類密度越大，數據的相似性越高。算法中其他參數的選擇原則如下：初始化抗體個數N根據經驗選定，其大小不影響聚類結果，但選擇過大影響計算速度，過小則體現不了抗原特征，一般取N=20?？寺〕藬狄蜃应恋倪x擇取決于初始抗體的個數N。最佳抗體選擇率opR一般取初始抗體的10%到20%，但opR的取值應保證每代至少有一個最優抗體克隆擴增。最差抗體選擇率wsR體現免疫系統的自組織特性，一般取值不應超過10%。從抗體多樣性的角度考慮，再次選擇率rsR可以取較大的值，但聚類的目的是減少數據冗余信息，rsR不易太大，一般取克隆細胞的10%作為部分記憶細胞。
4 交通時段的免疫聚類研究
交通時段的人工免疫聚類分析分兩步進行:第一步將交通數據看作免疫系統的抗原;第二步采用常規的聚類分析方法，對交通流量的免疫記憶集做聚類分析，實現交通時段的自動劃分。
交通工程實踐中，一般以15min的交通流量為基礎進行交通時段的劃分，將一天的96個交通流量數據作為免疫系統的抗原。
4.1 交通數據的預處理
考慮交通數據變化較大（如白天峰值時段的交通流量與夜晚谷值時段的交通流量相差十分懸殊），聚類前首先應用式(12)對交通數據做標準化變換處理：
(12)
式中“*”表示交通流量的原始數據。聚類實踐表明，如果直接應用每天的交通數據進行聚類，結果存在文獻[2]指出的“時段沖突”或“聚類重疊”，即同一時間段在不同的工作日（如每周的星期一）歸屬于不同的類。（3節中各式的p=1，Ag，Ab，M等矩陣均降為同維列向量）。
4.2 交通時段聚類分析實例
本文結合現實應用的需要，利用錦州交警支隊提供的解放路的交通數據庫，進行基于人工免疫算法的交通聚類研究，實現城市交通時段的自動劃分。圖2為根據歷史交通數據的96個平均流量繪制的解放路與士英街路口星期一的交通流量時間曲線圖。
圖2 24小時平均交通流量曲線
把上述96個平均交通流量作為抗原應用于3節的人工免疫聚類算法，進行免疫識別和記憶。算法中的參數設置如下：初始化抗體個數N=20；最佳抗體選擇率opR=20%；克隆乘數因子α =1；再次選擇率rsR=20%，wsR=10%；最大迭代次數NA=15；為保證抗體的多樣性，σd取0.001，σs為0.05。表1是交通流數據的人工免疫計算過程，共分15代。
表1 聚類數據的人工免疫計算過程：
從數據分類結果可以看出第9次迭代結果，記憶數據集同抗原數據之間具有較大的平均親和力，免疫記憶數據集的規模適中，是一種較為理想的數據分類結構。
為直觀起見，將由人工免疫算法得到的記憶數據應用譜系圖的方法描述如圖3所示，顯然，當距離值取0.1時，第9次迭代結果的14個記憶數據被清晰地分成了5類。
圖3 交通流記憶細胞集的聚類譜系圖
采用重心法計算各交通數據與記憶類重心之間的距離，進行交通數據的二次聚類，并與其交通時段對應，得到解放路與士英街路口星期一的交通時段劃分情況如圖4所示。即根據交通流量可以把全天分為如下幾個交通時段:類I時段22:45-5:15；類II時段12:15-14:00，20:30-22:45；類III時段5:15-6:30, 8:15-11:00；類Ⅳ時段11:00-12:15，16:00- 18:00，19:15-20:30;類V時段6:30-8:15，14:00-16:00，18:00-19:15。
圖4 TOD交通時段劃分
5 結束語
人工免疫數據聚類算法可以有效減少聚類數據的冗余信息，特別適合于解決分級聚類等傳統方法不適應的大數據量聚類問題。作者把建立的人工免疫聚類算法應用于城市交通時段的自動劃分，克服了人工時段劃分的不合理性。合理設置參數的取值范圍可以滿足不同聚類問題的需要。
其它作者：
王艷秋（1955-），女，教授，遼寧工業大學信息科學與工程學院院長，博士，碩士研究生導師，研究方向：近代交流調速系統；智能控制。
張?。?981- ），男，遼寧工業大學研究生，研究方向：智能控制。
參考文獻
[1]肖人彬, 王磊.人工免疫系統:原理、模型、分析及展望[J]. 計算機學報, 2002, 25 (12) : 1282 - 1291.
[2]HAUSER T, SCHERER W. Data mining tools for real time traffic signal decision support and maintenance[C]//Proc of IEEE Int Conf on Systems, Man, and Cybernetics. Tucson, USA: IEEE Press, 2001:1471-1477.
[3]PARK.B, LEE Do-Hoon, YUN Hsoo. Enhancement of Time of Day Based Traffic Signal Control [C]// Proc of IEEE Int Conf on Systems, Man, and Cybernetics. USA: IEEE Press, 2003:3619 - 3624.
[4]林學顏, 張玲. 現代細胞與分子免疫學[M].北京:科學出版社, 1999:46-62.
[5]CASTROL, ZUBENF. An evolutionary immune network for data clustering[C]// Proc of the Sixth Brazilian Symposium on Neural Networks. Janeiro: IEEE Press, 2000: 84-89.
[6]DASGU PTAD, FORRESTS. Artificial immune systems in industrial applications[C]//Proc of Second In t Conf on Intelligent Processing and Manufacturing of Materials. Honolulu, USA: IEEE Press, 1999: 257-267.
[7]Dasnupta D. Artificial Immune Systems and Their Applications[M].New York: Sprinner~Verlan, 1999.
[8]TIMM IS J, N EAL M. Artificial immune systems for data analysis [J]. B io System s, 2000, 55 (2): 143 - 150.
[9]D. K. Merchant, G. L. Nemhauser. Optimality conditions for a dynamic traffic assignment model [J]. Transportation Science B, 1978, 12: 200-207.
北京市公安局海淀分局備案號：11010802023656號