《微軟亞研院的AIOps底層算法： KPI快速聚類》要點：
本文介紹了微軟亞研院的AIOps底層算法： KPI快速聚類，希望對您有用。如果有疑問，可以聯系我們。

導讀

智能運維中存在海量時序數據(KPI)需要監控、檢測異常、關聯, 而AIOps的一個底層算法就是把大規模時序數據快速準確地聚類成有限的若干類別,從而大大降低后續數據分析與挖掘工作的開銷.?其應用場景包括自動適配異常檢測算法、輔助標注、輔助構建故障傳播鏈等.?本文介紹的案例是由微軟亞洲研究院發表在數據庫領域頂級會議VLDB 2015的文章《Yading: Fast Clustering of Large-Scale Time Series Data》.

簡介

在大數據時代,快速、大規模的分析技術的重要性日益凸顯,人們利用這些技術完成實時和交互性任務中的數據分析工作.運維中常見的KPI數據是一種時間序列數據,它具有數據實例多、維度高的特點.為了降低數據分析工作的開銷,提高分析效率,人們希望將海量的時序數據曲線分為若干類別,從而減少需要考察的曲線數目.因此,如何對大規模的時間序列數據進行快速、準確的聚類是一個關鍵性問題.

本文中,作者設計了一套端到端的時序數據聚類算法Yading,實現了對大規模時間序列數據的高效、準確、自動化聚類.為驗證算法效果,作者在公開數據集上將Yading與若干傳統時序數據聚類算法進行對比,并在微軟的實際工業數據上對算法進行了測試,證明了Yading的高效性和分類準確性.

時序數據聚類的挑戰

• 時序數據數量大、維度高.運維中的時序數據集通常具有大量實例(如數百萬個),每個實例具有較高維度(如數千維),難以使用傳統的聚類方法進行快速聚類.
• 時序數據實例間的相似性難以準確刻畫.不同于簡單的數值型、類別型數據,時間序列數據上通常存在著相位擾動和隨機噪聲,使得對時序數據實例之間的相似性刻畫較為困難.不恰當的相似性度量會大大降低聚類的準確性.
• 聚類算法參數難以確定.許多聚類算法的效果和參數的選取有密切關系.面對大規模的時序數據,難以人工選取合適的參數.需要設計更智能的參數選擇方法.

設計思想

為應對上述挑戰,本文設計了一套端到端的時序數據聚類算法Yading,分以下三步實現大規模時序數據的快速、準確聚類,算法框架如下圖所示.

1. 輸入數據集采樣.對大量的時序數據進行隨機采樣,并使用逐段聚集平均(PAA)算法縮減每條時序數據實例的維度.用采樣后的數據集作為聚類算法的輸入.

2. 在采樣后的數據集上進行時序數據聚類.使用L1距離作為時序數據曲線間的相似性度量.在基于密度的聚類算法DBSCAN的基礎上,設計出多密度的聚類算法Multi-DBSCAN,并使算法能夠自動決定參數.

3. 對大量數據采用分派(assignment)策略進行分類.對于采樣中未被選擇的大量時序數據曲線,采用分派策略將其分到與其L1距離最近的已聚類曲線所屬的聚類簇中.同時建立了有序鄰居圖(Sorted Neighbor Graph, SNG)輔助計算時序數據實例之間的距離,提高分派算法的計算效率.

1、輸入數據集采樣

大規模的時序數據集中通常含有數以萬計的時序數據實例,每個實例上含有大量的數據點,直接對整個數據集進行聚類將帶來巨大的計算開銷.因此,本文通過隨機采樣和維度縮減的手段降低需要考察的實例數目和維度,將采樣后的數據集作為聚類模塊的輸入,降低計算開銷.

由于不需要對輸入數據的分布作任何假設,隨機采樣(random sampling)是一種減少數據實例個數的有效手段.采樣過程中需要遵循兩個原則：(1)每個類別的數據均在采樣集中出現至少m次.(2)采樣集中各類別數據所占比例與原數據集中的比例偏差不超過給定閾值ε.基于上述原則,作者采用數學方法推導出采樣數據集大小的上界和下界,對原始數據集進行隨機采樣.

對于每個時序數據實例,使用逐段聚集平均(Piecewise Aggregate Approximation,PAA)進行維度縮減.具體的,對于一條長度為D的時序數據,PAA將其劃分為d個幀(d<D),將每個幀用一個值(例如該幀上數據點的均值)表示,從而將時序數據的長度從D減小為d,達到降維的目的.

通過上述兩項操作,能夠從規模為N*D的原始數據集中獲得規模為s*d的采樣數據集(s≤N, d≤D),且采樣集保持原數據集的分布(underlying distribution)不變.用采樣集作為聚類模塊的輸入,大大降低了計算開銷.

轉載請注明本頁網址：
http://www.snjht.com/jiaocheng/1944.html