曾俊義

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

0 引言

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

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

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

1.1 確定全局頻繁項(xiàng)目集

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

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

圖1 全局頻繁項(xiàng)目集確定過(guò)程示意圖

1.2 候選項(xiàng)目集的生成

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

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

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

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

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

2 全局頻繁項(xiàng)目集的更新計(jì)算

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

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

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

3 實(shí)例分析

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

3.1 實(shí)驗(yàn)準(zhǔn)備

實(shí)驗(yàn)中利用已過(guò)往的全局頻繁項(xiàng)目作為實(shí)驗(yàn)對(duì)象，進(jìn)行仿真實(shí)驗(yàn)，采用已過(guò)往的全局頻繁項(xiàng)目作為實(shí)驗(yàn)對(duì)象，是因?yàn)樵谙嗤h(huán)境下進(jìn)行求解可以精準(zhǔn)地對(duì)比出求解的準(zhǔn)確率以及求解速率，選取5 個(gè)已過(guò)往的全局頻繁項(xiàng)目，對(duì)全局頻繁項(xiàng)目進(jìn)行全局頻繁項(xiàng)目集求解的準(zhǔn)確率以及求解速率進(jìn)行驗(yàn)證。

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

3.2 實(shí)驗(yàn)過(guò)程

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

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

3.3 實(shí)驗(yàn)結(jié)果分析

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

表1 實(shí)驗(yàn)結(jié)果對(duì)比表

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

表2 實(shí)驗(yàn)結(jié)果對(duì)比表

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

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

4 結(jié)語(yǔ)

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