關(guān)聯(lián)規(guī)則改進(jìn)算法及其在地鐵運(yùn)營中的應(yīng)用

周永強(qiáng) 楊振華

摘? 要： 為了探索天氣與地鐵客流量之間的關(guān)系，為地鐵運(yùn)營部門科學(xué)合理的調(diào)度、預(yù)案的制定提供幫助，對(duì)地鐵大數(shù)據(jù)進(jìn)行了關(guān)聯(lián)規(guī)則挖掘，并對(duì)經(jīng)典的關(guān)聯(lián)規(guī)則算法Apriori進(jìn)行了改進(jìn)。改進(jìn)算法提高了從海量數(shù)據(jù)中取得頻繁項(xiàng)目集的效率，降低了對(duì)計(jì)算機(jī)資源的消耗，高效地挖掘出了天氣因素對(duì)地鐵客流影響的規(guī)律。

關(guān)鍵詞： 關(guān)聯(lián)規(guī)則; Apriori; 算法; 頻繁項(xiàng)目集

中圖分類號(hào)：TP393? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：1006-8228（2021）04-57-03

Abstract： In order to explore the relationship between weather and subway passenger flow， provide help for scientific and reasonable scheduling and plan formulation. The association rule mining to the subway big data is carried out and the classical association rule algorithm Apriori is improved. The improved algorithm improves the efficiency of obtaining frequent item sets from massive data and reduces the consumption of computer resources， so that the rules of the influence of weather factors on subway passenger flow are mined efficiently.

Key words： association rule; Apriori; algorithm; frequent item sets

0 引言

隨著城市化進(jìn)程的發(fā)展，城市人口高速增長，大量的城市人口給交通帶來了極大的壓力。為了緩解交通壓力[4]，許多城市都大力發(fā)展地鐵建設(shè)。然而乘客人數(shù)過多，在高峰期地鐵站仍然是人潮涌動(dòng)。當(dāng)天氣變化時(shí)也會(huì)對(duì)地鐵交通產(chǎn)生極大影響。因此，天氣因素對(duì)地鐵客流的影響就成了我們的研究對(duì)象。隨著地鐵電子化車票的使用，地鐵運(yùn)營公司已經(jīng)收集了海量的用戶乘車數(shù)據(jù)。我們嘗試采用關(guān)聯(lián)規(guī)則方法對(duì)出行數(shù)據(jù)中蘊(yùn)含的潛在知識(shí)進(jìn)行挖掘，找出其中有價(jià)值的信息。

1 Apriori算法研究

關(guān)聯(lián)規(guī)則挖掘的過程分為兩個(gè)步驟：第一步，從事務(wù)數(shù)據(jù)庫中找出所有滿足支持度的頻繁項(xiàng)集;第二步，從頻繁項(xiàng)集中找出所有滿足置信度的規(guī)則。找出頻繁項(xiàng)集是進(jìn)行關(guān)聯(lián)規(guī)則挖掘的基礎(chǔ)，也是最耗時(shí)耗力的一步，也因此成為大多數(shù)關(guān)聯(lián)規(guī)則研究的熱點(diǎn)[5]。

頻繁項(xiàng)集挖掘經(jīng)典的算法是Apriori算法，它挖掘的主要步驟是：①首先，掃描事務(wù)數(shù)據(jù)庫D，找出其中的頻繁1項(xiàng)集L1。②由頻繁1項(xiàng)集L1進(jìn)行L1 X L1連接運(yùn)算產(chǎn)生候選頻繁2項(xiàng)集C2。再次掃描事務(wù)數(shù)據(jù)庫D，找出其中的頻繁2項(xiàng)集L2。重復(fù)上述過程，直至找出所有的頻繁k項(xiàng)集Lk。

Apriori的算法如下：

L1=frequent_1_itemsets（D）; //找到所有頻繁1項(xiàng)集L1，

D是事務(wù)數(shù)據(jù)庫的所有項(xiàng)

for（k=2;Lk-1≠?;k++） {

Ck=generate（Lk-1）;

for each transaction t∈D {

for each item ji∈Ck {

if （ji∈t） then ji.count=ji.count+1

}

}

Lk={ j∈Ck|ji.count>min_support }

}

L=LULk //找到所有的頻繁項(xiàng)集

2 Apriori算法的改進(jìn)

