基于主成分分析的模糊頻繁項(xiàng)集合挖掘方法

耿立校，李恒昱，劉麗莎

(河北工業(yè)大學(xué)，天津 300401)

1 引言

模糊頻繁項(xiàng)集合的挖掘是數(shù)據(jù)挖掘的關(guān)鍵步驟[1]，但通常情況下頻繁項(xiàng)集合的數(shù)量較多，導(dǎo)致挖掘過(guò)程難度較大。針對(duì)數(shù)據(jù)中最大模糊頻繁項(xiàng)集合中含有頻繁項(xiàng)的特點(diǎn)，對(duì)模糊頻繁項(xiàng)集合挖掘展開(kāi)研究[2，3]。

文獻(xiàn)[4]提出基于高效改進(jìn)的模糊頻繁項(xiàng)集合挖掘方法。該方法首先掃描數(shù)據(jù)庫(kù)，構(gòu)建存儲(chǔ)項(xiàng)集關(guān)系的"投影"數(shù)據(jù)架構(gòu)，提取出頻繁1-項(xiàng)集和頻繁2-項(xiàng)集，其次構(gòu)建高階項(xiàng)集的位置索引表，在跨越式搜索和連接的基礎(chǔ)上找出模糊頻繁項(xiàng)集合，實(shí)現(xiàn)模糊頻繁項(xiàng)集合挖掘。但是由于該方法在模糊頻繁項(xiàng)集合挖掘前沒(méi)有對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，無(wú)法減少數(shù)據(jù)變量中的項(xiàng)，導(dǎo)致冗余數(shù)據(jù)的計(jì)算量過(guò)大，進(jìn)而加大了方法運(yùn)行內(nèi)存。文獻(xiàn)[5]提出基于DiffNodeset結(jié)構(gòu)的模糊頻繁項(xiàng)集合挖掘方法。該方法運(yùn)用數(shù)據(jù)結(jié)構(gòu)DiffNodeset求出支持度，并利用線(xiàn)性連接方法來(lái)降低連接的復(fù)雜度，減少無(wú)效計(jì)算量，其次在集合枚舉樹(shù)搜索空間的基礎(chǔ)上利用優(yōu)化剪枝策略減小搜索空間范圍，最后中和超集檢測(cè)技術(shù)提取模糊頻繁項(xiàng)集合，實(shí)現(xiàn)模糊頻繁項(xiàng)集合挖掘，該方法未利用主成分分析法對(duì)數(shù)據(jù)進(jìn)行降維，而是直接對(duì)數(shù)據(jù)重新運(yùn)算，只能在原始信息素排序表的基礎(chǔ)上進(jìn)行挖掘，該方法的挖掘計(jì)算量過(guò)大。文獻(xiàn)[6]提出基于AO算法的模糊頻繁項(xiàng)集合挖掘方法，該方法在滑動(dòng)窗口思想的基礎(chǔ)上對(duì)模糊頻繁項(xiàng)集合分塊挖掘，當(dāng)滿(mǎn)窗口有模糊頻繁項(xiàng)集合進(jìn)入時(shí)，利用區(qū)域插入的方式獲取全新模糊頻繁項(xiàng)集合，并求解支持度，同時(shí)結(jié)合超集檢測(cè)，保證在最高效率下挖掘出模糊頻繁項(xiàng)集合，實(shí)現(xiàn)模糊頻繁項(xiàng)集合挖掘，該方法沒(méi)有對(duì)模糊頻繁項(xiàng)集合進(jìn)行間隔約束處理而是直接挖掘模糊頻繁項(xiàng)集合，導(dǎo)致散亂數(shù)據(jù)不能保持平衡，數(shù)據(jù)散亂程度過(guò)高，該方法的準(zhǔn)確率、召回率和F1值均均不夠理想。

為解決上述方法中存在的問(wèn)題，引入主成分分析法，優(yōu)化間隔約束條件下的模糊頻繁項(xiàng)集合挖掘方法。通過(guò)實(shí)驗(yàn)驗(yàn)證了所提方法具有一定應(yīng)用優(yōu)勢(shì)，為相關(guān)領(lǐng)域的研究提供可靠依據(jù)。

2 模糊頻繁項(xiàng)集合預(yù)處理

2.1 修補(bǔ)模糊頻繁缺損數(shù)據(jù)

經(jīng)過(guò)標(biāo)準(zhǔn)化處理后的模糊頻繁數(shù)據(jù)可相互對(duì)比，進(jìn)而排除量綱帶來(lái)的影響[7]，假設(shè)標(biāo)準(zhǔn)化處理后的模糊頻繁項(xiàng)集合為X，X是由n個(gè)自身帶有s維模糊頻繁項(xiàng)數(shù)據(jù)的向量X1，X2，…，Xn組成，其中向量Xj=(x1j，x2j，…，xsj)T∈Rs，j=1，2，…，n，xi0j0是模糊頻繁項(xiàng)的缺損數(shù)據(jù)，即需要修補(bǔ)的模糊頻繁項(xiàng)數(shù)據(jù)。

