陳翠娟

(福州理工學(xué)院，福建 福州 350506)

計(jì)算機(jī)硬件技術(shù)的發(fā)展為軟件應(yīng)用創(chuàng)造了良好條件，現(xiàn)代信息社會(huì)各領(lǐng)域工作離不開(kāi)軟件的應(yīng)用，軟件應(yīng)用為各行業(yè)信息整理與快速獲取創(chuàng)造便利[1]。計(jì)算機(jī)軟件應(yīng)用過(guò)程中隨時(shí)產(chǎn)生大規(guī)模的應(yīng)用數(shù)據(jù)、日志信息，反映了軟件運(yùn)行的一定規(guī)律。對(duì)于企業(yè)而言，計(jì)算機(jī)軟件可能蘊(yùn)藏海量有價(jià)值的財(cái)務(wù)信息、管理運(yùn)營(yíng)數(shù)據(jù)、人力資源管理信息，對(duì)其進(jìn)行有效挖掘才能更好地利用這些軟件大數(shù)據(jù)，提取有價(jià)值信息為企業(yè)運(yùn)營(yíng)創(chuàng)造利益[2]。本研究利用關(guān)聯(lián)分析原理充分挖掘計(jì)算機(jī)軟件內(nèi)部蘊(yùn)含的大數(shù)據(jù)，提出了基于改進(jìn)Apriori算法挖掘計(jì)算機(jī)軟件事務(wù)數(shù)據(jù)庫(kù)的關(guān)聯(lián)規(guī)則。

1 基于Apriori算法的計(jì)算機(jī)軟件數(shù)據(jù)挖掘方法

1.1 Apriori算法基本原理

Apriori算法是以迭代的方式獲取數(shù)據(jù)候選項(xiàng)集，利用剪枝操作選取候選項(xiàng)集中的頻繁項(xiàng)集，在此基礎(chǔ)上不斷獲得候選項(xiàng)集、生成頻繁項(xiàng)集，當(dāng)出現(xiàn)頻繁項(xiàng)集量最大時(shí)可以終止迭代[3]。在Apriori算法中存在事務(wù)集合{G1,G2,…,Gm}，也稱(chēng)為事務(wù)數(shù)據(jù)庫(kù)，其中由差異項(xiàng)或者差異屬性組成的集合可以表示為{I1,I2,…,In}。Apriori算法的項(xiàng)目集表示為E，包括E的事務(wù)集與事務(wù)總量的比值E?I稱(chēng)為支持度，頻繁項(xiàng)集由此可以定義為“支持度不小于支持度閾值的項(xiàng)目集”，其余項(xiàng)目集則屬于非頻繁項(xiàng)集[4]。公式(1)為支持度計(jì)算公式，支持度表示數(shù)據(jù)庫(kù)同時(shí)包含A和B事務(wù)的百分比：

supp(A?B)=P(AB)

(1)

公式(1)解釋為在事務(wù)數(shù)據(jù)庫(kù)中，數(shù)據(jù)庫(kù)包含A與包含B的比值情況。

基于Apriori算法對(duì)計(jì)算機(jī)軟件數(shù)據(jù)進(jìn)行關(guān)聯(lián)分析的過(guò)程基本分為兩個(gè)步驟：一是找到軟件事務(wù)數(shù)據(jù)庫(kù)的全部頻繁項(xiàng)集，定義為L(zhǎng)；二是在L中獲得軟件數(shù)據(jù)之間的潛在關(guān)聯(lián)規(guī)則。

Apriori算法的頻繁挖掘特征使其對(duì)內(nèi)存有較高的要求，經(jīng)典的Apriori算法挖掘關(guān)聯(lián)規(guī)則過(guò)程中效率不高、消耗內(nèi)存較大，成為普遍存在的問(wèn)題[5]。上述兩個(gè)步驟描述中，前者是Apriori算法性能的關(guān)鍵保障，頻繁項(xiàng)集挖掘復(fù)雜、計(jì)算量大將導(dǎo)致算法迭代用時(shí)增加，最終挖掘結(jié)果的效率與精準(zhǔn)度難以保障；而后者相對(duì)前者的實(shí)現(xiàn)方法更為簡(jiǎn)單，并且比較依賴(lài)上一步驟獲得的結(jié)果，所以，該研究在經(jīng)典Apriori算法基礎(chǔ)上著重優(yōu)化“計(jì)算機(jī)軟件數(shù)據(jù)頻繁項(xiàng)集選取”這一步驟，提升整個(gè)算法挖掘關(guān)聯(lián)規(guī)則的精準(zhǔn)度，以獲得計(jì)算機(jī)軟件數(shù)據(jù)之間的強(qiáng)關(guān)聯(lián)規(guī)則。

