王艷輝, 王淑君, 李 曼, 林 帥
(1. 北京交通大學 軌道交通控制與安全國家重點實驗室,北京 100044; 2. 北京交通大學 交通運輸學院,北京 100044;3. 北京交通大學 北京市城市交通信息智能感知與服務工程技術研究中心,北京 100044)
動車組是由自動化控制設備、列車設備以及線路等眾多單元構成的復雜機電設備集成系統,系統中的不同設備之間及同1設備的不同部分之間相互關聯、緊密耦合,單1故障往往會引起“牽一發而動全身”的“水波效應”,造成由微小故障涌現成嚴重故障的后果。
為此,本文基于CRHX型動車組牽引系統的故障數據,課題組前期利用改進N-Gram算法[1]提取故障信息特征詞,在此研究成果的基礎上,挖掘故障數據中蘊含的關聯規則,研究設備間的關聯失效關系。
對于關聯規則挖掘算法的研究始于Agrawal等人于1993年首次提出Apriori算法[2],傳統的關聯規則挖掘算法大多數是以Apriori算法為基礎。該算法需要多次掃描數據庫并生成大量候選集,效率較低。針對Apriori算法的缺陷,Han J[3]等人提出一種基于頻繁模式樹(FP-tree)進行頻繁項集挖掘的FP-Growth算法,該算法只需掃描數據庫兩次且不需要產生候選集,顯著縮小了搜索空間,相對于Apriori算法的效率有1個數量級的改善[4]。但是該算法需要遞歸地生成大量的條件FP-樹,耗費大量的存儲空間和時間。為此研究者提出了許多基于該算法的改進算法:基于hash表的FP-tree頻繁模式挖掘算法[5],頻繁項集并行挖掘算法[6],基于MapReduce的FP-Growth算法[7],MS-FP-Growth算法[8],信息導向的FP-Growth算法[9],基于項目約束的改進FP-Growth算法[10]等。上述算法從不同方面對FP-Growth算法進行了改進,但每次生成新的FP樹時依然需要2次遍歷條件模式基,導致系統需要反復申請本地以及數據庫服務器的資源查詢相同內容的海量數據,一方面使算法的執行效率大大降低,另一方面給數據庫服務器帶來負擔。
基于上述算法存在的問題,同時結合動車組故障信息特征詞的特點,本文在經典FP-Growth算法的基礎上加入關系表得到改進的FP-Growth算法,避免了第1次遍歷條件模式基,提高了算法的效率。利用改進的FP-Growth算法針對設備故障信息特征詞挖掘頻繁項集,進一步得到設備關聯失效規則,構建設備關聯失效模型并以CRHX型動車組牽引系統為例進行分析,驗證了該算法的可行性、實用性和高效性。
本文依據CRHX型動車組牽引系統自2011年1月至2012年4月的故障數據進行研究,共計6 000余條,部分故障數據見表1。對以上數據進行初步分析后發現存在以下問題。

