一種基于非獨立同分布下K-means算法的系統日志分析方法

摘要：系統日志作為記錄系統操作和事件信息的重要資源，對保障系統安全和優化系統性能具有至關重要的作用。利用K-means算法進行系統日志分析能夠幫助管理員對日志進行分類管理，通過對相似日志條目的自動聚類，提高日志檢索和管理的效率。傳統K-means聚類算法一般采用歐氏距離作為相似性度量方法，該方法忽略了對象屬性之間存在的耦合關系，是假設數據具有獨立同分布的特性的，然而在現實的數據中，對象屬性之間會存在一些復雜的耦合關系，是非獨立同分布的。文章提出一種基于非獨立同分布下K-means算法的系統日志分析方法，以非獨立同分布的思想進行相似性度量。實驗結果表明該方法能夠獲得較高的準確率和較低的聚類執行時間。

關鍵詞：非獨立同分布；K-means算法；日志分析；相似性度量；耦合關系

中圖分類號：TP391

文獻標志碼：A

0 引言

隨著信息技術的不斷發展，大數據時代的到來使得系統日志數據量急劇增加，系統日志已經成為一種非常重要的數據形式。系統日志是記錄系統、應用程序或網絡設備活動的重要數據源，通過對日志數據進行分析，可以為系統運行狀態、故障排查、性能優化和安全審計提供關鍵信息。為了進行有效的日志分析，需要經歷收集日志、解析日志和數據存儲等步驟。通過收集各種來源的日志數據，可以建立全面的日志庫，方便后續的分析。對收集到的日志數據進行解析處理，將其轉化為結構化的格式，以便后續的分析。將解析后的日志數據存儲到適當的存儲系統中，如關系型數據庫、NoSQL數據庫或日志管理平臺。在分析階段，可以應用數據挖掘技術、統計分析、機器學習和人工智能等方法，深入挖掘日志數據背后的價值信息。根據分析結果生成報告和可視化圖表，幫助用戶更直觀地理解和利用分析結果，提供決策支持和改進系統性能或安全性，提升整體運營效率。

系統日志分析是一項復雜而重要的工作，通過規范的日志處理流程和有效的分析方法，可以充分挖掘日志數據所蘊含的有價值信息，為系統管理和運維工作提供強有力的支持。聚類分析作為一種無監督的機器學習方法，在數據分析領域發揮著重要作用。特別是K-means算法，由于其算法簡潔、易于實現且可解釋性強，成為最常用的聚類方法之一。在系統日志分析領域，K-means算法可以應用于多個方面，它能夠幫助管理員對日志進行分類管理，通過對相似日志條目的自動聚類，提高日志檢索和管理的效率。能夠識別出日志中的正常行為模式，進而通過對比分析，有效定位潛在的異常或入侵行為，為系統的安全防護提供支持。還可以輔助進行系統性能評估，通過對日志數據中的性能指標進行聚類，幫助發現系統性能瓶頸，指導系統優化決策。當前，已有許多聚類分析算法應用于日志分析，例如：Liu等^［1］提出了使用MapReduce的網絡日志分析聚類優化算法，然而在處理大規模網絡日志數據時，會面臨計算速度慢、磁盤I/O開銷大的問題。Ghamdi等^［2］提出了使用Spark的聚類處理方法等。目前，使用的對日志分析方法都是建立在獨立同分布基礎上的，然而，現實中的數據對象屬性之間是非獨立同分布的，數據對象屬性之間會存在一些復雜的耦合關系^［3］。這種關系在現有的計算對象屬性相似性方法中大多都被忽略了。鑒于這種情況，文章在考慮了對象屬性之間的相互關系的基礎上，以非獨立同分布的思想為基礎進行相似性度量，更加符合現實中數據的特性。這種方法能夠實現對相似日志條目進行高效聚類，提高日志檢索和管理的效率，同時降低聚類處理執行時間。

1 K-means算法

K-means算法是一種常用的基于劃分的無監督學習算法，用于將n個樣本數據集劃分成k個簇。其基本思想是通過不斷迭代的方式將數據點劃分到k個簇中，使得每個數據點與其所屬簇的中心點之間的距離平方和最小化，K-means算法的執行流程如下：

步驟1 隨機選取k個數據對象作為初始中心點，k表示簇的數目。

步驟2 計算所有數據對象與中心點之間的距離，將每個數據對象劃分到與其相似度最接近的中心點。通常采用計算數據對象之間的歐氏距離作為相似性度量方法。

步驟3 對于每個簇，重新計算簇中心，通常是簇中所有點的均值。