Apriori算法剪枝操作的過程是：用頻繁Lk-1項(xiàng)集連接產(chǎn)生候選頻繁k項(xiàng)集Ck，再統(tǒng)計(jì)每個(gè)候選頻繁項(xiàng)的k個(gè)子集是不是都在頻繁項(xiàng)集Lk-1中，如果有的子集不在Lk-1中，則該候選頻繁項(xiàng)一定不是頻繁的，應(yīng)當(dāng)排除。但是這種方法會(huì)產(chǎn)生大量候選頻繁項(xiàng)集。如果頻繁2項(xiàng)集L2有200000條，那么連接運(yùn)算將產(chǎn)生 19999900000條候選頻繁3項(xiàng)集，再依次檢查每個(gè)候選頻繁項(xiàng)的子集將花費(fèi)大量的計(jì)算資源[6]。

我們發(fā)現(xiàn)在頻繁k-1項(xiàng)集產(chǎn)生之后，頻繁k-1項(xiàng)集中的某些元素Ii（li在頻繁k-1項(xiàng)集出現(xiàn)次數(shù)小于k-1），那么它對(duì)于下一級(jí)的頻繁k項(xiàng)集的產(chǎn)生就已經(jīng)不起作用了。因?yàn)?，如果候選頻繁k項(xiàng)集Ck是頻繁的，則它的k-1項(xiàng)的子集也一定是頻繁的。所以它的每個(gè)子項(xiàng)一定會(huì)在頻繁k-1項(xiàng)集中出現(xiàn)至少k-1次。因此，可以在產(chǎn)生下一級(jí)候選頻繁項(xiàng)目集Ck之前，先從頻繁項(xiàng)目集Lk-1中刪除包含這些元素（Ii）的頻繁項(xiàng)目，這就會(huì)減少大量無用的候選頻繁項(xiàng)目集的產(chǎn)生[7]。

我們?cè)贏priori算法的剪枝過程中增加如下操作：

function reduce （Lk-1）

for i in 1…k-1 //設(shè)置計(jì)數(shù)標(biāo)記 A1，A2……Ak-1初始值為0

{ Ai.count=0 }

for each item c∈Lk-1 //統(tǒng)計(jì)頻繁k-1項(xiàng)集中，各個(gè)項(xiàng)目I[i]

出現(xiàn)的次數(shù)

{ for each item I[i]∈c }

{ Ai.count=Ai.count+1}

for i in 1…k-1 //從頻繁k-1項(xiàng)集中，去除適合產(chǎn)生候選頻繁k項(xiàng)集的項(xiàng)目

if Ai.count

{

for each item c∈Lk-1

if Ai∈c

delete c from Lk-1

}

例如，有頻繁2項(xiàng)集：

{I1，I2}，{I1，I5}，{I1，I6}，{I2，I4}，{I2，I5}，{I2，I7}，{I3，I5}，{I4，I7}，{I5，I7}

需要進(jìn)行連接運(yùn)算36次，將會(huì)產(chǎn)生候選頻繁3項(xiàng)集13個(gè)：{I1，I2，I4}，{I1，I2，I5}，{I1，I2，I6}，{I1，I2，I7}，{I1，I3，I5}，{I1，I5，I6}，{I1，I5，I7}，{I2，I3，I5}，{I2，I4，I5}，{I2，I4，I7}，{I2，I5，I7}，{I3，I5，I7}，{I4，I5，I7}，而我們的方法先統(tǒng)計(jì)各個(gè)頻繁2項(xiàng)集中每個(gè)元素出現(xiàn)的次數(shù)。I1：出現(xiàn)3次，I2：出現(xiàn)4次，I3：出現(xiàn)1次，I4：出現(xiàn)2次，I5：出現(xiàn)4次，I6：出現(xiàn)1次，I7：出現(xiàn)3次。因此，可以從頻繁2項(xiàng)集中，把包含I3和I6的項(xiàng)去掉。只需要進(jìn)行21次連接運(yùn)算，產(chǎn)生候選頻繁3項(xiàng)集8個(gè)：

{I1，I2，I4}，{I1，I2，I5}，{I1，I2，I7}，{I1，I5，I7}，{I2，I4，I5}，{I2，I4，I7}，{I2，I5，I7}，{I4，I5，I7}，產(chǎn)生的候選頻繁項(xiàng)目集就大為減少，這就極大地提高了查找頻繁項(xiàng)目集的效率。

3 實(shí)驗(yàn)對(duì)比分析

