李 鑫，史天運(yùn)，常 寶，馬小寧，劉 軍

（1.中國(guó)鐵道科學(xué)研究院研究生部，北京 100081；2.中國(guó)鐵道科學(xué)研究院集團(tuán)有限公司科技和信息化部，北京 100081；3.中國(guó)鐵道科學(xué)研究院集團(tuán)有限公司電子計(jì)算技術(shù)研究所，北京 100081）

鐵路機(jī)車(chē)的設(shè)備安全、周轉(zhuǎn)效率和維修質(zhì)量等對(duì)于保障鐵路運(yùn)輸生產(chǎn)效率有著重要的作用。隨著機(jī)車(chē)數(shù)量的增加、機(jī)車(chē)數(shù)據(jù)的不斷積累和數(shù)據(jù)獲取方式的不斷升級(jí)［1］，機(jī)車(chē)積累的運(yùn)行臺(tái)賬、監(jiān)測(cè)檢測(cè)、維修保養(yǎng)、事故故障等各類(lèi)數(shù)據(jù)不斷增多［2］，數(shù)據(jù)類(lèi)型日益豐富，蘊(yùn)含的數(shù)據(jù)價(jià)值不斷顯現(xiàn)。通過(guò)研究機(jī)車(chē)各類(lèi)數(shù)據(jù)間存在的關(guān)聯(lián)關(guān)系，可以挖掘出機(jī)車(chē)事故故障與機(jī)車(chē)運(yùn)用、整備、檢修等日常生產(chǎn)數(shù)據(jù)之間存在的關(guān)聯(lián)規(guī)則，這將對(duì)提高機(jī)車(chē)運(yùn)行質(zhì)量、提升故障診斷效率和安全管理能力、促進(jìn)機(jī)車(chē)檢修作業(yè)精細(xì)化水平起到較好的促進(jìn)作用。然而，由于數(shù)據(jù)挖掘技術(shù)在鐵路機(jī)務(wù)專(zhuān)業(yè)起步較晚，目前仍較難從大量數(shù)據(jù)中發(fā)掘蘊(yùn)含的重要信息，特別是與機(jī)車(chē)事故故障有關(guān)的關(guān)聯(lián)性信息。因此，運(yùn)用數(shù)據(jù)挖掘技術(shù)中的關(guān)聯(lián)規(guī)則分析方法，對(duì)機(jī)車(chē)事故故障及其關(guān)聯(lián)因素的探究，一直是鐵路機(jī)車(chē)質(zhì)量安全管理中的重點(diǎn)和難點(diǎn)。

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中的重要組成，其主要任務(wù)是挖掘出頻繁項(xiàng)集并生成關(guān)聯(lián)規(guī)則［3］。在實(shí)際的鐵路機(jī)車(chē)運(yùn)輸生產(chǎn)中，事故、故障、設(shè)備問(wèn)題等數(shù)據(jù)相較于機(jī)車(chē)的日常運(yùn)用、整備、檢修數(shù)據(jù)有著較低的發(fā)生概率，但是其對(duì)機(jī)車(chē)的質(zhì)量及安全狀態(tài)卻有著重要的影響。在對(duì)機(jī)車(chē)事故故障進(jìn)行關(guān)聯(lián)規(guī)則挖掘時(shí)，若以上所有數(shù)據(jù)均采用統(tǒng)一的支持度，很容易因設(shè)定的支持度過(guò)高而無(wú)法獲得與機(jī)車(chē)事故故障有關(guān)的關(guān)聯(lián)規(guī)則，或因設(shè)定的支持度過(guò)低而產(chǎn)生過(guò)多低價(jià)值的關(guān)聯(lián)規(guī)則。因此，進(jìn)行鐵路機(jī)車(chē)事故故障關(guān)聯(lián)規(guī)則挖掘時(shí)，需要對(duì)具有不同發(fā)生概率及重要性的數(shù)據(jù)設(shè)定不同的支持度，從而獲得更有價(jià)值的關(guān)聯(lián)規(guī)則。

目前最常用的多最小支持度關(guān)聯(lián)規(guī)則挖掘算法主要有2 類(lèi)。一類(lèi)是基于先驗(yàn)算法（Apriori Algo?rithm）形成的多最小支持度先驗(yàn)算法（MsApriori Algorithm）［4］及其相關(guān)改進(jìn)算法，這類(lèi)算法延續(xù)了Apriori 算法的基本思路，在數(shù)據(jù)挖掘過(guò)程中通過(guò)多次掃描數(shù)據(jù)庫(kù)，計(jì)算對(duì)應(yīng)候選項(xiàng)集的支持度，進(jìn)而篩選出頻繁項(xiàng)集［5］。但這個(gè)過(guò)程在增加內(nèi)存負(fù)擔(dān)的同時(shí)還會(huì)產(chǎn)生大量的候選項(xiàng)集［6］，存在數(shù)據(jù)集搜索次數(shù)多、內(nèi)存開(kāi)銷(xiāo)大、時(shí)間損耗嚴(yán)重等問(wèn)題。另一類(lèi)是利用頻繁模式增長(zhǎng)算法（FP-Growth Algorithm）［7］的思想，在樹(shù)結(jié)構(gòu)［8］的基礎(chǔ)上實(shí)現(xiàn)多最小支持度的關(guān)聯(lián)規(guī)則挖掘，如多最小支持度頻繁模式增長(zhǎng)算法（MS-Growth Algorithm）［9］等，這類(lèi)算法雖然在執(zhí)行速率上較MsApriori 算法有一定提升，但是普遍對(duì)內(nèi)存要求較高，且在挖掘的過(guò)程中需多次掃描構(gòu)建的樹(shù)，面對(duì)較大的數(shù)據(jù)集時(shí)會(huì)造成算法效率快速下降［10］。這2 類(lèi)算法均屬于水平挖掘算法［11］。

相對(duì)于水平挖掘算法，還有以垂直方式進(jìn)行挖掘的關(guān)聯(lián)規(guī)則挖掘算法，這種算法的效率較高，但無(wú)法實(shí)現(xiàn)多最小支持度情況下的關(guān)聯(lián)規(guī)則挖掘。例如等價(jià)變換類(lèi)算法（Eclat Algorithm）［12］，只需掃描1 次數(shù)據(jù)庫(kù)，即可快速求得候選項(xiàng)集的支持度，計(jì)算性能優(yōu)于Apriori算法等水平挖掘算法［13］，但尚不能直接應(yīng)用于機(jī)車(chē)事故故障的關(guān)聯(lián)規(guī)則挖掘場(chǎng)景。