表1 CRHX型動車組牽引系統部分故障數據表
(1) 故障數據量較大
動車組系統包含兩萬多個零部件,每個零部件都有可能存在多種故障情況;另外,每條故障數據又包含故障時間、故障描述、所屬列車編號等73個屬性字段,由此可見故障數據量的巨大。
(2) 故障數據的不一致性
目前故障數據主要是由人工記錄,大部分為描述性語言,不同的人對同一故障現象的命名不同,描述的詳細程度也不同,例如:對于部件的異常排風,有的故障描述中用的是“漏風”一詞,有的是“排風”,有的是“打風”。因此故障數據的格式缺乏統一的標準。
(3) 故障數據的不完整性
雖然經過人員的審核,故障數據中仍出現空缺值或由于人工記錄造成部分數據錯誤的情況。例如:“故障所屬設備”這一列數據中空缺值達到20%;某條故障數據中,危害等級為災難,而運營模式為正常,故障類別為碎修(未晚點),數據明顯錯誤。
(4) 故障數據屬性字段的冗余性
并非所有的故障數據都可以用來進行分析。比如部分數據為空白數據,部分數據為冗余數據對于本研究沒有意義。例如整列空白的字段包括:維修材料費用、修復后系統測試時間、修復后系統調試時間等,冗余字段包括:故障錄入人、故障錄入時間、審核人、審核時間等。
這些故障數據往往由于不便量化、不夠精確或由于應用技術的限制而無法被直接利用,無法充分有效地挖掘其中隱含的相關信息,因此前期課題組提出改進的N-Gram算法[1],利用此算法從故障數據中提取故障信息特征詞,經初步分析得出,故障信息特征詞具有以下特點:
(1) 故障信息特征詞是從故障數據中提取的概念標識,保留了原始故障數據的基本特征,仍可反映系統故障的基本情況。
(2) 相較于原始故障數據,故障信息特征詞更加簡潔、直觀、明了,便于關聯規則挖掘算法的應用。
(3) 故障信息特征詞中蘊含著設備的關聯失效關系。
(4) 故障信息特征詞提取的方式是否得當、提取的特征是否有效,直接影響到設備關聯失效規則挖掘的準確性。
基于動車組的故障數據及故障信息特征詞的以上特點,本文提出改進的FP-Growth算法挖掘設備的關聯失效規則,研究設備間的關聯失效關系。改進算法適用于此類以文字記錄為主的文本型數據庫的關聯規則挖掘。
FP-Growth算法是經典的關聯規則挖掘算法之一,該算法不產生候選模式,采用頻繁模式增長算法對頻繁項集進行壓縮,得到頻繁模式FP樹(Frequent Pattern Tree)[3]。FP樹是一種特殊的前綴樹,分為頻繁項目頭表和頻繁項前綴子樹,用樹的分支標識項目名稱,用樹的節點存儲后綴項。用路徑表示項集,存儲在1棵子樹中的項目具有相同前綴的項集。算法的主要思路為:把事務數據庫中所有的頻繁項集壓縮到1棵FP樹上,保留各個項集之間的關聯關系;之后把這種壓縮后的數據庫分成條件數據庫(特殊類型的映射數據庫),每條關聯規則就是1個頻繁項目,分別挖掘各個條件數據庫,并且創建1個項目頭表,每個項都要通過1個節點指向它在樹上的出現位置。所以項目事務數據庫中包含的所有信息都壓縮在FP樹中,對事務數據庫的挖掘變成對FP樹的挖掘。FP樹結構對數據起到良好的壓縮作用,只需掃描事務名稱和項目集合2次數據庫,即可將數據庫中頻繁項目信息全部壓縮存儲在FP樹上,其后對頻繁項集支持度的計算只需在FP樹上進行,不需要掃描整個數據庫。
2.1節的經典FP-Growth算法忽略了新支持度計數列表與原有支持度計數列表間的關系,因此需要2次遍歷條件模式基,不僅降低了算法效率而且給數據庫服務器造成負擔。在經典FP-Growth算法的基礎上加入關系表,通過使用二維向量記錄頻繁度,省略了每次構造新的條件FP樹時對條件模式基的第1次遍歷,僅需遍歷1次條件模式基,大大縮短建立FP樹的時間,算法效率明顯提高。具體改進思路為
(1) 遍歷事務集合S,得到各個項目的頻繁度后,剔除頻繁度低于支持度的項目,剩余項目按照支持度降序排列,生成頻繁項目集合L,得到項目表和FP樹。同時創建任意兩項關系表,詞關系表為1個二維表,記錄事務數據庫中任何兩項目同時出現的支持度計數。
(2) 關系表中記錄了事務數據庫中所有同時出現的任意2項的頻繁度F。刪除兩項目同時出現的頻繁度小于給定最小支持度的組合項目,得到新的關系表,稱此表為關系簡表。
(3) 根據關系簡表,創建不同后綴項目集β條件下的FP子樹。如當β={x}時,抽取關系簡表中與x相關的行、列值,將對應行值和列值相加,可得到條件β下,x與其他項的支持度計數,構建出當前條件下的FP子樹,進而得到不同后綴項目集β條件下的所有頻繁項目集。
改進的FP-Growth算法在對FP樹遍歷搜索頻繁項集時,利用關系簡表有效地提高了算法的效率。改進前后的FP-Growth算法,在FP樹的構造過程中是相同的,都是1次遍歷每個事務得到FP樹,同時統計每個事務的頻繁度,并降級排列,得到與FP樹對應的項目頭表。改進算法的實現流程為
Step1建立項目關系表。統計項目事務數據庫S中任意兩項同時出現的頻繁度,建立項目關系表,項目關系表中記錄了所有的兩兩項目同時出現的頻繁度,這里稱組合項的頻繁度。例如事務{A,B,C,D},則得到的所有二維向量關系為A,B、(A,C)、A,D、B,C、B,D、C,D,其中B,C≠C,B。
Step2建立項目關系簡表。由于對于組合頻繁度小于最小支持度的兩項目關系并不關心,因此需要把這些項目關系從表中刪除,得到新的項目關系表,將此表稱為關系簡表,見圖1。

