加權(quán)社會網(wǎng)絡(luò)低維冗余數(shù)據(jù)快速挖掘算法仿真

王 翔，謝勝軍

(西南民族大學，四川 成都 610041)

1 引言

伴隨計算機技術(shù)和社會加權(quán)網(wǎng)絡(luò)的快速變化，數(shù)據(jù)量急速增加，因此需要利用有效方式對重要信息進行快速提取，提高數(shù)據(jù)處理效率。

社會加權(quán)網(wǎng)絡(luò)作為由用戶個體之間通過社會關(guān)系構(gòu)成的網(wǎng)絡(luò)體系，每個單獨個體可以稱之為節(jié)點，每一節(jié)點之間具有關(guān)聯(lián)性。在社會網(wǎng)絡(luò)上的信息大多都是由用戶產(chǎn)生和制造的，其信息來源具有不確定性、虛假性以及不良性，這些信息可能會給人們的生活帶來不利影響?，F(xiàn)階段，數(shù)據(jù)挖掘技術(shù)已經(jīng)作為處理大規(guī)模數(shù)據(jù)的有效手段，但在大規(guī)模數(shù)據(jù)集中往往會存在較多的冗余性信息，并且這些信息呈現(xiàn)持續(xù)增加的趨勢，促使數(shù)據(jù)處理時耗費的時間較多，怎樣對數(shù)據(jù)信息進行快速挖掘成為相關(guān)領(lǐng)域中的研究熱點之一。

彭智勇等人[1]提出數(shù)據(jù)庫低維子空間偏移數(shù)據(jù)定位挖掘方法。首先根據(jù)爬蟲算法計算出低維子空間偏移數(shù)據(jù)信息的覆蓋率，再設(shè)定偏移數(shù)據(jù)稀疏閾值，融合微粒群算法根據(jù)該閾值進行偏移數(shù)據(jù)定位，挖掘出目標適應(yīng)值函數(shù)，然后將其適應(yīng)值與微粒子的全局最優(yōu)位置做對比，最終實現(xiàn)偏移數(shù)據(jù)定位挖掘。熊運余等人[2]提出一種基于網(wǎng)絡(luò)狀態(tài)異常情況的數(shù)據(jù)挖掘算法。首先運用小波變換方式對網(wǎng)絡(luò)狀態(tài)信號進行預處理，并獲取網(wǎng)絡(luò)狀態(tài)異常檢測的特征，再根據(jù)回聲狀態(tài)網(wǎng)絡(luò)進行網(wǎng)絡(luò)狀態(tài)異常檢測建模，使用遺傳算法對回聲狀態(tài)網(wǎng)絡(luò)的參數(shù)進行優(yōu)化處理，最后采用網(wǎng)絡(luò)狀態(tài)異常數(shù)據(jù)集對模型的有效性進行測試。

上述兩種方法在進行數(shù)據(jù)挖掘時，沒有綜合考慮到數(shù)據(jù)內(nèi)存中低維冗余數(shù)據(jù)問題，導致算法挖掘結(jié)果精度低，本文所提算法根據(jù)特征選擇獲取到數(shù)據(jù)冗余特征，運用屬性位復用方法，完成對低維冗余數(shù)據(jù)的挖掘，挖掘精度高，更加節(jié)省挖掘耗時，提高挖掘效率。

2 構(gòu)建加權(quán)社會網(wǎng)絡(luò)模型

在實際應(yīng)用中，動態(tài)網(wǎng)絡(luò)[3]在某一時刻所呈現(xiàn)出的整體重要性并不相同，需綜合考慮各個節(jié)點上網(wǎng)絡(luò)的不同權(quán)重，即考慮加權(quán)社會動態(tài)網(wǎng)絡(luò)。

綜合考慮加權(quán)社會動態(tài)網(wǎng)絡(luò)中的海量數(shù)據(jù)信息，會產(chǎn)生大量無關(guān)屬性，對數(shù)據(jù)挖掘的精準度會造成一定影響，因此需要構(gòu)建加權(quán)社會網(wǎng)絡(luò)模型。由于在加權(quán)社會網(wǎng)絡(luò)中個體之間的關(guān)系程度是不均等的，故在網(wǎng)絡(luò)連接邊上加入權(quán)重因素，獲取節(jié)點間的相似度，合理運用向量的夾角余弦計算出相似度，其表達式為：

(1)