本文基于運(yùn)用深度優(yōu)先策略的Eclat算法思路，通過(guò)構(gòu)建最小支持度索引表，以各項(xiàng)目的最小支持度值為排序依據(jù)重新構(gòu)建垂直格式數(shù)據(jù)集，形成基于多最小支持度的Eclat 改進(jìn)算法——MsEclat 算法，使其能夠在多最小支持度情況下挖掘出關(guān)聯(lián)規(guī)則；再對(duì)MsEclat 算法進(jìn)一步改進(jìn)，將算法與位運(yùn)算求交集、等價(jià)類(lèi)并行運(yùn)算這2 種數(shù)據(jù)處理方法加以融合，形成優(yōu)化的MsEclat 算法，使其更好地應(yīng)用于大數(shù)據(jù)分析場(chǎng)景，能夠更加高效地挖掘出與機(jī)車(chē)事故故障等小概率項(xiàng)目有關(guān)的頻繁項(xiàng)集；通過(guò)算法對(duì)比，驗(yàn)證MsEclat 算法及其優(yōu)化算法在多最小支持度關(guān)聯(lián)規(guī)則挖掘方面的計(jì)算效率優(yōu)勢(shì)；以某鐵路局2019—2020 年的機(jī)車(chē)運(yùn)轉(zhuǎn)養(yǎng)護(hù)大數(shù)據(jù)為例，采用優(yōu)化的MsEclat 算法，挖掘機(jī)車(chē)事故故障的關(guān)聯(lián)規(guī)則，再進(jìn)一步以篩選得到的6條代表性關(guān)聯(lián)規(guī)則為例，分析該局機(jī)車(chē)的事故故障發(fā)生情況及質(zhì)量安全狀態(tài)。

1 MsEclat算法的背景知識(shí)

1.1 垂直格式數(shù)據(jù)集

