In-network PCA and anomaly detection閱讀筆記

論文：In-network PCA and anomaly detection. L. Huang, X. Nguyen, M. Garofalakis, M. I. Jordan, A. Joseph, and N. Taft. In B. Schoelkopf, J. Platt and T. Hofmann (Eds.), Advances in Neural Information Processing Systems (NIPS) 19, 2007

筆記：基于PCA做分布式網絡異常檢測，PCA是一種高維資料降維的利器，研究表明正常的網絡流量表面上是多元的，其實可以在低維空間表示。另外，研究表明，有異常的高維流量空間可以分解為兩個子空間，即 F=Fnormal+Fanomaly 。對高維流量空間的特征向量按照特征值從大到小排名，排名前 k 個的特征值的特征向量可以用來表示Fnormal，而異常流量則相應的，由剩餘的 n−k 個特征值來表征。上述過程，可以通過PCA算法來實作，前 k 個主成份對應正常流量，而後 n−k 個主成份對應異常流量。是以，可以通過PCA來進行異常檢測。

那麼，流量矩陣是如何生成的呢？有n個負責資料采集的Agent，每個時間步将更新的資料發送給中樞（Coordinator），并由中樞來生成流量矩陣。另外，中樞有個時間窗，時間窗的長度為m，每次隻從最近的m個時間步的資料中生成流量矩陣，是以該矩陣的次元為 m∗n 。現在的問題是，Agent如果數量很多，且采樣的粒度很細，那麼每個時間步中樞獲得的資料量将是巨大，并會生成一個很大的矩陣，實時運算的效率會很低，隻能做off-line的分析。有沒有辦法減少網絡開銷，并實作on-line的分析呢？這個問題也可以變為如何提高矩陣的PCA效率的問題。一方面可以從PCA算法着手，另一方面可以從矩陣着手——實作矩陣的稀疏化。In-network PCA and anomaly detection這篇文章正是從後者着手，基于這樣一個觀察：正常流量遠大于異常流量，而正常流量的資訊熵很低，沒有必要每個時間步都要把更新的資料彙報給中樞，可以設定一個範圍，在該範圍内可以不用彙報。那麼，由于彙報的資料少了，中樞生成的流量矩陣也變得稀疏，PCA的效率自然高。

但是，最難的是确定不用彙報的範圍，這個範圍可以用一個參數 Δ 來表征，即 [R−Δ，R+Δ] 。 Δ 大了，彙報的資料少了，那麼最終異常檢測的精确度 P 就低了。是以，如何在保證精确度P的前提下，實作自适應 Δ 的選擇，就是In-network PCA and anomaly detection這篇文章的最大貢獻。這篇文章基于随機噪聲矩陣的統計分析理論（a stochastic matrix perturbation analysis）給出了答案。