孫 紅 李存進(jìn)
(1.上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院,上海,200093;2.上?,F(xiàn)代光學(xué)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,上海,200093)
數(shù)據(jù)挖掘技術(shù)通過對(duì)數(shù)據(jù)對(duì)象進(jìn)行定性處理,從而分析并得出一些潛在的有用的信息。利用數(shù)據(jù)挖掘分析方法對(duì)交通數(shù)據(jù)進(jìn)行實(shí)時(shí)可靠的分析能夠有效緩解交通壓力改善交通服務(wù)[1]。遺傳算法(Genetic algorithm,GA)作為一種基于自然選擇和基于遺傳學(xué)原理的隨機(jī)并行搜索算法,在很多領(lǐng)域中都有成功的應(yīng)用[2],然而傳統(tǒng)GA[3]存在早熟與搜索效率低的缺陷。自適應(yīng)GA可以通過對(duì)其中2個(gè)重要參數(shù),即交叉算子與變異算子,進(jìn)行適當(dāng)?shù)淖赃m應(yīng)調(diào)整以達(dá)到全局最優(yōu)與收斂速度之間的最佳平衡[4]?;谀:鼼A的挖掘通過關(guān)聯(lián)規(guī)則和模糊GA的合理融合有著更好的挖掘性能[5],但依舊存在收斂性較差問題;有學(xué)者提出了基于聚類和基于專家經(jīng)驗(yàn)相結(jié)合的自動(dòng)篩選方法,實(shí)現(xiàn)了關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘在交通數(shù)據(jù)中的實(shí)際應(yīng)用[6];數(shù)據(jù)挖掘結(jié)合貝葉斯算法在氣象數(shù)據(jù)中的應(yīng)用也具有良好的預(yù)測(cè)效果[7];模糊集和模糊關(guān)聯(lián)規(guī)則的自動(dòng)挖掘中,基于GA的自動(dòng)聚類方法有顯著的成效[8]。作為影響GA的2個(gè)重要參數(shù):交叉和變異概率,很多學(xué)者對(duì)其加以改進(jìn)以提高可用性與適用性,加快收斂速度,有學(xué)者通過非線性排序減少近親遺傳取得了不錯(cuò)的效果[9],改進(jìn)后的自適應(yīng)GA算法的收斂性還可以通過采取最優(yōu)保存策略得以保障[10],而其交叉與變異算子也有著各種各樣的改進(jìn)以保障其全局最優(yōu)的優(yōu)勢(shì)[11-12]。
本文提出一種將自適應(yīng)GA和關(guān)聯(lián)規(guī)則相融合的方法,對(duì)傳統(tǒng)算法Apriori和FP-Growth[13]的優(yōu)劣進(jìn)行分析,最終選擇GA用于交通數(shù)據(jù)關(guān)聯(lián)規(guī)則的挖掘[14],并根據(jù)其具體需求對(duì)GA進(jìn)行適當(dāng)?shù)淖赃m應(yīng)改進(jìn)。與此同時(shí),通過引入親密度的參數(shù)來適當(dāng)調(diào)整其客觀性。以Hadoop集群的搭建,將關(guān)聯(lián)規(guī)則部署到大數(shù)據(jù)分析技術(shù)的流行開源平臺(tái)——Hadoop上以提升挖掘海量數(shù)據(jù)的效率。
Apriori算法[15]作為最經(jīng)典的算法,其基礎(chǔ)是頻繁項(xiàng)集先驗(yàn)知識(shí)。Apriori算法的主要問題在于:為了搜索全部頻繁模式,就要對(duì)事務(wù)庫(kù)進(jìn)行重復(fù)掃描,而且為了獲得較長(zhǎng)頻繁模式,其過程中有著大量的候選短頻繁模式產(chǎn)生,所以這就導(dǎo)致Apriori有著較大的時(shí)間以及空間復(fù)雜度。FP-Growth算法是Han在2000年提出的一個(gè)新的算法模型,用于解決這一瓶頸問題。算法主要分為2個(gè)過程:構(gòu)造FP-Tree和挖掘頻繁模式。研究表明,F(xiàn)P-Growth適應(yīng)挖掘不同長(zhǎng)度的頻繁模式,其在效率上要比Apriori快出一個(gè)數(shù)量級(jí)[16]。當(dāng)FP-growth搜索頻繁項(xiàng)集時(shí),它生成大量條件模式庫(kù)并構(gòu)造條件頻繁模式樹,這不僅影響頻繁項(xiàng)集的挖掘效率,增加了數(shù)據(jù)庫(kù)服務(wù)器的負(fù)擔(dān),對(duì)于海量數(shù)據(jù)而言,它的時(shí)間和空間復(fù)雜度依舊很大。
GA作為一種模擬自然進(jìn)化過程搜索最優(yōu)解的方法,因其在算法過程中無需產(chǎn)生大量的頻繁模式,是Apriori和FP-Growth的有效補(bǔ)充。GA通過將實(shí)際研究對(duì)象的值按某種方式進(jìn)行編碼后轉(zhuǎn)化為染色體,編碼不僅簡(jiǎn)單易于實(shí)現(xiàn),而且便于遺傳算子的操作,這里選擇實(shí)數(shù)編碼方式,如表1所示。
表1 事務(wù)數(shù)據(jù)庫(kù)Tab.1 Transaction database
事務(wù)數(shù)據(jù)庫(kù)中的個(gè)體編碼就是一個(gè)元素個(gè)數(shù)為n的實(shí)數(shù)數(shù)列,A[i]為字段i,i=1,2,3,…,n;用數(shù)值0~M[r]表示字段A[i]屬性值,比如天氣狀況,可用“1”表示“晴天”,“2”表示“小雪”,這里,“天氣”就是字段,而“晴天”和“小雪”就是“天氣”這個(gè)字段的其中2個(gè)屬性值。此外,“0”值被用來表示此屬性與其他屬性無關(guān)聯(lián)。
染色體結(jié)構(gòu)編碼結(jié)構(gòu)如表2所示。支持度和置信度在關(guān)聯(lián)規(guī)則中有著很重要的作用,兩者一高一低或者一低一高都說明規(guī)則是無效的。適應(yīng)度函數(shù)在GA中用于評(píng)估群體中的每個(gè)個(gè)體的利與弊,起著關(guān)鍵性的作用,這里采用結(jié)合支持度作為適應(yīng)度函數(shù)如下
表2 事務(wù)數(shù)據(jù)庫(kù)中個(gè)體編碼方式Tab.2 The individual encoding of transaction database
式中:X,Y分別為關(guān)聯(lián)規(guī)則的先導(dǎo)(Antecedent/left-hand-side,LHS)和 后 繼 (Consequent/right-hand-side,RHS),min_sup為最小支持度閾值,Count(X?Y)為絕對(duì)支持度,關(guān)聯(lián)規(guī)則X?Y相對(duì)支持度為sup(X?Y)=Count(X?Y)/|D|。X?Y為所需規(guī)則時(shí),fitness(X?Y)>1,而fitness(X?Y)<1的規(guī)則于下一代的遺傳操作中淘汰。故只有高支持度的個(gè)體才可以存活下來。
因?yàn)閿?shù)據(jù)中記錄量不同,字段數(shù)不同,字段屬性不同,所對(duì)應(yīng)的min_sup也是應(yīng)該不同的,1000條20字段屬性范圍[1,10]的min_sup應(yīng)該比100條10字段屬性范圍[1,3]的min_sup要大,所以min_sup必須和實(shí)際情況相符合,這里取min_conf=40%,而min_sup的動(dòng)態(tài)變化如下
選擇是一個(gè)選擇較優(yōu)個(gè)體的操作。由于傳統(tǒng)的選擇算子沒有考慮到關(guān)聯(lián)規(guī)則的支持度和置信度,因此,本文選擇將相對(duì)支持度大于min_sup的個(gè)體都將被保留進(jìn)入到下一代。交叉操作作為GA的關(guān)鍵步驟是將2個(gè)父代個(gè)體的染色體進(jìn)行部分基因的交換從而得出新的子代個(gè)體,本文選用單點(diǎn)交叉方式。本文采取的染色體編碼方式是實(shí)數(shù)編碼,結(jié)合單點(diǎn)交叉,再在此基礎(chǔ)上融入均勻交叉的思想,設(shè)定好交叉點(diǎn)后,任意選擇進(jìn)行互換的部分無論是交叉點(diǎn)前面的還是后面的基因,都能避免無關(guān)基因過早收斂。變異在GA中能夠維持群體的多樣性[17]。
對(duì)于GA而言,有一個(gè)不可避免的問題就是容易早熟問題,而交叉概率Pc和變異概率Pm可以對(duì)這一問題有一定的避免作用。對(duì)于傳統(tǒng)GA而言,Pc和Pm都是常數(shù),一般取值為Pc? [0.4,0.9],Pm? [0.01,0.1]。在 GA 進(jìn)化的早期階段,如果使用固定的Pm值,當(dāng)Pm較小時(shí)不會(huì)對(duì)群體產(chǎn)生什么影響,利于新基因的產(chǎn)生,較大會(huì)破壞群體的優(yōu)秀基因。也就是說雖然交叉概率越大,算法的搜索區(qū)域越大,但是卻會(huì)導(dǎo)致遺傳模式很容易被破壞,過小又會(huì)使得搜索時(shí)間過長(zhǎng),過程緩慢,算法顯得很遲鈍。對(duì)于變異概率而言,過大會(huì)使其成為一般性的隨機(jī)搜索算法,反之難以產(chǎn)生新個(gè)體[18]。自適應(yīng)GA對(duì)這2個(gè)參數(shù)進(jìn)行動(dòng)態(tài)變化,這種動(dòng)態(tài)變化是根據(jù)其進(jìn)化的代數(shù)以及適應(yīng)度進(jìn)行的合理調(diào)整。適當(dāng)對(duì)Pc和Pm變化使得產(chǎn)生出的個(gè)體能夠作為相對(duì)優(yōu)良個(gè)體從而保護(hù)其優(yōu)良性。反之,比平均值小則需增大Pc,減小Pm。在這種調(diào)節(jié)方法下的GA無需過大的進(jìn)化代數(shù)就更容易減弱全局搜索能力,慢慢增加其局部搜索能力,提高算法效率與適用性。
在解決實(shí)際問題時(shí),一般希望算法可以在一開始快速搜索,當(dāng)獲取的遺傳模式越來越好時(shí),放慢腳步,保護(hù)遺傳模式。因此,文獻(xiàn)[11]對(duì)交叉、變異概率進(jìn)行了自適應(yīng)改進(jìn),有
文獻(xiàn)[12]對(duì)文獻(xiàn)[11]的Pc和Pm進(jìn)一步改進(jìn)如下
式中:fmax為整個(gè)的最大適應(yīng)度值,favg為每代的平均值,f'為2個(gè)要交叉的個(gè)體中較大值,f為要變異個(gè)體的值,Pc1和Pc2均為交叉概率,取值Pc1=0.9,Pc2=0.6,Pm1和Pm2均為變異概率,取值Pm1=0.1,Pm2=0.01。該自適應(yīng)改進(jìn)在求解類似旅行商(Traveling salesman problem,TSP)等問題時(shí)有不錯(cuò)表現(xiàn),但是應(yīng)用在關(guān)聯(lián)規(guī)則當(dāng)中,當(dāng)f'≥favg時(shí)Pc值只在(Pc1-Pc2)的小范圍內(nèi)變動(dòng),其主要原因是個(gè)體支持度與最小支持度的比值波動(dòng)范圍不是很大,所以導(dǎo)致沒有明顯的自適應(yīng)效果。
本文對(duì)Pc和Pm值進(jìn)行如下改進(jìn)
式中:Pc1取值為 0.9,Pc2取值為 0.6,Pm1取值為0.1,Pm2取值為0.01,終止條件為最大進(jìn)化代數(shù)MaxGen=1000。
為解決一般關(guān)聯(lián)規(guī)則中出現(xiàn)的不相關(guān)的無用規(guī)則問題,本文引入了一種新的方法——親密度,以避免實(shí)際問題中出現(xiàn)的負(fù)相關(guān)關(guān)系,從而規(guī)避無用規(guī)則,提高實(shí)用性和可靠性。親密度的定義如下
式中:置信度為conf(X?Y)=Count(X?Y)/Count(X),最小置信度表示為min_conf。當(dāng)intimacy(X?Y)=1時(shí),稱為不相關(guān)規(guī)則,即兩者是相互獨(dú)立的;intimacy(X?Y)<1稱為負(fù)相關(guān),即項(xiàng)目集合Y會(huì)因項(xiàng)目集合X的發(fā)生而減小其發(fā)生的可能性;intimacy(X?Y)>1稱為正相關(guān),即Y會(huì)因X而增加發(fā)生的可能性。
基于式(9)親密度的挖掘模型如圖1所示。
圖1 引入親密度的關(guān)聯(lián)規(guī)則模型Fig.1 Association rule model framework with intimacy
算法流程如下。
步驟1初始化Pc,Pm,n等參數(shù),隨機(jī)生成初始種群Porigin={A1,A2,A3,…,An}。
步驟2計(jì)算min_sup和種群Porigin中每個(gè)個(gè)體的適應(yīng)度fitness(X?Y)。
步驟3個(gè)體是通過基于適應(yīng)度比例選擇從群體中選出,如果fitness(X?Y)≥min_sup則復(fù)制到下一代個(gè)體,否則保留并計(jì)算m。
步驟4如果m<n,隨機(jī)生成n-m個(gè)個(gè)體,并根據(jù)式(7,8)進(jìn)行自適應(yīng)遺傳操作和變異操作。
步驟5對(duì)規(guī)則集中的個(gè)體進(jìn)行判斷,分別計(jì)算每個(gè)規(guī)則(X?Y)的sup(X?Y),conf(X?Y)和 intimacy(X?Y)。
步驟6如果滿足sup(X?Y)> min_sup, conf(X?Y)>min_conf和intimacy(X?Y)>1的條件,那么取Best_Rules=Best_Rules U{(X?Y)}。
步驟7獲取相關(guān)性并提取強(qiáng)關(guān)聯(lián)規(guī)則。
本實(shí)驗(yàn)先后采用了氣象數(shù)據(jù)集和某城市交通事故數(shù)據(jù)集進(jìn)行改進(jìn)算法的驗(yàn)證,因氣象數(shù)據(jù)集涉及衛(wèi)星云圖的安全問題,不能獲取即時(shí)的準(zhǔn)確信息,存在一定誤差,所以本文主要以交通事故數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)分析。該交通事故數(shù)據(jù)集包含了豐富的信息,有45個(gè)字段,包括發(fā)生事故時(shí)候道路的等級(jí)、位置特征、當(dāng)時(shí)的天氣情況等,特定事故數(shù)據(jù)情況的字段,每個(gè)要素及其編碼值如表3、4所示。
表3 字段編碼值對(duì)應(yīng)數(shù)據(jù)表Tab.3 Field encoding value data table
表4 編碼與各要素對(duì)應(yīng)表Tab.4 The corresponding table of codes and element
“云計(jì)算”技術(shù)即為通過網(wǎng)絡(luò)訪問非本地資源的計(jì)算服務(wù)(包括數(shù)據(jù)處理、存儲(chǔ)和信息服務(wù)等),這些資源能夠方便且高效地部署,并不用過多的人為操作[19]。Hadoop是Apache Foundation開發(fā)的開源分布式計(jì)算平臺(tái),Hadoop MapReduce是在硬件集群上并行處理大量數(shù)據(jù)的軟件框架。MapReduce將大型作業(yè)劃分為較小的作業(yè),然后并行處理這些作業(yè),最后將其結(jié)果存儲(chǔ)在分布式文件系統(tǒng)中。MapReduce將數(shù)據(jù)的處理分為Map和Reduce這2個(gè)主要階段進(jìn)行[20]。Map階段的任務(wù)執(zhí)行過程為:Map:Reduce的執(zhí)行過程為pReduce流程圖如圖2所示。Hadoop的框架最核心的基礎(chǔ)架構(gòu)就是其分布式文件系統(tǒng)(Hadoop distributed file system,HDFS)和并行計(jì)算框架MapReduce(Google MapReduce的開源實(shí)現(xiàn))。HDFS為大量數(shù)據(jù)提供存儲(chǔ),而MapReduce為其提供計(jì)算[21]。HDFS架構(gòu)如圖3所示,HDFS的主控節(jié)點(diǎn)為NameNode,HDFS從節(jié)點(diǎn)為DataNode,用于存儲(chǔ)大規(guī)模數(shù)據(jù)。MapReduce的主控節(jié)點(diǎn)為JobTracker,MapReduce的從節(jié)點(diǎn)為TaskTracker,用于管理每個(gè)節(jié)點(diǎn)上計(jì)算任務(wù)的執(zhí)行。數(shù)據(jù)存儲(chǔ)主節(jié)點(diǎn)NameNode和并行計(jì)算主節(jié)點(diǎn)JobTracker可以設(shè)置在同一主節(jié)點(diǎn)上或2個(gè)不同節(jié)點(diǎn)上[22]。
圖2 MapReduce處理過程流程圖Fig.2 MapReduce process flow chart
由于需要處理大量數(shù)據(jù),本文使用具有完全分發(fā)模式的Hadoop平臺(tái)。實(shí)驗(yàn)搭建4節(jié)點(diǎn)集群,其中1個(gè)節(jié)點(diǎn)作為Namenode和JobTracker的服務(wù)節(jié)點(diǎn),其他3個(gè)節(jié)點(diǎn)作為Datanode和Task-Tracker節(jié)點(diǎn)。節(jié)點(diǎn)IP分配以及每個(gè)節(jié)點(diǎn)的功能如圖4所示。
圖3 HDFS架構(gòu)Fig.3 HDFS architecture
圖4 Hadoop平臺(tái)環(huán)境Fig.4 Hadoop platform environment
首先在一臺(tái)計(jì)算機(jī)上隨機(jī)產(chǎn)生n個(gè)群體,然后用MapReduce將群體分而治之,將群體分為m個(gè)部分,對(duì)每一部分單獨(dú)進(jìn)行計(jì)算與遺傳操作。流程圖如圖5所示。
圖5 融合GA算法的關(guān)聯(lián)規(guī)則挖掘MapReduce化Fig.5 Association rule mining based on GA and MapReduce
交叉概率Pc和變異概率Pm的曲線如圖6,7所示。由圖6可知,Pc隨著進(jìn)化代數(shù)的增加而減小,最后趨于0.3。由圖7可知,Pm隨著進(jìn)化代數(shù)的增加而增大,且最后趨于0.09。改進(jìn)后的算法在進(jìn)化剛開始階段新個(gè)體的生成主要受到交叉算子的影響,但是隨后由于交叉概率趨于一定值,從而使優(yōu)良基因得以保護(hù)。同樣地,初期變大的Pm又可以幫助其脫離局部最優(yōu)從而產(chǎn)生新個(gè)體。
圖6 改進(jìn)自適應(yīng)Pc線圖Fig.6 Improved adaptivePccurve
圖7 改進(jìn)自適應(yīng)Pm曲線圖Fig.7 Improved adaptivePmcurve
將經(jīng)典GA、文獻(xiàn)[12]算法(改進(jìn)1)和本文的改進(jìn)算法(改進(jìn)2)應(yīng)用于關(guān)聯(lián)規(guī)則挖掘后的實(shí)驗(yàn)結(jié)果如圖8所示。
由圖8可知,本文改進(jìn)算法在解的質(zhì)量方面與經(jīng)典算法和改進(jìn)1算法相比均有一定的提升。
圖8 改進(jìn)自適應(yīng)GA算法與經(jīng)典GA算法對(duì)比Fig.8 Comparison between improved adaptive GA and traditional GA
算法效率由于會(huì)受到數(shù)據(jù)中的要素個(gè)數(shù)、屬性的取值范圍以及數(shù)據(jù)量的影響,據(jù)此將FP-Growth算法效率和改進(jìn)后的融合GA與關(guān)聯(lián)規(guī)則的算法效率在這三方面進(jìn)行比較,得出時(shí)間比(優(yōu)化自適應(yīng)GA/FP-Growth)的曲線圖如圖9,10,11所示。
從結(jié)果可得GA挖掘多字段多屬性值時(shí)優(yōu)勢(shì)顯著,雖然隨數(shù)據(jù)量遞增,GA的計(jì)算效率較FP-Growth算法較低,但其加速比在可接受范圍之內(nèi),如果字段數(shù),也就是數(shù)據(jù)庫(kù)中交通事故的屬性越多,則改進(jìn)GA的效率相比較FP-Growth越好;同樣,若每個(gè)屬性的取值范圍越大,改進(jìn)GA的效率也更好;但是,改進(jìn)GA對(duì)于遞增的數(shù)據(jù)庫(kù)數(shù)據(jù)量沒有FP-Growth表現(xiàn)好。綜上,改進(jìn)自適應(yīng)GA較FP-Growth算法更適用于結(jié)構(gòu)復(fù)雜的交通事故數(shù)據(jù)挖掘,雖然GA比FP-Growth對(duì)于數(shù)據(jù)量遞增時(shí)效率較低,但二者差距不大,當(dāng)數(shù)據(jù)量在10000條記錄以下時(shí)比值都在4以下,而當(dāng)數(shù)據(jù)量超過10000條時(shí),二者算法效率都比較低,所以進(jìn)一步并行化可解決算法對(duì)大數(shù)據(jù)的處理。綜合來看自適應(yīng)GA更適合挖掘結(jié)構(gòu)復(fù)雜的交通數(shù)據(jù)。
圖9 交通數(shù)據(jù)要素個(gè)數(shù)下的時(shí)間比(數(shù)據(jù)量:1000,屬性取值范圍:[1,10])Fig.9 The time ratio under the number of traffic data elements
圖10 屬性范圍下的時(shí)間比(屬性范圍(數(shù)據(jù)量:1000,字段數(shù):20))Fig.10 Time ratio under property range
圖11 記錄量下的時(shí)間比(交通要素個(gè)數(shù):20,屬性值取值范圍:[1,10])Fig.11 Record the time ratio under the quantity
當(dāng)挖掘好頻繁模式后,對(duì)頻繁模式進(jìn)行置信度計(jì)算,挖掘強(qiáng)關(guān)聯(lián)規(guī)則,提取后的結(jié)果以1000條記錄、20個(gè)字段、屬性取值范圍[1,10]為例有:
(1)酒后駕駛和疲勞駕駛引發(fā)的交通事故較多(支持度很高);
(2)發(fā)生事故地點(diǎn)附近寫字樓密集,即交通流量大,則人員死亡數(shù)相對(duì)較低;
(3)惡劣天氣,包括雪天、霧天在快速路上發(fā)生交通事故較多;
(4)違反交通規(guī)則的駕駛員容易造成交通事故。
本文針對(duì)交通數(shù)據(jù)未被充分利用、潛在價(jià)值未被充分挖掘的問題,提出了關(guān)聯(lián)規(guī)則在智能交通中的應(yīng)用,利用自適應(yīng)GA的全局優(yōu)化能力將其融合到關(guān)聯(lián)規(guī)則中,最后在提取規(guī)則前引入了親密度的度量方法提高了可靠性。通過Hadoop平臺(tái)進(jìn)行實(shí)驗(yàn)驗(yàn)證,實(shí)驗(yàn)表明改進(jìn)后的方法在算法的收斂性以及解的質(zhì)量上均有一定優(yōu)勢(shì),且挖掘效率較傳統(tǒng)方法有一定的提升,也進(jìn)一步證明了大數(shù)據(jù)分析技術(shù)在智能交通挖掘上的優(yōu)勢(shì)。然而對(duì)于更為復(fù)雜的實(shí)際數(shù)據(jù)所生成的復(fù)雜離散屬性,可能會(huì)顯得有所不足,接下來的研究工作可通過引入神經(jīng)網(wǎng)絡(luò)對(duì)數(shù)據(jù)中的特征進(jìn)行細(xì)化分析以提高方法的精度。