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

曾俊義

（惠州城市職業學院民生學院，惠州516025）

0 引言

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

1 優化求解的體系

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

1.1 確定全局頻繁項目集

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

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

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

1.2 候選項目集的生成

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

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

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

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

式中，UL 代表當前數據狀態；P 代表數據庫類型。依托頻繁項目k，全局隸屬度函數x 的確定，完成了候選項目集的生成，基于全局頻繁項目集的確定，優化了全局頻繁項目求解體系。

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

二分搜索算法是一種基于數學計算的系統數據求解方法，在進行全局頻繁項目集的計算中，優化傳統，求解體系，針對靜態數據、動態數據能夠實現實時更新計算，對于數據進行自動獲取，自我識別，生成候選項目集，進行求解。

在更新計算過程中，與傳統計算不同首先要確定全局頻繁項目的計算節點，根據動態節點，利用計算機模擬計算技術，對節點的運動進行模擬計算，并用真實值與模擬值做差，將差值控制在0.04%以內，則說明模擬計算值接近于真實值[7]。可用于動態數據節點的計算，應用于全局頻繁，項目集的更新計算中。設動態節點方程可用公式（3）表示[8]：

基于動態節點方程的確定，以及平均更新計算表達式σ的求解，實現了全局頻繁項目集的更新計算，基于二分搜索算法優化求解體系，實現了二分搜索算法在全局頻繁項目集求解中的應用。

3 實例分析

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

3.1 實驗準備

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

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

3.2 實驗過程

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

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

3.3 實驗結果分析

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

表1 實驗結果對比表

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

表2 實驗結果對比表

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

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

4 結語

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