基于改進K-means算法的指標閾值告警方法研究

許 健，王 琪，唐海榮，韓少聰，張 弛，陳 梁，倪 洋

（南京南瑞信息通信科技有限公司，南京 211106）

0 引言

電網企業信息化運維系統在日益復雜的運維活動中扮演著重要角色，提升了信息運維工作水平和工作效率。其組件化的中臺設計可以有效降低系統耦合，提高基礎服務可復用性。被管IT資源可按以下分類：主機、數據庫、中間件、網絡、安全、存儲、虛擬化、服務、應用、機房環境等。各類資源下具有不同的指標，指標是對資源性能的數據描述或狀態描述。運維人員在監測某些指標的異常狀態時首先需要配置相應的閾值規則，當采集的指標數據不在閾值范圍內則判定為區間越界，需要及時產生告警并通知給運維人員。

面對大量復雜多樣的指標，運維人員手動錄入閾值規則往往依托經驗，一定程度上影響著告警準確性，并且重復勞動增加了運維負擔。當業務需求變化時，運維人員需要重新編輯之前的閾值規則，維護成本較高，閾值規則的靈活性較差。針對這些痛點，本文轉變靜態閾值的配置思路，引入簡單高效的K-means聚類分析方法，充分利用指標歷史數據分析產生各時段動態閾值的區間上下限，降低人工參與度，提高閾值告警規則配置的靈活性和告警的準確性。傳統K-means算法聚類數和中心點的選取缺乏明確標準定義［1］，改進隨機選取問題來優化算法聚類效果。

1 指標閾值告警

1.1 采集監測層次關系

電網企業信息化運維系統監測的資源指標數據由采集控制組件提供。采集控制組件基于各類采集插件，實現支持多級復雜主、子資源結構關系的安全設備、存儲設備、網絡設備、數據庫、虛擬化及大數據部分類型的組件數據采集。資源監測組件基于微服務架構接口規范為上層應用提供主機、數據庫、中間件、網絡設備、安全設備、存儲設備及云平臺等資源的狀態監測數據、性能數據及告警數據服務。采集監測的層次關系如圖1所示。

圖1中的異常告警及通知依賴于運維人員配置的指標閾值，實時采集的指標值存儲到消息總線上，兩者進行閾值規則匹配。比如CPU使用率大于95%時則產生告警等級為嚴重的告警，并對告警信息進行通知分發。

圖1 采集監測層次關系

1.2 傳統閾值告警配置流程

電網企業信息化運維系統在日常運維中需要由人工來錄入指標的閾值告警規則，配置過程中需要進行較多的頁面交互，主要流程如下：

（1）在系統菜單中進入告警策略管理頁面，在主資源類型下新增相應的告警策略，主資源類型包括服務器類、數據庫類、中間件類、網絡設備、鏈路、安全設備、云平臺等。

（2）點擊告警策略中的觸發條件藍色數字下鉆到該策略的資源與指標關聯列表頁面。主資源下包含許多子資源，不同主子資源又包含豐富的指標。

（3）點擊需要監測的指標中的觸發規則藍色數字下鉆到該指標的觸發規則配置頁面。配置閾值告警規則，填寫閾值上下限、持續時間、告警級別等表單信息，確認保存。

從整個流程來看，面對豐富的監測指標，一是交互多重復工作量大，二是對運維人員的經驗有一定要求。且當業務需求變化時，還需回到原表單處重新編輯閾值告警規則，維護成本較高，欠缺靈活性。

1.3 聚類分析指標閾值告警

聚類分析屬于無監督學習，常見的分類主要有基于層次的聚類算法、基于劃分的聚類算法、基于密度的聚類算法、基于網絡的聚類算法和基于模型的聚類算法［2］。

針對上節提到的問題，轉變靜態閾值的配置思路，從運維現場每五分鐘采集一次指標數據來看，有豐富的指標歷史數據可供使用，便可聚類分析出各時段指標的動態閾值上下限，降低人工參與度，提高閾值告警規則配置的靈活性和告警的準確性。

2 改進K-means算法

2.1 確定最佳聚類數的方法

2.1.1 手肘法

手肘法通過樣本聚類總誤差平方和SSE這一指標來表示樣本的聚合程度，其值越小表示類間樣本越緊湊。SSE的計算公式為

其中，Ci表示第i個類，n表示Ci中的樣本點，mi是Ci中所有樣本的均值。每個類的聚合程度會隨著聚類數k的增大而逐漸提高，樣本劃分越來越精細，誤差平方和SSE也會逐漸變小。在聚類初期，k小于真實聚類數，k的增大會迅速增加每個類的聚合程度，SSE的下降幅度也會很大；而當k到達真實聚類數時，再增大k時樣本聚合程度改變不會很大，SSE的下降幅度隨著k值的繼續增大而趨于平緩，即SSE和k的關系圖是一個手肘的形狀，而這個肘部對應的k值就是數據的真實聚類數。然而，SSE加和的方式會使得某些分類效果較差的類計算所得的類間誤差平方和被聚類效果較好的類間誤差平方和中和［3］，本文進一步結合統計學中的Gap Statistic方法來確定最佳聚類數。

