劉永富，陳永生

(同濟(jì)大學(xué) 電子與信息工程學(xué)院，上海 200331)

當(dāng)今社會(huì)飛速發(fā)展，城市軌道交通已經(jīng)成為都市生活密不可分的部分。作為一種安全、可靠、清潔、快捷的公共交通運(yùn)輸方式，其為解決我國(guó)人口密集的大城市日益嚴(yán)重的交通擁擠問(wèn)題的重要手段之一。至2010年底，上海已經(jīng)投入運(yùn)營(yíng) 12條線。其中新投入的 6、7、8、9、11號(hào)線均采用基于通信的信號(hào)系統(tǒng)(CBTC)，如此便會(huì)產(chǎn)生大量的日志數(shù)據(jù)。為了使維護(hù)人員能從維修層面，根據(jù)日志中所記載錯(cuò)誤，快速對(duì)系統(tǒng)故障定位，繼而對(duì)設(shè)備進(jìn)行相關(guān)修理，本文利用數(shù)據(jù)挖掘技術(shù)對(duì)日志進(jìn)行關(guān)聯(lián)分析并根據(jù)關(guān)聯(lián)法則，增加錯(cuò)誤診斷準(zhǔn)確性，以防微杜漸，避免釀成事故。

1 關(guān)聯(lián)算法設(shè)計(jì)

日志分析系統(tǒng)的總體結(jié)構(gòu)設(shè)計(jì)思路：以日志資源庫(kù)為基石，以分析平臺(tái)為運(yùn)行支撐，以關(guān)聯(lián)分析功能為中心，建立系統(tǒng)架構(gòu)，并在此系統(tǒng)架構(gòu)的支持下開(kāi)發(fā)軟件。

關(guān)于關(guān)聯(lián)算法的設(shè)計(jì)，選擇目前比較成熟的Apriori算法并加以改進(jìn)。

1.1 Apriori算法介紹

Apriori算法是一種挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。它利用頻繁項(xiàng)集性質(zhì)，用逐層搜索的迭代方法來(lái)找出所有的頻繁項(xiàng)集。首先，找出頻繁1-項(xiàng)集的集合，該集合記作L1。L1用于找頻繁2-項(xiàng)集的集合 L2，而L2用于找L3，如此下去，直到不能找到頻繁k-項(xiàng)集為止。在第 k次循環(huán)中，先產(chǎn)生候選 k項(xiàng)集的集合 Ck，Ck的項(xiàng)集是用來(lái)產(chǎn)生頻繁項(xiàng)集的候選集。Ck中的每個(gè)元素在數(shù)據(jù)庫(kù)中根據(jù)支持度計(jì)數(shù)進(jìn)行驗(yàn)證，決定是否加入Lk[1-2]。

設(shè)有初始項(xiàng)目集 L， 包含 Zk(k＝1～t)，Zk＝(z1，z2，z3，……)，標(biāo)志 TID(1~t)，設(shè) min_sup=a%，(即出現(xiàn)次數(shù)不少于 b次，b＝a%×t)。設(shè)置 K為項(xiàng)目的元素?cái)?shù) (舉例見(jiàn)表1)，算法如下：

(1)重建事務(wù)集數(shù)據(jù)庫(kù)：搜索包含 z1(單個(gè)item)的出現(xiàn)次數(shù)，生成u1； 搜索包含z2的出現(xiàn)次數(shù)，生成 u2； 以此類推，生成 un。

(2)在U中去掉出現(xiàn)次數(shù)少于b的項(xiàng)，簡(jiǎn)化數(shù)據(jù)庫(kù)(存在臨時(shí)表中)。

(3)計(jì)算 u1∪u2，如交集中項(xiàng)數(shù)少于 b則舍去，大于b則儲(chǔ)存為新的集合。 同理計(jì)算 u1∪u3，u1∪u4，…，u1∪un，u2∪u3，…，un-1∪un。 新生成的頻繁 2項(xiàng)集合表示為 Ln。

(4)計(jì)算 L1∪L2?？?L2中第一個(gè) item是否存在于 L1中：若存在，忽略；若不存在，則將此item與L1組成三項(xiàng)集，如交集中項(xiàng)數(shù)少于b則舍去，大于b則儲(chǔ)存，并儲(chǔ)存與之相應(yīng)的項(xiàng)目集。同理類似處理 L1∪L3，L1∪L4，……L1∪Ln，L2∪L3……Ln-1∪Ln。 整理結(jié) 果 ，去 掉重復(fù) 的 項(xiàng) 目集，得到頻繁三項(xiàng)集。