在式中，x1k和y2k作為節(jié)點向量U1和向量U2中存在的元素。

建立加權(quán)社會網(wǎng)絡(luò)模型如圖1所示。

建立加權(quán)網(wǎng)絡(luò)模型，綜合考慮用戶之間的多重關(guān)系和關(guān)系強弱程度[4]，其構(gòu)建步驟如下所示：

1)根據(jù)用戶收藏的Web頁數(shù)據(jù)集，通過關(guān)鍵詞集向量空間實現(xiàn)用戶興趣建模。

2)根據(jù)數(shù)據(jù)集構(gòu)建加權(quán)社會網(wǎng)絡(luò)模型和投影網(wǎng)絡(luò)。

3)依據(jù)用戶的向量空間模型獲取用戶之間存在的相似度，獲得相似度矩陣。

4)把以上信息進行輸入，從而建立加權(quán)社會網(wǎng)絡(luò)INTER。

在投影網(wǎng)絡(luò)內(nèi)，可以將相似度稱之為數(shù)據(jù)節(jié)點間存在的連邊權(quán)值，將其作為節(jié)點之間的連接強度。設(shè)置閾值θ，并將權(quán)值不大于θ的弱連接邊全部去除，能夠減少運算量。

所建立的加權(quán)社會網(wǎng)絡(luò)以用戶作為節(jié)點，用戶間存在的交互關(guān)系作為邊，使其保持復雜網(wǎng)絡(luò)的性能的同時提高網(wǎng)絡(luò)穩(wěn)定性。

3 低維冗余數(shù)據(jù)快速挖掘

3.1 特征選擇

不相關(guān)和冗余特征會影響網(wǎng)絡(luò)性能和數(shù)據(jù)挖掘[5]結(jié)果，伴隨數(shù)據(jù)量的增加，冗余特征的指數(shù)也隨之增長，算法的準確率會隨著冗余特征的增多而下降，因此在數(shù)據(jù)挖掘之前要進行相關(guān)特征與冗余特征選擇，以提升挖掘精度與效率。

在特征選擇的過程中，確定特征之間的相關(guān)性[6]尤為重要。但伴隨高維數(shù)據(jù)的快速增長與特征選擇技術(shù)的進步，對數(shù)據(jù)特征的冗余性研究逐步加深，故特征選擇的首要任務(wù)就是提取數(shù)據(jù)特征間的相關(guān)性和冗余性。

設(shè)置F為原始特征數(shù)據(jù)集，F(xiàn)i為該數(shù)據(jù)集之中的特征向量，Si為最優(yōu)特征子集，且Si=F-{Fi}，C作為各個類別信息，那么當Fi為相關(guān)性較強的特征時，其充要條件表達式為：

P(C|Fi，Si)≠P(C|Si)

(2)

當Fi為相關(guān)性較弱的特征時，其充要條件表達式為

(3)

當Fi為不相關(guān)性特征時，其充要條件表達式為

(4)

從以上描述中可以看出，在最優(yōu)特征子集中一定存在較強的相關(guān)特征，不一定存在較弱的相關(guān)特征，在某種情形下可能會對分類模式與結(jié)果造成影響。還可以確定的是，最優(yōu)特征子集中一定不存在無相關(guān)性的特征。較弱的相關(guān)性特征選擇時，可能數(shù)據(jù)挖掘結(jié)果造成影響。為了可以有效辨別其特性，提出了冗余性特征的概念，以下描述的是特征的冗余性。

設(shè)置G為當前的特征子集，并且G?F，那么Fi成為相關(guān)特征子集G的冗余特征的充要條件為：向量Fi表示的是相關(guān)特征，并且在G內(nèi)具有一個向量Fi的馬爾可夫毯Mi，當Mi?F(Fi?Mi)需滿足以下條件

(F-Mi-{Fi}，C|Fi，Mi)=P(F-Mi-{Fi}，C|Mi)

(5)

從中可以看出，馬爾可夫毯Mi即能夠代表特征向量Fi與其它特征之間的關(guān)系，又能夠代表特征向量Fi與類別信息C的相關(guān)性，若去除原始數(shù)據(jù)特征集中的Fi，并保證信息不遺失，必須確保Mi存在，因此Mi即為數(shù)據(jù)冗余性特征。