假設(shè)向量Xj中的行向量為bi(i=1，…，s)，列向量為aj(j=1，…，n)，則模糊頻繁項(xiàng)集合X的矩陣表達(dá)式為

(1)

將模糊頻繁項(xiàng)集合X中的缺損數(shù)據(jù)xi0j0所在的第i0行進(jìn)行消除，獲取全新數(shù)據(jù)A，其矩陣表達(dá)式為

(2)

(3)

(4)

根據(jù)上述算法的逆過(guò)程將標(biāo)準(zhǔn)化數(shù)據(jù)還原成帶有量綱的數(shù)據(jù)，最終輸出的數(shù)據(jù)就是標(biāo)準(zhǔn)化后的完整數(shù)據(jù)。

2.2 基于主成分分析法的數(shù)據(jù)降維

主成分分析法是數(shù)據(jù)降維的重要手段之一，可提高數(shù)據(jù)挖掘效率，與其它降維手段相比，主成分分析法的降維力度最強(qiáng)[8]，該方法將修補(bǔ)后的完整模糊頻繁項(xiàng)數(shù)據(jù)進(jìn)行數(shù)值化處理，并按照數(shù)據(jù)類(lèi)型將模糊頻繁項(xiàng)數(shù)據(jù)劃分成多個(gè)子數(shù)據(jù)集，并逐一進(jìn)行降維，保證最大程度地排除數(shù)據(jù)中的冗余特征，其大致過(guò)程為：

①構(gòu)建觀(guān)測(cè)矩陣

假設(shè)數(shù)據(jù)中含有m個(gè)變量，對(duì)所有變量進(jìn)行n次觀(guān)測(cè)后每個(gè)子數(shù)據(jù)中都會(huì)生成n條樣本數(shù)據(jù)，進(jìn)而生成的觀(guān)測(cè)數(shù)據(jù)矩陣表達(dá)式為

(5)

式中，xij表示分割后的子數(shù)據(jù)集，m表示模糊頻繁項(xiàng)數(shù)據(jù)矩陣的行，即矩陣的每一行均是數(shù)據(jù)進(jìn)行數(shù)值化后的一個(gè)樣本模糊頻繁項(xiàng)數(shù)據(jù)，n表示模糊頻繁項(xiàng)數(shù)據(jù)矩陣的列，即劃分后的子數(shù)據(jù)內(nèi)的主成分樣本個(gè)數(shù)。

②數(shù)據(jù)中心標(biāo)準(zhǔn)化

(6)

③求解樣本數(shù)據(jù)相關(guān)矩陣R

④特征分解矩陣R，獲取R=U∧UT

1)計(jì)算樣本相關(guān)矩陣R的特征值

經(jīng)計(jì)算發(fā)現(xiàn)矩陣R中含有m個(gè)特征值，將所有特征值自大到小的順序進(jìn)行排列后得到λ1≥λ2≥…≥λm≥0，進(jìn)而求出所有主成分的貢獻(xiàn)率，從中選取貢獻(xiàn)率在85%以上的成分，并在這些成分中篩選出符合特征值小于1的前p主成分，篩選后的成分記為主成分分析結(jié)果，則主成分貢獻(xiàn)率公式為

Cj=λj/(λ1+λ2+…+λm)

(7)

利用式(10)即可計(jì)算出每個(gè)主成分的貢獻(xiàn)率，即每種成分可提供的信息量，Cj越大說(shuō)明成分中信息量越多，且每個(gè)成分各自獨(dú)立存在，即不存在信息重復(fù)的情況，因此提取滿(mǎn)足上式兩個(gè)要求的特征值即可。

2)計(jì)算特征向量

根據(jù)特征值的排序運(yùn)算出對(duì)應(yīng)的特征向量eig1，eig2，…，eigm，這些特征向量屬于單位向量，即|eigi|=1，且特征向量?jī)蓛上嘟?，即eigi⊥eigj。

3)構(gòu)建主成分載荷矩陣

根據(jù)貢獻(xiàn)率最高的前p個(gè)主成分生成主成分載荷陣Um×p=(eig1，eig2，…，eigp)，則此矩陣就是主成分分析的最終結(jié)果，其中，m是特征向量的個(gè)數(shù)。

⑤將原始變量轉(zhuǎn)換為主成分變量即可實(shí)現(xiàn)特征降維，即最大程度減少模糊頻繁項(xiàng)數(shù)據(jù)數(shù)量，其表達(dá)式為

