Fp-growth改進(jìn)算法在公務(wù)用車調(diào)度系統(tǒng)中的研究與應(yīng)用?

陳 君肖 鋒

（1.渭南師范學(xué)院網(wǎng)絡(luò)安全與信息化學(xué)院網(wǎng)絡(luò)安全與信息化工程技術(shù)中心 渭南 714000）（2.西安工業(yè)大學(xué)計算機(jī)科學(xué)與工程學(xué)院 西安 710032）

1 引言

我們可以通過公務(wù)用車調(diào)度管理系統(tǒng)對企事業(yè)單位的公務(wù)用車進(jìn)行車輛調(diào)度、駕駛員管理、車輛管理等工作，能夠?qū)崿F(xiàn)管理員對公務(wù)用車的信息的添加、刪除、修改、查詢等，在最短時間實現(xiàn)公務(wù)用車的合理調(diào)度，通過使用此系統(tǒng)可以完善車隊的管理，提高管理質(zhì)量和管理效率。因此有效地對網(wǎng)絡(luò)招聘系統(tǒng)中的數(shù)據(jù)進(jìn)行分析挖掘，找出其中的規(guī)律已顯得尤為重要。

本文利用基于項頭表節(jié)點(diǎn)的Fp-growth改進(jìn)算法，對公務(wù)用車調(diào)度管理系統(tǒng)中車輛類型、使用部門、用車人數(shù)、車牌號、所屬部門、駕駛員、行駛里程等信息進(jìn)行對比、分析，從中發(fā)現(xiàn)用車規(guī)律，方便車輛調(diào)度。例如：使用哪種車型的一般用車人數(shù)在多少人，哪些部門經(jīng)常使用什么車型的車輛，哪些單位用車使用車輛較為頻繁，行車年限在多少年的車輛使用率較高等。經(jīng)過對相關(guān)數(shù)據(jù)的分析有效地幫助有關(guān)部門對車輛的調(diào)度進(jìn)行更好的分配和管理，提高車輛調(diào)度效率［1］。

2 數(shù)據(jù)挖掘及關(guān)聯(lián)規(guī)則概念

數(shù)據(jù)挖掘（Data Mining）是指從大量的、不完全的、模糊的、有噪聲的、隨機(jī)的數(shù)據(jù)中提取隱含其中的、事先不知道的、有用的知識和信息的過程［2］。數(shù)據(jù)挖掘主要包括概念描述，關(guān)聯(lián)分析、分類、預(yù)測和聚類分析等內(nèi)容［3］。數(shù)據(jù)挖掘技術(shù)目前已在制造業(yè)、金融業(yè)、電信業(yè)、保險業(yè)、醫(yī)療和零售業(yè)等領(lǐng)域得到了廣泛的應(yīng)用［4］。隨著信息技術(shù)的快速發(fā)展，數(shù)據(jù)挖掘技術(shù)將成為商業(yè)智能、生物工程、網(wǎng)絡(luò)服務(wù)等領(lǐng)域研究熱點(diǎn)［5］。

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的一種，關(guān)聯(lián)規(guī)則的挖掘就是產(chǎn)生支持度和置信度大于使用者設(shè)定的最小取值的有效性規(guī)則［6］。關(guān)聯(lián)規(guī)則挖掘可分為兩步：首先，找出所有頻繁項集，就是找出所有出現(xiàn)頻率至少和預(yù)定義的最小支持度一樣的項集；然后，由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則［7］。

3 FP-Growth算法

FP-growth算法是韓家煒等提出的一種基于FP-tree的頻繁項集挖掘算法，此算法是將原始數(shù)據(jù)集壓縮到一棵FP-tree上，在整個挖掘過程中只需要掃描原始數(shù)據(jù)集兩次，并且在它的挖掘過程中不產(chǎn)生候選項集，挖掘效率得到了一定的提高［8～10］。

FP-Growth算法具有以下優(yōu)點(diǎn)：首先，F(xiàn)P-Growth算法只需要掃描原始數(shù)據(jù)集兩次，可以將一個大型的數(shù)據(jù)庫有效地壓縮成比原數(shù)據(jù)庫小很多的高密度的數(shù)據(jù)結(jié)構(gòu)，避免了對數(shù)據(jù)庫的重復(fù)掃描。其次，F(xiàn)P-Growth算法是基于FP-tree的挖掘算法，它采取模式增長的遞歸性策略，提出無候選項集的挖掘方法，在進(jìn)行頻繁模式挖掘時有效地提高挖掘的效率［11～13］。

4 基于項頭表節(jié)點(diǎn)的Fp-growth改進(jìn)算法

4.1 基本思想及算法描述