步驟4 重復循環執行步驟2和步驟3，直到準則函數收斂為止，準則函數表示如公式（1）所示。

其中，k是聚類簇的個數，m是簇中數據對象的個數，O_ij是第i個類簇中第j個數據將對象，C_i是第i個簇的均值。

在K-means算法中，通常采用樣本之間的距離來表示樣本之間的相似性。2個樣本之間的距離越大，表示2個樣本越不相似，差異性越大。2個樣本之間的距離越小，表示2個樣本越相似，差異性越小。不同的相似性度量函數會對聚類結果產生影響。由于K-means聚類算法是基于歐式距離作為相似性度量的，這種度量方法在實際應用中存在一定的缺陷。例如：歐氏距離將向量各個維度之間的差異等同對待，而實際情況下樣本屬性的重要程度往往不同。歐氏距離對異常值和噪聲數據點比較敏感，這些異常值可能影響簇的形狀和大小，從而影響聚類結果的準確性。因此，選擇合適的相似性度量標準是影響聚類分析結果的關鍵因素，不同標準會導致不同聚類效果，必須根據具體需求選擇適合的度量標準。研究學者從多個方面研究了相似性度量方法，比如：王熙照等^［4］提出了一種間接的學習權值算法，改進了歐氏距離同等看待樣本中所有特征值的不足。劉寶生等^［5］利用負相關系數加權歐氏距離可以充分體現屬性在聚類中的重要性，提高了聚類效果。宋宇辰等^［6］通過優化傳統K-means聚類算法的相似性度量，劃分的樣本點現在由已聚類的所有樣本點共同決定。衛俊霞等^［7］將光譜相似度匹配算法融到K-means算法中，形成一種新的光譜分類算法，找出2條距離最遠的光譜作為參考光譜，用歐氏距離法或夾角余弦法對數據立方體進行分類。

2 非獨立同分布下K-means算法

在傳統K-means算法中，采用計算距離的方法作為相似性度量，假設數據對象屬性之間是獨立同分布的，在計算相似性時，沒有考慮到數據對象屬性之間可能存在一些復雜的耦合關系，這樣會導致在計算相似性時產生一定的誤差，進而直接影響聚類結果。2011年操龍兵首次提出非獨立同分布的思想。隨后，許多研究者將其應用于各種領域。Wang等^［8］在無監督學習中提出了耦合名義上的相似性度量來代替傳統的歐氏距離度量。Jian等^［9］為無監督學習定義了一個耦合度量相似度，它具有靈活性，能捕獲從值到屬性到對象的異構耦合關系，適應非獨立同分布的數據。因此，基于非同分布的思想，利用耦合關系進行相似性度量是可行的。

2.1 相似性計算

建立一個對象屬性耦合關系表，能夠更直觀地展現對象屬性之間的關聯。從表1中可以明顯看出，每個數據集包含多個數據對象，每個數據對象都帶有多個屬性，而每個屬性又具有不同的屬性值。在表中，各對象屬性之間可能存在相互關系。例如：屬性a₁包含的屬性值A₁、A₂、A₃、A₄、A₅之間相互關聯，形成屬性值之間的耦合關系。此外，屬性a₁也可能受其他屬性的影響，即屬性之間相互關聯，形成屬性間耦合關系。因此，在計算對象間相似性時，須要全面考慮屬性內部和屬性間的耦合關系。

設數據集合為U={U₁，U₂，…，U_n}，表示包含n個對象的非空數據集合，A={A₁，A₁，…，A_m}，表示每個對象包含的m個屬性，V=∪ⁿ_j-1V_j，表示對象對應所有屬性值集合，其中，V_j是屬性A_j的一組屬性值，f=Uⁿ_i-1f_i（f_i：U→V_i）表示屬性值和對象之間關系的映射函數集合。

（1）定義信息函數。

信息函數用于從表中提取信息，根據信息函數F^*（U_i）可以知道對象U₁，U₂在A₂屬性上的值分別是V₁₂和V₂₂，通過函數G^*（V_i）確定A₂屬性值為V₁₂時的對象U₁。

（2）屬性A_j中的任意2個屬性值V_xj和V_yj之間內部耦合屬性相似性IaASV（Intra-coupled Attribute Similarity for Values）為：

δ^Ia_j（V_xj，V_yj）=|g_j（V_xj）|·|g_j（V_yj）||g_j（V_xj）|+|g_j（V_yj）|+|g_j（V_xj）|·|g_j（V_yj）|（4）

其中，g_j（V_xj）=｛U_j|V_ij=V_xj，1≤j≤m，1≤i≤n｝是屬性A_j所包含屬性值V_xj的所有對象的集合，|g_j（V_xj）|是集合中包含的對象個數。IaASV表示屬性值頻率之間的關系，頻率越接近屬性值越相似。