(8)

式中，ηi表示轉(zhuǎn)化后的主成分變量，其中i=1，2，…，p，ξj表示原始變量，且j=1，2，…，m。

2.3 間隔約束最大模糊頻繁項(xiàng)目集

在實(shí)際挖掘過(guò)程中，有項(xiàng)約束是最常用的約束條件[9]，假設(shè)項(xiàng)目約束條件是B，且B為I內(nèi)的布爾代表公式，I是由多個(gè)不同的模糊頻繁項(xiàng)目構(gòu)成的集合，將約束條件B轉(zhuǎn)換成析取范式(DNF)，即B1∨B2∨B3∨…∨Bk形式，在DNF形式下的約束條件集合為B={B1，B2，B3，…，BK}，且每個(gè)Bi表示b1∧b2∧b3∧…∧b1，其中bj∈I，假設(shè)T是模糊頻繁項(xiàng)目集合的一個(gè)交易數(shù)據(jù)庫(kù)，已知布爾表達(dá)式B，則可將間隔約束條件下的模糊頻繁項(xiàng)目集合挖掘問(wèn)題轉(zhuǎn)化成提取符合約束條件B的模糊頻繁項(xiàng)目集合問(wèn)題，且挖掘過(guò)程中還需保證挖掘結(jié)果的支持度大于等于固定的最小支持度閾值[10]。

3 模糊頻繁項(xiàng)目集合挖掘

模糊頻繁項(xiàng)集合中的數(shù)據(jù)雖隸屬于同一數(shù)據(jù)庫(kù)，但實(shí)際上數(shù)據(jù)分散在各個(gè)場(chǎng)地，將模糊頻繁項(xiàng)數(shù)據(jù)利用傳統(tǒng)方法進(jìn)行分類(lèi)難度較大，而蟻群優(yōu)化系統(tǒng)具有記憶性、自主性、反應(yīng)性、容錯(cuò)性、社會(huì)性、移動(dòng)性以及適應(yīng)性等優(yōu)點(diǎn)[11]，基于以上優(yōu)點(diǎn)可將此方法應(yīng)用于數(shù)據(jù)挖掘中，同時(shí)可建立出一條又一條互不依賴(lài)的規(guī)則，按照歷史錯(cuò)誤更新經(jīng)驗(yàn)，逐一計(jì)算得出最優(yōu)解，即生成ACO分布式分類(lèi)算法，此算法首先將數(shù)據(jù)進(jìn)行初始化處理，獲取所有挖掘通道的相關(guān)信息，并計(jì)算出數(shù)據(jù)相關(guān)函數(shù)，進(jìn)而生成一條有規(guī)則又互不依賴(lài)的數(shù)據(jù)挖掘通道，其次修剪規(guī)則從而修改蟻群爬行路徑的信息，最終在所有規(guī)則中提取出一條質(zhì)量最優(yōu)的規(guī)則，根據(jù)此規(guī)則挖掘出模糊頻繁項(xiàng)數(shù)據(jù)。

綜上所述可知在建立規(guī)則前必須提前求解規(guī)則內(nèi)所需的條件項(xiàng)，并根據(jù)規(guī)則自身的條件項(xiàng)得出可能執(zhí)行此任務(wù)的可能性P，其表達(dá)式為

Pij(t)=Rij(t)2/θ+Rij(t)2

(9)

利用蟻群算法建立出規(guī)則后的信息素總數(shù)表達(dá)式為

τij(t)=τij(t-1)·(1-1/(1+Q))

+(1-ρ)·τij(t-1)

(10)

式中，ρ表示信息素可能損失的概率，Q表示根據(jù)蟻群算法建立的規(guī)則質(zhì)量。

參數(shù)ρ可直接反映出蟻群算法在爬行過(guò)程中信息的損失速度，因此參數(shù)ρ越大，此路徑中的信息損失速度越快。在對(duì)一個(gè)訓(xùn)練集進(jìn)行多次蟻群算法后即可獲取多條數(shù)據(jù)分類(lèi)規(guī)則，利用Q選取出其中質(zhì)量最優(yōu)的規(guī)則，則Q的表達(dá)式為

Q=(TruePos/FalseNeg+TruePos)×

(TrueNeg/FalsePos+TrueNeg)

(11)