為使數(shù)據(jù)挖掘工作更有利的開展，對數(shù)據(jù)集進行特征選擇，能夠快速地獲得海量數(shù)據(jù)當中的冗余性信息，很大程度的降低了數(shù)據(jù)規(guī)模，并且提高了數(shù)據(jù)挖掘算法的高效性和準確性，提高數(shù)據(jù)挖掘效果。

3.2 支持度計算

為實現(xiàn)低維冗余數(shù)據(jù)的快速挖掘[7]，在挖掘前需要計算支持度，支持度表示前項與后項在一個數(shù)據(jù)集中同時出現(xiàn)的頻率，是冗余數(shù)據(jù)去除的基礎(chǔ)。首先設(shè)置低維冗余數(shù)據(jù)的集合即U，在集合內(nèi)的數(shù)據(jù)相關(guān)性的表達式為

(6)

其中，Cu所描述的是與數(shù)據(jù)u相對應(yīng)的數(shù)據(jù)塊ID集。

低維冗余數(shù)據(jù)集U的支持度能夠通過以下公式得出

Sup(U)=|{Bb|U∈Ab}|

(7)

在式(7)中，Bb是數(shù)據(jù)塊ID集中數(shù)據(jù)b的數(shù)據(jù)塊，Ab作為b新對應(yīng)的數(shù)據(jù)庫。

3.3 關(guān)聯(lián)規(guī)則下數(shù)據(jù)快速挖掘算法

在加權(quán)社會網(wǎng)絡(luò)中，低維冗余數(shù)據(jù)區(qū)別較大[8]。根據(jù)關(guān)鍵程度進行區(qū)分，可以劃分為直接或間接作用屬性兩種。但是從根本上來看直接作用屬性可以在一定程度上呈現(xiàn)出在數(shù)據(jù)中較為明顯的重要信息[9]。間接作用屬性可以根據(jù)數(shù)據(jù)給出相應(yīng)的輔助信息，例如某些數(shù)據(jù)中的較小細節(jié)，因此可以利用支持度與可信度對低維冗余數(shù)據(jù)關(guān)聯(lián)規(guī)則進行評價，并按照直接屬性對其限制，大幅度減少無用規(guī)則的產(chǎn)生。

將S作為屬性集合，C作為屬性之關(guān)聯(lián)集合，即D?S，若集合S依附于集合D，那么可以得出此集合將稱之為關(guān)鍵屬性集，之中的屬性被稱之為關(guān)鍵屬性。

在運算時，通常將關(guān)鍵屬性ε作為權(quán)衡關(guān)聯(lián)規(guī)則的一項標準，再對ε進行進一步評價，其表達式為

L(ε)=f[L1(ε)，Sup(ε)，g(ε)]

(8)

其中，Sup(ε)描述的是支持度，g(ε)描述的是可信度[10]。L1(ε)具有以下特點：如若關(guān)聯(lián)規(guī)則ε中蘊含著關(guān)鍵屬性，那么L1(ε)=1，若與之相反，那么L1(ε)=0。把具有關(guān)鍵屬性的規(guī)則作為關(guān)聯(lián)規(guī)則，若不存在那么將作為不關(guān)聯(lián)規(guī)則。

步驟1：輸入數(shù)據(jù)：關(guān)鍵屬性集D和數(shù)據(jù)庫U。

步驟2：輸出數(shù)據(jù)：具有關(guān)鍵屬性因素的關(guān)聯(lián)規(guī)格集合E。

步驟3：相關(guān)性參數(shù)：gmin作為最小可信度，Sup min作為最小支持度。

(9)

a為限制條件的屬性集，PBM為a對應(yīng)屬性位構(gòu)成的集合。

(10)

在根據(jù)式(11)計算出集合U關(guān)于S′的整數(shù)，公式如下

(11)

對其進行簡化處理后的公式為

US′=2(k-m)-1

(12)

其中候選部分處在[1，2(k-m)-1]的范圍中。若M為復用向量，運用M將關(guān)于S′的US′整數(shù)還原成U關(guān)于S的整數(shù)US在其中復用向量的表達式即

(13)

若Y(x)∈[1，2(k-m)-1]，將Y(x)進行二進制數(shù)轉(zhuǎn)換，那么其二進制向量值為Y(x)T。

運用候選部分中臨界值呈現(xiàn)雙向變化，利用其對冗余數(shù)據(jù)進行控制。設(shè)Y(x)s為遞增量，其初始數(shù)值為1，Y(x)d作為遞減量，其初始數(shù)值為2(k-m)-1。根據(jù)復用向量M，將Y(x)s和Y(x)d還原至低維冗余數(shù)據(jù)Ns和Nd，其表達式為