(5)重復(fù)上述步驟，得到頻繁k項(xiàng)集。

1.2 Apriori算法改進(jìn)

在求解頻繁k+1項(xiàng)集的時(shí)候，若其不在長(zhǎng)度為k的頻繁項(xiàng)集之間時(shí)，則必然不在長(zhǎng)度為k+1-頻繁項(xiàng)集之中，而任意一個(gè)k-項(xiàng)集的支持度與規(guī)模小于它的事務(wù)無(wú)關(guān)，故可以直接舍去，從而減少掃描的數(shù)據(jù)量。因此可以在遍歷事務(wù)集時(shí)先遍歷長(zhǎng)度為k的頻繁項(xiàng)集，若存在，再遍歷事務(wù)表。在隨后的過(guò)程中，及時(shí)刪除其中不可能出現(xiàn)在候選項(xiàng)集中的記錄，即字段長(zhǎng)度不大于將要生成的k-頻繁項(xiàng)集k值，而且也不被包含在頻繁項(xiàng)集中的記錄。

改進(jìn)算法通過(guò)先遍歷長(zhǎng)度為k的頻繁項(xiàng)集，減少訪問(wèn)事務(wù)表中的無(wú)效記錄，從而使訪問(wèn)次數(shù)減少而提高了運(yùn)行效率。

1.3 算法示例

(1)初始事務(wù)表 ，取 min_sup＝50%(＝2)，初始項(xiàng)目集表如表1所示。(2)項(xiàng)目集 Z5={1，2，3，4，5}經(jīng)過(guò)變換，如表 2 所示。項(xiàng)目4去掉。表2中為新得到的頻繁一項(xiàng)集，將這些數(shù)據(jù)插入到臨時(shí)表Temp中。

表1 初始項(xiàng)目集表

表2 Z5={1，2，3，4，5}經(jīng)過(guò)變換

表3 二項(xiàng)集

表4 三項(xiàng)集

(3)從 Temp表中得到 K值為1的事務(wù)集，根據(jù)算法敘述生成二項(xiàng)集，如表3所示。

根據(jù)支持度值，將事務(wù)集1 2、1 5去掉，得到頻繁二項(xiàng)集，將這些數(shù)據(jù)插入到臨時(shí)表Temp中。

(4)求出頻繁三項(xiàng)集

從Temp表中得到K值為2的事務(wù)集，根據(jù)算法敘述生成三項(xiàng)集，如表4所示。

根據(jù)支持度值，將事務(wù)集1 2 3、1 3 5 去掉得到頻繁三項(xiàng)集，將這些數(shù)據(jù)插入到臨時(shí)表Temp中。

（5)使用類似的方法可以求出頻繁K項(xiàng)集。

2 PMI日志分析

2.1 PMI簡(jiǎn)介

Alcatel-Thales CBTC信號(hào)系統(tǒng)中實(shí)現(xiàn)聯(lián)鎖功能的設(shè)備稱為 PMI，完整 CBTC調(diào)試完成后 PMI將屬于 ZC(區(qū)域控制器)的一部分，仍然實(shí)現(xiàn)聯(lián)鎖功能。主要組成：計(jì)算機(jī)聯(lián)鎖模塊 (MEI)，看門狗機(jī)架 (CDG)，通信模塊(SCOM)和維護(hù)輔助系統(tǒng)(SAM)。

ZC-PMI聯(lián)鎖結(jié)構(gòu)如圖1所示。

圖1 ZC-PMI聯(lián)鎖結(jié)構(gòu)

