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

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

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

中圖分類號：TP391

文獻標志碼：A

0 引言

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

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

1 K-means算法

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

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

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

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

步驟4 重復循環(huán)執(zhí)行步驟2和步驟3，直到準則函數(shù)收斂為止，準則函數(shù)表示如公式（1）所示。

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

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

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

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

2.1 相似性計算

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

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

（1）定義信息函數(shù)。

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

（2）屬性A_j中的任意2個屬性值V_xj和V_yj之間內(nèi)部耦合屬性相似性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）|是集合中包含的對象個數(shù)。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的權(quán)重表示為α_k，∑nk=1，k≠jα_k=1，α_k∈［0，1］。

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

②α_k是屬性A_k的權(quán)重參數(shù)，利用互信息求取權(quán)重矩陣對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表示的是存在于屬性內(nèi)部的耦合關系，δ^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 根據(jù)公式（4）計算屬性A_j的任意2個屬性值V_xj和V_yj的性值的內(nèi)部耦合屬性相似性IaASV。

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

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

2.2 算法描述

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

Input：數(shù)據(jù)集，聚類類別數(shù)k。

Ouput：劃分好的k個類別。

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

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

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

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

3 實驗結(jié)果

3.1 實驗數(shù)據(jù)

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

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

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

3.2 實驗結(jié)果及分析

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

3.2.1 Iris數(shù)據(jù)集實驗結(jié)果分析

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

3.2.2 某公司系統(tǒng)服務器日志數(shù)據(jù)實驗結(jié)果分析

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

4 結(jié)語

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

參考文獻

［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，F(xiàn)ATTA G D.Efficient clustering techniques on Hadoop and Spark［J］.International Journal of Big Data Intelligence，2019（3）：269-290.

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

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

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

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

［7］衛(wèi)俊霞，相里斌，高曉惠，等.基于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