2.1.2 Gap Statistic法

Gap Statistic的主要思想是計算每一類里各樣本兩兩之間歐式距離的平方和，并將其與構建的參考零均值均勻分布所得的聚類結果相比較，從而確定數據集的最佳聚類數目。當聚類數k為最優值時，Gap Statistic這個統計量達到最大值，也意味著此時的聚類結果與零均值均勻分布產生的數據的聚類結果差別最大。算法流程分為以下三步：

第1步：改變聚類數量k從1到kmax，計算不同k值對應的類內偏離和wk，計算公式為

其中Cr表示聚類得到的第r類，nr表示樣本個數，表示該類中所有樣本兩兩之間的距離和。

第2步：構建B個參考零均值均勻分布數據，改變聚類數量k從1到kmax，計算不同k值對應的類內偏離和wkb，b=1,2,…,B,k=1, 2, …,kmax。

第3步：對前兩步的類內偏離和取對數處理，二者比較后的差值作為Gap（k），計算公式為

2.2 確定初始聚類中心點的方法

傳統K-means算法在開始運行時初始聚類中心的選取是隨機的［4］，對聚類結果的影響較大。為了避免聚類中心陷入局部最優解，仿生智能優化算法的出現提高了K-means算法的全局搜索能力，比較流行的算法有螢火蟲算法、森林優化算法、遺傳算法等［5］。本文采用變步長螢火蟲算法的最優解作為初始聚類中心點。

2.2.1 螢火蟲算法

螢火蟲算法是一種基于群體的隨機搜索算法［6］。把空間各點看成螢火蟲，利用發光弱的螢火蟲受發光強的螢火蟲吸引的特點進行位置迭代，從而完成尋優過程。尋優過程和螢火蟲的相對亮度和相互吸引度有關。相對亮度用式（4）表示，相互吸引度用式（5）表示：

式（4）、式（5）中的γ為光吸收因子，一般情況下γ∈ [0.01,100]［7］，r為兩只螢火蟲間的歐式距離，I0表示r為0時的亮度，β0表示r為0時的吸引度，也即最大吸引度。發光越亮代表其位置越好，最亮螢火蟲即代表函數的最優解。發光越亮的螢火蟲對周圍螢火蟲的吸引度越高，同時與距離成反比，距離越大吸引度越小，若發光亮度一樣，則螢火蟲做隨機運動進行位置更新，假設Xj比Xi吸引度高，Xi位置更新計算公式為

其中α為步長因子，rand()為[-0.5,0.5]區間范圍內的隨機擾動［8］。

算法流程如下：

第1步：初始化算法參數：螢火蟲數量、光吸收因子、最大吸引度、步長因子和最大迭代次數；

第2步：計算初始位置處的螢火蟲目標函數值作為各自的最大熒光亮度；

第3步：計算螢火蟲群的相對亮度和相互吸引度，根據相對亮度判斷螢火蟲移動方向，更新位置；

第4步：根據更新后的位置，重新計算相對亮度；

第5步：當滿足最大迭代次數則輸出最優個體值，否則返回第3步繼續下一次尋優。

2.2.2 變步長螢火蟲算法

隨著迭代次數的增加，螢火蟲群會在最優值附近聚集［9］。此時螢火蟲個體與最優值之間的距離已經非常小，在個體向最優值趨近的過程中，很可能會出現螢火蟲移動的距離大于個體與最優值間距的情況，而導致個體更新自己位置時跳過了最優值，出現震蕩，將會導致最優值發現率降低，影響算法的收斂精度和速度。為了盡量避免由上述原因造成的收斂較慢情況，潘曉英等［10］采用自適應移動步長代替原有固定步長，通過螢火蟲種群的聚合程度令步長變化呈減小的趨勢，自適應移動步長計算公式為

其中α,為螢火蟲每一代的自適應步長因子，D(Ci)t+1為螢火蟲種群移動后的類間距離和。本文借鑒了該思想，在算法開始時，將初始步長設定為相對較大值，而后隨著迭代次數增加設定一個判定條件：當迭代次數達到最大迭代次數的一半時，用式（8）替代固定步長α，使其逐漸減小趨于0，第t次的步長因子為

其中e為自然常數，則螢火蟲算法將在開始時具有較好的全局尋優能力，迅速定位在接近全局最優解的區域，而后期也具有良好的局部搜索能力，能精確得到全局最優解。

2.3 改進K-means算法總結

聚類數和初始聚類中心點的選取對算法的結果有重要的影響。針對手肘法可能出現“肘點”不明確問題，進一步結合Gap Statistic確定出最佳聚類數；針對螢火蟲算法隨著迭代次數增加可能會在最優值附近出現震蕩的問題，改變步長因子來提高螢火蟲算法的全局尋優和局部搜索能力，將最優值作為K-means聚類算法的初始中心點。改進后的K-means算法流程如圖2所示。

