黃瑜

摘 要： 針對大型數(shù)據(jù)庫在進(jìn)行關(guān)聯(lián)挖掘過程中，挖掘準(zhǔn)確度低、效率差的問題，提出并設(shè)計了基于貝葉斯信息標(biāo)準(zhǔn)BIC評分函數(shù)的大型數(shù)據(jù)庫關(guān)聯(lián)挖掘算法。在對大型數(shù)據(jù)庫關(guān)聯(lián)數(shù)據(jù)獲取基礎(chǔ)上，采用貝葉斯信息標(biāo)準(zhǔn)BIC評分函數(shù)對數(shù)據(jù)進(jìn)行預(yù)處理，并給出預(yù)處理流程，建立挖掘所需的新關(guān)聯(lián)規(guī)則，根據(jù)其關(guān)聯(lián)規(guī)則實現(xiàn)大型數(shù)據(jù)庫的關(guān)聯(lián)挖掘。實驗結(jié)果表明，采用改進(jìn)挖掘算法，其挖掘準(zhǔn)確率達(dá)到了91.3%，相比傳統(tǒng)挖掘算法提高了約35.9%，具有一定的優(yōu)勢。

關(guān)鍵詞： 大型數(shù)據(jù)庫； 關(guān)聯(lián)規(guī)則； 挖掘算法； 關(guān)聯(lián)挖掘； 評分函數(shù)； 數(shù)據(jù)預(yù)處理

中圖分類號： TN919.25?34； TP301.6 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2018）20?0045?04

Abstract： In allusion to the problems of low mining accuracy and poor mining efficiency during the association mining process of the large?scale database， an association mining algorithm based on the Bayesian information standard BIC scoring function is proposed and designed for the large?scale database. On the basis of association data acquisition of the large?scale database， the data is preprocessed by using the Bayesian information standard BIC scoring function， the preprocessing flow is given， new association rules needed in mining are established， and the association mining of the large?scale database is realized according to the association rules. The experimental results show that the improved mining algorithm achieves a mining accuracy of 91.3%， which improves approximately 35.9% in comparison with the traditional mining algorithm and has a certain advantage.

Keywords： large?scale database； association rule； mining algorithm； association mining； scoring function； data preprocessing

0 引 言

當(dāng)今，數(shù)據(jù)容量規(guī)模的擴大，導(dǎo)致數(shù)據(jù)規(guī)模擴大、復(fù)雜化，人們無法快速找到感興趣的數(shù)據(jù)，對于此類爆炸式增長的數(shù)據(jù)，人們進(jìn)行數(shù)據(jù)處理以及數(shù)據(jù)分析的能力非常有限。因此，數(shù)據(jù)挖掘技術(shù)得到了廣泛重視及深入研究，逐步成為重要研究領(lǐng)域[1?2]。

數(shù)據(jù)挖掘即從大量不完全、有噪聲、模糊隨機數(shù)據(jù)中獲取包含有人們事先不知道又潛在有用信息及知識處理進(jìn)程[3]。該方法之所以被稱為未來信息處理重要技術(shù)之一，關(guān)鍵是它以一種全新概念轉(zhuǎn)變著人類使用數(shù)據(jù)的模式。但數(shù)據(jù)庫技術(shù)作為一種最基礎(chǔ)的信息儲存及管理形式，依舊以聯(lián)機事務(wù)處理為重點使用，對決策、解析、預(yù)測等高級性能的支持技術(shù)較少。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的一個重要分支，廣泛應(yīng)用在多個領(lǐng)域，如數(shù)據(jù)分析、數(shù)據(jù)庫設(shè)計、倉儲規(guī)劃、網(wǎng)絡(luò)故障解析等[4?5]，導(dǎo)致已有的數(shù)據(jù)庫規(guī)模迅速擴大，對大規(guī)模數(shù)據(jù)庫關(guān)聯(lián)規(guī)則挖掘的研究成為了該領(lǐng)域具備關(guān)鍵理論價值及現(xiàn)實意義事件。對此，提出并設(shè)計了基于貝葉斯信息標(biāo)準(zhǔn)BIC評分函數(shù)的大型數(shù)據(jù)庫關(guān)聯(lián)挖掘算法。