PMI接收到ATS的進(jìn)路請(qǐng)求/進(jìn)路取消命令，排列/取消進(jìn)路。PMI會(huì)按進(jìn)路定義中的順序預(yù)留進(jìn)路元素。如果收到的進(jìn)路有區(qū)域重疊，PMI按接收的順序排列重疊區(qū)域的進(jìn)路。一旦進(jìn)路使用完畢，PMI就會(huì)逐段解鎖進(jìn)路。PMI不會(huì)激活敵對(duì)進(jìn)路(反向進(jìn)路、交叉進(jìn)路)。數(shù)據(jù)庫(kù)中含有一個(gè)敵對(duì)進(jìn)路表，PMI通過(guò)檢查該表來(lái)確保從ATS“進(jìn)路請(qǐng)求”命令中接收到的進(jìn)路，不會(huì)與現(xiàn)有的已排列進(jìn)路相沖突。PMI通過(guò)ATS的“道岔動(dòng)作”或“進(jìn)路請(qǐng)求”命令接收道岔動(dòng)作請(qǐng)求。如果道岔已經(jīng)移動(dòng)，那么PMI就拒絕ATS的道岔動(dòng)作請(qǐng)求。PMI會(huì)評(píng)估道岔動(dòng)作規(guī)則從而決定請(qǐng)求的道岔是否可以動(dòng)作。如果道岔是故障的，那么PMI會(huì)拒絕道岔動(dòng)作請(qǐng)求[3]。

2.2 PMI日志

PMI采用2*2取1的工作方式，如此每天便會(huì)產(chǎn)生大量的日志記錄，其中包括正常工作信息以及出錯(cuò)信息。現(xiàn)主要對(duì)報(bào)錯(cuò)、警告信息進(jìn)行相關(guān)分析研究。PMI日志格式如圖2所示。

(1)日期時(shí)間：該記錄產(chǎn)生時(shí)間；

(2)行號(hào)：該記錄唯一標(biāo)識(shí)；

圖2 PMI日志格式

(3)信息類型：A(報(bào)警或意見(jiàn))、C(故障診斷或指示器)、E(消息發(fā)送)、P(狀態(tài)圖轉(zhuǎn)變)等；

(4)錯(cuò)誤關(guān)鍵字：表示該記錄具體錯(cuò)誤，例如：TAZ、COMP、DISPO 等；

(5)報(bào)警參數(shù)：表示該記錄產(chǎn)生的具體位置[2]。

2.3 事務(wù)集提取及關(guān)聯(lián)分析

將系統(tǒng)重啟一次表示為一個(gè)事務(wù)，日志中會(huì)記錄該次重啟的原因。重啟可能有多個(gè)錯(cuò)誤，這就有必要分析其關(guān)聯(lián)性，從而做到防微杜漸。

分析步驟如下：

(1)建立如表5所示的ItemDB表，用于存儲(chǔ)事務(wù)集；

表5 ItemDB表結(jié)構(gòu)

(2)建立如表6所示的Temp表，用于存儲(chǔ)頻繁項(xiàng)目集；

(3)遍歷日志，根據(jù)錯(cuò)誤關(guān)鍵字進(jìn)行文字匹配，將所有錯(cuò)誤存入到ItemDB中作為事務(wù)集；

(4)利用關(guān)聯(lián)規(guī)則對(duì)事務(wù)集進(jìn)行分析，得出錯(cuò)誤之間的關(guān)聯(lián)性；

表6 Temp表結(jié)構(gòu)

(5)分析關(guān)聯(lián)性，得出終結(jié)。

該系統(tǒng)主要完成了對(duì)PMI日志的研究，同時(shí)利用關(guān)聯(lián)規(guī)則進(jìn)行了相關(guān)分析。借于此，對(duì)地鐵維護(hù)、檢修人員有如下好處：(1)快速對(duì)系統(tǒng)故障定位，修理相關(guān)設(shè)備；(2)增加錯(cuò)誤診斷準(zhǔn)確性，減少?zèng)]有必要的排查；(3)若錯(cuò)誤A與錯(cuò)誤B關(guān)聯(lián)，則A發(fā)生的情況下，須預(yù)防B發(fā)生，做到防微杜漸，避免釀成事故。

[1]朱輝生.關(guān)聯(lián)規(guī)則挖掘的兩種改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用與軟件，2006，23(8)：117-119.

[2]毛國(guó)君，段立娟.數(shù)據(jù)挖掘原理與算法[M].北京：清華大學(xué)出版社，2005.

[3]曹錦磊.簡(jiǎn)析地鐵PMI系統(tǒng)[EB/OL].2009-8.

[4]法國(guó)THALES集團(tuán).PMI維護(hù)與安裝技術(shù)文檔[Z].2010.

[5]Judith Bishop.C#3.0 Design Patterns[M].O′Reilly Media，Inc.2007.