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

關(guān)鍵詞：非獨(dú)立同分布；K-means算法；日志分析；相似性度量；耦合關(guān)系

中圖分類號：TP391

文獻(xiàn)標(biāo)志碼：A

0 引言

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

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

1 K-means算法

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

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

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

步驟3 對于每個簇，重新計(jì)算簇中心，通常是簇中所有點(diǎn)的均值。

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

2 非獨(dú)立同分布下K-means算法

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

2.1 相似性計(jì)算

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

設(shè)數(shù)據(jù)集合為U={U₁，U₂，…，U_n}，表示包含n個對象的非空數(shù)據(jù)集合，A={A₁，A₁，…，A_m}，表示每個對象包含的m個屬性，V=∪ⁿ_j-1V_j，表示對象對應(yīng)所有屬性值集合，其中，V_j是屬性A_j的一組屬性值，f=Uⁿ_i-1f_i（f_i：U→V_i）表示屬性值和對象之間關(guān)系的映射函數(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表示屬性值頻率之間的關(guān)系，頻率越接近屬性值越相似。

（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） 計(jì)算公式為：

②α_k是屬性A_k的權(quán)重參數(shù)，利用互信息求取權(quán)重矩陣對A_k賦值，計(jì)算公式為：

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

其中，I（A_i，A_j·）是屬性A_i和A_j的互信息，計(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)部的耦合關(guān)系，δ^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是耦合屬性值相似性。

計(jì)算相似性的步驟為：

Step1 根據(jù)公式（4）計(jì)算屬性A_j的任意2個屬性值V_xj和V_yj的性值的內(nèi)部耦合屬性相似性IaASV。

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

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

2.2 算法描述

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

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

Ouput：劃分好的k個類別。

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

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

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

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

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

3.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

4 結(jié)語

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

參考文獻(xiàn)

［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］李方方.非獨(dú)立同分布推薦系統(tǒng)研究［D］.北京：北京理工大學(xué)，2014.

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

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

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

［7］衛(wèi)俊霞，相里斌，高曉惠，等.基于K-均值聚類與夾角余弦法的多光譜分類算法［J］.光譜學(xué)與光譜分析，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