1.基本介紹
現實世界中，很多資料的次元非常高，許多傳統的異常檢測方法在高維資料中無法有效工作。這也叫次元災難/次元詛咒/次元懲罰。
在高維空間中，當進行全維分析時，資料變得稀疏，真正的異常值被多個不相關維數的噪聲效應所掩蓋。
次元災難的一個主要原因是在高維情況下，難以定義一個點的相關局部性。例如，在高維空間中，所有點對幾乎是等距的。這種現象被稱為資料稀疏或距離集中。而異常值是定義為稀疏區域中的資料點，這導緻了一種鑒别性差的情況，即所有資料點都位于幾乎相同的稀疏區域中，具有全次元。
1.1 局部相關次元
局部相關次元：一個物體可能有幾個被測量的量，這個物體的顯著異常行為可能隻反映在這些量的一小部分中。
也即，一小部分的測量的資料中可能可以找到異常值，因為資料次元不高，但是當來自測量的資料以全次元表示時，異常資料點将在幾乎所有資料視圖中顯式為正常。即大量正常測量的噪聲變化将掩蓋異常值。
是以，異常值通常嵌入到局部相關的子空間中。
是以，探索低維子空間以獲得感興趣的偏差是有意義的。這種方法過濾掉了大量維數的加性效應，并導緻了更健壯的異常值。
1.2 投影異常值檢測 / 子空間異常值檢測
在缺少屬性值的資料集中，這種低維投影也經常可以被識别。這對于許多實際問題是有用的。因為很多情況下，特征提取是一個困難的過程，并且通常存在不完整的特征描述。
例如，在機身故障檢測中，可能隻應用了一個測試子集，是以隻有一個次元子集的值可以用于異常分析。
這種模型稱為投影異常值檢測，或叫做子空間異常檢測。
1.3 相關子空間的識别
相關子空間的識别是一個非常具有挑戰性的問題。 這是因為高維資料的可能投影數與資料的維數呈指數關系。 一種有效的離群點檢測方法需要對資料點和維數進行綜合搜尋，以揭示最相關的離群點。 這是因為不同的次元子集可能與不同的異常值相關。
一般來說，為每個資料點選擇一個單一的相關子空間會導緻不可預測的結果，是以，将來自多個子空間的結果組合起來是很重要的。換句話說，子空間的異常檢測本質上是一個以集合為中心的問題。
1.4 識别子空間的幾類常用方法
基于稀有性：
這些方法視圖從底層分布的稀有性來發現子空間。這裡的主要挑戰是計算，因為在高維中，稀有子空間的數量遠遠大于密集子空間的數量。
無偏：
在這些方法中，子空間是以無偏的方式采樣的，并且分數被組合在采樣的子空間上。
當子空間從原始屬性集采樣時，該方法稱為特征袋。
在任意定向的子空間被采用的情況下，該方法被稱為旋轉袋或旋轉子空間采樣。
雖然這些方法很簡單，但是通常工作的很好。
基于聚合的方法：
在這些方法中，聚合統計 (如資料的全局或局部子集的聚類統計、方差統計或非均勻統計) 用于量化子空間的相關性。
與基于稀有的統計不同，這些方法量化了全局或局部參考集的統計屬性，而不是試圖直接識别很少填充的子空間。
由于這類方法僅提供弱提示（且易于出錯）來辨別相關子空間，是以采樣多個子空間是至關重要的。
2.Axis-Parallel Subspaces軸-并行子空間（組合多個子空間采樣）
2.1 基本介紹
Axis-Parallel Subspaces，中文翻譯過來是“軸-平行子空間”，首先來看這種方法具體是什麼意思，“軸”指的是資料軸，比如我們在二維坐标系上的x, y軸。“平行”, 指的是和資料軸平行的資料集，通俗來講就是資料的總體分布是和軸平行的。當然，這是在低維資料空間中可以使用該方法。
在軸-平行子空間方法中，異常值是由軸-平行子空間定義的。在這些方法中，是在原始資料的特征子集中定義一個異常值。然後需要仔細量化這樣才能比較各個子空間的得分。除此之外，還需要量化各種子空間在暴露異常值方面的有效性的方法。
軸-平行方法使用的方法有兩個主要變化：
第一類方法：逐個點地檢測，并确定其相關的外圍子空間。這本質上是一種基于執行個體的方法。顯然，計算上是昂貴的。但是該方法提供了細粒度的分析，也助于提供内涵知識（即解釋一個點為什麼是異常點）。
第二類方法：通過預先建立子空間模型來識别異常值。通過模型對每個點進行評分。在某些情況下，每個模型可能對應于單個子空間。分數通常是通過使用不同模型獲的結果的內建分數來評分的。組合分數往往會增強分數的局部子空間特性，因為內建方法（內建學習）能夠減少表示偏差。
這類方法如特征袋、旋轉袋、子空間直方圖和隔離森林。
在子空間分析中，基于內建的分析是很重要的。由于來自不同子空間的異常值分數可能有很大的不同，是以通常很難完全信任來自單個子空間的分數，組合多個子空間的結果分數是很重要的。
本章主要探讨的是利用組合多個子空間的優點的幾種方法。
2.2 異常檢測的遺傳算法
子空間異常值是通過在低維空間中找到具有異常低密度的資料局部區域來識别的。
可以利用遺傳算法來尋找這種局部子空間區域。然後，異常值由它們在這些區域的成員組成來定義。
2.2.1 定義異常低維投影
為了識别異常的低維投影，重要的是要提供适當的統計資料來定義異常的低維投影。
異常的低維投影是指資料密度特别低于平均值的投影。
可以使用基于網格的方法來識别稀疏填充的局部子空間區域。
2.2.2 定義子空間搜尋的遺傳算子
由于指數計算的複雜性，對所有子空間進行詳盡的搜尋是不切實際的。 是以，需要一種選擇性搜尋方法，它将大部分子空間修剪。 這個問題的本質是，在滿足稀疏條件的基于網格的子空間上沒有向上或向下封閉的屬性。 在頻繁的模式挖掘等其他問題中，這些屬性經常被利用。 然而，與頻繁的模式挖掘不同，在頻繁的模式挖掘中，人們正在尋找頻率較高的模式，尋找次元的稀疏子集的問題具有在幹草堆中找到針頭的味道。
（選擇————交叉————變異）
2.3 尋找基于距離的外圍子空間
書中一開始提到了HOS-Miner算法，這裡有一篇論文《HOS-Miner: A System for Detecting Outlying Subspaces of High-dimensional Data》專門講這個算法用于檢測高維資料中的外圍子空間，附上論文連結（https://eprints.usq.edu.au/5654/1/Zhang_Lou_Ling_Wang_VLDB%2704_AV.pdf）
資料X的外圍子空間的定義：
For a given data point X , determine the set of subspaces such that the sum of its k -nearest neighbor distances in that subspace is at least δ . 對于一個給定的資料點X，确定子空間的集合，使得它在該子空間中的K最近鄰距離之和至少為δ。
随着維數的增加，子空間更有可能是外圍的。
可以利用不同剪枝特性和遺傳算法尋找外圍子空間。
2.4 特征袋：一種子空間采樣的視角
組合來自多個子空間的異常值的最簡單的方法是使用特征袋，這是一種內建方法（內建學習：三個臭皮匠，賽過一個諸葛亮）。
內建的每個基本元件使用以下步驟：
第一步：随機從（d/2）到(d−1)中選擇一個整數r。【注：（d/2）是向下取整】
第二步：從疊代t中的底層資料集随機選擇r特征（不替換），以便在第t次疊代中建立r維資料集Dt。
第三步：将離群點檢測算法Ot應用于資料集上，以便計算每個資料點的得分。
總結以下就是：在定義域内随機選擇整數r，然後選擇r個特征以建立資料集Dt，最後将異常檢測算法運用在該資料集上，并計算每個資料點的得分。
原則上，在每次疊代中，可以使用不同的離群點檢測算法，前提是在過程結束後将分數歸一化為Z值（Z值計算：減去均值再除以标準差）。 規範化也是必要的，以解釋不同的子空間樣本包含不同數量的特征。 然而，有研究者也使用LOF算法（局部異常因子）進行所有疊代。
在過程結束時，組合來自不同算法的離群點分數有以下兩種可能的方式之一：
廣度優先方法：在這種方法中，算法的排序用于組合目的。 在所有不同的執行中，排名第一的異常值被排在第一位，其次是排名第二的異常值（删除重複），以此類推。 由于某一特定等級内的異常值之間的連接配接斷裂，可能存在微小的變化。
累加和方法：彙總了不同算法執行的離群點分數。 排名靠前的離群點在此基礎上被檢測出來。 人們還可以将此過程視為等同于內建方法（內建學習）中的平均組合函數。
子空間采樣可以對大量子空間進行采樣，以提高魯棒性。
使用內建方法可以降低表示的偏差。
2.5 投影聚類集合
Projected clustering methods defifine clusters as sets of points together with sets of dimensions in which these points cluster well.
1、【投影聚類方法将聚類定義為點的集合（一組點）和次元集合（一組次元），這些次元中的點可以很好地聚類。】
在第四章提到聚類和異常檢測是互補關系。那是否也可以将投影或子空間聚類用于異常檢測。
使用投影聚類算法的集合進行異常檢測：
1.在資料集上使用像PROCLUS這樣的随機投影聚類方法來建立一組投影叢集。
2.根據每個點與它所屬的簇的相似度，量化其離群值。 相關分數的示例包括大小、尺寸、到群集質心的（預計）距離或這些因素的組合。 正确的度量選擇對所使用的特定聚類算法敏感。
了解這種基于聚類的方法的關鍵點是，雖然以內建為中心的方法對于成功至關重要，但是發現的異常值類型對底層聚類很敏感。 是以，局部敏感的聚類內建将使離群點局部敏感。 一個對子空間敏感的聚類集合将使離群值對子空間敏感，而對相關敏感的聚類集合将使離群值對相關性敏感。
2.6 線性時間的子空間直方圖
具有散列的子空間直方圖的線性時間，并稱為RS-Hash。基本思想是在大小為s的資料樣本上重複建構基于網格的直方圖，并以內建為中心的方法組合分數。每個直方圖都建構在資料的随機選擇子空間上。子空間的維數和網格區域的大小特定于其集合分量的。在內建元件的測試階段，根據網格區域中（來自訓練樣本的）點數的對數對資料中的所有N點進行評分。對多個大小為s的樣本重複該方法。将針對特定點的分數在不同的內建元件上取平均值，以建立最終結果，該結果非常可靠。網格區域的尺寸和大小的變化由整數維數參數r和分數網格大小參數f∈（0，1）控制，它們在不同的內建分量中随機變化。
2.7 隔離森林
隔離森林也是用于聚類的極随機聚類森林(ERC-Fore st)的特例。
隔離森林是一組隔離樹的集合組合。在隔離樹種，使用軸-平行切割在随機選擇的屬性中的随機選擇的分區點上對資料進行遞歸分區，以便将執行個體隔離到具有越來越少執行個體的節點中，直到将這些點隔離成包含一個執行個體的單例節點。在這種情況下，包含異常值的樹枝的深度明顯較小，因為這些資料點位于稀疏區域中。是以，将葉子到根的距離用作異常值。通過平均隔離森林的不同樹中資料點的路徑長度來執行最終組合步驟。
還有另一篇比較通俗易懂的部落格基于孤立/隔離森林的異常檢測。
2.8 選擇高對比度的子空間（HiCS）
特征袋中讨論了随機樣本子空間，如果許多元度是不相關的，那麼至少有幾個次元很可能包含在每個子空間樣本中。同時，由于許多元度被丢棄，導緻資訊丢失。這些影響不利于方法的準确性。是以，是否有可能執行一個預處理，其中選擇少數量的高對比度子空間。這種方法也被稱為HiCS，因為它是選擇高對比度的子空間。
高對比度子空間：當在子空間裡可以明确的分辨出離群點和其他資料對象時，将賦予該子空間很高的對比度值。
2.9 子空間投影的局部選擇
可以使用相關子空間投影的局部統計選擇來識别異常值。換句話說，子空間投影的選擇針對特定資料點進行了優化，是以給定資料點的位置在選擇過程中至關重要。
2.10 基于距離的參考集
有一種基于距離的方法，用于在資料的低維投影鐘尋找離群點。在這種方法中，不是試圖在整個資料中找到異常低密度的局部子空間，而是針對每個資料點提供局部分析。對于每個資料點X，識别一個點S(X)的參考集。參考集S(X)被生成為最接近候選點的頂部k點，使用共享最近鄰距離。
3 .廣義子空間（即任意定向的子空間）
3.1 基本介紹
盡管軸平行方法對于在大多數實際設定中查找離群值有效，但在點沿資料的任意低維流形對齊的情況下，對查找離群值不是很有用。 例如，在下圖圖5.4的情況下，二維資料中沒有一維特征可以找到離群值。 另一方面，可以找到局部的一維相關子空間，以便大多數資料沿着這些局部的一維子空間對齊，并且剩餘的偏差可以分類為離群值。 盡管此特定資料集由于其維數較低而似乎相對容易檢測到異常值，但是随着維數的增加，此問題可能會變得更具挑戰性。
廣義子空間算法是由以下兩個思想來推廣的：
基于PCA的線性模型可以發現資料中的全局相關區域。例如，在上圖5.3的情況下，可以通過确定這些全局相關方向來有效地識别異常值。然而，圖5.4中沒有這種全局相關方向。
當資料沿着低維的軸-平行子空間的簇自然對齊時，軸-平行子空間方法可以很好地發現異常值。但是，在圖5.4中，其中的資料是沿任意相關方向對齊，這種情況下，軸-平行子空間方法無法有效工作。
廣義子空間分析的目标是結合上面兩種算法的思想。
即，發現異常值的同時還要确定任意定向子空間。
3.2 廣義投影聚類方法
“廣義”通俗來講就是資料是任意定向的。在廣義投影聚類方法中，聚類是在資料的任意對齊子空間中識别的，以确定除了叢集之外的異常值。顯然，異常值就是和叢集不一緻的資料。
使用該方法的主要目的是确定叢集，在查找異常值方法不是特别高效。
該方法有時可能發現的是弱異常值，即噪聲資料。
對于如何正确區分弱異常值（噪聲資料）和強異常值（真正的異常），最簡單的方法是計算每個候選離群點到每個聚類質心的局部馬氏距離。
3.3 利用特定執行個體參考集
為了确定針對特定資料點的局部性進行優化的異常值，關鍵是确定針對正在評分的候選資料點X進行優化的局部子空間。
這種子空間的确定是不平凡的，因為通常不能從資料的局部聚集屬性中推斷出它，以檢測罕見執行個體的行為。
最近提出了一種使用參考集在廣義子空間中尋找異常值的方法。與較早的廣義子空間聚類方法的主要差別在于，局部參考集特定于各個資料點，而聚類提供了一組固定的參考集，用于對所有點進行評分。這種靈活性的代價是，找到每個點特定參考集的運作時間為O(N)，是以該方法需要O(N^2)時間進行評分。
3.4 旋轉子空間采樣（旋轉袋）
旋轉子空間采樣是一種內建方法，它改善了特征袋。這種方法也成為旋轉袋。
特征袋是為了發現軸-平行子空間中的異常值，旋轉袋是為了發現廣義子空間中的異常值。
因為旋轉袋是一種內建方法，是以可以使用任何現成的異常檢測算法（如LOF）作為基檢測器。
旋轉袋的基本思想：
旋轉袋的基本思想是在低維空間中對随機旋轉的子空間進行采樣，并在這個低維空間中對每個點進行評分。各個子空間的分數可以組合起來。該方法使用維數為 r =2+ （√ d/2) 的子空間，這比特征袋中使用的子空間的典型維數低得多。這是因為旋轉袋運作不同程度地從所有次元捕獲資訊。這也有助于擷取多樣性的子空間，進而提高整體得分的品質。
旋轉袋算法流程：
1. 确定資料中随機旋轉的軸系統
2.從旋轉軸系統中采樣r=2+(√ d/2) 方向。沿着r個方向投影資料。（r個随機旋轉軸需要互相正交，就像在PCA中一樣。）
3.在投影資料上運作基離群值檢測器以及存儲每個資料點的異常值分數。
擷取了每個點的不同預測的分數後，可以使用平均或最大值進行組合最後分數。
如上圖5.6所示，通過綜合兩個試圖，可以通過平均或最大值擷取A和B的最後分數。
這個例子也說明內建方法如何克服單個檢測器中的表示偏差，以便提高一個更通用的模型。這也是內建學習的内容。
3.5 非線性子空間
子空間異常檢測最艱難的情況是資料流形存在于任意形狀的低維子空間中。如下圖5.7所示。
從上圖可以看到，任意形狀的簇可以存在于低維資料流形中。
面對上面這種情況，需要使用适當的局部非線性變換。這種提取是使用譜方法/譜嵌入(Spectral methods)實作的，也可以看作是一類特殊的核方法（其專門針對非線性的情況），它對發現任意形狀的簇是比較有效的。
在這裡，譜嵌入和K近鄰檢測器組合使用。
3.6 回歸模組化技術
可以使用回歸模型進行子空間異常檢測，方法是識别違反屬性依賴性的點。
基本思想是将一個 d 維無監督異常檢測問題分解為一組 d 回歸模組化問題。
我們可以使用現成的回歸模型預測剩餘的 (d-1) 個屬性的每個屬性。對于每個執行個體，彙總預測各種屬性的評分誤差以建立異常值分數。
4.子空間方法的探讨
高維異常檢測分析的困難的主要原因是一些維數的局部噪聲和無關性質的掩蓋效應，這也往往表現為在距離上的集中。即在高維稀疏資料中，正常資料和異常資料的距離非常難判斷。
目前在文獻中主要研究是局部特征相關和距離集中這兩個方面。
局部無關屬性：
是以，通過使用全維距離度量，很難有效地确定異常值，因為噪聲和無關次元的平均行為。此外，不可能先驗地修剪特定的特征，因為不同的點可能顯示不同類型的異常模式，每個模式使用不同的特征或視圖 。
正是因為高維資料中全維特征選擇的無效性，導緻了局部特征選擇或局部降維方法。
噪聲和無關屬性更有可能導緻距離的集中。
異常值通常是由少量次元的行為來定義的。
有許多高維資料集，其中一個可以通過更簡單的全維算法執行有效的孤立點檢測。 特定算法在全維資料集上的有效性取決于應用場景和提取特征的方式。 如果在提取特征時考慮到特定的異常檢測場景，那麼全維算法可能會很好地工作。 盡管如此，子空間分析往往會發現異常值，而這些異常值不容易被其他全維算法發現。
事實上，子空間分析不應該被看作是一種獨立的方法，而應該被看作是一種內建方法，以提高各種類型的基探測器的性能。
無論是開發一種用于高維孤立點檢測的特定基礎方法（如子空間直方圖)，還是将其封裝在現有檢測器(如特征和旋轉套袋）上，将這一原理納入孤立點檢測中都有明顯的好處。 此外，子空間分析提供了關于異常因果關系的有用見解；人們可以使用相關的局部子空間來提取對相關特征的特定組合的了解。
當異常值存在于少量局部相關次元時，子空間分析尤其有效。
在設計子空間方法時需要記住以下原則：
1、直接探索稀有區域是可能的，盡管由于組合爆炸，它在計算上具有挑戰性
2、基于聚合的方法隻提供有關子空間的弱提示。 這些方法的主要力量僅在于通過将來自不同子空間的結果組合在一起的中心設定。
3、內建的組成部分的設計應考慮到效率因素。 這是因為有效的元件能夠實際使用更多的元件以獲得更好的精度。
一個有趣的觀察是，即使使用弱基探測器，組合它們往往會産生非常強的結果（三個臭皮匠，賽過諸葛亮）。 特征袋、子空間直方圖和旋轉袋等方法的成功是基于這一事實。 請注意，在每種情況下，底層基檢測器不是特别強；但最終的離群點檢測結果是非常有效的。 在高維孤立點檢測和內建分析領域的最新進展是非常重要的。 盡管取得了這些進展，許多高維資料集仍然是孤立點分析的挑戰。
5.總結
子空間方法用于異常檢測的情況下，一個資料點的異常傾向被大量局部非資訊次元的噪聲效應稀釋。 在這種情況下，通過搜尋資料點明顯偏離正常行為的子空間，可以顯著地銳化異常分析過程。 最成功的方法為候選離群點識别多個相關子空間，然後将來自不同子空間的結果組合起來，以建立一個更健壯的基于內建的排序。