1 數(shù)據(jù)庫關(guān)聯(lián)數(shù)據(jù)分析

在對大型數(shù)據(jù)庫進(jìn)行關(guān)聯(lián)挖掘過程中，其數(shù)據(jù)庫的獲取及數(shù)據(jù)預(yù)處理是影響關(guān)聯(lián)挖掘的關(guān)鍵步驟。對此，在數(shù)據(jù)庫獲取后，對數(shù)據(jù)進(jìn)行預(yù)處理過程中，采用自適應(yīng)函數(shù)對其進(jìn)行分析，提高大型數(shù)據(jù)庫數(shù)據(jù)性能，為進(jìn)行關(guān)聯(lián)挖掘提供基礎(chǔ)依據(jù)。

1.1 數(shù)據(jù)庫獲取分析

數(shù)據(jù)庫還原模塊在運行時，首先將運行環(huán)境初始化，包括環(huán)境變量初始化、配置文件初始化、公共變量和數(shù)據(jù)緩存初始化[6]。然后進(jìn)行網(wǎng)絡(luò)設(shè)備初始化，最后創(chuàng)建數(shù)據(jù)庫還原模塊的工作線程，包括數(shù)據(jù)流還原線程、攔截數(shù)據(jù)包線程和數(shù)據(jù)包處理分析調(diào)度線程[7]。攔截數(shù)據(jù)包線程的主要功能是攔截網(wǎng)上的數(shù)據(jù)包，數(shù)據(jù)流還原線程的主要功能是還原網(wǎng)絡(luò)數(shù)據(jù)包，并將還原結(jié)果存入數(shù)據(jù)庫還原模塊的數(shù)據(jù)庫中。數(shù)據(jù)包處理分析調(diào)度線程主要對不同的數(shù)據(jù)包進(jìn)行調(diào)度。

數(shù)據(jù)獲取中主要獲取內(nèi)容是相關(guān)數(shù)據(jù)來源記錄信息、具體數(shù)據(jù)特征、獲取數(shù)據(jù)所需時間等。實現(xiàn)這一目標(biāo)的方式有很多種，其主要依據(jù)是借助各種途徑，對數(shù)據(jù)進(jìn)行采集。

1.2 數(shù)據(jù)庫關(guān)聯(lián)數(shù)據(jù)預(yù)處理

數(shù)據(jù)庫數(shù)據(jù)量較大，若要增加挖掘效率，實現(xiàn)挖掘的目的，要對數(shù)據(jù)提前進(jìn)行一定處理，即預(yù)處理，重點包括數(shù)據(jù)采集、整理、選擇、轉(zhuǎn)存等流程。在數(shù)據(jù)整理方面，重點是對具有冗余特征的數(shù)據(jù)刪除、對類似數(shù)據(jù)項進(jìn)行合并、篩查修正數(shù)據(jù)信息等[7]。在此之后進(jìn)行集體的篩選處理，把來自不同源點的數(shù)據(jù)匯集起來，對數(shù)據(jù)進(jìn)行篩查，找出適合搜尋需求的數(shù)據(jù)種類[8]。最后對數(shù)據(jù)進(jìn)行轉(zhuǎn)換，把最終得到的數(shù)據(jù)對應(yīng)地進(jìn)行適應(yīng)度函數(shù)調(diào)整、轉(zhuǎn)變成更適合使用的格式，方便進(jìn)行關(guān)聯(lián)挖掘解析。

在進(jìn)行關(guān)聯(lián)數(shù)據(jù)預(yù)處理過程中，把網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)作為最優(yōu)化問題，對挖掘目標(biāo)進(jìn)行搜索評分。對此采用較為常用的評分函數(shù)有貝葉斯信息標(biāo)準(zhǔn)BIC評分函數(shù)，對數(shù)據(jù)進(jìn)行預(yù)處理。該評分函數(shù)具備以下幾個優(yōu)點[9]：一是不依附先驗概率，不對先驗概率分布情況進(jìn)行估計；二是在樣本集合過大時，能夠近似地對后驗概率進(jìn)行驗證；三是在沒有規(guī)定多項式分布及Dirichlet先驗概率情況下，和MDL測度取負(fù)號的結(jié)果近似相等。因此，在本算法中使用BIC評分函數(shù)作為適應(yīng)度函數(shù)，并認(rèn)為BIC的得分越高，適應(yīng)度越好，為后續(xù)的關(guān)聯(lián)挖掘提供基礎(chǔ)。BIC評分函數(shù)如下：

