二分搜索算法在全局頻繁項目集求解中的應(yīng)用

曾俊義

（惠州城市職業(yè)學(xué)院民生學(xué)院，惠州516025）

0 引言

目前主流的全局頻繁項目集求解方法主要包括，基于快速挖掘的全局頻繁項目集求解方法，以及基于Apriori 算法的全局頻繁項目集求解方法兩種，但由于兩種算法的全局項目求解側(cè)重點不同，導(dǎo)致在全局頻繁項目求解中，存在求解準(zhǔn)確率與求解速率較低的不足[1]，為此提出了二分搜索算法在全局頻繁項目集求解中的應(yīng)用。依托全局頻繁項目集的確定，利用頻繁項目k 和全局隸屬度函數(shù)x 的計算，實現(xiàn)了候選項目集的生成，優(yōu)化了全局頻繁項目集求解體系；根據(jù)數(shù)據(jù)的動態(tài)求解，實現(xiàn)了全局頻繁項目集的更新計算，完成了二分搜索算法在全局頻繁項目集求解中的應(yīng)用，為保證提出的求解方法的有效性，進(jìn)行仿真實驗，實驗數(shù)據(jù)表明，提出的全局頻繁項目集求解方法具有較高的有效性。

1 優(yōu)化求解的體系

與傳統(tǒng)全局頻繁項目集求解方法不同，利用二分搜索算法通過優(yōu)化求解體系，利用全局頻繁項目集的更新計算，實現(xiàn)頻繁項目集的求解，在優(yōu)化求解體系過程中，利用二分搜索算法，首先確定全局頻繁項目集對象，然后根據(jù)頻繁項目集的確定，生成候選項目集，對候選項目集進(jìn)行計算，優(yōu)化傳統(tǒng)全局頻繁項目集求解逐條過程，針對候選項集進(jìn)行分析，通過全局頻繁項目集的更新計算，實現(xiàn)頻繁項目集的求解。

1.1 確定全局頻繁項目集

設(shè)數(shù)據(jù)庫項目D1，D2，D3，…，Dn屬于同一類別項目，那么根據(jù)同一項目建立一個數(shù)據(jù)集和D，D={D1，D2，D3，…，Dn}，D 又稱作項目集[2]。在數(shù)據(jù)庫調(diào)取項目集的過程中，例如D1、D3、D5被多次重復(fù)調(diào)去，那么在項目集D 的范圍內(nèi)，構(gòu)建一個P 的集合，P∈D，P={D1，D3，D5}，那么由D1、D3、D5組成的集合P 稱作為頻繁項目集，又因為數(shù)據(jù)庫中包含多個D 類集合，同時包含頻繁項目集P，多個頻繁項目集的集合，稱作為全局頻繁項目集[3]。

確定全局頻繁項目集，首先要確定某個項目的數(shù)據(jù)集合D，再通過項目集合D 確定頻繁項目D1，D3，D5，…，Dn，構(gòu)建該項目的頻繁項目集，是通過往復(fù)的構(gòu)建，將所有的頻繁項目集進(jìn)行組合，構(gòu)成了全局頻繁項目集。確定過程是通過全局規(guī)則庫，利用全局控制模塊、規(guī)則管理模塊對數(shù)據(jù)庫信息進(jìn)行篩選，基于網(wǎng)絡(luò)，在用戶端逐漸顯示局部頻繁集項目，局部頻繁項目集的顯示是根據(jù)局部規(guī)則庫、局部數(shù)據(jù)庫或其他數(shù)據(jù)庫接口，依托關(guān)聯(lián)規(guī)則挖掘模塊、數(shù)據(jù)庫管理模塊、局部控制模塊進(jìn)行顯示，利用外部設(shè)備人機交互功能顯示在工作人員面前，其全局頻繁項目集的確定過程，如圖1 所示[4]。

圖1 全局頻繁項目集確定過程示意圖

1.2 候選項目集的生成