式中，TruePos代表規(guī)則路徑中滿(mǎn)足規(guī)則的條件項(xiàng)，且此條件項(xiàng)的數(shù)量和預(yù)測(cè)出規(guī)則類(lèi)型數(shù)量一致，F(xiàn)alsePos代表規(guī)則路徑中滿(mǎn)足規(guī)則的條件項(xiàng)，但此條件項(xiàng)的數(shù)量和預(yù)測(cè)出規(guī)則類(lèi)型數(shù)量不相同，F(xiàn)alseNeg代表規(guī)則路徑中不符合規(guī)則的條件項(xiàng)，但此條件項(xiàng)的數(shù)量和預(yù)測(cè)出規(guī)則類(lèi)型數(shù)量一致，TeueNeg代表規(guī)則路徑中不符合規(guī)則的條件項(xiàng)，且此條件項(xiàng)的數(shù)量和預(yù)測(cè)出規(guī)則類(lèi)型數(shù)量不相同。

根據(jù)信息素和啟發(fā)函數(shù)值選出最優(yōu)規(guī)則路徑后將條件項(xiàng)添加到規(guī)則路徑中，保證數(shù)據(jù)分類(lèi)準(zhǔn)確率最高的同時(shí)還可簡(jiǎn)化分類(lèi)規(guī)則[12]，將數(shù)據(jù)進(jìn)行最優(yōu)分類(lèi)，實(shí)現(xiàn)模糊頻繁項(xiàng)集合挖掘。

4 實(shí)驗(yàn)與結(jié)果

為驗(yàn)證所提方法的整體有效性，對(duì)間隔約束條件下的模糊頻繁項(xiàng)集合挖掘方法、文獻(xiàn)[4]方法和文獻(xiàn)[5]方法進(jìn)行運(yùn)行內(nèi)存和挖掘有效性的測(cè)試。

4.1 運(yùn)行內(nèi)存大小測(cè)試

根據(jù)圖1可看出隨著最小支持度的增加，三種挖掘方法的運(yùn)行內(nèi)存均有所下降，進(jìn)而提高系統(tǒng)的流暢程度，但所提方法的運(yùn)行內(nèi)存最大為65M，隨著最小支持度的增加其運(yùn)行內(nèi)存一直在下降，因此所提方法的系統(tǒng)最流暢，其它兩種方法的運(yùn)行內(nèi)存過(guò)于依賴(lài)系統(tǒng)支持度，在支持度過(guò)小的情況下兩種方法的最大運(yùn)行內(nèi)存分別為105M和140M，導(dǎo)致文獻(xiàn)[4]方法和文獻(xiàn)[5]方法的系統(tǒng)比較卡頓，而所提方法可一直保證系統(tǒng)流暢是因?yàn)樵谶M(jìn)行模糊頻繁項(xiàng)集合挖掘前對(duì)數(shù)據(jù)進(jìn)行了預(yù)處理，數(shù)據(jù)變量中的項(xiàng)明顯下降，排除大量冗余數(shù)據(jù)，保證了系統(tǒng)的流暢程度，降低運(yùn)行內(nèi)存使用率。

圖1 不同方法的運(yùn)行內(nèi)存使用情況

4.2 挖掘有效性測(cè)試

隨機(jī)選取了六組訓(xùn)練數(shù)據(jù)，比較三種方法處理后的數(shù)據(jù)精確率、召回程度以及F1值，模糊頻繁項(xiàng)集合中的信息素比較散亂，對(duì)這種數(shù)據(jù)進(jìn)行挖掘有較大的難度，難以保證其挖掘有效性，如圖2所示，文獻(xiàn)[4]方法在挖掘時(shí)只能加大計(jì)算量進(jìn)而提高準(zhǔn)確率、召回率和F1值，文獻(xiàn)[5]方法沒(méi)有做任何處理，導(dǎo)致其挖掘有效性十分低下，而所提方法經(jīng)過(guò)對(duì)數(shù)據(jù)的間隔約束處理后進(jìn)行數(shù)據(jù)挖掘，相當(dāng)于將信息素進(jìn)行一個(gè)平衡處理，使得數(shù)據(jù)的散亂程度有所改善，因此無(wú)論是所提方法的準(zhǔn)確率、召回率還是F1值，它都是三種方法中最優(yōu)的方法，驗(yàn)證了所提方法的有效性。

圖2 不同方法的挖掘有效性

5 結(jié)束語(yǔ)

為解決目前方法所存在的問(wèn)題，提出了間隔約束條件下的模糊頻繁項(xiàng)集合挖掘方法，該方法首先對(duì)模糊頻繁項(xiàng)集合進(jìn)行預(yù)處理和約束，其次利用蟻群算法分類(lèi)項(xiàng)目，最終實(shí)現(xiàn)模糊頻繁項(xiàng)集合挖掘，解決運(yùn)行內(nèi)存過(guò)大和挖掘有效性低的問(wèn)題，此方法提高項(xiàng)集查找速度，將原本需要多次完成的任務(wù)一次完成，大大縮小工作壓力，降低成本。