Step3考慮項目頭表中項目頻繁度最小的項目。項目A出現在表格的最后為項目頻繁度最小的項,此時令后綴項目集β={A},獲取關系簡表中第1行和第1列中關于A的所有項目的支持度信息,可以得到{(A,B):1+0;(A,C):2+0;(A,D):1+0;A,E:1+0};相關項目的支持度集合記為L_A,因此L_A={B:1+0;C:2+0;D:1+0;E:1+0};剔除支持度小于2的項目,可得條件項目基為{(C:2)},得到對應的頻繁項目集合為{{C,A}:2}。
Step4當后綴項目集β={E}時,在關系簡表中獲取與E相關的第5列的所有項目的支持度信息,具體結果為{(E,A):0+1;(E,B):0+3;(E,C):0+2;(E+D):0+0};相關項目的支持度集合L_E={A:0+1,B:0+3,C:0+2};剔除支持度小于2的項目,可得條件項目基為{(B:2),C:2},得到對應的頻繁項目集合為{{B,E}:2,{C,E}:2}。
同上述步驟,當β={C}時,相關項目的支持度集合L_C={A:0+2,B:0+2,D:1+0,E:2+0},條件項目基{B:2,E:2},得到對應的頻繁項目集合為{{B,C}:2,{E,C}:2},整個算法的具體實現流程見圖2。

為證明本文中改進FP-Growth算法的準確性與高效性,將其與兩類經典算法(改進Apriori算法與FP-Growth算法)進行了性能方面的對比與分析。測試環境為Intel Core 2,主頻2 GHz,內存2 GB,操作系統為Windows7,使用Java編程。其中改進Apriori算法代碼中采用了許多優化措施,其性能已大大優于最初的Apriori算法,是公認的Apriori算法的最佳實現。由于所采用的3種算法在同一數據集和相同支持度下得到的頻繁項集完全相同,因此很好地證明了改進FP-Growth算法的準確性。
本實驗中采用的測試數據集為T10I4D100K和Retail,均屬于稀疏型數據集,其中T10I4D100K共有10 0000條記錄,包含870個項目,項目的支持度分布較均勻,最大項目支持度計數為7 828,而Retail是更稀疏數據集,共有88 162條記錄,包含8 708個項目,項目的支持度跨度較大,最大項目支持度計數為50 675。實驗分別對這2個數據集從2個方面進行算法運行時間的比較,一個方面是測試使用關系簡表后對算法運行時間的影響,在對兩個數據集都選擇支持度為0.1的條件下,每次加載不同的事務數量進行測試,實驗結果見圖3;另一個方面是測試至多掃描一次事務數據庫對算法運行時間的影響,對2個數據集都加載全部事務,每次選擇不同的支持度,實驗結果見圖4。圖4中給出的運行時間是從讀取數據開始,一直到得出所有頻繁項集的時間,但不包括輸出結果的時間。


表2 針對T10I4D100K數據集不同支持度下的算法占用內存比

支持度/%FP?Growth算法/改進FP?Growth算法改進Apriori算法/改進FP?Growth算法81.211.361.212.842.914.223.819.315.227.5

