王 翔，謝勝軍

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

1 引言

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

3.1 特征選擇

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

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

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

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

(2)

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

(3)

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

(4)

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

設(shè)置G為當(dāng)前的特征子集，并且G?F，那么Fi成為相關(guān)特征子集G的冗余特征的充要條件為：向量Fi表示的是相關(guān)特征，并且在G內(nèi)具有一個(gè)向量Fi的馬爾可夫毯Mi，當(dāng)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ù)挖掘工作更有利的開展，對(duì)數(shù)據(jù)集進(jìn)行特征選擇，能夠快速地獲得海量數(shù)據(jù)當(dāng)中的冗余性信息，很大程度的降低了數(shù)據(jù)規(guī)模，并且提高了數(shù)據(jù)挖掘算法的高效性和準(zhǔn)確性，提高數(shù)據(jù)挖掘效果。

3.2 支持度計(jì)算

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

(6)

其中，Cu所描述的是與數(shù)據(jù)u相對(duì)應(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新對(duì)應(yīng)的數(shù)據(jù)庫(kù)。

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

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

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

在運(yùn)算時(shí)，通常將關(guān)鍵屬性ε作為權(quán)衡關(guān)聯(lián)規(guī)則的一項(xiàng)標(biāo)準(zhǔn)，再對(duì)ε進(jìn)行進(jìn)一步評(píng)價(jià)，其表達(dá)式為

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

(8)

其中，Sup(ε)描述的是支持度，g(ε)描述的是可信度[10]。L1(ε)具有以下特點(diǎn)：如若關(guān)聯(lián)規(guī)則ε中蘊(yùn)含著關(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ù)庫(kù)U。

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

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

(9)

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

(10)

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

(11)

對(duì)其進(jìn)行簡(jiǎn)化處理后的公式為

US′=2(k-m)-1

(12)

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

(13)

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

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

Ns=ZpMY(x)s

(14)

Nd=ZpMY(x)d

(15)

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

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

(16)

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

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

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

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

將本文算法與文獻(xiàn)[1]和文獻(xiàn)[2]算法的挖掘聚類效果進(jìn)行對(duì)比分析，如圖2所示。

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

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

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

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

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

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

圖3 不同算法挖掘耗時(shí)比較

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

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

5 結(jié)論

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