第一步，閱讀《機器學習》（周志華）的第九章聚類，主要圍繞3個問題展開描述

1、聚類可以解決哪類問題？

聚類本身適用的問題場景：分類，以及其它問題的數據處理前序步驟，或者回歸。即可以是單獨過程，也可以是其他學習演算法的前驅過程，故聚類可以用作其他過程的前序處理，整體思路應該是通的。但聚類是否對數據有要求呢，因為我的數據是時序數據，是有固定順序的數據。我認為，數據雖是時序數據，但可以認為第一個週期的數據和第8個週期的數據是一個簇，但和第2個週期的數據不屬於一個簇，我感覺這樣正常，即完全可以使用聚類。

2、如何評價聚類的效果好壞？

兩個方法，一是經驗值對比法，外部指標法對比法：JC指數、FMI指數、Rand指數，三者的值都是在[0,1]，值越大越好。二是內部指標法，即固定的指標值計算，DBI係數和DI係數（根據距離推導）

距離的選擇：閔可夫斯基距離（歐拉距離是其特殊情況），VDM距離，；連續變數適用閔可基，離散變數適用VDM，混合的就可以兩個混合使用。但問題來了，我的時序數據是屬於連續的嗎（是時序，但非實時），連續該怎麼理解呢？，如果把連續和離散的區別理解為，不是離散就一定是連續，離散變數的數據的值域不可限定的，故時序數據不是離散數據，那麼就可以理解為連續數據。再者是時間本身就是連續的，那麼其指標值必然也是連續的，但是我們只是按特定週期去取的而已，如果我把特定的規律的週期看做是新的時間維度，那麼該序列就是連續數據。

3、聚類的常用演算法思路：

a.從數據本身出發，即認為數據中是有代表性的樣本，即可以根據數據本身自動分簇。由此產生的演算法有K均值演算法，學習向量量化、高斯混合聚類。

b.從數據特徵出發：基於密度的聚類演算法，如DBSCAN演算法

c.從一般性出發，層次聚類演算法，如AGENS演算法（需要預設聚類的簇數）

總結：從演算法的設計思路來看，我的數據應該沒有代表性的樣本，也無法設定確定數目的簇個數，最合適的反而是密度法。那麼問題來了，如何定義密度，計算出來後可以通過比值的方式去確定自身是不是異常，那麼怎麼定義相對密度，超出多少為異常，有沒有優化的超參數處理方法。

第二步，從問題出發，選定密度演算法，LOF演算法介紹：Local Outlier factor

LOF演算法參考學習材料：blog.csdn.net/bbbeoy/ar

該演算法是基本可以理解為是由概念構成的，概念定義完了，演算法也就出來了。其特點就是不依賴數據本身的分佈特徵（如3-sigma法依賴數據的正態分佈），而且可以通過密度量化數據的異常程度，並非只有異常或正常。

關於密度的定義：點P的與它K-neibors的平均距離的倒數。那麼怎麼定義它的鄰居們，怎麼纔算是鄰居們，其實是按距離來計算的，K-distance實際上就是在畫圈

1、K-鄰近距離：點P的周圍點中，第K近的點與P之間的距離。標準定義如下：

K-鄰近距離（k-distance）：在距離數據點 p 最近的幾個點中，第 k 個最近的點跟點 p 之間的距離稱為點 p 的 K-鄰近距離，記為 k-distance (p) 。

2、可達距離：點P與點O之間的可達距離是兩者的實際距離與P的k-distance的最大值。標準定義如下：

可達距離（rechability distance）：可達距離的定義跟K-鄰近距離是相關的，給定參數k時， 數據點 p 到 數據點 o 的可達距離 reach-dist（p, o）為數據點 o 的K-鄰近距離 和 數據點p與點o之間的直接距離的最大值。即：

3、局部可達密度，就是通過距離畫了圈圈，而後定義具體的密度值，就是可達距離範圍內的點的平均距離的倒數。標準定義如下：

局部可達密度（local rechability density）：局部可達密度的定義是基於可達距離的，對於數據點 p，那些跟點p的距離小於等於 k-distance（p）的數據點稱為它的 k-nearest-neighbor，記為 $N_k(p)$，數據點 p 的局部可達密度為它與鄰近的數據點的平均可達距離的倒數，即：

4、關於異常程度的定義，是相對密度，即點和點的局部可達密度比較。標準定義如下：

局部異常因子（local outlier factor）：根據局部可達密度的定義，如果一個數據點跟其他點比較疏遠的話，那麼顯然它的局部可達密度就小。但LOF演算法衡量一個數據點的異常程度，並不是看它的絕對局部密度，而是看它跟周圍鄰近的數據點的相對密度。這樣做的好處是可以允許數據分佈不均勻、密度不同的情況。局部異常因子即是用局部相對密度來定義的。數據點 p 的局部相對密度（局部異常因子）為點p的鄰居們的平均局部可達密度跟數據點p的局部可達密度的比值，根據局部異常因子的定義，如果數據點 p 的 LOF 得分在1附近，表明數據點p的局部密度跟它的鄰居們差不多；如果數據點 p 的 LOF 得分小於1，表明數據點p處在一個相對密集的區域，不像是一個異常點；如果數據點 p 的 LOF 得分遠大於1，表明數據點p跟其他點比較疏遠，很有可能是一個異常點。

演算法落地的步驟：

1、計算每個數據點與其他數據點的距離，並由近及遠排序

2、定義K

3、找到K-nearest-neighbor，計算LOF

演算法問題：

1、當存在K個重複的點時，即沒法畫圈求密度，這時候的密度是無窮大，在實際應用時，為了避免這樣的情況出現，可以把 k-distance 改為 k-distinct-distance，不考慮重複的情況。或者，還可以考慮給可達距離都加一個很小的值，避免可達距離等於零。

2、演算法要計算每個數據點之間的距離，時間複雜度為$O(n^2)，為此產生了優化演算法，比如FastLOF，先將數據集化成多個小子集，計運算元集的LOF，異常的先剔除，而後重新找鄰居，再更新lof值。


推薦閱讀：
相關文章