（3）基于屬性A_k的屬性A_j的任意2個屬性值V_xj和V_yj之間值的屬性間耦合相似性IeASV（Inter-coupled Attribute Similarity for Value）為：

δ^Ie_j（V_xjV_yj）=∑nk=1，k≠jα_kδ_j|k（V_xjV_yj）（5）

其中，屬性a_k的權重表示為α_k，∑nk=1，k≠jα_k=1，α_k∈［0，1］。

①δ_jk為基于交集的相互耦合相對相似性IRSI（Inter-coupled Relative Similarity Based on Intersection Set） 計算公式為：

②α_k是屬性A_k的權重參數，利用互信息求取權重矩陣對A_k賦值，計算公式為：

R=I（A_i，A_j·）H（A_i）+H（A_j·）（7）

其中，I（A_i，A_j·）是屬性A_i和A_j的互信息，計算公式為：

I（A_i，A_j）=∑V_j∈A_j∑V_i∈A_ip（V_i，V_j）logp（V_i，V_j）p（V_i）p（V_j）（8）

（4）屬性A_j的屬性值V_xj和V_yj的對象的耦合屬性值相似性 （CASV）為：

δ^A_j（V_xj，V_yj）=δ^Ia_j（V_xj，V_yj）*δ^Ie_j（V_xj，V_yj）（9）

其中，δ^Ia_j表示的是存在于屬性內部的耦合關系，δ^Ie_j表示的是存在于屬性之間的耦合相似性。

（5）2個對象U_x和U_y的對象耦合相似性（CASO）公式為：

CASO（U_x，U_y）=∑nj=1δ^A_j（V_xj，V_yj）（10）

其中，V_xj和V_yj分別是對象U_x和U_y的屬性A_j的屬性值，δ^A_j是耦合屬性值相似性。

計算相似性的步驟為：

Step1 根據公式（4）計算屬性A_j的任意2個屬性值V_xj和V_yj的性值的內部耦合屬性相似性IaASV。

Step2 計算屬性值V_xj和V_yj基于交集的相互耦合相對相似性的屬性間耦合相似性IeASV。

Step3 根據用公式（9）計算對象間耦合屬性值相似性CASV，利用公式（10）計算對象耦合相似性（CASO）。

2.2 算法描述

非獨立同分布下K-means算法具體步驟如下：

Input：數據集，聚類類別數k。

Ouput：劃分好的k個類別。

Step1：在數據集中選取k個樣本點C=｛c₁，c₂，…，c_k｝，作為初始簇類中心。

Step2：針對數據集中每個樣本點，根據2.1方法計算它到k個簇類中心的耦合相似性并將其歸屬到相似性最大的簇類中心所對應的類中。

Step3：針對每個簇類，重新計算每個簇的簇類中心，將每個簇類中所包含樣本點的均值作為新的中心點。

Step4：重復迭代執行Step2和Step3，直到聚類準則函數收斂，算法結束并輸出k個簇類劃分結果。

3 實驗結果

3.1 實驗數據

為了驗證文章所提方法的有效性，分別對2個數據集進行了實驗，主要從聚類結果的準確性和聚類處理的執行時間2個方面入手，旨在比較非獨立同分布下K-means算法與傳統K-means算法效果。

（1）為驗證非獨立同分布下K-means算法的準確率，實驗選擇在UCI數據集上進行驗證，選自UCI中非常具有代表性的鳶尾花數據集（Iris），其中，包含150個樣本對象，每個對象都有鳶尾花的花蕊長度和寬度以及花瓣長度和寬度4個屬性，樣本數據被分成3個品種的鳶尾花，分別山鳶尾（Setosa）、 雜色鳶尾（Versicolour）和維吉尼亞鳶尾（Virginica）。

（2）為了檢驗非獨立同分布下K-means算法的執行效率，實驗選自某公司系統服務器日志數據，選取其中10萬條日志數據，每條數據包含源系統日志中7個重要屬性，分別是日志ID、時間戳（Times tamp）、線程（Thread ID）、日志級別（Level）、類（Class）、包（Passage）、日志事件（Massage），數據大小約為385MB。實驗所用數據集信息如表2所示。

3.2 實驗結果及分析

文章利用非獨立同分布的思想，深入分析數據對象屬性之間的耦合關系，改進傳統K-means算法進行相似性度量時忽略對象屬性之間的關聯性的不足，提出新的相似性計算方法。實驗分別在Iris標準數據集和某公司系統服務器日志數據集上對改進算法的準確率及性能進行驗證。

