浅说孤立分布核函数（Isolation Distribution

孤立核（Isolation Kernel）函数是一种具备自适应数据局部密度分布的相似度度量方法。其可以收缩放大不同区域中数据点间的相似度，即同样两个数据点，放在密度较高的地方，其相似度就会变低，反之，这两个点放在密度较低的地方，其相似度就升高。换句话说就是增加低密度区域里物体之间的相似度，降低高密度区域里物体之间的相似度。这样一来在不同区域里面的数据密度分布差异就被减小了，也就达到了类似密度归一化的目的。由于很多基于密度或距离计算的机器学习方法对数据密度分布非常敏感，这种相似度度量方法可以显著增加他们在分类，聚类和异常检测任务上的性能，我之前发布的文章对此也有初步讲解。

孤立核函数的核心思想是，以数据样本点为基准切分数据空间得到Ψ个子空间（cell），数据的A和B的相似度的就数是这俩个点切进同时一个子空间的概率。下图为数学公式表达:

孤立核函数的数学公式表达

为了具备自适应的特性，孤立核函数的计算过程采取了基于样本数据的空间切割的方法。其首先随机从数据样本中抽取Ψ个点样本，然后以每个样本点为基准切分数据空间。切分的方法有很多种，比如用维诺图，超球，超立方体等，只要这个切分后的每个子空间（cell）符合俩个特征：1. 切分后的每个子空间都没有交集（non-overlapping）；2. 子空间占据的体积大小由原始数据密度分布决定，由于越密的地方采样点越多，则密度高的区域子空间越多体积即越小。

基于蒙特卡洛的方法，以上切分数据空间的操作可以独立重复次。比如独立重复切分空间100次，发现A和B同时在一个子空间的次数为8次，则A到B的相似度为8%=0.08，A到B的距离（相异度）为0.92。由于数据分布越密集的地方会被划分得越多，那么A和B如果在这些地方，则他们更容易掉进不同的子空间里面而得到更小的相似度。

核函数的原理就是把数据先映射到某个特征空间（希尔伯特空间），然后俩个数据点的相似度就是他们在这个希尔伯特空间中特征的内积。孤立核函数的计算过程也可以用核映射来表示，每次切完数据空间后，可以把每个子空间做标记，然后用一组二元向量来表示需要计算相似度的数据点，如下图所示。这些向量拼接起来就是孤立核特征值。可以发现和的内积就是他俩向量中同时都为1的个数，即x和y掉进同一个子空间的次数。 就是归一化后的概率，也可以做为相似度来当作之后的不同的数据挖掘任务输入。

如果我们用维诺图来切一组二维数据，红色的点表示每次抽样的样本点，黑色的线段为这8个样本点产生的维诺图边界。每次切割后数据空间后我们都可以有8个子空间，因此可以用一组8位的向量代表任何一个数据点，即用1指示该数据点存在于某子空间。比如x如果在某次切割后洛在第一个子空间，那它对应的向量就是1 0 0 0 0 0 0 0。如果我们对该数据空间独立切割100次，那么我们就可以用8*100=800位的向量代表一个数据点。

可以发现，经过孤立核映射，每个数据都可以变成个维度的向量。但是如果该数据通过高斯核函数映射，理论上得到的是无限的维度的向量，目前的方法都是用采样得到近似的有限维度。因此这个有限维度映射是孤立核函数的另一大优点。

孤立核函数的作用是计算某俩个数据点直接的相似度，如果需要计算一个数据点x到一个分布或者一组数据A之间的相似度，我们可以用点间平均相似度来表示：

用孤立核函数计算一个点到一组数据的平均相似度

这个过程可以描述为2步：

1. 把数据点x和数据集A中的每个数据点都映射到孤立核空间，即每个点都变成个特征的向量。
2. 计算x和A中的每个数据点在孤立核空间的平均内积，即平均相似度。
   其中第二步可以等价为首先计算A中的每个数据点在该孤立核空间的平均特征值即)，再用该均值和x的映射去算内积。

以此类推，如果计算俩个分布或数据集之间的相似度，我们可以得到如下分布核函数公式：

分布核函数计算俩个数据集之间的相似度

这个过程可以描述为2步：

1. 把数据集A和B中的每个数据点都映射到孤立核空间，即每个点都变成个维度的向量。
2. 计算A中每个点到B中每个点的平均相似度。可以简化为先对数据集A和B分别求出其在孤立核空间的特征均值，即和。然后得出和的内积。

第二步如果用计算配对的平均相似度，则计算量会到，其中n和m分别为数据集A和B的大小。如果先把数据集A和B在核空间求均值，再做内积，这样计算量则减到线性即。这样一来，就可以通过孤立分布核函数设计线性复杂的的算法来处理海量数据的相似度计算。

下图展示了，, 分别映射到孤立核空间的三个点，即每个集合中的数据在希尔伯特空间的均值。如果要计算新数据x离哪个集合最相似，就是直接求离哪个均值最近，这种计算过程全是线性的复杂的。基于此特性，我们目前发表了2篇聚类文章，第一个是psKC【1】，其是在静态数据上首个理论上最快的线性聚类算法。需要注意k-means并不是线性的，它是因为限制了迭代次数才能在大数据上面运行。第二个算法是StreaKHC【2】，它是在流数据上首个理论上最快的层次聚类算法。

左图为三组数据的原始特征空间，右图为左图三组数据在孤立核空间（希尔伯特空间）求得的均值。

对于异常分布检测，首先把每个分布用孤立核函数映射到希尔伯特空间并用均值作为代表。然后可以再一次用孤立核函数映射到希尔伯特空间，然后用现有的检测方法来找到异常点，这些异常点就是指代原始数据空间中的异常分布，如下图所示【3】。

异常分布的查找步骤演示，这里有2层孤立核函数映射，第一层是把原始数据影视后求出每个分布的均值。第二层是在第一层上再一次做映射，这样可以把第一层的异常点更加孤立出来。

此外，我们还可以把时间序列切片，每个片段当作一组数据或一种分布，然后计算每个片段到其他片段的相似度。那些和大部分其他片段相似度很低的片段就是异常片段，示例如下图。于是乎，我们开发了目前最快的时间序列异常检测方法【4】，该方法打破了100多年来在时间序列上仅有的时域和频域方法的一种范式转变。

上图里的橙色为异常时间片段，下图蓝色的柱状图是IDK计算的每个片段与其他片段的相似度，越低表示该片段越可能是异常。可以发现IDK可以完美的找到上图中的所有异常片段。

参考文献
【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.