通過(guò)兩種策略降低Apriori算法復(fù)雜度、減少掃描事務(wù)數(shù)據(jù)庫(kù)的頻次。首先構(gòu)建雙重支持度閾值規(guī)則，作為基于支持度篩選頻繁項(xiàng)集的條件；其次重新組建原始事務(wù)數(shù)據(jù)庫(kù)結(jié)構(gòu)，減少連接與剪枝工作量[6]。這兩種改進(jìn)策略一方面可以提高頻繁項(xiàng)集選取的冗余程度，精準(zhǔn)獲得計(jì)算機(jī)軟件數(shù)據(jù)挖掘的強(qiáng)關(guān)聯(lián)規(guī)則；另一方面節(jié)省Apriori 算法在頻繁項(xiàng)集挖掘部分的計(jì)算量，減少算法的內(nèi)存占用量，進(jìn)而提升計(jì)算機(jī)軟件數(shù)據(jù)挖掘的效率。

1.2 基于雙重支持度閾值的頻繁項(xiàng)集選取

事務(wù)數(shù)據(jù)庫(kù)生成候選項(xiàng)集之后需要在其中挖掘出強(qiáng)關(guān)聯(lián)的頻繁項(xiàng)集，一般Apriori算法僅采用一種支持度閾值約束頻繁項(xiàng)集的產(chǎn)生，導(dǎo)致有效頻繁項(xiàng)集的效率較低、準(zhǔn)確度不高。雙重支持度閾值規(guī)則是針對(duì)非頻繁項(xiàng)集與頻繁項(xiàng)集選取步驟而制定的，可以在短時(shí)間內(nèi)去除興趣度不高的非頻繁項(xiàng)集。

在數(shù)據(jù)項(xiàng)集E={e1,e2,…,en}中，為隨機(jī)k-項(xiàng)集A定義兩個(gè)支持度閾值，即非頻繁項(xiàng)集閾值和頻繁項(xiàng)集閾值，也稱(chēng)為兩種項(xiàng)集的最小支持度，分別用H1、H2表示，且H2大于H1，二者均在0之上。通過(guò)以上規(guī)則判斷當(dāng)前項(xiàng)集分類(lèi)型[7]：(1)若項(xiàng)集A為頻繁項(xiàng)集，此時(shí)supp(A)≥H2；(2)若項(xiàng)集A為非頻繁項(xiàng)集，此時(shí)supp(A)

1.3 基于映射規(guī)則重組事務(wù)數(shù)據(jù)庫(kù)結(jié)構(gòu)

為了進(jìn)一步減少事務(wù)數(shù)據(jù)庫(kù)頻繁項(xiàng)集選取工作量，對(duì)事務(wù)數(shù)據(jù)庫(kù)結(jié)構(gòu)進(jìn)行重構(gòu)，以省略不必要的連接與剪枝[9]。重構(gòu)數(shù)據(jù)庫(kù)的具體方法是基于映射結(jié)構(gòu)存儲(chǔ)計(jì)算機(jī)軟件數(shù)據(jù)庫(kù)的事務(wù)，達(dá)到壓縮事務(wù)數(shù)據(jù)庫(kù)的目的?；谟成涞氖聞?wù)數(shù)據(jù)存儲(chǔ)原理如下：定義項(xiàng)目集合為E={e1,e2,…,en}，R表示其中的一個(gè)事務(wù)，圖1為計(jì)算機(jī)軟件數(shù)據(jù)事務(wù)庫(kù)映射結(jié)構(gòu)圖。

圖1 計(jì)算機(jī)軟件數(shù)據(jù)事務(wù)庫(kù)映射結(jié)構(gòu)圖

圖1中一維數(shù)組是指Ek與Es的對(duì)應(yīng)值構(gòu)成的數(shù)組，其中dij計(jì)算方法如下：

dij={0,Ei?Rj

1,Ei∈Rj

(2)

其中，事務(wù)的數(shù)量采用m表示，i的取值在1～∣E∣之間，j的取值在1～m之間。

圖1中計(jì)算機(jī)軟件事務(wù)數(shù)據(jù)庫(kù)的項(xiàng)集數(shù)量采用sj的值來(lái)描述，計(jì)算方法如公式(3)所示：

(3)

公式中n表示項(xiàng)集的數(shù)量。

基于上述映射原理重新組建計(jì)算機(jī)軟件數(shù)據(jù)事務(wù)庫(kù)，壓縮數(shù)據(jù)庫(kù)的規(guī)模，同時(shí)基于雙重支持度閾值對(duì)候選項(xiàng)集進(jìn)行連接與剪枝，當(dāng)不生成頻繁項(xiàng)集時(shí)終止迭代，以選取強(qiáng)關(guān)聯(lián)的計(jì)算機(jī)軟件數(shù)據(jù)頻繁項(xiàng)集[10]。

2 實(shí)驗(yàn)分析

以某企業(yè)的人力資源管理軟件作為數(shù)據(jù)挖掘?qū)ο?，利用JAVA語(yǔ)言編寫(xiě)實(shí)驗(yàn)程序，在Windows7系統(tǒng)中展開(kāi)數(shù)據(jù)挖掘測(cè)試。研究引入經(jīng)典Apriori算法、GA-Apriori算法作為關(guān)聯(lián)規(guī)則挖掘的對(duì)比算法，通過(guò)對(duì)比實(shí)驗(yàn)分析該算法的挖掘性能。測(cè)試的事務(wù)數(shù)據(jù)庫(kù)包括2056條事務(wù)，測(cè)試前對(duì)事務(wù)庫(kù)進(jìn)行簡(jiǎn)單的詞匯刪除等預(yù)處理操作，避免增加關(guān)聯(lián)規(guī)則提取的工作量。

