基于“剪枝+并行”FP-Growth算法的密切接觸人員快速追蹤技術(shù)的研究

摘? 要：利用“剪枝+并行”式FP-Growth優(yōu)化算法，通過提升計算精度和速度的方式對疫情發(fā)生地區(qū)確診患者的密接人員、次密接人員和同時空關(guān)聯(lián)人員實行快速精準的排查。與傳統(tǒng)的FP-Growth算法相比，“剪枝+并行”式FP-Growth算法的計算性能得到顯著提升。通過對某地區(qū)測試者7天內(nèi)行跡及相關(guān)聯(lián)人員信息進行時間和準確方面的測試比較發(fā)現(xiàn)，計算時長縮短了近30%，準確率由82%提升至91%。實驗表明，利用優(yōu)化后的FP-Growth算法能夠較好地滿足疫情發(fā)生地區(qū)快速精準確定相關(guān)聯(lián)人員的要求。

關(guān)鍵詞：FP-Growth算法；關(guān)聯(lián)性；快速精準

中圖分類號：TP311.1? 文獻標識碼：A? 文章編號：2096-4706（2023）02-0034-05

Research on Fast Tracking Technology of Close Contacts Based on “Pruning + Parallel” FP-Growth Algorithm

LIU Cong

（Weifang Vocational College， Weifang? 261041， China）

Abstract： The “pruning + parallel” FP-Growth optimization algorithm is used to quickly and accurately check the close contact personnel， sub close contact personnel and simultaneous air contact personnel of the confirmed patients in the epidemic area by the ways of improving the calculation accuracy and speed. Compared with the traditional FP-Growth algorithm， the computational performance of the “pruning + parallel” FP-Growth algorithm has been significantly improved. Through testing and comparing the time and accuracy of testers' tracks and related personnel information within 7 days in a certain area， it is found that the calculation time is shortened by nearly 30%， and the accuracy rate is improved from 82% to 91%. The experiment shows that the optimized FP-Growth algorithm can better meet the requirements of quickly and accurately determining the relevant personnel in the epidemic area.

Keywords： FP-Growth algorithm; relevance; fast and accurate

0? 引? 言

截至2022年8月，國內(nèi)疫情仍處于低水平波動狀態(tài)，日均確診病例200人以上，無癥狀感染者1 000人以上，且變種病毒層出不窮，給地區(qū)疫情防控和經(jīng)濟發(fā)展造成極大麻煩。思考如何利用現(xiàn)代化分析技術(shù)快速有效追蹤密切接觸者，成為后疫情時代防控疫情、推動經(jīng)濟社會穩(wěn)定發(fā)展的關(guān)鍵點。

基于以上，本文提出利用改進的“剪枝+并行”式FP-Growth優(yōu)化算法對疫情發(fā)生區(qū)域確診人員的密接關(guān)聯(lián)人員情況進行快速準確定位，從而實現(xiàn)疫情地區(qū)的精準快速防控，及時有效切斷疫情傳播鏈，將疫情影響本地生產(chǎn)生活降低到最小[1-6]。

1? 改進FP-Growth算法實現(xiàn)關(guān)聯(lián)數(shù)據(jù)挖掘

由于本文中存在大量的數(shù)據(jù)處理和分析工作，過去傳統(tǒng)的FP-Growth算法已經(jīng)無法滿足大規(guī)模數(shù)據(jù)下的數(shù)據(jù)處理和分析。因此，根據(jù)前端特征數(shù)據(jù)采集設(shè)備所采集數(shù)據(jù)的特征，本文對傳統(tǒng)的FP-Growth算法進行優(yōu)化改進，利用MapReduce編程模型，對FP-Growth算法的各個步驟使用“剪枝+并行”法處理，優(yōu)化后的算法在計算效率上可提高約30%，運行內(nèi)存降低近40%，精準度提高10個百分點[7]。

1.1? FP-Growth算法和關(guān)聯(lián)規(guī)則算法原理

