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

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

中圖分類號(hào)：TP311.1? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：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月，國(guó)內(nèi)疫情仍處于低水平波動(dòng)狀態(tài)，日均確診病例200人以上，無癥狀感染者1 000人以上，且變種病毒層出不窮，給地區(qū)疫情防控和經(jīng)濟(jì)發(fā)展造成極大麻煩。思考如何利用現(xiàn)代化分析技術(shù)快速有效追蹤密切接觸者，成為后疫情時(shí)代防控疫情、推動(dòng)經(jīng)濟(jì)社會(huì)穩(wěn)定發(fā)展的關(guān)鍵點(diǎn)。

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

1? 改進(jìn)FP-Growth算法實(shí)現(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ù)的特征，本文對(duì)傳統(tǒng)的FP-Growth算法進(jìn)行優(yōu)化改進(jìn)，利用MapReduce編程模型，對(duì)FP-Growth算法的各個(gè)步驟使用“剪枝+并行”法處理，優(yōu)化后的算法在計(jì)算效率上可提高約30%，運(yùn)行內(nèi)存降低近40%，精準(zhǔn)度提高10個(gè)百分點(diǎn)[7]。

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

FP-Growth算法主要是通過利用和獲取構(gòu)建的樹形結(jié)構(gòu)圖中的相關(guān)事件集，來進(jìn)行關(guān)聯(lián)性分析，每個(gè)事件都會(huì)在樹形結(jié)構(gòu)圖中以路徑的形式標(biāo)出，出現(xiàn)疊加的路徑越多，說明在使用FP-Growth算法的優(yōu)勢(shì)越明顯。FP-Growth算法的實(shí)現(xiàn)需要經(jīng)過兩個(gè)過程，一是構(gòu)建FP-Tree，二是對(duì)FP-Tree進(jìn)行關(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)項(xiàng)，事件Y看作關(guān)聯(lián)規(guī)則的后續(xù)項(xiàng)，可用公式表示為：X—>Y，其中在關(guān)系規(guī)則中有兩個(gè)關(guān)鍵度，即一個(gè)是支持度（support），另一個(gè)是置信度（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)生主要來源于購(gòu)物方面的相關(guān)聯(lián)性分析，即在更好的服務(wù)購(gòu)物者的同時(shí)加大商品的銷量。在關(guān)聯(lián)規(guī)則中有兩個(gè)值較為關(guān)鍵，一是支持度事件值，另一個(gè)是置信度事件值，如果這兩個(gè)值的最小支持度（Min_support）和最小置信度（Min_confidence）都能夠達(dá)到自定義的閾值，那么系統(tǒng)在數(shù)據(jù)分析上就認(rèn)為運(yùn)用關(guān)聯(lián)規(guī)則是有意義的[9]。關(guān)聯(lián)規(guī)則在數(shù)據(jù)挖掘的整個(gè)過程中，需要經(jīng)歷兩步：一是要從原始數(shù)據(jù)信息中尋找出現(xiàn)頻率較高的事件集，即必須要大于等于最小支持度的閾值；二是要利用這些頻率較高的事件集來確定相關(guān)的關(guān)聯(lián)規(guī)則，即必須要滿足大于等于最小置信度的閾值。FP-Growth算法整體工作流程圖如圖1所示。

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

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

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

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

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

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

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

1.2.1? 樹枝合并化改進(jìn)

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1? 單機(jī)處理對(duì)比

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

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

2.2? 多節(jié)點(diǎn)性能測(cè)試

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

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

3? ?結(jié)? 論

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

[10] 晏杰，亓文娟.基于Apriori&FP-Growth算法的研究 [J].計(jì)算機(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é)報(bào)：自然科學(xué)版，2013，25（5）：651-657+670.

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

收稿日期：2022-09-02