大型數(shù)據(jù)庫(kù)的關(guān)聯(lián)挖掘算法設(shè)計(jì)

黃瑜

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

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

中圖分類號(hào)： TN919.25?34； TP301.6 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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ī)模的擴(kuò)大，導(dǎo)致數(shù)據(jù)規(guī)模擴(kuò)大、復(fù)雜化，人們無法快速找到感興趣的數(shù)據(jù)，對(duì)于此類爆炸式增長(zhǎng)的數(shù)據(jù)，人們進(jìn)行數(shù)據(jù)處理以及數(shù)據(jù)分析的能力非常有限。因此，數(shù)據(jù)挖掘技術(shù)得到了廣泛重視及深入研究，逐步成為重要研究領(lǐng)域[1?2]。

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

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

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

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

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

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

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

數(shù)據(jù)庫(kù)數(shù)據(jù)量較大，若要增加挖掘效率，實(shí)現(xiàn)挖掘的目的，要對(duì)數(shù)據(jù)提前進(jìn)行一定處理，即預(yù)處理，重點(diǎn)包括數(shù)據(jù)采集、整理、選擇、轉(zhuǎn)存等流程。在數(shù)據(jù)整理方面，重點(diǎn)是對(duì)具有冗余特征的數(shù)據(jù)刪除、對(duì)類似數(shù)據(jù)項(xiàng)進(jìn)行合并、篩查修正數(shù)據(jù)信息等[7]。在此之后進(jìn)行集體的篩選處理，把來自不同源點(diǎn)的數(shù)據(jù)匯集起來，對(duì)數(shù)據(jù)進(jìn)行篩查，找出適合搜尋需求的數(shù)據(jù)種類[8]。最后對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)換，把最終得到的數(shù)據(jù)對(duì)應(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)化問題，對(duì)挖掘目標(biāo)進(jìn)行搜索評(píng)分。對(duì)此采用較為常用的評(píng)分函數(shù)有貝葉斯信息標(biāo)準(zhǔn)BIC評(píng)分函數(shù)，對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。該評(píng)分函數(shù)具備以下幾個(gè)優(yōu)點(diǎn)[9]：一是不依附先驗(yàn)概率，不對(duì)先驗(yàn)概率分布情況進(jìn)行估計(jì)；二是在樣本集合過大時(shí)，能夠近似地對(duì)后驗(yàn)概率進(jìn)行驗(yàn)證；三是在沒有規(guī)定多項(xiàng)式分布及Dirichlet先驗(yàn)概率情況下，和MDL測(cè)度取負(fù)號(hào)的結(jié)果近似相等。因此，在本算法中使用BIC評(píng)分函數(shù)作為適應(yīng)度函數(shù)，并認(rèn)為BIC的得分越高，適應(yīng)度越好，為后續(xù)的關(guān)聯(lián)挖掘提供基礎(chǔ)。BIC評(píng)分函數(shù)如下：

在數(shù)據(jù)關(guān)聯(lián)挖掘中，若每個(gè)部分均要給出相應(yīng)的挖掘規(guī)則、頻繁集等，則需對(duì)選取范圍進(jìn)行確認(rèn)，并建立對(duì)應(yīng)向量，采用普通的安全多方循環(huán)協(xié)議進(jìn)行集合的合并。為了增加預(yù)處理的安全性能，采用基于可交換密鑰順序方法進(jìn)行安全加密處理。在共享的狀況下，能夠采用其余方式進(jìn)行可交換加密[10]。數(shù)據(jù)庫(kù)預(yù)處理流程如圖1所示，數(shù)據(jù)庫(kù)關(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)化過程中，首先對(duì)數(shù)據(jù)進(jìn)行一次掃描，搜出整體的頻繁1_項(xiàng)集；然后對(duì)搜出的頻繁1_項(xiàng)集進(jìn)行組合，依次產(chǎn)生頻繁2_項(xiàng)集、頻繁3_項(xiàng)集等。

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

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

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

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

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

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

3.2 結(jié)果分析

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

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

4 結(jié) 論

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

參考文獻(xiàn)

[1] 張忠林，田苗鳳，劉宗成.大數(shù)據(jù)環(huán)境下關(guān)聯(lián)規(guī)則并行分層挖掘算法研究[J].計(jì)算機(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算法實(shí)現(xiàn)大規(guī)模數(shù)據(jù)庫(kù)關(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ù)庫(kù)中的特定特征挖掘方法設(shè)計(jì)[J].沈陽工業(yè)大學(xué)學(xué)報(bào)，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ù)庫(kù)中的并行高效檢測(cè)方法仿真分析[J].計(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é)報(bào)，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].計(jì)算機(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].計(jì)算機(jī)工程與設(shè)計(jì)，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].計(jì)算機(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ù)庫(kù)查詢優(yōu)化[J].計(jì)算機(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è)計(jì)與實(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.