Ns=ZpMY(x)s

(14)

Nd=ZpMY(x)d

(15)

其中，當分別對Y(x)s和Y(x)d進行遞增和遞減處理后，低維冗余數(shù)據(jù)停止產(chǎn)生。

那么對于各個冗余數(shù)據(jù)項集I={Ns，Nd}來說，若含有I∩U≠φ，那么則要對其整體非空子集進行生成處理。針對各個非空子集，將規(guī)則γ?(1-γ)、g(ε)以及Sup(ε)代入到關(guān)聯(lián)規(guī)則集E中。所得公式即

(16)

獲取到低維冗余數(shù)據(jù)下的關(guān)聯(lián)規(guī)則集E，從而實現(xiàn)加權(quán)社會網(wǎng)絡(luò)低維冗余數(shù)據(jù)快速挖掘。

4 實驗結(jié)果

為了驗證本文算法的有效性，實驗環(huán)境采用Windows2000操作系統(tǒng)，運用Vc++6.0在內(nèi)存為128MB的平臺中進行仿真對比分析。

在實驗中運用的數(shù)據(jù)庫中的數(shù)據(jù)為：D為事務(wù)數(shù)據(jù)記錄的數(shù)量，T為數(shù)據(jù)數(shù)據(jù)記錄的均值長度，L為最大頻繁項目集數(shù)量，b為冗余性數(shù)據(jù)的數(shù)量，N為事務(wù)項目集的個數(shù)。

將本文算法與文獻[1]和文獻[2]算法的挖掘聚類效果進行對比分析，如圖2所示。

圖2 不同算法挖掘聚類效果比較

從圖2可以看出，在進行加權(quán)社會網(wǎng)絡(luò)低維冗余數(shù)據(jù)快速挖掘挖掘時，文獻[1]算法將所挖掘數(shù)據(jù)分為兩個大類，類別劃分不細，大幅度降低了數(shù)據(jù)挖掘精度；文獻[2]算法將所挖掘數(shù)據(jù)分為一個大類和兩個小類，聚類效果并不好；而本文算法將數(shù)據(jù)庫中的數(shù)據(jù)劃分為7個類別，聚類效果好。

在上述實驗的基礎(chǔ)上，進行不同算法挖掘精度比較，比較結(jié)果如表1所示。

表1 不同算法挖掘精度比較

分析上表可知，在60次仿真中，文獻[1]算法挖掘精度70.2%-77.8%之間變化，文獻[2]算法挖掘精度76.5%-85.1%范圍之內(nèi)波動，本文算法挖掘精度始終保持在97.4%以上，遠遠高于文獻對比算法，說明利用本文算法能夠精準挖掘出加權(quán)社會網(wǎng)絡(luò)中存在的低維冗余數(shù)據(jù)。

為驗證該算法能否實現(xiàn)加權(quán)社會網(wǎng)絡(luò)低維冗余數(shù)據(jù)快速挖掘，進行挖掘耗時比較實驗，實驗結(jié)果如圖3。

圖3 不同算法挖掘耗時比較

從圖3中可以看出，與文獻算法相比，本文算法所耗費時間更短，挖掘效率高，具有高效性、有效性和通用性。原因在于本文算法通過屬性位復用方法建立候選區(qū)域，生成關(guān)聯(lián)規(guī)則集，對符合關(guān)聯(lián)規(guī)則集的低維冗余數(shù)據(jù)聚類，提升數(shù)據(jù)挖掘效率。

綜上所述，本文方法在挖掘加權(quán)社會網(wǎng)絡(luò)中存在的低維冗余數(shù)據(jù)時，聚類效果好，所得數(shù)據(jù)更加精確，挖掘效率高，具有顯著的優(yōu)越性。

5 結(jié)論

本文通過建立社會加權(quán)網(wǎng)絡(luò)模型，保持原始數(shù)據(jù)的信息，然后利用特征選擇，獲取到冗余性信息，從而對支持度進行運算，根據(jù)關(guān)聯(lián)規(guī)則最終實現(xiàn)低維冗余數(shù)據(jù)快速挖掘。仿真結(jié)果表明：本文所提算法比其它兩種算法在挖掘時更加快速、準確，實用性強以及顯著優(yōu)越性。