基于項頭表節(jié)點(diǎn)的FP-growth改進(jìn)算法是指在Fp-tree中找到與頭表具有一樣的Node-Link時，都必須返回頭表中，逐個找出最后一個Node-Link項后，將新找到的項加入，每次有一個新的項目出現(xiàn)時都必須從頭表第一個項開始逐個尋找，直到找出最后一個，把原算法FP-tree和項頭表的Node_link字段刪除，將Ln當(dāng)作項頭表［14］。對任意頻繁項ai，先找到所有FP-tree節(jié)點(diǎn)的Item-name與ai的項名一樣的節(jié)點(diǎn)，針對找到的每個樹節(jié)點(diǎn)尋找其頻繁模式，找到頻繁項ai的所有頻繁模式［15］。改進(jìn)后的算法比原算法節(jié)省1/5樹的空間，它將Ln當(dāng)作了項頭表，所以省去了項頭表空間。

4.2 改進(jìn)后算法的優(yōu)點(diǎn)

FP-growth算法在Fp-tree中查找與頭表中具有一樣的Node-Link時，都必須回到頭表中，逐個找出最后一個Node-Link的項后，再將新找到的項加入其中，這就相當(dāng)于每有一個新的項出現(xiàn)時都必須從頭表第一個開始查找，直到找出最后一個為止，這樣數(shù)據(jù)量大的時候效率就會相對較低。而改進(jìn)后的基于項頭表節(jié)點(diǎn)的Fp-growth算法先找到所有Fp-tree節(jié)點(diǎn)的Item-name與ai的項名一樣的節(jié)點(diǎn)，針對找到的每個樹節(jié)點(diǎn)找到它的頻繁模式，這樣也就找到了頻繁項ai的所有頻繁模式，可節(jié)省1/3的項頭表空間和1/5樹的空間。實驗結(jié)果表明，基于項頭表節(jié)點(diǎn)的FP-growth改進(jìn)算法性能優(yōu)于FP-growth算法。

5 基于項頭表節(jié)點(diǎn)的FP-Growth算法的應(yīng)用

本文在內(nèi)存為4GB，CPU為intel2.6GHz，操作系統(tǒng)為Windows 10的硬件環(huán)境下，在Microsoft Vi?sual Studio 2015開發(fā)平臺中使用C＃語言，應(yīng)用FP-growth算法對公務(wù)用車調(diào)度管理系統(tǒng)的數(shù)據(jù)庫進(jìn)行數(shù)據(jù)挖掘并得出結(jié)論。

5.1 整理與轉(zhuǎn)換數(shù)據(jù)

首先對公務(wù)用車調(diào)度管理系統(tǒng)數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行整理。整理出的有公務(wù)用車調(diào)度信息主要包括：車輛類型、使用部門、用車人數(shù)、車牌號、所屬部門、駕駛員、行駛里程等。其中例舉了一條用戶的記錄如表1所示，關(guān)系數(shù)據(jù)庫屬性值與事務(wù)數(shù)據(jù)集中的項目對應(yīng)關(guān)系如表2所示，再將其進(jìn)行數(shù)據(jù)轉(zhuǎn)換，轉(zhuǎn)換后的事務(wù)數(shù)據(jù)如表3所示。

表1 記錄的字段名含義

表2 對應(yīng)關(guān)系表

表3 轉(zhuǎn)換后的事務(wù)數(shù)據(jù)

5.2 結(jié)果及分析

下面我們對整理和轉(zhuǎn)換后的數(shù)據(jù)進(jìn)行挖掘，輸入數(shù)據(jù)為事務(wù)數(shù)據(jù)表、最小支持度、最小值信度，輸出頻繁項集。設(shè)定最小支持度為s=5%，最小置信度為c=20%。挖掘結(jié)果如表4所示。

從表4可以得出以下結(jié)論：規(guī)則A表示使用SUV車輛的一般用車人數(shù)在3到4人，規(guī)則B表示使用MPV型車輛的用車人數(shù)在5到7人，與C表示使用商務(wù)面包型車輛的用車人數(shù)在8到16人，規(guī)則D和E表示后勤和營銷部分使用車輛較為頻繁，規(guī)則F表示行車?yán)锍淘?到8萬公里，行車年限在2到5年的車輛使用率較高，規(guī)則G表示后勤部門使用MPV型車輛較多。

表4 挖掘結(jié)果

6 結(jié)語

本文將Fp-growth算法進(jìn)行了改進(jìn)，提高了挖掘速度，并用改進(jìn)后的算法對公務(wù)用車調(diào)度管理系統(tǒng)中的數(shù)據(jù)進(jìn)行了挖掘和分析，從中發(fā)現(xiàn)公務(wù)用車的使用規(guī)律，為車輛調(diào)度部門和車輛使用部門提供了有用的信息。在算法的實際應(yīng)用過程中，特別是對大型事務(wù)數(shù)據(jù)庫進(jìn)行挖掘時，數(shù)據(jù)的準(zhǔn)備與選擇至關(guān)重要，它直接關(guān)系到數(shù)據(jù)挖掘的結(jié)果是否成功，是否具有實際效益，另在數(shù)據(jù)挖掘的過程中選取恰當(dāng)?shù)淖钚≈С侄群妥钚≈眯哦纫彩鞘种匾模缛≈颠^小，挖掘結(jié)果就會出現(xiàn)大量無用規(guī)則，影響執(zhí)行效率、浪費(fèi)系統(tǒng)資源，如取值過大，可能會找不出相關(guān)規(guī)則，無法達(dá)到目的。