FP-Growth算法主要是通過利用和獲取構(gòu)建的樹形結(jié)構(gòu)圖中的相關(guān)事件集，來進行關(guān)聯(lián)性分析，每個事件都會在樹形結(jié)構(gòu)圖中以路徑的形式標出，出現(xiàn)疊加的路徑越多，說明在使用FP-Growth算法的優(yōu)勢越明顯。FP-Growth算法的實現(xiàn)需要經(jīng)過兩個過程，一是構(gòu)建FP-Tree，二是對FP-Tree進行關(guān)聯(lián)性數(shù)據(jù)挖掘。

關(guān)聯(lián)規(guī)則在數(shù)學(xué)方面很容易理解，即某事件X和事件Y的關(guān)系，在其關(guān)聯(lián)算法中的應(yīng)用規(guī)則相類似，事件X看作關(guān)聯(lián)規(guī)則的前導(dǎo)項，事件Y看作關(guān)聯(lián)規(guī)則的后續(xù)項，可用公式表示為：X—>Y，其中在關(guān)系規(guī)則中有兩個關(guān)鍵度，即一個是支持度（support），另一個是置信度（confidence）[8]。

支持度，主要是指前導(dǎo)事件X和后續(xù)事件Y的共同事件在總事件Z中所占的比例，可以用數(shù)學(xué)公式表示為：P（X∪Y ）=（X∪Y ）/Z。

置信度，主要指是在總事件中前導(dǎo)事件X和后續(xù)事件Y共同出現(xiàn)與只包含X事件或Y事件的比例，可以用數(shù)學(xué)公式表示為：

P（X |Y ）=P（X∩Y ）/P（X ）或者P（Y |X ）=P（X∩Y ）/P（Y ）。

關(guān)聯(lián)規(guī)則的產(chǎn)生主要來源于購物方面的相關(guān)聯(lián)性分析，即在更好的服務(wù)購物者的同時加大商品的銷量。在關(guān)聯(lián)規(guī)則中有兩個值較為關(guān)鍵，一是支持度事件值，另一個是置信度事件值，如果這兩個值的最小支持度（Min_support）和最小置信度（Min_confidence）都能夠達到自定義的閾值，那么系統(tǒng)在數(shù)據(jù)分析上就認為運用關(guān)聯(lián)規(guī)則是有意義的[9]。關(guān)聯(lián)規(guī)則在數(shù)據(jù)挖掘的整個過程中，需要經(jīng)歷兩步：一是要從原始數(shù)據(jù)信息中尋找出現(xiàn)頻率較高的事件集，即必須要大于等于最小支持度的閾值；二是要利用這些頻率較高的事件集來確定相關(guān)的關(guān)聯(lián)規(guī)則，即必須要滿足大于等于最小置信度的閾值。FP-Growth算法整體工作流程圖如圖1所示。

1.1.1? 構(gòu)建FP-Tree樹

第一步：首先需要對總數(shù)據(jù)集進行一次檢索，找出每個事件字符所出現(xiàn)的頻次，然后依據(jù)支持度的最小閾值，假設(shè)Min_support=3，測試中使用列表1進行試驗分析，排除小于最小閾值的事件字符，從而得到新的列表，如表2所示。

第二步：再一次對新的數(shù)據(jù)集列表2進行一次檢索，設(shè)根節(jié)點為root，根據(jù)數(shù)列集中的事件字符依次以樹狀圖的形式下順，每次出現(xiàn)重復(fù)的字符就進行加1操作，最終得到完整地FP-Tree，具體執(zhí)行過程如圖2所示。

1.1.2? 對FP-Tree進行關(guān)聯(lián)性數(shù)據(jù)挖掘

