基于關聯(lián)規(guī)則的網絡數(shù)據(jù)動態(tài)聚類方法研究

王喆 宋曉峰 王玉芳

摘要：針對傳統(tǒng)聚類方法動態(tài)聚類效果差、耗時長的問題，提出了一種基于關聯(lián)規(guī)則的網絡數(shù)據(jù)動態(tài)聚類方法。通過對網絡數(shù)據(jù)屬性的分析，建立關聯(lián)規(guī)則，并在此基礎上確定網絡數(shù)據(jù)的值函數(shù)，實現(xiàn)網絡數(shù)據(jù)的動態(tài)聚類。實驗表明，該方法在改善聚類效果方面具有一定的優(yōu)勢。

關鍵詞： 網絡數(shù)據(jù);動態(tài)聚類;關聯(lián)規(guī)則

中圖分類號：TP391 ? ? ?文獻標識碼：A

文章編號：1009-3044（2021）32-0051-02

隨著網絡規(guī)模的不斷擴大和網絡數(shù)據(jù)的激增，網絡數(shù)據(jù)的碎片化和高度非結構化給網絡數(shù)據(jù)的挖掘和聚類帶來了挑戰(zhàn)，使其成為近年來學術界研究的熱點。例如，用戶瀏覽網站后留下的各種各樣的信息和數(shù)據(jù)，使得網絡數(shù)據(jù)迅速膨脹，在由此形成的網絡數(shù)據(jù)庫中，可以實時分析挖掘出用戶的個性化需求和興趣，以及用戶的職業(yè)、年齡、教育背景、地域等信息，對這些信息進行聚類分析，可以獲得網絡輿論和用戶態(tài)度等統(tǒng)計數(shù)據(jù)。但是，傳統(tǒng)聚類方法動態(tài)聚類效果差、耗時長，為此，本文提出了一種基于關聯(lián)規(guī)則的網絡數(shù)據(jù)動態(tài)聚類方法，利用網絡數(shù)據(jù)屬性進行關聯(lián)分析，確定網絡數(shù)據(jù)的值函數(shù)，實現(xiàn)網絡數(shù)據(jù)的動態(tài)聚類。實驗表明，該方法可有效改善聚類效果。

1 網絡數(shù)據(jù)屬性

當通用告警轉換為模糊告警的時候，模糊告警項的模糊支持度[X]定義為：

[fsupportX=1ni=1nj=1，k∈Fxjmμfiksij] ? ? ? ? ? ? ? ? ?（1）

其中：[n]為事件數(shù)量，[m]為集合X的元素個數(shù)，表[μfiksij]顯示了告警[j]與[X]關于模糊集[k]經過[i]轉換之后的關系。如果給定兩個集合[X=x1，x2，...，xp]和[Y=y1，y2，...，yq]，支持度和可信度的轉換關系[X?Y]定義如下;

[fsupportX?Y=1ni=1nj=1，k∈Fxjpμfjksij∧j=1，k∈Fyjqμfjksij] ? ? （2）

[fconfidenceX?Y=fsupportX?YfsupportXY] ? ? ? ? ? ? ? ? （3）

通過在模糊集中引入模糊關系度，加入模糊頻率集的特征以滿足向下封閉規(guī)則，也就是模糊頻率集的子集必須具有模糊頻率特性。