候選項目集的生成是依托全局頻繁項目集的確定，根據(jù)二分搜索算法，對確定的全局頻繁項目集進(jìn)行二分搜索計算，確定頻繁項目k，以及全局隸屬度函數(shù)x，生成候選項目集。

頻繁項目k 是根據(jù)單個集合D 掃描數(shù)據(jù)庫，進(jìn)行迭代計算，通過全局站點分析，其得出的頻繁項目k 可用公式（1）表示[5]：

式中，PD 代表項目集成系數(shù)，是形容項目集成度的系數(shù)，項目集成度越高則PD 值越大；a 代表數(shù)據(jù)庫集合相關(guān)指數(shù)，若該數(shù)據(jù)庫中，存在大量相似數(shù)據(jù)集合，那么次數(shù)據(jù)集合占整個數(shù)據(jù)庫的比例，即為數(shù)據(jù)庫相關(guān)指數(shù)；R 代表計算求解數(shù)據(jù)量，單位GB；IL 代表數(shù)據(jù)離散程度，H 代表數(shù)據(jù)極限。

根據(jù)公式（1）確定了頻繁項目k，依托k 值得確定，對全局隸屬度函x 進(jìn)行求解，其全局隸屬度函x 可用公式（2）表示[6]：

式中，UL 代表當(dāng)前數(shù)據(jù)狀態(tài)；P 代表數(shù)據(jù)庫類型。依托頻繁項目k，全局隸屬度函數(shù)x 的確定，完成了候選項目集的生成，基于全局頻繁項目集的確定，優(yōu)化了全局頻繁項目求解體系。

2 全局頻繁項目集的更新計算

二分搜索算法是一種基于數(shù)學(xué)計算的系統(tǒng)數(shù)據(jù)求解方法，在進(jìn)行全局頻繁項目集的計算中，優(yōu)化傳統(tǒng)，求解體系，針對靜態(tài)數(shù)據(jù)、動態(tài)數(shù)據(jù)能夠?qū)崿F(xiàn)實時更新計算，對于數(shù)據(jù)進(jìn)行自動獲取，自我識別，生成候選項目集，進(jìn)行求解。

在更新計算過程中，與傳統(tǒng)計算不同首先要確定全局頻繁項目的計算節(jié)點，根據(jù)動態(tài)節(jié)點，利用計算機模擬計算技術(shù)，對節(jié)點的運動進(jìn)行模擬計算，并用真實值與模擬值做差，將差值控制在0.04%以內(nèi)，則說明模擬計算值接近于真實值[7]?？捎糜趧討B(tài)數(shù)據(jù)節(jié)點的計算，應(yīng)用于全局頻繁，項目集的更新計算中。設(shè)動態(tài)節(jié)點方程可用公式（3）表示[8]：

基于動態(tài)節(jié)點方程的確定，以及平均更新計算表達(dá)式σ的求解，實現(xiàn)了全局頻繁項目集的更新計算，基于二分搜索算法優(yōu)化求解體系，實現(xiàn)了二分搜索算法在全局頻繁項目集求解中的應(yīng)用。

3 實例分析

為了保證提出的二分搜索算法的全局頻繁項目集求解方法有準(zhǔn)確性，以及速率，進(jìn)行實例分析，分析過程中，采用快速挖掘的全局頻繁項目集求解方法、Apriori 算法的全局頻繁項目集求解方法作為實驗對比對象，進(jìn)行全局頻繁項目集求解驗證。

3.1 實驗準(zhǔn)備

實驗中利用已過往的全局頻繁項目作為實驗對象，進(jìn)行仿真實驗，采用已過往的全局頻繁項目作為實驗對象，是因為在相同環(huán)境下進(jìn)行求解可以精準(zhǔn)地對比出求解的準(zhǔn)確率以及求解速率，選取5 個已過往的全局頻繁項目，對全局頻繁項目進(jìn)行全局頻繁項目集求解的準(zhǔn)確率以及求解速率進(jìn)行驗證。

由于全局頻繁項目存在偶然性，以及相似性，為此選擇5 個已過往的全局頻繁項目，對全局頻繁項目集求解的準(zhǔn)確率以及求解速率進(jìn)行分析驗證。

