加權社會網絡低維冗余數據快速挖掘算法仿真

王 翔，謝勝軍

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

1 引言

伴隨計算機技術和社會加權網絡的快速變化，數據量急速增加，因此需要利用有效方式對重要信息進行快速提取，提高數據處理效率。

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

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

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

2 構建加權社會網絡模型

在實際應用中，動態網絡[3]在某一時刻所呈現出的整體重要性并不相同，需綜合考慮各個節點上網絡的不同權重，即考慮加權社會動態網絡。

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

(1)

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

建立加權社會網絡模型如圖1所示。

建立加權網絡模型，綜合考慮用戶之間的多重關系和關系強弱程度[4]，其構建步驟如下所示：

1)根據用戶收藏的Web頁數據集，通過關鍵詞集向量空間實現用戶興趣建模。

2)根據數據集構建加權社會網絡模型和投影網絡。

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

4)把以上信息進行輸入，從而建立加權社會網絡INTER。

在投影網絡內，可以將相似度稱之為數據節點間存在的連邊權值，將其作為節點之間的連接強度。設置閾值θ，并將權值不大于θ的弱連接邊全部去除，能夠減少運算量。

所建立的加權社會網絡以用戶作為節點，用戶間存在的交互關系作為邊，使其保持復雜網絡的性能的同時提高網絡穩定性。

3 低維冗余數據快速挖掘

3.1 特征選擇

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

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

設置F為原始特征數據集，Fi為該數據集之中的特征向量，Si為最優特征子集，且Si=F-{Fi}，C作為各個類別信息，那么當Fi為相關性較強的特征時，其充要條件表達式為：

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

(2)

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

(3)

當Fi為不相關性特征時，其充要條件表達式為

(4)

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

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

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

(5)

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

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

3.2 支持度計算

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

(6)

其中，Cu所描述的是與數據u相對應的數據塊ID集。

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

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

(7)

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

3.3 關聯規則下數據快速挖掘算法

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

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

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

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

(8)

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

步驟1：輸入數據：關鍵屬性集D和數據庫U。

步驟2：輸出數據：具有關鍵屬性因素的關聯規格集合E。

步驟3：相關性參數：gmin作為最小可信度，Sup min作為最小支持度。

(9)

a為限制條件的屬性集，PBM為a對應屬性位構成的集合。

(10)

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

(11)

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

US′=2(k-m)-1

(12)

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

(13)

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

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

Ns=ZpMY(x)s

(14)

Nd=ZpMY(x)d

(15)

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

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

(16)

獲取到低維冗余數據下的關聯規則集E，從而實現加權社會網絡低維冗余數據快速挖掘。

4 實驗結果

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

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

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

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

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

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

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

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

為驗證該算法能否實現加權社會網絡低維冗余數據快速挖掘，進行挖掘耗時比較實驗，實驗結果如圖3。

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

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

綜上所述，本文方法在挖掘加權社會網絡中存在的低維冗余數據時，聚類效果好，所得數據更加精確，挖掘效率高，具有顯著的優越性。

5 結論

本文通過建立社會加權網絡模型，保持原始數據的信息，然后利用特征選擇，獲取到冗余性信息，從而對支持度進行運算，根據關聯規則最終實現低維冗余數據快速挖掘。仿真結果表明：本文所提算法比其它兩種算法在挖掘時更加快速、準確，實用性強以及顯著優越性。