垂直事務(wù)集合Tset。記事務(wù)集合為T(mén)={t1,t2,…,tn｝，項(xiàng)目集合為I={i1,i2,…,im｝，若T 與I 之間存在一定的對(duì)應(yīng)關(guān)系，二者共同構(gòu)成包含事務(wù)與項(xiàng)目的數(shù)據(jù)集，那么該數(shù)據(jù)集有2 種排序表示方式。若按事務(wù)對(duì)數(shù)據(jù)集排序，形成的數(shù)據(jù)集可稱(chēng)之為水平格式數(shù)據(jù)集；若按項(xiàng)目對(duì)數(shù)據(jù)集排序，形成的數(shù)據(jù)集則可稱(chēng)之為垂直格式數(shù)據(jù)集。水平格式數(shù)據(jù)集與垂直格式數(shù)據(jù)集的表示方式示例見(jiàn)表1 和表2。對(duì)于項(xiàng)目集合I 中的任意項(xiàng)目ij∈I，1≤j ≤m，記垂直事務(wù)集合為T(mén)set(ij)，表示垂直格式排序下，事務(wù)集合T中包含項(xiàng)目ij的所有事務(wù)的集合。

表1 水平格式數(shù)據(jù)集示例

表2 垂直格式數(shù)據(jù)集示例

1.2 支持度、置信度與提升度

1）支持度Ssup

引入支持度的概念，用Ssup表示同時(shí)包含1個(gè)或多個(gè)項(xiàng)目（或項(xiàng)目集合）的事務(wù)在事務(wù)集合中的占比。在Eclat算法中，項(xiàng)目集合{Ia∪Ib}(Ia?I，Ib?I)的支持度為Ssup(Ia∪Ib)，表示同時(shí)包含Ia和Ib的事務(wù)在事務(wù)集合F中的占比，其計(jì)算式為

支持度是衡量某一項(xiàng)目集合能否得到保留并生成關(guān)聯(lián)規(guī)則的重要參數(shù)，其衡量的標(biāo)準(zhǔn)被稱(chēng)為最小支持度Smin_sup，一般可人為設(shè)定。所有項(xiàng)目集合在參與衡量前被稱(chēng)為候選項(xiàng)集，而篩選后未被舍棄獲得保留的項(xiàng)目集合可被稱(chēng)為頻繁項(xiàng)集。某1 個(gè)含有k 個(gè)項(xiàng)目的項(xiàng)目集合在進(jìn)行保留或舍棄的選擇前，稱(chēng)為候選k 項(xiàng)集，若其支持度大于或等于Smin_sup，便被稱(chēng)為頻繁k項(xiàng)集［14］，得到保留。

2）支持度計(jì)數(shù)值Csup

項(xiàng)目集合的支持度與其對(duì)應(yīng)的Tset所含事務(wù)個(gè)數(shù)密切相關(guān)，因此引入支持度計(jì)數(shù)值的概念，用來(lái)表征項(xiàng)目集合的發(fā)生概率情況。設(shè)項(xiàng)目集合{Ia∪Ib}(Ia?I，Ib?I)的垂直事務(wù)集合為T(mén)set(Ia∪Ib)，則項(xiàng)目集合{Ia∪Ib}的支持度計(jì)數(shù)值Csup(Ia∪Ib)可表示為T(mén)set(Ia∪Ib)中的事務(wù)個(gè)數(shù)，其計(jì)算式為

與依據(jù)支持度衡量某1 個(gè)項(xiàng)目集合能否得到保留的過(guò)程類(lèi)似，在利用垂直格式數(shù)據(jù)集挖掘頻繁項(xiàng)集的過(guò)程中，可采用支持度計(jì)數(shù)值的大小作為項(xiàng)目集合是否能得到保留的依據(jù)。同樣需要人為設(shè)定1 個(gè)最小支持度計(jì)數(shù)值Cmin_sup，若某1 個(gè)候選k項(xiàng)集的支持度計(jì)數(shù)值大于或等于Cmin_sup，該項(xiàng)目集合才能得到保留并被稱(chēng)為頻繁k項(xiàng)集。

3）置信度Scon

引入置信度的概念，用來(lái)表征項(xiàng)目集合之間的影響程度。對(duì)于1 個(gè)關(guān)聯(lián)規(guī)則Ia?Ib，置信度Scon(Ia?Ib)表示包含Ia的事務(wù)中同時(shí)也包含Ib的事務(wù)的比例，即出現(xiàn)Ia時(shí)也同時(shí)出現(xiàn)Ib的概率，其計(jì)算式為

4）提升度Slif

置信度Scon(Ia?Ib)并不能完全反映Ia與Ib的相關(guān)聯(lián)程度，有時(shí)會(huì)出現(xiàn)Scon(Ia?Ib)小于包含Ib的事務(wù)在事務(wù)集合中占比的特殊情況，這說(shuō)明Ia出現(xiàn)時(shí)Ib也出現(xiàn)的概率要小于Ib單獨(dú)發(fā)生的概率，實(shí)則表明Ia與Ib之間是相互排斥的。因此引入提升度的概念，以便更加全面地分析Ia與Ib的關(guān)系。

對(duì)于1 個(gè)關(guān)聯(lián)規(guī)則Ia?Ib，提升度Slif(Ia，Ib)表示包含Ia的事務(wù)中同時(shí)也包含Ib的事務(wù)的比例與包含Ib的事務(wù)在事務(wù)集合中所占比例的比值，即“關(guān)聯(lián)規(guī)則Ia?Ib的置信度Scon(Ia?Ib)”除以“包含Ib的事務(wù)在事務(wù)集合F中的占比”，其計(jì)算式為

提升度Slif(Ia，Ib)反映了關(guān)聯(lián)規(guī)則Ia?Ib中Ia與Ib的關(guān)聯(lián)程度，其值大于1 表明二者呈正相關(guān)性，小于1 表明二者相互排斥，等于1 表明二者之間沒(méi)有關(guān)聯(lián)性。

1.3 多最小支持度下的頻繁項(xiàng)集判定

項(xiàng)目集合的最小支持度。在多最小支持度的關(guān)聯(lián)規(guī)則挖掘中，以項(xiàng)目集合中各個(gè)項(xiàng)目最小支持度的最小值作為整個(gè)項(xiàng)目集合的最小支持度［15］。例如：若項(xiàng)目集合I中各項(xiàng)目的最小支持度分別為Smin_sup(i1)，Smin_sup(i2)，…，Smin_sup(im)，則I的最小支持度的計(jì)算式為

1.4 面向有序項(xiàng)集的最小支持度索引表

最小支持度索引表。以最小支持度值（或最小支持度計(jì)數(shù)值）有序遞增的方式存儲(chǔ)所有項(xiàng)目的數(shù)據(jù)表。例如：若有1 個(gè)項(xiàng)目集合｛A，B，C，D，E｝，各項(xiàng)目的最小支持度計(jì)數(shù)值分別為3，5，2，4 和6，則各項(xiàng)目將依C，A，D，B 和E 的順序存入最小支持度索引表。

2 MsEclat算法

2.1 Eclat算法簡(jiǎn)述

1）Eclat算法基本思想

Eclat算法是1種深度優(yōu)先算法，利用概念格理論將垂直格式數(shù)據(jù)集劃分為不同的等價(jià)類(lèi)［16］，并通過(guò)Tset間的交集運(yùn)算篩選出頻繁項(xiàng)集。

概念格理論［17］引入等價(jià)類(lèi)的概念，使數(shù)據(jù)集在各個(gè)獨(dú)立的子空間內(nèi)自底向上完成頻繁項(xiàng)集的挖掘。具體來(lái)說(shuō)，設(shè)U 是1個(gè)由多個(gè)互不相同的集合構(gòu)成的空間，如果U 中任意2個(gè)集合的交集或并集也均包含于U，則U 為1個(gè)概念格；若選取U 中的部分集合構(gòu)成空間W，且W 中任意2 個(gè)集合的交集或并集也均包含于W，則W 為U 的1 個(gè)子概念格。進(jìn)一步地，設(shè)1 個(gè)概念格（或子概念格）中有多個(gè)由q個(gè)項(xiàng)目組成的有序集合，若這些集合具有相同的前綴，即前q-1 個(gè)項(xiàng)目相同，而第q 項(xiàng)不同，則這些集合屬于同1 個(gè)等價(jià)類(lèi)。需強(qiáng)調(diào)的是，單獨(dú)1個(gè)集合不能成為1個(gè)等價(jià)類(lèi)。

基于概念格理論，可以通過(guò)對(duì)2 個(gè)項(xiàng)目集合進(jìn)行可連接性判定，從而避免項(xiàng)目集合間不必要的連接操作。設(shè)項(xiàng)目集合Iu和Iv屬于同1 個(gè)等價(jià)類(lèi)，且均為頻繁k項(xiàng)集，則項(xiàng)目集合Iu和Iv是可連接的［18］，可記為Iu?Iv=Iu∪Iv={iu_1，iu_2，…，iu_(k-1)，iu_k，iv_k}。若將每個(gè)項(xiàng)目集合及其中的項(xiàng)目按一定順序排列，如果其中的2 個(gè)頻繁k 項(xiàng)集Iu和Iv不能連接，則Iu和Iv之后的所有項(xiàng)目集合都不滿足連接條件，無(wú)須再次進(jìn)行連接判斷。

2）Eclat算法流程

在挖掘頻繁項(xiàng)集時(shí)，首先掃描1 次原始數(shù)據(jù)集，將水平格式的數(shù)據(jù)變換成垂直格式的數(shù)據(jù)；記k=1，k表示候選項(xiàng)集（或頻繁項(xiàng)集）中項(xiàng)目的個(gè)數(shù)，從第1 個(gè)項(xiàng)目開(kāi)始，從上向下通過(guò)項(xiàng)目集合間的并集操作得到候選項(xiàng)集；通過(guò)對(duì)項(xiàng)目集合所對(duì)應(yīng)的Tset進(jìn)行交集運(yùn)算并計(jì)算其中的元素個(gè)數(shù)，得到候選項(xiàng)集的垂直事務(wù)集合及其支持度計(jì)數(shù)值。然后將候選項(xiàng)集的支持度計(jì)數(shù)值與設(shè)定的最小支持度計(jì)數(shù)值比較，剔除不符合要求的項(xiàng)目集合，從而得到頻繁項(xiàng)集。循環(huán)重復(fù)上述過(guò)程，以頻繁k 項(xiàng)集來(lái)產(chǎn)生候選k+1 項(xiàng)集，直到不再有新的頻繁項(xiàng)集產(chǎn)生為止。

3）Eclat算法的不足

顯然，在Eclat算法下的某些具體分析場(chǎng)景中，不同的項(xiàng)目并不是均勻分布的，且重要性各不相同，需針對(duì)不同的項(xiàng)目設(shè)定不同的最小支持度，但是Eclat 算法無(wú)法在多最小支持度的情況下挖掘出頻繁項(xiàng)集，需要對(duì)其算法進(jìn)行改進(jìn)。

2.2 改進(jìn)的Eclat算法——MsEclat算法

針對(duì)Eclat 算法的上述缺陷，提出1 種基于多最小支持度的Eclat改進(jìn)算法——MsEclat算法。該算法的思路是：利用Eclat 算法的基本思想，運(yùn)用多最小支持度關(guān)聯(lián)規(guī)則挖掘的相關(guān)理論知識(shí)，在最小支持度索引表的基礎(chǔ)上構(gòu)建新型垂直格式數(shù)據(jù)集、有序項(xiàng)集和等價(jià)類(lèi)，在項(xiàng)目集合中各項(xiàng)目具有不同最小支持度值的情況下，有效挖掘出相關(guān)的頻繁項(xiàng)集。

1）MsEclat算法的頻繁項(xiàng)集挖掘步驟

第1 步：掃描1 次數(shù)據(jù)庫(kù)后，將原始數(shù)據(jù)集由水平格式轉(zhuǎn)變?yōu)榇怪备袷?，同時(shí)將各項(xiàng)目（即候選1 項(xiàng)集）按照最小支持度索引表的順序由上到下排列。

第2 步：選定目標(biāo)項(xiàng)目X，將目標(biāo)項(xiàng)目X 及其Tset(X)設(shè)定為垂直格式數(shù)據(jù)集的首位；依序排列最小支持度索引表中排在項(xiàng)目X之后的項(xiàng)目，排項(xiàng)目X 之前的項(xiàng)目則依據(jù)最小支持度定義暫不考慮；將項(xiàng)目X 的最小支持度計(jì)數(shù)值Cmin_sup(X)設(shè)定為以項(xiàng)目X 為首項(xiàng)的各階項(xiàng)目集合的最小支持度計(jì)數(shù)值，若Tset(X)計(jì)數(shù)值小于Cmin_sup(X)，則結(jié)束分析，未挖掘到以項(xiàng)目X為分析目標(biāo)的頻繁項(xiàng)集。

第3 步：以項(xiàng)目X 為首項(xiàng)，與后續(xù)剩余項(xiàng)目依次連接，構(gòu)成候選2 項(xiàng)集，并將所有候選2 項(xiàng)集的Tset的計(jì)數(shù)值與Cmin_sup(X) 做比較，剔除小于Cmin_sup(X)的項(xiàng)目集合，由此得到以項(xiàng)目X 為分析目標(biāo)的頻繁2 項(xiàng)集；同樣地，在頻繁2 項(xiàng)集的基礎(chǔ)上按此方式繼續(xù)形成頻繁3項(xiàng)集。

第4 步：以項(xiàng)目X 為首項(xiàng)，依次在不同的等價(jià)類(lèi)中分別完成項(xiàng)目集合之間的連接和支持度計(jì)數(shù)值的比較，生成高階的頻繁項(xiàng)集。

第5 步：不斷重復(fù)第4 步，直到獲得以項(xiàng)目X為分析目標(biāo)的所有高階頻繁項(xiàng)集。

2）MsEclat算法實(shí)例

以表1 中所列的數(shù)據(jù)集為例，采用MsEclat 算法進(jìn)行頻繁項(xiàng)集挖掘的實(shí)例說(shuō)明如圖1 所示。先對(duì)數(shù)據(jù)集構(gòu)建相應(yīng)的最小支持度索引表，再分別以不同的項(xiàng)目為分析目標(biāo)，按頻繁項(xiàng)集挖掘過(guò)程逐一運(yùn)算，得到所有項(xiàng)目的高階頻繁項(xiàng)集。

圖1 采用MsEclat算法進(jìn)行頻繁項(xiàng)集挖掘的實(shí)例說(shuō)明

3 優(yōu)化的MsEclat算法

由MsEclat 算法的計(jì)算步驟可知，常規(guī)的Tset間交集運(yùn)算會(huì)消耗一定的時(shí)間及內(nèi)存，將其應(yīng)用于鐵路機(jī)車(chē)大數(shù)據(jù)分析時(shí)，因數(shù)據(jù)量巨大，將會(huì)影響算法的執(zhí)行效率。因此將位運(yùn)算求交集、等價(jià)類(lèi)并行運(yùn)算這2 種數(shù)據(jù)處理方法融入MsEclat 算法中，通過(guò)改善Tset間的交集運(yùn)算效率，同時(shí)利用等價(jià)類(lèi)開(kāi)展并行運(yùn)算，使得優(yōu)化的MsEclat 算法在處理較大規(guī)模數(shù)據(jù)集時(shí)的數(shù)據(jù)挖掘效率進(jìn)一步提高。

3.1 基于布爾矩陣的Tset位運(yùn)算求交集

引入布爾矩陣［19］，將Tset間常規(guī)的交集運(yùn)算轉(zhuǎn)變?yōu)?個(gè)1行n列矩陣的與運(yùn)算。其中，n為垂直事務(wù)集合中的最大事務(wù)個(gè)數(shù)，矩陣中有事務(wù)值的對(duì)應(yīng)位置設(shè)定為“1”，其余設(shè)為“0”。與運(yùn)算后得到的新的矩陣，便是2 個(gè)項(xiàng)目集合合并后新產(chǎn)生的Tset所對(duì)應(yīng)的布爾矩陣。這樣，當(dāng)事務(wù)數(shù)據(jù)的規(guī)模很大時(shí)，只需對(duì)2 個(gè)布爾矩陣進(jìn)行與運(yùn)算，統(tǒng)計(jì)新產(chǎn)生的矩陣中“1”的個(gè)數(shù)，即得到新項(xiàng)目集合的支持度計(jì)數(shù)值。這樣便在很大程度上降低了算法的時(shí)間復(fù)雜度，提高了挖掘效率。