在構(gòu)建FP-Tree結(jié)束后，選擇樹狀圖中固定節(jié)點字符，然后從樹狀圖中找出與固定節(jié)點字符相關(guān)聯(lián)的路徑，以s為例，可以看出從根節(jié)點root開始依次查找到與s相關(guān)的路徑分別為h{1}—>f{1}—>d{1}—>u{1}，h{1}—>f{1}—>d{1}和f{1}—>e{1}，然后按照上面的第二步操作重新進行建立樹狀圖，可以得到一個關(guān)于s的關(guān)聯(lián)性的項fs{3}。

以上就是關(guān)于FP-Growth算法實現(xiàn)關(guān)聯(lián)性的整個過程，該算法在查看本系統(tǒng)中的相關(guān)監(jiān)測人員的密切度方面有極大幫助。但是隨著數(shù)據(jù)量的增加，單一的FP-Growth算法在運算方面就比較吃力，為此，在設(shè)計無線管控系統(tǒng)時，考慮到了對FP-Growth算法進行一定優(yōu)化處理，采用并行+剪枝+FP-Growth的算法達到實際系統(tǒng)高效運算的目的。

1.2? 優(yōu)化改進FP-Growth算法

1.2.1? 樹枝合并化改進

首先，根據(jù)需求設(shè)定一個定義，假如構(gòu)建的FP-Tree的樹狀圖中的路徑M中含有非頻繁的事件r，路徑N中也包含非頻繁事件r，同時滿足M∈N，那么就可以把N中的事件r去掉，然后合并到較短的路徑M中，合并前的樹狀圖如圖3所示，合并后的樹狀圖如圖4所示。

依據(jù)此假設(shè)，對本文在優(yōu)化改進FP-Growth算法方面得到以下啟示：在面對多事件路徑時，對于路徑中存在的某些非頻繁的事件項，可以采用合并事件集路徑的方法，對FP-Growth算法進行升級改造，通過減少數(shù)據(jù)挖掘過程中的檢索路徑數(shù)量，來達到提高運算效率的目的[10]。

1.2.2? 數(shù)據(jù)挖掘并行化改進

依據(jù)前面的“剪枝”可以得知，主要是在構(gòu)建FP-Tree樹狀圖時進行路徑優(yōu)化處理，但是在后續(xù)對FP-Tree進行關(guān)聯(lián)性數(shù)據(jù)挖掘時，仍需繼續(xù)改進提速。因為在對數(shù)據(jù)進行挖掘時，對于不同事件集的挖掘，所對應(yīng)的頻繁項集是不同的，它決定著FP-Tree的復(fù)雜程度，同時FP-tree又主要作用于內(nèi)存中，所以FP-Tree的復(fù)雜程度越高，占用的內(nèi)存就越大，對于運行速率方面有一定影響。為此，本文繼續(xù)提出了把FP-Growth算法傳統(tǒng)的串行法變?yōu)椴⑿蟹ǖ脑O(shè)計，解決數(shù)據(jù)量規(guī)模較大的問題，在運算效率上得到進一步提高，并行法的結(jié)構(gòu)圖如圖5所示。

FP-Growth算法實行并行法的設(shè)計思路主要有以下幾步：

第一步：先對原始的數(shù)據(jù)信息求出其頻繁事件項集，然后對其不同事件出現(xiàn)的頻率由高到低進行編碼處理，最后把編寫好的列表文件傳送到指定的執(zhí)行文件中，編碼列表如表3所示。

第二步：對原始數(shù)據(jù)進行分組，把初始事件組轉(zhuǎn)換為編碼的事件組，然后對所有的事件進行分組劃分，設(shè)定分為α組和β組，事件項集合{h，f，d，e，u，v}包含分組α{h，f，d，e}和分組β{e，u，v}，若初始事組中的某一事件項既包含在α組中，又包含在β組中，那么這一事件項就要輸出到兩個分組中，具體分組情況如表4所示。

第三步：對上述分組結(jié)果，分別對每組的事件項進行建立樹狀圖的操作，具體的執(zhí)行步驟如上節(jié)對原始數(shù)據(jù)的樹狀圖操縱類似，新建的樹狀圖α和β分別如圖6和圖7所示。