2.1 關(guān)聯(lián)規(guī)則挖掘結(jié)果分析

基于本文算法得到某企業(yè)人力資源部分關(guān)聯(lián)規(guī)則如表1所示。表1中具體給出了與高素質(zhì)人才、高職稱(chēng)人才、高技術(shù)人才相關(guān)的關(guān)聯(lián)屬性，其支持度均低于頻繁項(xiàng)集支持度0.35，符合頻繁項(xiàng)集的支持度挖掘閾值標(biāo)準(zhǔn)。另外，與人力資源管理部分人員訪談得知，表1中數(shù)據(jù)挖掘結(jié)果全部符合實(shí)際情況，證明了本文算法挖掘人力資源類(lèi)計(jì)算機(jī)軟件數(shù)據(jù)的有效性。

表1 關(guān)聯(lián)規(guī)則提取結(jié)果

2.2 挖掘算法的性能分析

為了解本文算法挖掘計(jì)算機(jī)軟件數(shù)據(jù)的性能，記錄了經(jīng)典Apriori算法、GA-Apriori算法、本文算法挖掘在各個(gè)時(shí)間節(jié)點(diǎn)挖掘關(guān)聯(lián)規(guī)則的數(shù)量，如圖2所示。

圖2 3種算法的關(guān)聯(lián)規(guī)則挖掘性能對(duì)比

由圖2可知，當(dāng)挖掘關(guān)聯(lián)規(guī)則信息數(shù)量為50時(shí)，經(jīng)典Apriori算法、GA-Apriori算法、本文算法對(duì)應(yīng)的時(shí)間分別為10min、12.1min、3.5min，隨著挖掘結(jié)果的增多，本文算法時(shí)間開(kāi)銷(xiāo)增長(zhǎng)最為緩慢，并且其他兩種算法的時(shí)間開(kāi)銷(xiāo)曲線為較陡的上升曲線，可見(jiàn)處理相同數(shù)量的計(jì)算機(jī)軟件數(shù)據(jù)挖掘工作時(shí)，本文算法具有良好的效率優(yōu)勢(shì)。具體而言，是因?yàn)楸疚乃惴ɑ谟成湟?guī)則重新構(gòu)建計(jì)算機(jī)軟件事務(wù)數(shù)據(jù)庫(kù)，減少了Apriori算法不必要的連接與剪枝操作；在此基礎(chǔ)上設(shè)置雙重支持度閾值，同時(shí)提取頻繁項(xiàng)集與非頻繁項(xiàng)集，保障算法在較短的時(shí)間內(nèi)獲得強(qiáng)關(guān)聯(lián)度的頻繁項(xiàng)集。

3 結(jié)論

本文對(duì)經(jīng)典Apriori算法進(jìn)行改進(jìn)，改進(jìn)對(duì)象為頻繁項(xiàng)集挖掘環(huán)節(jié)，一方面設(shè)置雙重支持度閾值，高精度、高效率選取計(jì)算機(jī)軟件數(shù)據(jù)的頻繁項(xiàng)集；另一方面重構(gòu)事務(wù)數(shù)據(jù)庫(kù)結(jié)構(gòu)，利用映射規(guī)則存儲(chǔ)事務(wù)數(shù)據(jù)，避免重復(fù)數(shù)據(jù)存儲(chǔ)，大大壓縮了事務(wù)數(shù)據(jù)庫(kù)的規(guī)模。兩種策略的根本目的均是減少頻繁項(xiàng)集挖掘中的剪枝操作，減少不必要的計(jì)算量，降低計(jì)算復(fù)雜度。最后在實(shí)驗(yàn)分析中證明了本文算法挖掘人力資源類(lèi)計(jì)算機(jī)軟件數(shù)據(jù)的有效性，相比經(jīng)典Apriori算法以及GA-Apriori算法，本文算法效率性能有所提高。