大型數據庫的關聯挖掘算法設計

黃瑜

摘 要： 針對大型數據庫在進行關聯挖掘過程中，挖掘準確度低、效率差的問題，提出并設計了基于貝葉斯信息標準BIC評分函數的大型數據庫關聯挖掘算法。在對大型數據庫關聯數據獲取基礎上，采用貝葉斯信息標準BIC評分函數對數據進行預處理，并給出預處理流程，建立挖掘所需的新關聯規則，根據其關聯規則實現大型數據庫的關聯挖掘。實驗結果表明，采用改進挖掘算法，其挖掘準確率達到了91.3%，相比傳統挖掘算法提高了約35.9%，具有一定的優勢。

關鍵詞： 大型數據庫； 關聯規則； 挖掘算法； 關聯挖掘； 評分函數； 數據預處理

中圖分類號： TN919.25?34； TP301.6 文獻標識碼： 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 引 言

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

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

1 數據庫關聯數據分析

在對大型數據庫進行關聯挖掘過程中，其數據庫的獲取及數據預處理是影響關聯挖掘的關鍵步驟。對此，在數據庫獲取后，對數據進行預處理過程中，采用自適應函數對其進行分析，提高大型數據庫數據性能，為進行關聯挖掘提供基礎依據。

1.1 數據庫獲取分析

數據庫還原模塊在運行時，首先將運行環境初始化，包括環境變量初始化、配置文件初始化、公共變量和數據緩存初始化[6]。然后進行網絡設備初始化，最后創建數據庫還原模塊的工作線程，包括數據流還原線程、攔截數據包線程和數據包處理分析調度線程[7]。攔截數據包線程的主要功能是攔截網上的數據包，數據流還原線程的主要功能是還原網絡數據包，并將還原結果存入數據庫還原模塊的數據庫中。數據包處理分析調度線程主要對不同的數據包進行調度。

數據獲取中主要獲取內容是相關數據來源記錄信息、具體數據特征、獲取數據所需時間等。實現這一目標的方式有很多種，其主要依據是借助各種途徑，對數據進行采集。

1.2 數據庫關聯數據預處理

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

在進行關聯數據預處理過程中，把網絡結構學習作為最優化問題，對挖掘目標進行搜索評分。對此采用較為常用的評分函數有貝葉斯信息標準BIC評分函數，對數據進行預處理。該評分函數具備以下幾個優點[9]：一是不依附先驗概率，不對先驗概率分布情況進行估計；二是在樣本集合過大時，能夠近似地對后驗概率進行驗證；三是在沒有規定多項式分布及Dirichlet先驗概率情況下，和MDL測度取負號的結果近似相等。因此，在本算法中使用BIC評分函數作為適應度函數，并認為BIC的得分越高，適應度越好，為后續的關聯挖掘提供基礎。BIC評分函數如下：

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

2 關聯挖掘算法優化研究

在進行大數據關聯挖掘算法優化過程中，首先對數據進行一次掃描，搜出整體的頻繁1_項集；然后對搜出的頻繁1_項集進行組合，依次產生頻繁2_項集、頻繁3_項集等。

關聯挖掘算法優化流程圖如圖3所示。

在上述偽代碼顯示的過程中，采用“動態系統擴散”的方式從數據庫中形成一個基集，用基集替換初始數據集當作挖掘目標，計算支持度函數，獲取各項集支持度，搜出全部支持度大于支持度閾值的頻繁項集，形成全部的關聯規則。

3 系統性能測試

3.1 系統性能評估方法

實驗采用系統仿真的方式對算法有效性進行驗證，實驗環境如下。

系統硬件采用4 核1.66 GHz的CPU；RAM 10 GB。系統操作系統采用Windows 2010 Server；源數據庫使用默認.dat二進制的數據；輸出文件為.txt文本文件；以VC++ 6.0 sp6 編制為實驗程序；實驗期間斷開網絡連接，防止出現誤差；每一次實驗后對系統內存進行整理，讓每一次程序運行環境盡量統一。

3.2 結果分析

準確率對比結果如圖4所示。

由圖4可知，采用傳統挖掘算法進行數據庫挖掘時，在時間不定的情況下，其挖掘準確率隨著時間的增加出現下降的趨勢，準確率最高達到73.4%，最低為50.8%，平均準確率約為56.4%；采用改進方法時，隨著時間的增加，其挖掘準確率具有上升趨勢，準確率最高達到99.4%，最低為80.1%，平均值約為91.3%，相比傳統挖掘算法提高了約34.9%，具有一定的優勢。

4 結 論

針對傳統挖掘算法一直存在挖掘準確率低、效率差的問題，提出基于貝葉斯信息標準BIC評分函數的大型數據庫關聯挖掘算法。實驗結果表明，采用改進算法相比傳統挖掘算法準確率提高了約34.9%，具有顯著優勢。

參考文獻

[1] 張忠林，田苗鳳，劉宗成.大數據環境下關聯規則并行分層挖掘算法研究[J].計算機科學，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] 郝海濤，馬元元.應用Aprion算法實現大規模數據庫關聯規則挖掘的技術研究[J].現代電子技術，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] 劉平，王曉，劉春.小差異化圖像數據庫中的特定特征挖掘方法設計[J].沈陽工業大學學報，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] 楊小琴.大型數據庫中的并行高效檢測方法仿真分析[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] 趙學健，孫知信，袁源.基于預判篩選的高效關聯規則挖掘算法[J].電子與信息學報，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] 徐春，李廣原，王玄，等.一種基于倒排索引樹的增量更新關聯挖掘算法[J].計算機工程與科學，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] 朱益立，鄧珍榮，謝攀.基于有向無環圖的頻繁模式挖掘算法[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] 張亞玲，王婷，王尚平.增量式隱私保護頻繁模式挖掘算法[J].計算機應用，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] 林基明，班文嬌，王俊義，等.基于并行遺傳?最大最小蟻群算法的分布式數據庫查詢優化[J].計算機應用，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] 林凌，許然.基于圖像特征細化的海量數據挖掘系統設計與實現[J].現代電子技術，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.