周永強 楊振華

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

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

中圖分類號：TP393? ? ? ? ? 文獻標識碼：A? ? ?文章編號：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 引言

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

1 Apriori算法研究

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

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

Apriori的算法如下：

L1=frequent_1_itemsets（D）; //找到所有頻繁1項集L1，

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

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 //找到所有的頻繁項集

2 Apriori算法的改進

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

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

我們在Apriori算法的剪枝過程中增加如下操作：

function reduce （Lk-1）

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

{ Ai.count=0 }

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

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

{ for each item I[i]∈c }

{ Ai.count=Ai.count+1}

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

if Ai.count

{

for each item c∈Lk-1

if Ai∈c

delete c from Lk-1

}

例如，有頻繁2項集：

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

需要進行連接運算36次，將會產(chǎn)生候選頻繁3項集13個：{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)計各個頻繁2項集中每個元素出現(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項集中，把包含I3和I6的項去掉。只需要進行21次連接運算，產(chǎn)生候選頻繁3項集8個：

{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)生的候選頻繁項目集就大為減少，這就極大地提高了查找頻繁項目集的效率。

3 實驗對比分析

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

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

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

4 結(jié)束語

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

參考文獻（References）：

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

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

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

[4] 鄭淑鑒，楊敬鋒.國內(nèi)外交通擁堵評價指標計算方法研究[J].公路與汽運，2014.1.

[5] 劉麗娟.改進的Apriori算法的研究及應用[J].計算機工程與設計，2017.12.

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

[7] 張健，劉韶濤.事務約簡和2項集支持度矩陣快速剪枝的Apriori改進算法[J].華僑大學學報（自然科學版），2017.5.

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

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