3.2 基于MapReduce的等價(jià)類(lèi)并行運(yùn)算

根據(jù)概念格理論，數(shù)據(jù)集（概念格）按照可連接性劃分為多個(gè)等價(jià)類(lèi)，并依次在各個(gè)等價(jià)類(lèi)內(nèi)獨(dú)立地產(chǎn)生各階頻繁項(xiàng)集。當(dāng)數(shù)據(jù)量比較大時(shí)，串行計(jì)算會(huì)消耗大量的時(shí)間，影響數(shù)據(jù)挖掘的效率。因此在處理大規(guī)模數(shù)據(jù)集時(shí)，可以引入并行計(jì)算編程模型MapReduce［20］，通過(guò)并行運(yùn)算獲得3 階及以上的頻繁項(xiàng)集。所有的并行運(yùn)算過(guò)程均抽象成映射階段（Map）和歸約階段（Reduce）這2 個(gè)處理過(guò)程，避免了考慮工作調(diào)度、容錯(cuò)處理、網(wǎng)絡(luò)通信、負(fù)載平衡等細(xì)節(jié)［21］。Map 階段中各個(gè)節(jié)點(diǎn)讀取相應(yīng)的等價(jià)類(lèi)，其中各個(gè)項(xiàng)目集合分別連接得到相應(yīng)的高階候選項(xiàng)集，對(duì)應(yīng)的Tset完成交集運(yùn)算。之后轉(zhuǎn)入Reduce 階段，對(duì)新求得的高階候選項(xiàng)集及其Tset完成頻繁項(xiàng)集的篩選。最后匯總輸出，得到高階頻繁項(xiàng)集。