表3 針對Retail數據集不同支持度下的算法占用內存比
圖3(a)、3(b)分別給出了針對兩個數據集在不同事務數量下的算法運行時間比較情況。性能大致為:改進FP-Growth大于改進Apriori大于FP-Growth,且事務數量越多效率越高,主要原因是當事務數量增大時只需更新關系簡表,此后的挖掘可以脫離原數據庫進行,極大地縮小了開銷。對于T10I4D100K數據集,改進FP-Growth的效率比FP-Growth快3~5倍,比改進Apriori快2~4倍;對于Retail數據集,改進FP-Growth的效率比FP-Growth快4~8倍,比改進Apriori快2~4倍。圖4(a)、4(b)分別給出了在針對兩個數據集在不同支持度下的算法運行時間比較情況。性能大致為:改進FP-Growth>改進Apriori大于FP-Growth,且隨著支持度的增加,算法的效率也更高,當支持度增加到一定程度后,算法運行時間趨向1個穩定值。主要原因是絕大部分時間消耗在1次掃描事務數據庫上,而這部分時間不會發生變化。對于T10I4D100K數據集,改進FP-Growth的效率比FP-Growth快2~3倍,比改進Apriori快1倍以上;對于Retail數據集,改進FP-Growth的效率比FP-Growth快10%~40%,比改進Apriori快10%~30%。從測試結果可以看出,采用加入關系簡表改進措施后,改進FP-Growth算法的性能對于2個數據集都是效率最高的,其次為改進Apriori算法、FP-Growth算法。其中,采用優化措施后的Apriori算法,對于非稠密數據具有較高的效率,其性能優于FP-Growth算法。
此外可將算法所占用內存的比值對比其性能。結果見表2、表3,占用內存的比值分別為FP-Growth算法和改進Apriori算法與改進FP-Growth算法的比值。可見改進FP-Growth算法占用內存效率最低。其中,改進Apriori算法經優化后雖然運行速度較快,但是由于算法需要生成候選項集,因此占用內存仍然較高。而FP-Growth算法和改進FP-Growth算法不需產生候選項集,因此占用內存要明顯小于改進Apriori算法。此外,由于改進FP-Growth算法大大降低了掃描數據庫的次數,而且當支持度變化時無需再次訪問數據庫,因此內存占用也明顯小于FP-Growth算法。
因此,改進的FP-Growth算法在挖掘頻繁項集時優勢明顯,具有較好的性能。實驗結果證明了改進FP-Growth算法的準確性與高效性。
基于改進的FP-Growth算法挖掘設備的關聯失效規則,在前節中已經利用改進的FP-Growth算法得到了事務數據庫S中項目所有的頻繁項集,具體結果見表4。根據得到的頻繁項集,生成關聯失效規則,見表5,具體步驟[11]為
Step1對于任何一個頻繁項集l,產生l的所有非空子集;
Step2對于l的每個非空子集s,如果滿足置信度Confidence(s?l-s)≥minConf,則說明s與l-s之間存在關聯失效關系,則說明s?l-s為強關聯規則,即項l-s發生失效引起項s失效。

表4 事務數據庫S對應的頻繁項集

表5 關聯失效規則表
利用改進的FP-Growth算法對設備故障信息特征詞的事務數據庫進行分析,得到設備失效的頻繁項目集,挖掘出各個項目之間的關聯失效規則,進而建立關聯失效模型,具體步驟為
Step1建立事務數據庫。由設備故障信息特征詞構成的事務集合得到事務數據庫;
Step2建立頻繁項目集庫。根據改進的FP-Growth算法,得到事務數據庫中的頻繁i-項集(i=1,2,…,n),進而建立頻繁項集庫;
Step3挖掘項目的關聯失效規則。根據得到的頻繁項集找出影響項目和被影響項目,生成項目之間的關聯失效規則。關聯失效規則的前項和后項存在關聯失效關系,前項為被影響項,后項為影響項,后項發生失效會引起前項失效;
Step4建立關聯失效模型。由每個項目的關聯失效規則,得到所有項目的關聯失效規則,建立關聯失效模型,見圖5。