第四步：對新建的樹狀圖進行分別進行關(guān)聯(lián)性數(shù)據(jù)挖掘處理，一個map（）函數(shù)對應(yīng)一個分組進行挖掘操作，生成每個分組的頻繁事件項集，然后通過reduce（）函數(shù)操作，把分散的頻繁事件項集合并成一個大的整體，最后根據(jù)支持度和置信度得出數(shù)據(jù)關(guān)聯(lián)性挖掘的最終結(jié)果，具體操作如圖8所示。

1.3? 關(guān)聯(lián)性數(shù)據(jù)挖掘的實現(xiàn)

客戶端在點擊執(zhí)行關(guān)聯(lián)性查詢時，發(fā)送運行改進的FP-Growth算法的請求，程序端在接收到命令請求時會連同關(guān)聯(lián)性參數(shù)一起發(fā)送給FP-Growth_action函數(shù)進行處理，F(xiàn)P-Growth_action函數(shù)會啟動一個改進的FP-Growth算法線程，通過FP-Growth_monitor函數(shù)進行實時刷新監(jiān)控，就可以獲取到改進的FP-Growth算法運行后的實時數(shù)據(jù)信息[11]，具體調(diào)用改進的FP-Growth算法的流程圖如圖9所示。

2? 測試性能與結(jié)果分析

本文主要從單機數(shù)據(jù)處理和多節(jié)點性能測試兩方面對改進的FP-Growth算法和傳統(tǒng)的FP-Growth算法在性能方面進行差異化性能測試。

2.1? 單機處理對比

在保證實驗硬件、數(shù)據(jù)量等方面一致的前提下，通過植入兩種不同的算法，對運算性能進行測驗，同時為了保證實驗測驗的可靠性，減小誤差，分別對每組實驗數(shù)據(jù)進行100次以上的重復(fù)測驗，最后取其均值作為測驗結(jié)果進行分析。測試的方法主要是看折線圖中數(shù)據(jù)量和平均時間的比值大小，比例系數(shù)越小說明運算的效率越高，反之越低，具體的測試結(jié)果圖如圖10所示。

從測驗的結(jié)果中可以得出：當數(shù)據(jù)量較小時，傳統(tǒng)的FP-Growth算法在工作效率方面具有一定的優(yōu)勢，但是隨著數(shù)據(jù)量的增加，改進的FP-Growth算法就逐漸地顯示出其自身的優(yōu)勢。因此，把合并分支路徑和并行運算整體運用到FP-Growth算法中，能夠?qū)崿F(xiàn)在數(shù)據(jù)量不斷擴大的前提下，使運行的效率不至于出現(xiàn)急劇的下滑，大大地提高了關(guān)聯(lián)性數(shù)據(jù)挖掘的速率。

2.2? 多節(jié)點性能測試

為了進一步測驗優(yōu)化改進的FP-Growth算法性能，實驗中又設(shè)計了另外一組對比實驗，在集群的環(huán)境下測試該算法的性能。本實驗中采用主從式架構(gòu)，一共包含10個節(jié)點，其中1個節(jié)點作為服務(wù)節(jié)點，另外的9個節(jié)點作為數(shù)據(jù)節(jié)點，其他配置均相同。測驗中選擇最小的支持度分別為10%和20%，同時從數(shù)據(jù)庫中的相關(guān)存儲文件中隨機選取大量數(shù)據(jù)，構(gòu)建三組大數(shù)據(jù)，分別標記為D1、D2、D3。圖11至圖14分別顯示在最小支持度分別為10%和20%的情況下，三組不同的數(shù)據(jù)及9個任務(wù)節(jié)點執(zhí)行傳統(tǒng)FP-Growth算法和改進FP-Growth算法的時間對比。