3.3 大數(shù)據(jù)場(chǎng)景下的頻繁項(xiàng)集挖掘步驟

大規(guī)模數(shù)據(jù)集的事務(wù)或者項(xiàng)目規(guī)模往往極為龐大，其所對(duì)應(yīng)的候選項(xiàng)集和垂直事務(wù)集合的規(guī)模也十分巨大。在這樣的分析場(chǎng)景下，還需進(jìn)一步改進(jìn)MsEclat 算法，通過(guò)優(yōu)化的MsEclat 算法進(jìn)一步提高運(yùn)算效率，其數(shù)據(jù)挖掘過(guò)程可分為5個(gè)步驟。

第1步：初始化。

首先將各項(xiàng)目按照最小支持度計(jì)數(shù)值遞增的順序，構(gòu)建對(duì)應(yīng)的最小支持度索引表。之后掃描數(shù)據(jù)庫(kù)，將水平格式數(shù)據(jù)轉(zhuǎn)化為M行、N+1列的垂直格式數(shù)據(jù)表，其中M 為項(xiàng)目個(gè)數(shù)，N 為最大事務(wù)個(gè)數(shù)。數(shù)據(jù)表最左側(cè)1列依最小支持度計(jì)數(shù)值遞增順序由上向下依次填入各項(xiàng)目名稱(chēng)；各項(xiàng)目則按照各自的Tset在后面N 列形成相應(yīng)的布爾矩陣形式的垂直事務(wù)集合。后續(xù)階段將以新產(chǎn)生的垂直格式數(shù)據(jù)表為基礎(chǔ)挖掘頻繁項(xiàng)集。

第2步：挖掘目標(biāo)項(xiàng)目的頻繁2項(xiàng)集。

選定需研究的目標(biāo)項(xiàng)目Y，以項(xiàng)目Y 為首項(xiàng)，按照最小支持度索引表中的項(xiàng)目順序，以第1步中新產(chǎn)生的垂直格式數(shù)據(jù)表為數(shù)據(jù)基礎(chǔ)，將項(xiàng)目Y與其后面的項(xiàng)目依次連接，得到與項(xiàng)目Y 相關(guān)的候選2 項(xiàng)集。其中，各項(xiàng)目的垂直事務(wù)集合則按照位運(yùn)算的方法完成交集運(yùn)算得到候選2 項(xiàng)集的垂直事務(wù)集合。以項(xiàng)目Y 的最小支持度計(jì)數(shù)值Cmin_sup(Y)為篩選條件，剔除事務(wù)數(shù)小于該值的候選項(xiàng)集，從而得到與項(xiàng)目Y相關(guān)的頻繁2項(xiàng)集。

第3步：獲得頻繁3項(xiàng)集的等價(jià)類(lèi)。

從多年的傳統(tǒng)教學(xué)結(jié)果來(lái)看，大多數(shù)學(xué)生反映通信電子電路課程內(nèi)容難，學(xué)習(xí)效果較差。其中最主要的原因是通信電子電路的先修課程較多，需要用到大量的先修課程理論知識(shí)。例如，器件的非線性特性涉及半導(dǎo)體物理和模擬電子電路課程的內(nèi)容，電路的設(shè)計(jì)和分析涉及電路分析、模擬電子電路、高等數(shù)學(xué)等課程的內(nèi)容，信號(hào)的處理和傳輸又涉及信號(hào)與系統(tǒng)、微波等課程的內(nèi)容。對(duì)于先修課程基礎(chǔ)薄弱的學(xué)生，教師在有限的課堂時(shí)間里很難做到把整個(gè)知識(shí)體系梳理一遍，沒(méi)有足夠的時(shí)間回顧致使學(xué)生跟不上進(jìn)度。

以第2 步中得到的頻繁2 項(xiàng)集為基礎(chǔ)，所有頻繁2 項(xiàng)集依次與其后面的項(xiàng)目集合連接，得到與目標(biāo)項(xiàng)目Y 相關(guān)的候選3項(xiàng)集以及對(duì)應(yīng)的垂直事務(wù)集合。依然以Cmin_sup(Y)為篩選條件，得到與項(xiàng)目Y相關(guān)的頻繁3 項(xiàng)集。之后，按照概念格理論，將頻繁3項(xiàng)集劃分為不同的等價(jià)類(lèi)，作為下一階段的輸入。

第4步：得到頻繁k項(xiàng)集。

調(diào)用并行計(jì)算編程模型MapReduce，將上一階段得到的等價(jià)類(lèi)分配到不同的節(jié)點(diǎn)，進(jìn)行頻繁k項(xiàng)集的挖掘。然后重新劃分等價(jià)類(lèi)并循環(huán)該步驟，直到獲得與項(xiàng)目Y相關(guān)的最高階頻繁項(xiàng)集為止。