圖2 改進K-means算法流程圖

3 實驗分析

3.1 實驗環境搭建

為驗證改進K-means算法的指標閾值告警方法，在電網企業某省公司信息化運維系統測試環境中進行數據測試。采集由五臺物理機組成，操作系統為centos7.5，配置為32核CPU，64 G內存，500 G硬盤。其中兩臺部署weblogic集群及jar包庫，三臺部署采集后臺服務。信息化運維系統采集控制組件和資源監測組件進行容器化部署。

3.2 實驗流程

第1步：對樣本個數為n的指標數據進行缺失值處理，缺失值采用該指標當天的平均值填充。

第2步：利用二分查找，計算[1,?n]范圍內不同k值下誤差平方和以及類內偏離和。

第3步：繪制出誤差平方和隨k值增加的變化趨勢，記錄誤差平方和減少趨勢不再明顯時的k1值。

第4步：計算樣本在均勻分布推斷下的平均類內偏離和。

第5步：計算樣本類內偏離和與平均類內偏離和的log差作為Gap Statistic。

第6步：繪制出Gap Statistic隨k值增加的變化趨勢Gap（k）函數，記錄Gap（k）max時的k2值。

第7步：比較第2步和第5步中的k值，如果兩者相等則將此k值作為樣本聚類個數，如果不等則k1不斷遞增1，取Gap（k1）最大時的k1作為樣本聚類個數。

第8步：設定變步長螢火蟲算法參數：綜合考慮精度和計算開銷，設定螢火蟲數量為，光吸收因子為0.5，最大吸引度為1，最大迭代次數為200，初始步長因子設定為0.95，當迭代次數達到100時，按式（9）減少步長因子，迭代直到收斂到最優解作為初始聚類中心點。

第9步：由第7步得到的最佳聚類數和第8步得到的初始聚類中心點進行K-means聚類分析，繪制結果。

3.3 結果分析

實驗指標數據選取CPU使用率，采樣周期為5分鐘，按天計，一天可采集24*60/5=288個CPU使用率數值，連續四周的工作日共計288*5*4=5760個樣本。檢查樣本數據中是否存在缺失項，若存在則采用該天的CPU使用率平均值填充缺失值。在anaconda3環境中啟動Jupyter Notebook后運行了python代碼，繪制出實驗流程第3步中的誤差平方和隨k值增加的變化趨勢，如圖3所示，第6步中的Gap Statistic隨k值增加的變化趨勢如圖4所示。

圖3 誤差平方和隨k值增加的變化趨勢

圖4 Gap Statistic隨k值增加的變化趨勢

由圖3、圖4可知，“肘點”的k值為4，Gap Statistic取最大值時的k值為4，故本次實驗的最佳聚類數為4，由實驗流程第8步求得的初始聚類中心點進行K-means聚類分析，結果如圖5所示，橫軸表示時間，進行歸一化處理后，范圍為0～23，單位為h，指代一天24小時；縱軸表示CPU使用率，范圍為0～100，單位為%。

圖5 CPU使用率聚類模擬實驗

從聚類結果來看，整個圖形近似呈現正態分布的特征，即業務活躍時段如早晨8點到下午5點，有著較高的網站訪問量、程序計算以及數據庫讀寫等操作，CPU使用率活動在20%～90%之間；而非業務活躍時段如非工作時段和夜間，網站訪問量降低后，機器的壓力也隨之減少，CPU使用率基本在20%以下。從時間段劃分來看，上午10點到下午4點之間，CPU使用率有較大概率大于60%，為了留有一定的富余量應對業務高峰，此時應將告警的閾值適當降低，例如大于80%則產生告警級別為警告的告警。綜上所述，通過改進后的K-means算法能夠聚類分析出各時段的動態閾值，由后臺微服務動態調整并與消息總線上采集的指標進行閾值規則匹配。電網企業某省公司現場運維運用新算法后，產生了更加精確的告警，降低了運維人員維護的工作量。

4 結語

電網企業信息化運維系統由人工配置指標閾值告警欠缺靈活性且重復工作量大，針對這一痛點，采用簡單高效的K-means聚類算法對指標歷史數據按時間進行劃分并由后臺微服務調整各時段的動態閾值。聚類數的設定和初始聚類中心點的選取對聚類結果有很大影響。針對手肘法可能出現“肘點”不明確問題，進一步結合GapStatistic確定出最佳聚類數；針對螢火蟲算法隨著迭代次數增加可能會在最優值附近震蕩問題，改變步長因子來提高螢火蟲算法的全局尋優和局部搜索能力，將最優值作為K-means聚類算法的初始中心點。通過電網企業某省公司信息化運維系統測試環境采集的CPU使用率歷史數據進行聚類分析實驗，結合業務特性分析了不同時段CPU使用率的閾值情況，實驗結果表明改進的K-means算法能有效分析出指標不同時段的閾值情況，從而可由后臺微服務調整動態閾值，減輕運維人員在系統中配置大量的指標閾值告警規則，降低了系統的運維成本，進一步提升了告警的準確性。