基于關聯規則的網絡數據動態聚類方法研究

王喆 宋曉峰 王玉芳

摘要：針對傳統聚類方法動態聚類效果差、耗時長的問題，提出了一種基于關聯規則的網絡數據動態聚類方法。通過對網絡數據屬性的分析，建立關聯規則，并在此基礎上確定網絡數據的值函數，實現網絡數據的動態聚類。實驗表明，該方法在改善聚類效果方面具有一定的優勢。

關鍵詞： 網絡數據;動態聚類;關聯規則

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

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

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

1 網絡數據屬性

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

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

其中：[n]為事件數量，[m]為集合X的元素個數，表[μ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）

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

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

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

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

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

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

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

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

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

2 動態聚類分析

2.1關聯規則

在網絡數據之間存在許多未知的關聯，關聯分析可以獲得很多有價值的結果。

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

（2）項目集：一個條目集是所有條目集合的任意子集。[k]表示任意條目集中的條目數量，則該條目集為[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）關聯規則：可通過邏輯表達式[X→Y]來描述，[X]和[Y]為中所有項目的集合，其中[X?Y=Φ]。[X→Y]的強度可通過支持和[X→Y]的可信度來描述。

2.2 值函數

假定仿真控制的有限狀態為：

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

其中：[T]表示狀態集;[I]和[O]分別表示輸入和輸出集;[μ]和[η]分別表示狀態轉換函數和輸出轉換函數。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 動態分類

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

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

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

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

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

其中，[uik]為網絡數據[uk]與以[vi]為中心的屬性[i]的關聯度，[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]為網絡數據集的分類的數目，[ni]為具有屬性[i]的網絡數據的數量， [mi]為具有屬性[i]的網絡數據的平均距離，[m]為所有網絡數據點之間的平均距離，[xj]為第[j]個采樣值。為了使低維度空間中各類網絡數據集之間的距離更小/更大，通過以下方式獲取聚類函數：

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

3 實驗結果分析

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

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

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

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

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

4 結論

實驗結果表明，本文提出的基于關聯規則的網絡數據動態聚類方法具有較高的聚類純度，在提高動態聚類效率方面有一定的優勢。

參考文獻：

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

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

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

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

[5] 張太華，胡小光，楊靜.一種基于關聯規則的知識推送方法[J].機械設計與制造，2020（2）：300-303.

【通聯編輯：唐一東】