從以上兩組測驗對比圖中的折線規(guī)律可以得出。在數(shù)據(jù)量一定的情況下，隨著節(jié)點數(shù)的增加，通過優(yōu)化改進的FP-Growth算法的相對運行時間在不斷減少。出現(xiàn)這種狀況的主要原因在于，節(jié)點數(shù)量的增加導(dǎo)致消耗通信時間的增加程度明顯的小于計算時間所減少的程度。另外，相同的數(shù)據(jù)，會隨著最小支持度的增加而相對應(yīng)的運行時間有所減少，這是因為最小支持度變大后，頻繁數(shù)據(jù)項集的數(shù)量和長度也會相應(yīng)地減少，從而運行時間縮短[12]。

3? ?結(jié)? 論

本文在研究FP-Growth算法的基礎(chǔ)上，針對當前疫情區(qū)域人員信息數(shù)據(jù)量大、數(shù)據(jù)及時性高等特點和存在的問題，提出了一種基于“剪枝+并行”FP-Growth算法的密切接觸人員快速追蹤技術(shù)的方法，并在實地場景進行測驗。但仍有改進的余地，下一步的研究工作主要有以下幾個方面：

（1）目前還存在數(shù)據(jù)采集過程中斷斷續(xù)續(xù)不穩(wěn)定的情況，數(shù)據(jù)的傳輸過程中如何提高丟包率是接下來需要考慮的因素之一。

（2）對算法進一步優(yōu)化，減少在使用過程中算法訓(xùn)練所需的次數(shù)，使精度的提高更快。

（3）通過更多的實驗，進一步精確算法的主要參數(shù)值，以盡可能提高算法性能。

參考文獻：

[1] 秦雷.公安監(jiān)控聯(lián)手“數(shù)字城管”南崗公安分局新中心揭牌 [N].哈爾濱日報，2008-04-11（2）.

[2] 汪明峰，顧成城.上海智慧城市建設(shè)中公共WLAN熱點的空間分析與檢討 [J].地理科學(xué)進展，2015，34（4）：438-447.

[3] 張崢嶸.淺談公安網(wǎng)絡(luò)監(jiān)控系統(tǒng)的建設(shè)與管理 [J].中國公共安全，2013（13）：130-133.

[4] 向庭勇，向庭波.用大數(shù)據(jù)技術(shù)構(gòu)建公安Wi-Fi偵測系統(tǒng)的研究與應(yīng)用 [J].中國公共安全，2016（13）：75-81.

[5] 陳剛，羌鈴鈴.針對不同平臺系統(tǒng)獲取MAC地址的特定方法 [J].微計算機信息，2012，28（5）：182—183+154.

[6] 公安監(jiān)控網(wǎng)絡(luò)集成系統(tǒng)為平安城市保駕護航 [J].中國公共安全，2015（7）：127-128.

[7] 馬月坤，劉鵬飛，張振友，等.改進的FP-Growth算法及其分布式并行實現(xiàn) [J].哈爾濱理工大學(xué)學(xué)報，2016，21（2）：20-27.

[8] 陸楠，王喆，周春光.基于FP-tree頻集模式的FP-Growth算法對關(guān)聯(lián)規(guī)則挖掘的影響 [J].吉林大學(xué)學(xué)報：理學(xué)版，2003（2）：180-185.

[9] 張星，李蓓.FP-Growth關(guān)聯(lián)規(guī)則挖掘的改進算法 [J].平頂山工學(xué)院學(xué)報，2008（1）：21-24.

[10] 晏杰，亓文娟.基于Apriori&FP-Growth算法的研究 [J].計算機系統(tǒng)應(yīng)用，2011，47（7）：153-155.

[11] 何月順.關(guān)聯(lián)規(guī)則挖掘技術(shù)的研究及應(yīng)用 [D].南京：南京航空航天大學(xué)，2010.

[12] 楊勇，王偉.一種基于MapReduce的并行FP-growth算法 [J].重慶郵電大學(xué)學(xué)報：自然科學(xué)版，2013，25（5）：651-657+670.

作者簡介：劉聰（1990—），男，漢族，山東濰坊人，助教，碩士研究生，研究方向：圖像識別和算法研究。

收稿日期：2022-09-02