在數(shù)據(jù)關(guān)聯(lián)挖掘中，若每個部分均要給出相應(yīng)的挖掘規(guī)則、頻繁集等，則需對選取范圍進(jìn)行確認(rèn)，并建立對應(yīng)向量，采用普通的安全多方循環(huán)協(xié)議進(jìn)行集合的合并。為了增加預(yù)處理的安全性能，采用基于可交換密鑰順序方法進(jìn)行安全加密處理。在共享的狀況下，能夠采用其余方式進(jìn)行可交換加密[10]。數(shù)據(jù)庫預(yù)處理流程如圖1所示，數(shù)據(jù)庫關(guān)聯(lián)挖掘系統(tǒng)結(jié)構(gòu)圖如圖2所示。

2 關(guān)聯(lián)挖掘算法優(yōu)化研究

在進(jìn)行大數(shù)據(jù)關(guān)聯(lián)挖掘算法優(yōu)化過程中，首先對數(shù)據(jù)進(jìn)行一次掃描，搜出整體的頻繁1_項集；然后對搜出的頻繁1_項集進(jìn)行組合，依次產(chǎn)生頻繁2_項集、頻繁3_項集等。

關(guān)聯(lián)挖掘算法優(yōu)化流程圖如圖3所示。

在上述偽代碼顯示的過程中，采用“動態(tài)系統(tǒng)擴散”的方式從數(shù)據(jù)庫中形成一個基集，用基集替換初始數(shù)據(jù)集當(dāng)作挖掘目標(biāo)，計算支持度函數(shù)，獲取各項集支持度，搜出全部支持度大于支持度閾值的頻繁項集，形成全部的關(guān)聯(lián)規(guī)則。

3 系統(tǒng)性能測試

3.1 系統(tǒng)性能評估方法

實驗采用系統(tǒng)仿真的方式對算法有效性進(jìn)行驗證，實驗環(huán)境如下。

系統(tǒng)硬件采用4 核1.66 GHz的CPU；RAM 10 GB。系統(tǒng)操作系統(tǒng)采用Windows 2010 Server；源數(shù)據(jù)庫使用默認(rèn).dat二進(jìn)制的數(shù)據(jù)；輸出文件為.txt文本文件；以VC++ 6.0 sp6 編制為實驗程序；實驗期間斷開網(wǎng)絡(luò)連接，防止出現(xiàn)誤差；每一次實驗后對系統(tǒng)內(nèi)存進(jìn)行整理，讓每一次程序運行環(huán)境盡量統(tǒng)一。

3.2 結(jié)果分析

準(zhǔn)確率對比結(jié)果如圖4所示。

由圖4可知，采用傳統(tǒng)挖掘算法進(jìn)行數(shù)據(jù)庫挖掘時，在時間不定的情況下，其挖掘準(zhǔn)確率隨著時間的增加出現(xiàn)下降的趨勢，準(zhǔn)確率最高達(dá)到73.4%，最低為50.8%，平均準(zhǔn)確率約為56.4%；采用改進(jìn)方法時，隨著時間的增加，其挖掘準(zhǔn)確率具有上升趨勢，準(zhǔn)確率最高達(dá)到99.4%，最低為80.1%，平均值約為91.3%，相比傳統(tǒng)挖掘算法提高了約34.9%，具有一定的優(yōu)勢。

4 結(jié) 論

針對傳統(tǒng)挖掘算法一直存在挖掘準(zhǔn)確率低、效率差的問題，提出基于貝葉斯信息標(biāo)準(zhǔn)BIC評分函數(shù)的大型數(shù)據(jù)庫關(guān)聯(lián)挖掘算法。實驗結(jié)果表明，采用改進(jìn)算法相比傳統(tǒng)挖掘算法準(zhǔn)確率提高了約34.9%，具有顯著優(yōu)勢。