第5步：輸出結(jié)果。

匯總各階段得到的與項(xiàng)目Y 相關(guān)的各階頻繁項(xiàng)集及其垂直事務(wù)集合，以供后續(xù)分析、計(jì)算之用。

如需得到所有項(xiàng)目相關(guān)的各階頻繁項(xiàng)集，只需依照最小支持度索引表依次選定各個(gè)項(xiàng)目為目標(biāo)項(xiàng)目，不斷循環(huán)第2～5步，并對(duì)結(jié)果加以匯總即可。

4 算法對(duì)比

分別開(kāi)展MsEclat 算法與MsApriori 算法、MS-Growth 算法這2 種水平挖掘算法的對(duì)比，以及MsEclat 算法與其優(yōu)化算法的對(duì)比，從計(jì)算時(shí)間的角度考察算法效率。處理規(guī)模極大的數(shù)據(jù)集時(shí)，MsApriori算法與MS-Growth 算法將無(wú)法進(jìn)行有效運(yùn)算，而在小規(guī)模數(shù)據(jù)集的情況下，又很難表現(xiàn)出MsEclat 算法與其優(yōu)化算法的差異，故2 次對(duì)比實(shí)驗(yàn)選用不同規(guī)模的數(shù)據(jù)集。

4.1 MsEclat算法與水平挖掘算法對(duì)比

實(shí)驗(yàn)環(huán)境：處理器為Intel i5-8250u 1.8 GHz，內(nèi)存8 GB，操作系統(tǒng)為Windows 10，軟件環(huán)境為python 3.7.3，開(kāi)發(fā)環(huán)境為PyCharm。

選取數(shù)據(jù)規(guī)模和數(shù)據(jù)稠密程度各不相同的3個(gè)數(shù)據(jù)集Mushroom，Pumsb_star 和Car Evaluation（分別取自關(guān)聯(lián)規(guī)則挖掘數(shù)據(jù)庫(kù)http://fimi.uantwer?pen.be/data/以及https://archive.ics.uci.edu/），根據(jù)各個(gè)數(shù)據(jù)集不同的稠密程度，將數(shù)據(jù)集中的項(xiàng)目按照30%，40%和30%的比例賦予不同的最小支持度，對(duì)比MsEclat 算法與MsApriori 算法、MSGrowth 算法挖掘頻繁項(xiàng)集所用的時(shí)間，計(jì)算結(jié)果見(jiàn)表3。

表3 3個(gè)數(shù)據(jù)集下不同算法的計(jì)算結(jié)果

從計(jì)算結(jié)果可以看出，MsEclat 算法的時(shí)間開(kāi)銷(xiāo)明顯優(yōu)于同屬于水平挖掘算法的MsApriori 算法和MS-Growth 算法。分析其原因，一是MsEclat算法繼承了Eclat 算法的垂直數(shù)據(jù)格式，只需遍歷1 次數(shù)據(jù)庫(kù)即可進(jìn)行頻繁項(xiàng)集的挖掘工作；二是MsEclat 算法在頻繁項(xiàng)集的挖掘過(guò)程中，僅涉及垂直事務(wù)集合的交集運(yùn)算以及最小支持度的大小比較等簡(jiǎn)單操作，時(shí)間和內(nèi)存消耗不高；三是MsEclat算法依然延續(xù)了概念格與等價(jià)類(lèi)的思想，避免了項(xiàng)目集合之間不必要的連接操作，進(jìn)一步提高了挖掘效率。

4.2 MsEclat算法與其優(yōu)化算法對(duì)比

實(shí)驗(yàn)環(huán)境：最大節(jié)點(diǎn)數(shù)為10 的分布式計(jì)算集群（Hadoop），每個(gè)節(jié)點(diǎn)的處理器為Intel i5-5200u 2.2 GHz，內(nèi)存8 GB，操作系統(tǒng)為Ubuntu Linux。

由數(shù)據(jù)生成器分別產(chǎn)生規(guī)模約為0.5，1.1，1.7 和2.3 GB 的數(shù)據(jù)集，每個(gè)數(shù)據(jù)集的項(xiàng)目數(shù)為1 000 個(gè)，事務(wù)數(shù)分別為3×106，6×106，9×106和12×106條。每個(gè)數(shù)據(jù)集中的項(xiàng)目按照30%，40%和30%的比例進(jìn)行劃分，并分別賦予0.4，0.6 和0.8的最小支持度。節(jié)點(diǎn)數(shù)為6時(shí)，MsEclat算法與其優(yōu)化算法對(duì)不同規(guī)模數(shù)據(jù)集的處理時(shí)間如圖2 所示。由圖2可以看出：MsEclat算法經(jīng)過(guò)2種數(shù)據(jù)處理方法的優(yōu)化后，計(jì)算效率明顯提高；隨著數(shù)據(jù)規(guī)模的增大，優(yōu)化算法在計(jì)算時(shí)間上的優(yōu)勢(shì)愈發(fā)明顯。其余節(jié)點(diǎn)數(shù)時(shí)的實(shí)驗(yàn)情況與此類(lèi)同，不再展開(kāi)。

圖2 MsEclat 算法與其優(yōu)化算法對(duì)不同規(guī)模數(shù)據(jù)集的處理時(shí)間

節(jié)點(diǎn)數(shù)不同的情況下，優(yōu)化的MsEclat 算法對(duì)不同規(guī)模數(shù)據(jù)集的處理時(shí)間如圖3 所示。由圖3 可以看出：隨著計(jì)算節(jié)點(diǎn)的增加，優(yōu)化的MsEclat 算法對(duì)不同規(guī)模的數(shù)據(jù)集的處理時(shí)間逐漸減少；當(dāng)計(jì)算節(jié)點(diǎn)增加到一定的數(shù)量后，受分布式計(jì)算集群間通信時(shí)間的影響，算法計(jì)算時(shí)間的減少程度逐漸減弱。

圖3 優(yōu)化的MsEclat 算法在不同節(jié)點(diǎn)數(shù)時(shí)對(duì)不同規(guī)模數(shù)據(jù)集的處理時(shí)間

5 算例分析