為了驗(yàn)證我們的改進(jìn)效果，我們將改進(jìn)的算法與傳統(tǒng)算法進(jìn)行了時(shí)間對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)我們選取了印度地鐵從2012.10.2到2017.5.17的33750條數(shù)據(jù)，記錄了每個(gè)小時(shí)的乘車人數(shù)以及當(dāng)時(shí)的天氣狀況，包括出行日期、是否節(jié)假日、空氣指數(shù)、濕度、風(fēng)速、風(fēng)向、可見度、降雨指數(shù)、降雪指數(shù)、溫度、天氣類型，以及乘客人數(shù)，如圖1所示。

先后使用傳統(tǒng)的Apriori算法與改進(jìn)算法，計(jì)算在不同支持度下，挖掘頻繁項(xiàng)集需要的時(shí)間。最終實(shí)驗(yàn)挖掘結(jié)果如圖2所示。

從實(shí)驗(yàn)的對(duì)比結(jié)果可以看出改進(jìn)的Apriori算法挖掘出頻繁項(xiàng)目集的速度比傳統(tǒng)的Apriori算法快了很多，速度最高提高了26%，特別是在支持度較低的情況下，優(yōu)勢(shì)十分的明顯。

4 結(jié)束語

本文對(duì)傳統(tǒng)的關(guān)聯(lián)規(guī)則算法Apriori進(jìn)行了改進(jìn)，更加精確有效的產(chǎn)生了候選頻繁項(xiàng)目集，提高了關(guān)聯(lián)規(guī)則挖掘的效率。最后使用改進(jìn)的算法對(duì)地鐵出行數(shù)據(jù)進(jìn)行了挖掘，分析發(fā)現(xiàn)，從時(shí)間來看雨雪類天氣對(duì)地鐵客流的影響在周末和上下班的高峰期影響較大[8]，從空間來看從城市的中心到郊區(qū)，天氣因素對(duì)地鐵客流的影響在逐步減弱，地鐵出行無規(guī)律的人群等容易受到極端天氣因素的影響。因此，我們可以通過對(duì)天氣數(shù)據(jù)分析來預(yù)判地鐵客流的變化情況，提前做好科學(xué)的預(yù)案，保障地鐵交通暢通、高效運(yùn)行。特別是在商業(yè)集中的景點(diǎn)，上下班的高峰時(shí)段，密切留意天氣的變化情況，如果發(fā)現(xiàn)客流量異常等突發(fā)情況[9]，及時(shí)采取應(yīng)急處置預(yù)案。保證地鐵的高效運(yùn)營。

參考文獻(xiàn)（References）：

[1] 賈熹濱，葉穎婕，陳軍成.基于關(guān)聯(lián)規(guī)則的交通事故影響因素的挖掘[J].計(jì)算機(jī)科學(xué)，2018.S1.

[2] 喬春凱，趙佳文.基于時(shí)序關(guān)聯(lián)規(guī)則挖掘的交通擁堵預(yù)測(cè)研究[J].科技創(chuàng)新與應(yīng)用，2017.1.

[3] 王平水.關(guān)聯(lián)規(guī)則挖掘算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2010.46（30）：115-116

[4] 鄭淑鑒，楊敬鋒.國內(nèi)外交通擁堵評(píng)價(jià)指標(biāo)計(jì)算方法研究[J].公路與汽運(yùn)，2014.1.

[5] 劉麗娟.改進(jìn)的Apriori算法的研究及應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì)，2017.12.

[6] 關(guān)聯(lián)規(guī)則算法優(yōu)化研究與實(shí)現(xiàn)[J].世界科技研究與發(fā)展，2010.3.

[7] 張健，劉韶濤.事務(wù)約簡(jiǎn)和2項(xiàng)集支持度矩陣快速剪枝的Apriori改進(jìn)算法[J].華僑大學(xué)學(xué)報(bào)（自然科學(xué)版），2017.5.

[8] 梁晨，熊萍.基于地鐵運(yùn)營大數(shù)據(jù)的乘客出行效用分析[J].交通與運(yùn)輸，2020.S2：149-154

[9] 陳東洋，陳德旺，陳開河，肖李德，江世雄.基于客流大數(shù)據(jù)分析和支持向量回歸的地鐵乘客出行時(shí)間預(yù)測(cè)研究[J].現(xiàn)代城市軌道交通，2020.9：70-76