參考文獻(xiàn)

[1] 張忠林，田苗鳳，劉宗成.大數(shù)據(jù)環(huán)境下關(guān)聯(lián)規(guī)則并行分層挖掘算法研究[J].計算機科學(xué)，2016，43（1）：286?289.

ZHANG Zhonglin， TIAN Miaofeng， LIU Zongcheng. Parallel hierarchical association rule mining in big data environment [J]. Computer science， 2016， 43（1）： 286?289.

[2] 郝海濤，馬元元.應(yīng)用Aprion算法實現(xiàn)大規(guī)模數(shù)據(jù)庫關(guān)聯(lián)規(guī)則挖掘的技術(shù)研究[J].現(xiàn)代電子技術(shù)，2016，39（7）：124?126.

HAO Haitao， MA Yuanyuan. Using Aprion algorithm to implement association rule mining technology of large?scale database [J]. Modern electronics technique， 2016， 39（7）： 124?126.

[3] 劉平，王曉，劉春.小差異化圖像數(shù)據(jù)庫中的特定特征挖掘方法設(shè)計[J].沈陽工業(yè)大學(xué)學(xué)報，2017，39（5）：562?566.

LIU Ping， WANG Xiao， LIU Chun. Design of specific feature mining method in image database with small alienation [J]. Journal of Shenyang University of Technology， 2017， 39（5）： 562?566.

[4] 楊小琴.大型數(shù)據(jù)庫中的并行高效檢測方法仿真分析[J].計算機仿真，2016，33（7）：392?394.

YANG Xiaoqin. Simulation analysis of parallel and efficient detection method in large database [J]. Computer simulation， 2016， 33（7）： 392?394.

[5] 趙學(xué)健，孫知信，袁源.基于預(yù)判篩選的高效關(guān)聯(lián)規(guī)則挖掘算法[J].電子與信息學(xué)報，2016，38（7）：1654?1659.

ZHAO Xuejian， SUN Zhixin， YUAN Yuan. An efficient association rule mining algorithm based on prejudging and screening [J]. Journal of electronics & information technology， 2016， 38（7）： 1654?1659.

[6] 徐春，李廣原，王玄，等.一種基于倒排索引樹的增量更新關(guān)聯(lián)挖掘算法[J].計算機工程與科學(xué)，2016，38（5）：1039?1045.

XU Chun， LI Guangyuan， WANG Xuan， et al. An incremental updating association rule mining algorithm based on inverted index tree [J]. Computer engineering and science， 2016， 38（5）： 1039?1045.

[7] 朱益立，鄧珍榮，謝攀.基于有向無環(huán)圖的頻繁模式挖掘算法[J].計算機工程與設(shè)計，2017，38（5）：1237?1241.

ZHU Yili， DENG Zhenrong， XIE Pan. Mining frequent itemsets algorithm based on directed acycline graph [J]. Computer engineering and design， 2017， 38（5）： 1237?1241.

[8] 張亞玲，王婷，王尚平.增量式隱私保護(hù)頻繁模式挖掘算法[J].計算機應(yīng)用，2018，38（1）：176?181.

ZHANG Yaling， WANG Ting， WANG Shangping. Incremental frequent pattern mining algorithm for privacy?preserving [J]. Journal of computer applications， 2018， 38（1）： 176?181.

[9] 林基明，班文嬌，王俊義，等.基于并行遺傳?最大最小蟻群算法的分布式數(shù)據(jù)庫查詢優(yōu)化[J].計算機應(yīng)用，2016，36（3）：675?680.

LIN Jiming， BAN Wenjiao， WANG Junyi， et al. Query optimization for distributed database based on parallel genetic algorithm and max?min ant system [J]. Journal of computer applications， 2016， 36（3）： 675?680.

[10] 林凌，許然.基于圖像特征細(xì)化的海量數(shù)據(jù)挖掘系統(tǒng)設(shè)計與實現(xiàn)[J].現(xiàn)代電子技術(shù)，2016，39（24）：113?115.

LIN Ling， XU Ran. Design and implementation of mass data mining system based on image feature refinement [J]. Modern electronics technique， 2016， 39（24）： 113?115.