現(xiàn)以某鐵路局2019—2020 年的機(jī)車(chē)數(shù)據(jù)為例，采用優(yōu)化的MsEclat 算法，進(jìn)行機(jī)車(chē)事故故障的關(guān)聯(lián)規(guī)則挖掘。

5.1 待分析項(xiàng)目選取

從不同維度，選取可用于開(kāi)展機(jī)車(chē)事故故障關(guān)聯(lián)分析的項(xiàng)目共計(jì)64 項(xiàng)，例如機(jī)車(chē)運(yùn)用質(zhì)量、整備質(zhì)量、檢修質(zhì)量、專(zhuān)項(xiàng)整治、綜合評(píng)價(jià)和基本信息等，詳見(jiàn)表4。根據(jù)該局2019—2020 年機(jī)車(chē)數(shù)據(jù)，得到的事務(wù)集合中共有事務(wù)31 332 條，每1 條事務(wù)中的項(xiàng)目均由上述這64個(gè)項(xiàng)目組成。

表4 機(jī)車(chē)事故故障關(guān)聯(lián)分析的項(xiàng)目

根據(jù)數(shù)據(jù)占比、重要程度、專(zhuān)家意見(jiàn)等因素，對(duì)機(jī)破、運(yùn)用故障、碎修、五項(xiàng)專(zhuān)檢問(wèn)題、性能試驗(yàn)問(wèn)題、機(jī)車(chē)春季鑒定整修、總體質(zhì)量評(píng)價(jià)這些細(xì)分維度下的項(xiàng)目賦予不同的最小支持度計(jì)數(shù)值，并形成最小支持度索引表，見(jiàn)表5。表中項(xiàng)目的最小支持度計(jì)數(shù)值越小，表示該項(xiàng)目在數(shù)據(jù)集中出現(xiàn)頻次較低，但重要程度較高。表中未列出的其他項(xiàng)目的最小支持度統(tǒng)一定為0.2，即最小支持度計(jì)數(shù)值為6 266。

表5 重點(diǎn)關(guān)注項(xiàng)目的最小支持度索引表

5.2 關(guān)聯(lián)規(guī)則挖掘

采用優(yōu)化的MsEclat 算法進(jìn)行挖掘，在6 個(gè)分布式節(jié)點(diǎn)的情況下耗時(shí)僅3.945 034 s，挖掘得到頻繁項(xiàng)集156 條，其中頻繁1 項(xiàng)集24 條、頻繁2 項(xiàng)集60 條、頻繁3 項(xiàng)集54 條、頻繁4 項(xiàng)集17 條、頻繁5 項(xiàng)集1 條。結(jié)合業(yè)務(wù)部門(mén)意見(jiàn)，從中篩選出6 條具有代表性的頻繁項(xiàng)集形成相應(yīng)的關(guān)聯(lián)規(guī)則見(jiàn)表6，表中部分?jǐn)?shù)據(jù)已做脫敏處理。

對(duì)表6 所列的關(guān)聯(lián)規(guī)則逐一分析，可得到該局機(jī)車(chē)的事故故障發(fā)生情況及質(zhì)量安全狀態(tài)如下。

表6 挖掘形成的6條代表性關(guān)聯(lián)規(guī)則

（1）所有事務(wù)中，項(xiàng)目“機(jī)破發(fā)生1 次”與“H1 機(jī)務(wù)段”共同發(fā)生286 次，占所有事務(wù)的比例為0.91%，“機(jī)破發(fā)生1 次”對(duì)于“H1 機(jī)務(wù)段”的置信度高達(dá)90.22%，提升度為3.12，表示每月發(fā)生1 次機(jī)破的機(jī)車(chē)有90.22%的比例集中在H1 機(jī)務(wù)段，這條關(guān)聯(lián)規(guī)則說(shuō)明H1 機(jī)務(wù)段的機(jī)車(chē)每月較容易發(fā)生1 次機(jī)破問(wèn)題，因此該段在機(jī)車(chē)質(zhì)量安全管理中，應(yīng)對(duì)機(jī)車(chē)機(jī)破問(wèn)題的防范加以關(guān)注。

（2）項(xiàng)目“運(yùn)用故障高發(fā)”與“行車(chē)安全裝備問(wèn)題較多”共同發(fā)生31 次，其置信度為83.78%，提升度達(dá)到了21.27，表明機(jī)車(chē)運(yùn)用故障的高發(fā)往往伴隨著較多的行車(chē)安全裝備問(wèn)題，二者間的關(guān)聯(lián)性很強(qiáng)。機(jī)車(chē)的行車(chē)安全裝備包含機(jī)車(chē)信號(hào)、列車(chē)運(yùn)行監(jiān)控記錄裝置、機(jī)車(chē)綜合無(wú)線通信設(shè)備、機(jī)車(chē)車(chē)載安全防護(hù)系統(tǒng)等多種設(shè)備，雖然這條關(guān)聯(lián)規(guī)則的支持度僅有0.10%，在所有事務(wù)中同時(shí)出現(xiàn)的占比不高，但考慮到運(yùn)用故障和行車(chē)安全裝備問(wèn)題對(duì)于機(jī)車(chē)的運(yùn)行安全有著較為嚴(yán)重的影響，因此機(jī)車(chē)日常養(yǎng)護(hù)維修作業(yè)中，應(yīng)加強(qiáng)對(duì)于行車(chē)安全裝備的質(zhì)量把控，減少運(yùn)用故障的高發(fā)對(duì)機(jī)車(chē)行車(chē)安全的影響。

（3）項(xiàng)目“D 級(jí)機(jī)車(chē)”與“碎修超多”共同發(fā)生247次，“D級(jí)機(jī)車(chē)”對(duì)于“碎修超多”的置信度為65.52%，二者的提升度高達(dá)22.83，表明該局總體質(zhì)量最差的D級(jí)機(jī)車(chē)與機(jī)車(chē)碎修問(wèn)題有很強(qiáng)的關(guān)聯(lián)性，該局65.52%的D 級(jí)機(jī)車(chē)經(jīng)常表現(xiàn)出超多的碎修問(wèn)題，因此在對(duì)全局質(zhì)量狀態(tài)最差的D級(jí)機(jī)車(chē)開(kāi)展專(zhuān)項(xiàng)整治工作時(shí)，可從運(yùn)用質(zhì)量維度下的碎修問(wèn)題著手，有針對(duì)性地安排相應(yīng)的檢修修程，減少機(jī)車(chē)故障數(shù)量，提升全局機(jī)車(chē)質(zhì)量。