[I=i1，i2，...，im]表示模糊告警數(shù)據(jù)庫中的所有告警集，[S]為一個[k-]項目集[（k

[FS，n=ij∈Sμj+j=1n-kμij] ? ? ? ? ? ? ? ? ? ? ? ? ? ? （4）

其中，[ij∈Suj]表示項目集[S]中的[k]個模糊關系度之和，[j=1n-kμij]表示除去[S]后的具有最大關系度的前[n-k]個早期告警的模糊關系度之和。根據(jù)最小模糊支持度，支持[n-]項目集S的頻率項的數(shù)量不能太低：

[CS，n=fminsup×TFS，n] ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （5）

其中，[fminsup]表示所有支持k-項目集s的閾值的最小值。

因此，在聚類過程中，必須根據(jù)網絡數(shù)據(jù)的屬性分別進行處理。成員是這種屬性的函數(shù)關聯(lián)關系。通過上面的分析，成員表達式可修改為如下形式：

[u*ik=uikpik] ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（6）

其中，[uik]是成員函數(shù)，[pik]是網絡數(shù)據(jù)屬性對成員函數(shù)的貢獻。

2 動態(tài)聚類分析

2.1關聯(lián)規(guī)則

在網絡數(shù)據(jù)之間存在許多未知的關聯(lián)，關聯(lián)分析可以獲得很多有價值的結果。

（1）事件及項目集合：分別用[D]和[I]表示，此處[D=d1，d2，...，dx，...dn]，[I=i1，i2，...，iy，...in]。

（2）項目集：一個條目集是所有條目集合的任意子集。[k]表示任意條目集中的條目數(shù)量，則該條目集為[k]條目的集合。若包含在每個事件中的條目集是[I]的子集，那么：

[dx=i1，i2，...，ik，1≤k≤m]

（3）支持：表示在[D]中[X]和[Y]共存的概率。當D中項目集[X]存在的概率大于集合支持閾值，意味著[X]是一個高頻率項目集。這種情況下，支持閾值就是最小支持。[k]頻率項目集可利用[Lk]來描述。

（4）可信度：當[D]中共存項目集[X]和[Y]時，表明[D]中[Y]的頻度包含了[X]的頻度。在計算可信度的過程中，通常采用最小值作為可信度的預設值，也稱為最小可信度。

（5）關聯(lián)規(guī)則：可通過邏輯表達式[X→Y]來描述，[X]和[Y]為中所有項目的集合，其中[X?Y=Φ]。[X→Y]的強度可通過支持和[X→Y]的可信度來描述。

2.2 值函數(shù)

假定仿真控制的有限狀態(tài)為：

[Z=T，I，O，μ，η] ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （7）

其中：[T]表示狀態(tài)集;[I]和[O]分別表示輸入和輸出集;[μ]和[η]分別表示狀態(tài)轉換函數(shù)和輸出轉換函數(shù)。

假設節(jié)點[i]的狀態(tài)變量為[si]，當節(jié)點與其相鄰節(jié)點通信時，[si]表示在多場景交互處理中的各種物理量。當所有節(jié)點的狀態(tài)變量都一致的時候，該模型就達到了一致收斂。下面為連續(xù)時間一致性算法公式：

[sit=-j∈Nnθijsit-sjt] ? ? ? ? ? ? ? ? ? ? ? ? ?（8）

在公式中，[n]表示模型中迭代的次數(shù);[θij]表示在節(jié)點連接仿真結構圖中的鄰接矩陣中所有數(shù)據(jù)對應的元素。對于任意特征J，由于其在數(shù)據(jù)表示中具有不同的意義，他具有不同的權值[wj]。矢量模型的基本思想通過矢量[W1，W2，W3，...，Wn]來表示。有許多算法可用于計算權值[wj]，通常用[TF-IDF]公式計算：

[wj=kfk，d×log2Nnjk∈d1+log2kfk，d×Nnk] ? ? ? ? ? ? ? ? ? ? ? ?（9）

其中，[nj]為網絡數(shù)據(jù)特征項的權值，[nk]為網絡數(shù)據(jù)特征項目的個數(shù)，N為網絡數(shù)據(jù)特征總數(shù)，[kfk，d]為相同網絡數(shù)據(jù)同時存在的特征的數(shù)量。網絡數(shù)據(jù)特征的相似性[x]和[y]可通過以下公式計算：

[Simx，y=x·yxy] ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （10）

其中：[x]為網絡數(shù)據(jù)特征[x]的屬性矢量，[y]為網絡數(shù)據(jù)特征[y]的屬性矢量，[xy]為屬性矢量單元，[·]為點積。

基于時間抽樣的序列可以相等的時間間隔記錄網絡數(shù)據(jù)特征存儲的位置：

[T=e1，y1，t1，...，...，ei，yi，ti，...，...，en，yn，tn，...ti=t1+（i-1）Δt] ? ? ? ? ? ? ?（11）

其中[ei，yi1≤i≤n]為在[ti]時刻網絡數(shù)據(jù)對象的空間位置，[Δt]為網絡數(shù)據(jù)存儲的時間間隔，兩個存儲空間[Ti]和[Tj]的間隔計算公式為：

[DTWTi，Tj=0m=0∧n=0dispi1，pj1+DTWRtm≠0∧n≠0∞m=0∨n=0] ? ? （12）

其中，[m]和[n]分別為網絡數(shù)據(jù)存儲空間[Ti]和[Tj]包含的網絡數(shù)據(jù)的數(shù)量;[dispi1，pj1]為[Ti]和[Tj]的第一個點之間的歐拉距離;[Rt]為網絡數(shù)據(jù)特征存儲的第一個點之后的剩余時間。

在分類之前，需要定義一個值函數(shù)用于確定當分類算法的停止點。以傳統(tǒng)分類算法定義的值函數(shù)如下：

[V=j=1cVj=j=1cxi∈gjcdisxi，cj] ? ? ? ? ? ? ? ? ? ?（13）

其中：[cj]為網絡數(shù)據(jù)中心;[disxi，cj]為任意網絡數(shù)據(jù)對象[xi]和數(shù)據(jù)庫中心[cj]之間的距離。

與k-均值算法不同，模糊c-均值算法將網絡數(shù)據(jù)集分為多個模糊子集，利用關系矩陣來表達每個元素歸屬于每個群的程度：

[V=j=1cxi∈gjfmijdisxi，cj2] ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （14）

其中：[m]為模糊聚類算法的模糊度。

2.3 動態(tài)分類

為了獲得值函數(shù)的最小值判據(jù)，可利用拉格朗日乘數(shù)法來產生一個新的目標函數(shù)：

[V（F，c1，...，cc，λ1，...，λn）=i=1cλij=1cfij-1fmijdisxi，xj] ? ? ? （15）

模糊c-均值聚類算法目標函數(shù)的約束條件如下：

[JECMU，V=k=1Ni=1Cuikmxk-vi2] ? ? ? ? ? ? ? （16）

[s.t.i=1Cuik=1k=1，2，...，N] ? ? ? ? ? ? ? ? ? ? （17）

其中，[uik]為網絡數(shù)據(jù)[uk]與以[vi]為中心的屬性[i]的關聯(lián)度，[0≤uik≤1]， [ui=ui1，ui2，...，uiN]， [1≤i≤C]。

假設內部類的分散矩陣[Sb]和[Sw]表示每一個屬性點與屬性集的關系，則每一個屬性點及其所屬的類的關系為：

[Sb=i=1cnimi-mmi-mT] ? ? ? ? ? ? ? ? ? ? （18）

[Sw=i=1cj∈clanimi-xjmi-xjT] ? ? ? ? ? ? ? ? ? ? （19）

其中[c]為網絡數(shù)據(jù)集的分類的數(shù)目，[ni]為具有屬性[i]的網絡數(shù)據(jù)的數(shù)量， [mi]為具有屬性[i]的網絡數(shù)據(jù)的平均距離，[m]為所有網絡數(shù)據(jù)點之間的平均距離，[xj]為第[j]個采樣值。為了使低維度空間中各類網絡數(shù)據(jù)集之間的距離更小/更大，通過以下方式獲取聚類函數(shù)：

[JFw=wTSbwwTSww] ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（20）

3 實驗結果分析

在對改進的聚類算法進行性能測試的時候，實驗平臺為Weka6.0，采用Java語言實現(xiàn)。采用純度作為聚類方法的評價指標。聚類純度用來衡量網絡數(shù)據(jù)聚類處理的準確率：

[Purity=i=1kMaxjMijH] ? ? ? ? ? ? ? ? ? ? ? ? ? ? （21）

其中，[H]為網絡數(shù)據(jù)的量，[Mij]為具有屬性[i]和[j]的網絡數(shù)據(jù)，[k]為網絡數(shù)據(jù)聚類算法中的類的總數(shù)。

在實驗中，將文獻[2]、文獻[3]和文獻[4] 采用的方法與本方法進行了對比，不同動態(tài)聚類方法的純度見表1。

由表1可以看出，本文使用的方法純度值約為0.951，比文獻[2]高約0.105，比文獻[3]高0.256，比文獻[4]高0.308，整體純度高，聚類效果好。

4 結論

實驗結果表明，本文提出的基于關聯(lián)規(guī)則的網絡數(shù)據(jù)動態(tài)聚類方法具有較高的聚類純度，在提高動態(tài)聚類效率方面有一定的優(yōu)勢。

參考文獻：

[1] 鐘耀霞，程建斌，項正山.傳感網絡局部離群數(shù)據(jù)動態(tài)聚類算法仿真[J].計算機仿真，2020，37（11）：312-315，421.

[2] 姜延文.大數(shù)據(jù)分析下多維離散數(shù)據(jù)高效聚類方法仿真[J].計算機仿真，2019，36（2）：205-208.

[3] 楊慧婷，楊文忠，殷亞博，等.基于深度信念網絡的K-means聚類算法研究[J].現(xiàn)代電子技術，2019，42（8）：145-150.

[4] 葉福蘭.基于離群點檢測的不確定數(shù)據(jù)流聚類算法研究[J].中國電子科學研究院學報，2019，14（10）：1094-1099.

[5] 張?zhí)A，胡小光，楊靜.一種基于關聯(lián)規(guī)則的知識推送方法[J].機械設計與制造，2020（2）：300-303.

【通聯(lián)編輯：唐一東】