利用改進的FP-Growth算法對CRHX型動車組的牽引系統進行實例分析。CRHX型動車組采用動力分散交流傳動方式,最高運營速度為250 km/h。整個車體采用8輛編組形式,4動2拖,分為2個動力單元,每個動力單元包括兩個動車和2輛拖車(T-M-M-T)[12]。CRHX型動車組牽引系統由兩個基本動力單元組成,每個基本動力單元主要由1臺牽引變壓器、2臺牽引變流器、8臺三相交流異步牽引電機構成。
基于2011年至2012年期間CRHX型動車組牽引系統的故障數據進行分析,每條故障數據包含故障編號、列車編號、故障模式、故障日期、初步處理措施、初步原因、危害等級、運營模式、運行公里數、故障所屬系統、所屬子系統、所屬部件等屬性。提取到的CRHX型動車組牽引系統故障信息特征詞如下:電壓互感器、自動過分相裝置、受電弓、高壓隔離開關、主斷路器、避雷器、四象限整流器、輔助逆變器、牽引電機、牽引逆變器等設備。選取6 000多條故障數據,構建2 000多個事務,得到包含2 000多個項目集合的事務數據庫,事務數據庫的部分結果見表6。
為使關聯分析簡單化,需要對事務數據庫中的設備進行字母編碼,編碼規則見表7。將牽引系統設備的事務數據庫按照編碼規則進行設備編碼,得到新的事務數據庫,部分編碼后的事務數據庫見表8。

表6 事務數據庫的部分結果

表7 設備編碼定義表

表8 部分編碼后的事務數據庫
基于改進的FP-Growth算法對設備的編碼事務數據庫進行關聯失效分析,具體分析步驟為
Step1構建頻繁模式樹FP-tree
(1) 掃描編碼事務數據庫,統計各個項目的支持度,生成長度為l的頻繁項目候選集q及其支持度。對候選集q,按照支持度降序排列,本文設定最小支持度為20,將支持度小于20的項目刪除,生成頻繁項目集合L,具體生成結果見表9。

表9 各個項目頻繁度匯總表
(2) 創建FP樹根節點,標記為“null”,按照FP樹的創建過程,得到牽引系統的FP樹,見圖6。

Step2遍歷FP樹挖掘頻繁項集
按照改進的FP-Growth算法構建頻繁項集,基于Java編程語言對該算法進行實現。經過程序的運行,遍歷根據牽引系統事務數據庫構造的FP樹,同時結合根據支持度構建的二維簡表,得到項目的各個頻繁項集。
Step3構建關聯失效模型
根據各個頻繁項目集合可以找到各個項目的關聯項目,找到被影響項目和影響項目,得到設備之間的關聯失效規則,見表10。

表10 牽引系統設備的關聯失效規則表
根據關聯失效規則中前項與后項的關系便可建立設備的關聯失效模型,結果見圖7。該模型很好地描述了動車組設備的關聯失效過程及機理。以關聯失效模型為研究基礎,進一步展開對設備間關聯失效特性、關聯失效傳播的機制及相關防控策略的研究,可以使設備故障得到早診斷、早預防、早處理,防止設備故障的進一步擴大。因此本文提出的關聯失效模型構建方法具有一定的理論依據和指導意義,并為其他領域的關聯失效研究提供了參考。

采用與前節相同的3種算法代碼進行性能測試。實驗采用的測試數據集為CRHX型動車組牽引系統的設備故障信息特征詞,具有6 850條記錄,包含2 730個事務,與T10I4D100K、Retail數據集同屬于稀疏型數據集。測試環境為Intel Core 2,主頻2 GHz,內存2 GB,操作系統為Windows7,使用Java編程。