3.2 實驗過程

由于本次實驗采用的是，根據(jù)不同全局頻繁項目集求解，對已過往的全局頻繁項目進(jìn)行求解，用參數(shù)對比方法的驗證準(zhǔn)確率以及求解速率，為此需構(gòu)建過去實驗環(huán)境，讓快速挖掘的全局頻繁項目集求解方法、Apriori 算法的全局頻繁項目集求解方法、二分搜索算法的全局頻繁項目集求解方法，不接觸原有求解數(shù)據(jù)結(jié)果的同時進(jìn)行求解數(shù)據(jù)分析。結(jié)論與事實進(jìn)行對比，分析其求解準(zhǔn)確率以及求解速率。

實驗過程中，首先建立還原實驗場景，采用相同環(huán)境下相同時間節(jié)點對全局頻繁項目集求解，例如在編號1 的全局頻繁項目集中，載入需要進(jìn)行實驗的快速挖掘的全局頻繁項目集求解方法，對全局頻繁項目集求解，再利用其他兩種全局頻繁項目集求解方法對該項目進(jìn)行求解，當(dāng)三種方法求解完成后，記錄求解值以及求解速率。以此類推，進(jìn)行五組試驗，當(dāng)五組試驗全部求解完成，并于該全局頻繁項目集真實結(jié)果進(jìn)行對比，并進(jìn)行求解準(zhǔn)確率記錄。用以設(shè)定的標(biāo)準(zhǔn)的時間值和試驗中全局頻繁項目集求解時間進(jìn)行對比，并記錄相應(yīng)求解速率。將所有記錄的數(shù)值，形成實驗結(jié)果圖表進(jìn)行對比參考。

3.3 實驗結(jié)果分析

根據(jù)時間過程，得出快速挖掘的全局頻繁項目集求解方法、Apriori 算法的全局頻繁項目集求解方法、二分搜索算法的全局頻繁項目集求解方法，在不同時間段的態(tài)勢預(yù)測情況，根據(jù)記錄的數(shù)據(jù)，形成全局頻繁項目集求解準(zhǔn)確率試驗結(jié)果，如表1 所示。

表1 實驗結(jié)果對比表

同理，形成全局頻繁項目集求解速率，如表2所示。

表2 實驗結(jié)果對比表

根據(jù)實驗結(jié)果可以得出，在求解準(zhǔn)確率和求解速率方面，二分搜索算法的全局頻繁項目集求解方法，具有較高的準(zhǔn)確率以及速率，但從整體上看，快速挖掘的全局頻繁項目集求解方法，求解的速率相對比較快，但隨著全局頻繁項目集求解越多，準(zhǔn)確率有所下降，失誤點較多。Apriori 算法的全局頻繁項目集求解方法，具有較高的準(zhǔn)確率，但整體求解速率，略低于提出的二分搜索算法的全局頻繁項目集求解方法。

通過實驗數(shù)據(jù)的統(tǒng)計計算得出，二分搜索算法的全局頻繁項目集求解方法準(zhǔn)確率為61.56%，快速挖掘的全局頻繁項目集求解方法準(zhǔn)確率為55.96%，Apriori算法的全局頻繁項目集求解方法準(zhǔn)確率為45.17%。提出的二分搜索算法的全局頻繁項目集求解方法，較快速挖掘的全局頻繁項目集求解方法和Apriori 算法的全局頻繁項目集求解方法具有更高的準(zhǔn)確率。

4 結(jié)語

本文提出了二分搜索算法在全局頻繁項目集求解中的應(yīng)用。依托全局頻繁項目集的確定，候選項目集的生成，優(yōu)化了全局頻繁項目集求解體系；根據(jù)全局頻繁項目集的更新計算，完成了二分搜索算法在全局頻繁項目集求解中的應(yīng)用，實驗數(shù)據(jù)表明，提出的全局頻繁項目集求解方法具有較高的有效性，希望本文的研究能夠為全局頻繁項目集求解方法提供理論支撐。