孤立核（Isolation Kernel）函數(shù)是一種具備自適應(yīng)數(shù)據(jù)局部密度分布的相似度度量方法至会。其可以收縮放大不同區(qū)域中數(shù)據(jù)點(diǎn)間的相似度，即同樣兩個(gè)數(shù)據(jù)點(diǎn)矮慕，放在密度較高的地方帮匾，其相似度就會(huì)變低，反之痴鳄，這兩個(gè)點(diǎn)放在密度較低的地方瘟斜，其相似度就升高。換句話(huà)說(shuō)就是增加低密度區(qū)域里物體之間的相似度夏跷，降低高密度區(qū)域里物體之間的相似度哼转。這樣一來(lái)在不同區(qū)域里面的數(shù)據(jù)密度分布差異就被減小了明未，也就達(dá)到了類(lèi)似密度歸一化的目的槽华。由于很多基于密度或距離計(jì)算的機(jī)器學(xué)習(xí)方法對(duì)數(shù)據(jù)密度分布非常敏感，這種相似度度量方法可以顯著增加他們?cè)诜诸?lèi)趟妥，聚類(lèi)和異常檢測(cè)任務(wù)上的性能猫态，我之前發(fā)布的文章對(duì)此也有初步講解。
孤立核函數(shù)的核心思想是，以數(shù)據(jù)樣本點(diǎn)為基準(zhǔn)切分?jǐn)?shù)據(jù)空間得到Ψ個(gè)子空間（cell）亲雪，數(shù)據(jù)的A和B的相似度的就數(shù)是這倆個(gè)點(diǎn)切進(jìn)同時(shí)一個(gè)子空間的概率勇凭。下圖為數(shù)學(xué)公式表達(dá):
為了具備自適應(yīng)的特性，孤立核函數(shù)的計(jì)算過(guò)程采取了基于樣本數(shù)據(jù)的空間切割的方法义辕。其首先隨機(jī)從數(shù)據(jù)樣本中抽取Ψ個(gè)點(diǎn)樣本虾标，然后以每個(gè)樣本點(diǎn)為基準(zhǔn)切分?jǐn)?shù)據(jù)空間。切分的方法有很多種灌砖，比如用維諾圖璧函，超球，超立方體等基显，只要這個(gè)切分后的每個(gè)子空間（cell）符合倆個(gè)特征：1. 切分后的每個(gè)子空間都沒(méi)有交集（non-overlapping）蘸吓；2. 子空間占據(jù)的體積大小由原始數(shù)據(jù)密度分布決定，由于越密的地方采樣點(diǎn)越多撩幽，則密度高的區(qū)域子空間越多體積即越小库继。
基于蒙特卡洛的方法，以上切分?jǐn)?shù)據(jù)空間的操作可以獨(dú)立重復(fù)次窜醉。比如獨(dú)立重復(fù)切分空間100次宪萄，發(fā)現(xiàn)A和B同時(shí)在一個(gè)子空間的次數(shù)為8次，則A到B的相似度為8%=0.08榨惰，A到B的距離（相異度）為0.92雨膨。由于數(shù)據(jù)分布越密集的地方會(huì)被劃分得越多，那么A和B如果在這些地方读串，則他們更容易掉進(jìn)不同的子空間里面而得到更小的相似度聊记。
核函數(shù)的原理就是把數(shù)據(jù)先映射到某個(gè)特征空間（希爾伯特空間），然后倆個(gè)數(shù)據(jù)點(diǎn)的相似度就是他們?cè)谶@個(gè)希爾伯特空間中特征的內(nèi)積恢暖。孤立核函數(shù)的計(jì)算過(guò)程也可以用核映射來(lái)表示排监，每次切完數(shù)據(jù)空間后，可以把每個(gè)子空間做標(biāo)記杰捂，然后用一組二元向量來(lái)表示需要計(jì)算相似度的數(shù)據(jù)點(diǎn)舆床，如下圖所示。這些向量拼接起來(lái)就是孤立核特征值嫁佳“ざ樱可以發(fā)現(xiàn)
和
的內(nèi)積就是他倆向量中同時(shí)都為1的個(gè)數(shù)，即x和y掉進(jìn)同一個(gè)子空間的次數(shù)蒿往。
就是歸一化后的概率盛垦，也可以做為相似度來(lái)當(dāng)作之后的不同的數(shù)據(jù)挖掘任務(wù)輸入。
可以發(fā)現(xiàn)积蜻，經(jīng)過(guò)孤立核映射馒稍，每個(gè)數(shù)據(jù)都可以變成個(gè)維度的向量。但是如果該數(shù)據(jù)通過(guò)高斯核函數(shù)映射浅侨，理論上得到的是無(wú)限的維度的向量纽谒，目前的方法都是用采樣得到近似的有限維度。因此這個(gè)有限維度映射是孤立核函數(shù)的另一大優(yōu)點(diǎn)如输。
孤立核函數(shù)的作用是計(jì)算某倆個(gè)數(shù)據(jù)點(diǎn)直接的相似度鼓黔，如果需要計(jì)算一個(gè)數(shù)據(jù)點(diǎn)x到一個(gè)分布或者一組數(shù)據(jù)A之間的相似度，我們可以用點(diǎn)間平均相似度來(lái)表示：
這個(gè)過(guò)程可以描述為2步：
- 把數(shù)據(jù)點(diǎn)x和數(shù)據(jù)集A中的每個(gè)數(shù)據(jù)點(diǎn)都映射到孤立核空間不见，即每個(gè)點(diǎn)都變成
個(gè)特征的向量澳化。
- 計(jì)算x和A中的每個(gè)數(shù)據(jù)點(diǎn)在孤立核空間的平均內(nèi)積，即平均相似度稳吮。
其中第二步可以等價(jià)為首先計(jì)算A中的每個(gè)數(shù)據(jù)點(diǎn)在該孤立核空間的平均特征值即)缎谷，再用該均值
去算內(nèi)積。
以此類(lèi)推灶似，如果計(jì)算倆個(gè)分布或數(shù)據(jù)集之間的相似度列林，我們可以得到如下分布核函數(shù)公式：
這個(gè)過(guò)程可以描述為2步：
- 把數(shù)據(jù)集A和B中的每個(gè)數(shù)據(jù)點(diǎn)都映射到孤立核空間，即每個(gè)點(diǎn)都變成
- 計(jì)算A中每個(gè)點(diǎn)到B中每個(gè)點(diǎn)的平均相似度希痴。可以簡(jiǎn)化為先對(duì)數(shù)據(jù)集A和B分別求出其在孤立核空間的特征均值春感，即
砌创。然后得出
第二步如果用計(jì)算配對(duì)的平均相似度鲫懒，則計(jì)算量會(huì)到嫩实，其中n和m分別為數(shù)據(jù)集A和B的大小。如果先把數(shù)據(jù)集A和B在核空間求均值窥岩，再做內(nèi)積甲献，這樣計(jì)算量則減到線(xiàn)性即
。這樣一來(lái)谦秧，就可以通過(guò)孤立分布核函數(shù)設(shè)計(jì)線(xiàn)性復(fù)雜的的算法來(lái)處理海量數(shù)據(jù)的相似度計(jì)算竟纳。
下圖展示了，
,
分別映射到孤立核空間的三個(gè)點(diǎn)疚鲤，即每個(gè)集合中的數(shù)據(jù)在希爾伯特空間的均值锥累。如果要計(jì)算新數(shù)據(jù)x離哪個(gè)集合最相似，就是直接求
離哪個(gè)均值最近集歇，這種計(jì)算過(guò)程全是線(xiàn)性的復(fù)雜的桶略。基于此特性诲宇，我們目前發(fā)表了2篇聚類(lèi)文章际歼，第一個(gè)是psKC【1】，其是在靜態(tài)數(shù)據(jù)上首個(gè)理論上最快的線(xiàn)性聚類(lèi)算法姑蓝。需要注意k-means并不是線(xiàn)性的鹅心，它是因?yàn)橄拗屏说螖?shù)才能在大數(shù)據(jù)上面運(yùn)行。第二個(gè)算法是StreaKHC【2】纺荧，它是在流數(shù)據(jù)上首個(gè)理論上最快的層次聚類(lèi)算法旭愧。
對(duì)于異常分布檢測(cè)输枯，首先把每個(gè)分布用孤立核函數(shù)映射到希爾伯特空間并用均值作為代表。然后可以再一次用孤立核函數(shù)映射到希爾伯特空間占贫，然后用現(xiàn)有的檢測(cè)方法來(lái)找到異常點(diǎn)桃熄，這些異常點(diǎn)就是指代原始數(shù)據(jù)空間中的異常分布，如下圖所示【3】型奥。
此外坑匠，我們還可以把時(shí)間序列切片血崭，每個(gè)片段當(dāng)作一組數(shù)據(jù)或一種分布，然后計(jì)算每個(gè)片段到其他片段的相似度厘灼。那些和大部分其他片段相似度很低的片段就是異常片段夹纫，示例如下圖。于是乎设凹，我們開(kāi)發(fā)了目前最快的時(shí)間序列異常檢測(cè)方法【4】舰讹，該方法打破了100多年來(lái)在時(shí)間序列上僅有的時(shí)域和頻域方法的一種范式轉(zhuǎn)變。
參考文獻(xiàn)
【1】Ting, Kai Ming, Jonathan R. Wells, and Ye Zhu. "Point-set kernel clustering." IEEE Transactions on Knowledge and Data Engineering (2022).
【2】Han, Xin, et al. "Streaming hierarchical clustering based on point-set kernel." Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022.
【3】Ting, Kai Ming, et al. "Isolation distributional kernel: A new tool for kernel based anomaly detection." Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020.
【4】Ting, Kai Ming, et al. "A new distributional treatment for time series and an anomaly detection investigation." Proceedings of the VLDB Endowment 15.11 (2022): 2321-2333.