3.2.1 Iris數據集實驗結果分析

實驗將傳統的K-means算法和非獨立同分布下K-means算法的準確率進行比較。在相同實驗環境下，2種算法各運行10次并進行比較。結果顯示，在傳統K-means算法運行10次時，準確率最高為84.00%，最低為56.32%；而改進后的算法運行10次時，準確率最高為93.89%，最低為73.59%。顯然，非獨立同分布下K-means算法在對數據集進行聚類的準確性高于傳統K-means算法。實驗結果證明非獨立同分布下K-means算法是有效的。聚類準確率比較結果如表3所示。

3.2.2 某公司系統服務器日志數據實驗結果分析

實驗將傳統的K-means算法和非獨立同分布下K-means算法的聚類執行時間進行比較，對比了數據集中100條數據、1000條數據、10000條數據和100000條數據的執行時間。在相同實驗環境下，2種算法在執行時間上存在明顯差別。從圖1中可以看出，非獨立同分布下K-means算法在不同規模數據集上的聚類執行時間均明顯低于傳統的K-means算法。實驗結果表明，基于非獨立同分布下K-means算法在系統日志聚類分析中節省了執行時間。

4 結語

文章提出一種基于非同分布下K-means算法的系統日志分析方法并對傳統K-means算法中相似性度量方法進行了分析。在傳統K-means聚類算法中，通常采用歐氏距離作為相似性度量方法，該方法假設數據對象之間滿足獨立同分布特性，這種假設方式計算的距離無法準確反映對象之間的相似程度，直接影響聚類結果的準確性。文章在非同分布思想的指導下深入分析了對象屬性之間的耦合關系并將這種耦合關系作為相似性度量的方法。通過文章提出的方法，彌補了傳統K-means算法在相似性度量方面的不足。實驗結果表明，基于非同分布下K-means算法的系統日志分析方法具有較高的準確率，能夠快速準確地對相似日志條目進行聚類，提高日志檢索和管理的效率。

參考文獻

［1］LIU X J，YUAN J B，CAO F P.Data distribution K-means clustering for cloud computing［J］.Journal of Chinese Computer Systems，2017（4）：712-715.

［2］GHAMDI S A，FATTA G D.Efficient clustering techniques on Hadoop and Spark［J］.International Journal of Big Data Intelligence，2019（3）：269-290.

［3］李方方.非獨立同分布推薦系統研究［D］.北京：北京理工大學，2014.

［4］王熙照，王亞東，湛燕.學習特征權值對K—均值聚類算法的優化［J］.計算機研究與發展，2003（6）：869-873.

［5］劉寶生，閆莉萍，周東華.幾種經典相似性度量的比較研究［J］.計算機應用研究，2006（11）：1-3.

［6］宋宇辰，張玉英，孟海東.一種基于加權歐氏距離聚類方法的研究［J］.計算機工程與應用，2007（4）：179-180.

［7］衛俊霞，相里斌，高曉惠，等.基于K-均值聚類與夾角余弦法的多光譜分類算法［J］.光譜學與光譜分析，2011（5）：1357-1360.

［8］WANG C，DONG X，ZHOU F，et al.Coupled attribute similarity learning on categorical data［J］.IEEE Transactions on Neural Networks amp; Learning Systems，2015（4）：781-797.

［9］JIAN S，CAO L，LU K，et al.Unsupervised coupled metric similarity for Non-IID categorical data［J］.IEEE Transactions on Knowledge and Data Engineering，2018（9）：1810-1823.

（編輯 王永超）

System log analysis method based on K-means algorithm within non-independent and identical distribution

XIE Qingqing

（Shandong Open University， Jinan 250100， China）

Abstract：As an important resource for recording system operation and event information， system logs play a vital role in ensuring system security and optimizing system performance. The K-means algorithm can help administrators classify and manage logs， and improve the efficiency of log retrieval and management through automatic clustering of similar log entries. The traditional K-means clustering algorithm generally uses Euclidean distance as a similarity measurement method， which ignores the coupling relationship between object attributes， and assumes that the data has the characteristics of independent and identical distribution， but in the real data， there will be some complex coupling relationships between object attributes， which are non-independent and identically distributed. In this paper， a system log analysis method for K-means algorithm within non-independent identical distribution is proposed， and the similarity is measured by the idea of non-independent identical distribution. Experimental results show that the K-means algorithm based on non-independent identical distribution proposed in this paper can obtain high accuracy and low clustering execution time.

Key words：non-independent and identical distribution; K-means algorithm; log analysis; similarity measures; coupling relationship