日本在线www-日本在线播放一区-日本在线不卡免费视频一区-日本在线不卡视频-成人影院久久久久久影院-成人影院一区二区三区

3 人工免疫聚類分析算法

    AIS借鑒了一些生物免疫系統(tǒng)的功能、原理和模型，使用學(xué)習(xí)、記憶和關(guān)聯(lián)檢索來完成識(shí)別與分類任務(wù)，具有強(qiáng)大的和魯棒的信息處理能力，是一種有效的數(shù)據(jù)聚類分析方法[7]。AIS將待分析的數(shù)據(jù)作為抗原，通過抗體對(duì)抗原的學(xué)習(xí)、記憶過程來識(shí)別、分類不同數(shù)據(jù)，并從中找出數(shù)據(jù)間的相關(guān)性能。

    假設(shè)標(biāo)稱為[0，1]下的Q個(gè)輸入數(shù)據(jù)集構(gòu)成抗原Ag，聚類分析的目的就是要通過免疫學(xué)習(xí)，尋找記憶數(shù)據(jù)集M作為輸入數(shù)據(jù)的聚類。

    為描述算法的方便，定義如下變量：

    Ag：輸入抗原，即待聚類的輸入數(shù)據(jù)集合，或研究問題的論域： 

          （1）

    Ab：抗體，即N個(gè)初始網(wǎng)絡(luò)細(xì)胞：

                （2）

    M：記憶數(shù)據(jù)集，即nt個(gè)網(wǎng)絡(luò)記憶細(xì)胞：

                （3）

    ：所有抗體與抗原Agj的距離度量矢量和親和力矢量；

    ：M中抗體的相似度矢量；

    Nc：激發(fā)細(xì)胞產(chǎn)生的克隆細(xì)胞數(shù)量；

    Cj：激發(fā)細(xì)胞產(chǎn)生的克隆細(xì)胞群體，親和力成熟后變?yōu)镃。

    基于免疫網(wǎng)絡(luò)理論和克隆選擇原理的人工免疫聚類算法由如下步驟構(gòu)成[5，6，7，8］：

    Step1 隨機(jī)初始化N個(gè)抗體Ab，作為初始網(wǎng)絡(luò)細(xì)胞。

    Step2 設(shè)定循環(huán)控制參數(shù)。

    Step3 輸入待聚類數(shù)據(jù)作為抗原，對(duì)抗原Agj(j=1，2,…,Q)進(jìn)行如下操作：

    Step3.1 計(jì)算距離度量矢量Dj和親和力矢量AFj：

    抗原與抗體之間的距離用歐幾里德距離定義，即

       （4）

    根據(jù)聚類分析的特點(diǎn)，抗原與抗體之間的親和力采用式(5)定義：

         (5)

    于是

           (6)

        (7)

    Step3.2按照opR(optimal selecting Rate)的比率從Ab中選擇n個(gè)與Agj具有最高親和力的抗體進(jìn)行克隆擴(kuò)增，產(chǎn)生對(duì)應(yīng)的克隆細(xì)胞集合Cj。根據(jù)克隆選擇原理，抗體與抗原的親和力越大，抗體產(chǎn)生的克隆細(xì)胞數(shù)量越多。對(duì)n個(gè)選擇細(xì)胞按親和力從小到大的順序排序，克隆細(xì)胞的數(shù)量按下式計(jì)算。

        (8)

    式中：Nc為n個(gè)抗體產(chǎn)生的克隆細(xì)胞總數(shù)；α為乘數(shù)因子，用于控制克隆群體的規(guī)模；Int(.)為取整函數(shù)。

    Step3.3 應(yīng)用式(9)對(duì)克隆的抗體進(jìn)行隨機(jī)變異操作，實(shí)現(xiàn)親和力的成熟，產(chǎn)生具有更高親和力的抗體細(xì)胞C。

         （9）

    式中：rand(CR，NR)為隨機(jī)函數(shù)，表示從CR中隨機(jī)抽取NR個(gè)變量；μ為抗體的變異率。生物免疫系統(tǒng)抗體變異的實(shí)質(zhì)是基因片斷的重組，使得子代抗體與抗原的親和力得以迅速提高，而且與抗原具有較大親和力的抗體具有較小的變異率。抗體的變異率按式(10)確定：

        (10)

    式中：AFv為抗體親和力的標(biāo)稱值，k為比例因子，η為衰減控制系數(shù)。k與η的合理取值可以保證變異個(gè)體在其允許的域值范圍[0，1]之內(nèi)。

    Step3.4 計(jì)算C的抗體細(xì)胞與抗原Agj的親和力矢量AFc j。

    Step3.5 按照rsR(re-selecting Rate)的比率，選擇C中若干個(gè)與抗原Agj具有最高親和力的抗體，作為部分記憶細(xì)胞Mp 。

    Step3.6 去除Mp中相似度sij小于閾值σd的抗體，產(chǎn)生新的記憶集Mk ，實(shí)現(xiàn)免疫系統(tǒng)克隆抑制的效果。抗體的相似度sij用抗體間的歐幾里德距離描述，即：

        (11)

    Step3.7 把部分記憶細(xì)胞Mk合并到記憶細(xì)胞集合M(M [M;Mk])。

    Step4 計(jì)算M中各記憶細(xì)胞的相似度矢量S，去除M中相似度sij低于閾值σs的抗體，實(shí)現(xiàn)不同克隆集的網(wǎng)絡(luò)抑制。sij按式(11)計(jì)算。

    Step5 按照wsR(worst selecting Rate)的比率，隨機(jī)產(chǎn)生若干個(gè)抗體替換原抗體中親和力較低的個(gè)體，體現(xiàn)免疫系統(tǒng)的自組織功能。

    Step6 變量替換，返回Step3，進(jìn)行下一代的網(wǎng)絡(luò)學(xué)習(xí)，直到達(dá)到要求的學(xué)習(xí)代數(shù)，或滿足設(shè)定的聚類迭代要求（如迭代達(dá)到了預(yù)定的記憶細(xì)胞的個(gè)數(shù)或抗原與記憶細(xì)胞的平均親和力達(dá)到了預(yù)定的誤差范圍等）。

    學(xué)習(xí)過程結(jié)束后，算法的輸出M為聚類數(shù)據(jù)的記憶數(shù)據(jù)集，S為記憶數(shù)據(jù)集各抗體之間的相似度。根據(jù)待聚類數(shù)據(jù)與各記憶細(xì)胞的距離，或抗原與記憶細(xì)胞的親和度，可方便的實(shí)現(xiàn)對(duì)抗原數(shù)據(jù)的聚類。上述聚類算法的核心是保持網(wǎng)絡(luò)抗體代克隆、變異及抑制的操作，最終產(chǎn)生記憶數(shù)據(jù)集。

    調(diào)節(jié)抑制閾值σs可以控制網(wǎng)絡(luò)的學(xué)習(xí)規(guī)模和性能，閾值越大，得到的免疫記憶數(shù)據(jù)越多，分類密度越大，數(shù)據(jù)的相似性越高。算法中其他參數(shù)的選擇原則如下：初始化抗體個(gè)數(shù)N根據(jù)經(jīng)驗(yàn)選定，其大小不影響聚類結(jié)果，但選擇過大影響計(jì)算速度，過小則體現(xiàn)不了抗原特征，一般取N=20。克隆乘數(shù)因子α的選擇取決于初始抗體的個(gè)數(shù)N。最佳抗體選擇率opR一般取初始抗體的10%到20%，但opR的取值應(yīng)保證每代至少有一個(gè)最優(yōu)抗體克隆擴(kuò)增。最差抗體選擇率wsR體現(xiàn)免疫系統(tǒng)的自組織特性，一般取值不應(yīng)超過10%。從抗體多樣性的角度考慮，再次選擇率rsR可以取較大的值，但聚類的目的是減少數(shù)據(jù)冗余信息，rsR不易太大，一般取克隆細(xì)胞的10%作為部分記憶細(xì)胞。

4 交通時(shí)段的免疫聚類研究

    交通時(shí)段的人工免疫聚類分析分兩步進(jìn)行:第一步將交通數(shù)據(jù)看作免疫系統(tǒng)的抗原;第二步采用常規(guī)的聚類分析方法，對(duì)交通流量的免疫記憶集做聚類分析，實(shí)現(xiàn)交通時(shí)段的自動(dòng)劃分。

    交通工程實(shí)踐中，一般以15min的交通流量為基礎(chǔ)進(jìn)行交通時(shí)段的劃分，將一天的96個(gè)交通流量數(shù)據(jù)作為免疫系統(tǒng)的抗原。

    4.1 交通數(shù)據(jù)的預(yù)處理

    考慮交通數(shù)據(jù)變化較大（如白天峰值時(shí)段的交通流量與夜晚谷值時(shí)段的交通流量相差十分懸殊），聚類前首先應(yīng)用式(12)對(duì)交通數(shù)據(jù)做標(biāo)準(zhǔn)化變換處理：

        (12)

    式中“*”表示交通流量的原始數(shù)據(jù)。聚類實(shí)踐表明，如果直接應(yīng)用每天的交通數(shù)據(jù)進(jìn)行聚類，結(jié)果存在文獻(xiàn)[2]指出的“時(shí)段沖突”或“聚類重疊”，即同一時(shí)間段在不同的工作日（如每周的星期一）歸屬于不同的類。（3節(jié)中各式的p=1，Ag，Ab，M等矩陣均降為同維列向量）。

    4.2 交通時(shí)段聚類分析實(shí)例

    本文結(jié)合現(xiàn)實(shí)應(yīng)用的需要，利用錦州交警支隊(duì)提供的解放路的交通數(shù)據(jù)庫，進(jìn)行基于人工免疫算法的交通聚類研究，實(shí)現(xiàn)城市交通時(shí)段的自動(dòng)劃分。圖2為根據(jù)歷史交通數(shù)據(jù)的96個(gè)平均流量繪制的解放路與士英街路口星期一的交通流量時(shí)間曲線圖。

圖2   24小時(shí)平均交通流量曲線

    從數(shù)據(jù)分類結(jié)果可以看出第9次迭代結(jié)果，記憶數(shù)據(jù)集同抗原數(shù)據(jù)之間具有較大的平均親和力，免疫記憶數(shù)據(jù)集的規(guī)模適中，是一種較為理想的數(shù)據(jù)分類結(jié)構(gòu)。

    為直觀起見，將由人工免疫算法得到的記憶數(shù)據(jù)應(yīng)用譜系圖的方法描述如圖3所示，顯然，當(dāng)距離值取0.1時(shí)，第9次迭代結(jié)果的14個(gè)記憶數(shù)據(jù)被清晰地分成了5類。

    采用重心法計(jì)算各交通數(shù)據(jù)與記憶類重心之間的距離，進(jìn)行交通數(shù)據(jù)的二次聚類，并與其交通時(shí)段對(duì)應(yīng)，得到解放路與士英街路口星期一的交通時(shí)段劃分情況如圖4所示。即根據(jù)交通流量可以把全天分為如下幾個(gè)交通時(shí)段:類I時(shí)段22:45-5:15；類II時(shí)段12:15-14:00，20:30-22:45；類III時(shí)段5:15-6:30, 8:15-11:00；類Ⅳ時(shí)段11:00-12:15，16:00- 18:00，19:15-20:30;類V時(shí)段6:30-8:15，14:00-16:00，18:00-19:15。

圖4   TOD交通時(shí)段劃分