（4）項(xiàng)目“性能試驗(yàn)問(wèn)題較多”“H3 機(jī)務(wù)段”和“C 級(jí)機(jī)車(chē)”共同發(fā)生85 次，“性能試驗(yàn)問(wèn)題較多”對(duì)于“H3 機(jī)務(wù)段”和“C 級(jí)機(jī)車(chē)”的置信度為54.49%，提升度為18.68。表明全局發(fā)生較多性能試驗(yàn)問(wèn)題的機(jī)車(chē)，有54.49%的比例集中于H3 機(jī)務(wù)段的C 級(jí)機(jī)車(chē)，且表現(xiàn)出很強(qiáng)的關(guān)聯(lián)性。因此，該段在對(duì)總體質(zhì)量較差的C級(jí)機(jī)車(chē)進(jìn)行檢修維護(hù)作業(yè)時(shí)，可從機(jī)車(chē)檢修工作中的性能試驗(yàn)入手，加強(qiáng)性能試驗(yàn)所涉及的制動(dòng)機(jī)、高低壓、負(fù)載等機(jī)車(chē)設(shè)備的檢查維修力度，防范機(jī)車(chē)設(shè)備故障的發(fā)生，促進(jìn)C級(jí)機(jī)車(chē)的質(zhì)量提升。

（5）項(xiàng)目“零公里質(zhì)量鑒定問(wèn)題過(guò)多”“H2機(jī)務(wù)段”和“B 級(jí)機(jī)車(chē)”共同發(fā)生93 次，“零公里質(zhì)量鑒定問(wèn)題過(guò)多”對(duì)于“H2 機(jī)務(wù)段”和“B 級(jí)機(jī)車(chē)”的置信度達(dá)到60.78%，提升度為8.51，表明H2 機(jī)務(wù)段的B 級(jí)機(jī)車(chē)更容易發(fā)生零公里質(zhì)量鑒定問(wèn)題，因此該段在機(jī)車(chē)檢修作業(yè)中，可針對(duì)零公里質(zhì)量鑒定中發(fā)現(xiàn)的機(jī)車(chē)質(zhì)量問(wèn)題，有的放矢地加強(qiáng)相應(yīng)機(jī)車(chē)設(shè)備的維護(hù)保養(yǎng)，減輕該問(wèn)題對(duì)B級(jí)機(jī)車(chē)的影響。

（6）項(xiàng)目“五項(xiàng)專(zhuān)檢問(wèn)題過(guò)多”“H3 機(jī)務(wù)段”“B 級(jí)級(jí)車(chē)”和“碎修較多”共同發(fā)生103 次，“五項(xiàng)專(zhuān)檢問(wèn)題過(guò)多”對(duì)于“H3 機(jī)務(wù)段”“B 級(jí)級(jí)車(chē)”和“碎修較多”的置信度為60.23%，提升度為14.12，表明H3 機(jī)務(wù)段的B 級(jí)機(jī)車(chē)中，“五項(xiàng)專(zhuān)檢問(wèn)題過(guò)多”與“碎修較多”這2 項(xiàng)機(jī)車(chē)質(zhì)量問(wèn)題之間存在較強(qiáng)的關(guān)聯(lián)性。機(jī)車(chē)五項(xiàng)專(zhuān)檢涵蓋了走行部、車(chē)頂高壓設(shè)備、DC 600V 直流供電、制動(dòng)機(jī)、防火等多種設(shè)備，因此該段應(yīng)針對(duì)性地開(kāi)展跨運(yùn)輸生產(chǎn)環(huán)節(jié)的專(zhuān)項(xiàng)整治工作，減少五項(xiàng)專(zhuān)檢問(wèn)題和碎修問(wèn)題的發(fā)生。

6 結(jié) 語(yǔ)

本文立足鐵路機(jī)務(wù)專(zhuān)業(yè)的機(jī)車(chē)事故故障關(guān)聯(lián)分析需要，采用Eclat 算法的垂直數(shù)據(jù)挖掘思想，通過(guò)改善其無(wú)法滿足多最小支持度關(guān)聯(lián)規(guī)則挖掘的缺陷，提出了MsEclat 這一改進(jìn)算法，詳細(xì)闡釋了MsEclat 算法的數(shù)據(jù)挖掘思路，并給出示例。進(jìn)一步地，為更好實(shí)現(xiàn)大數(shù)據(jù)場(chǎng)景下的關(guān)聯(lián)規(guī)則挖掘，利用布爾矩陣和并行計(jì)算編程模型MapReduce 對(duì)MsEclat 算法加以?xún)?yōu)化，形成優(yōu)化的MsEclat 算法，設(shè)計(jì)了相應(yīng)的頻繁項(xiàng)集挖掘步驟。選取數(shù)據(jù)規(guī)模和數(shù)據(jù)稠密程度各不相同的3 個(gè)數(shù)據(jù)集，將MsEclat算法與MsApriori 算法、MS-Growth 算法這2 種水平挖掘算法以及優(yōu)化的MsEclat 算法分別進(jìn)行比較，證明MsEclat 算法及其優(yōu)化算法在多最小支持度關(guān)聯(lián)規(guī)則挖掘的執(zhí)行效率上均有著極好的表現(xiàn)，特別是優(yōu)化的MsEclat 算法，處理大規(guī)模數(shù)據(jù)時(shí)的執(zhí)行效率得到進(jìn)一步提高。將優(yōu)化的MsEclat 算法應(yīng)用到某鐵路局的機(jī)車(chē)事故故障關(guān)聯(lián)分析這一具體的大數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘場(chǎng)景，得到了與機(jī)車(chē)事故故障這類(lèi)重點(diǎn)數(shù)據(jù)相關(guān)的多條關(guān)聯(lián)規(guī)則，如運(yùn)用故障的高發(fā)有83.78%的可能性會(huì)伴隨著較多的行車(chē)安全裝備問(wèn)題等等，并分別做出了相應(yīng)分析，證實(shí)該算法對(duì)科學(xué)、高效、精準(zhǔn)地開(kāi)展鐵路設(shè)備質(zhì)量安全狀態(tài)分析具有良好的技術(shù)支撐作用。