圖8給出了在上述數據集不同支持度下的算法運行時間比較情況。在不同支持度下改進FP-Growth算法的運行效率都明顯優于FP-Growth算法和改進Apriori算法,大致為改進FP-Growth算法大于改進Apriori算法,改進Apriori算法大于FP-Growth算法,改進FP-Growth算法的效率比FP-Growth算法快2~3倍,比改進Apriori算法快1~2倍。而且隨著支持度閾值的減小,改進FP-Growth算法的增長趨勢也較平緩,當支持度閾值較小時,改進FP-Growth算法的優勢更能凸顯。因此,改進FP-Growth算法優勢明顯,具有較好的性能。
本文依據前期課題組對故障數據的研究成果,在故障信息特征詞的基礎上展開對動車組的設備間關聯失效關系的研究。在深入了解關聯分析的理論知識和經典案例的基礎上提出關聯規則挖掘算法,即改進的FP-Growth算法。經典FP-Growth算法中需要2次掃描數據庫建立FP樹,針對此問題對算法進行改進,提出了使用關系表的方法,從而省去經典算法對條件模式基的第1次遍歷,至多掃描數據庫1次。而且當支持度計數和數據變化時,只需要更新關系表,此后的挖掘可以脫離原數據庫進行,極大地縮小了開銷。以兩類經典數據集對改進算法進行了性能測試,表明該算法是1個高效準確的關聯規則挖掘算法。
基于改進的FP-Growth算法對故障信息的特征詞進行關聯分析,挖掘設備關聯失效規則并構建設備關聯失效模型,為動車組故障傳播、故障診斷及維修方面的研究提供了理論依據。并以CRHX型動車組牽引系統進行了實例分析,驗證了本方法的有效性,由于故障數據有限,后續需要從大樣本角度對該方法的實用性進行進一步的應用和檢驗。然而對于具有關聯失效關系的設備,其發生的故障相互影響,甚至循環作用,使得故障診斷變得非常復雜,以關聯失效模型為載體探求系統故障診斷方法成為進一步研究的重點問題。另外,一般的關聯規則挖掘方法多數是大眾化、通用型的,很少有專門為分析和挖掘動車組的故障數據而設計的。為此必須根據動車組的特點進行改進和創新現有方法,并進行合理組合,從而提高關聯失效規則挖掘的高效性和準確性。
參考文獻:
[1] 李曼. 基于機器學習的故障識別方法與系統研制[D].北京:北京交通大學, 2015.
[2] AGRAWAL R, IMIELINSKI T, SWAMI A. Mining Association Rules Between Sets of Items in Large Databases[J]. ACM Sigmod Record, 1993, 22(2): 207-216.
[3] HAN Mining. Frequent Patterns without Candidate Generation[C]//Proceedings of the 2000 ACM-SIGMOD International Conference on Management of Data.New York:ACM, 2000:1-12.
[4] SINGH A K, KUMAR A, MAURYA A K. An Empirical Analysis and Comparison of Apriori and FP-growth Algorithm for Frequent Pattern Mining[C]// Proceedings of the IEEE 2014 International Conference on Advanced Communication Control and Computing Technologies(ICACCCT). New York: IEEE, 2014:1 599-1 602.
[5] 李也白, 唐輝, 張淳, 等. 基于改進的FP-tree的頻繁模式挖掘算法[J].計算機應用, 2011,31(1): 101-105.
LI Yebai,TANG Hui,ZHANG Chun,et al. Frequent Pattern Mining Algorithm Based on Improved FP-tree [J].Application Research of Computers, 2011,31(1): 101-105.
[6] 李力, 翟東海, 靳蕃. 一種頻繁項集并行挖掘算法[J].鐵道學報, 2003,25(6):71-75.
LI Li,ZHAI Haidong, JIN Fan. A Parallel Algorithm for Frequent Itemsets Mining[J]. Journal of the China Railway Society, 2003, 25(6):71-75.
[7] CHEN X S, ZHANG S, TONG H, et al. FP-growth Algorithm Based on the Boolean Matrix and Mapreduce[J].Journal of South China University of Technology,2014:42(1):135-141.
[8] TAKTAK W, SLIMANI Y. MS-FP-Growth: A Multi-support Vrsion of FP-Growth Agorithm[J]. International Journal of Hybrid Information Technology, 2014, 7(3):147-157.
[9] NEERBEK J. Message-driven FP-growth[C]//Proceedings of the ACM 2012 International Conference on WICSA/ECSA Companion Volume. New York:ACM, 2012: 29-36.
[10] 趙孝敏, 何松華, 李賢鵬, 等. 一種改進的 FP-Growth 算法及其在業務關聯中的應用[J]. 計算機應用, 2008,28(9):2 341-2 344.
ZHAO Xiaomin,HE Songhua, LI Xianpeng,et al. Improved FP-Growth Algorithm and Its Application in the Business Association [J].Application Research of Computers, 2008, 28(9):2 341-2 344.
[11] 沈斌. 關聯規則技術研究[M].杭州:浙江大學出版社,2011:3-12.
[12] 王華勝, 王憶巖, 謝川川, 等. CRH2型動車組可靠性建模與分配[J].鐵道學報, 2009,31(5):108-112.
WANG Huasheng,WANG Yiyan, XIE Chuanchuan, et al. Reliability Modeling and Assigning for CRH2 Electric Multiple Unit [J]. Journal of the China Railway Society, 2009,31(5):108-112.