孤立核（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掉进同一个子空间的次数。
就是归一化后的概率，也可以做为相似度来当作之后的不同的数据挖掘任务输入。
可以发现，经过孤立核映射，每个数据都可以变成个维度的向量。但是如果该数据通过高斯核函数映射，理论上得到的是无限的维度的向量，目前的方法都是用采样得到近似的有限维度。因此这个有限维度映射是孤立核函数的另一大优点。
孤立核函数的作用是计算某俩个数据点直接的相似度，如果需要计算一个数据点x到一个分布或者一组数据A之间的相似度，我们可以用点间平均相似度来表示：
这个过程可以描述为2步：
- 把数据点x和数据集A中的每个数据点都映射到孤立核空间，即每个点都变成
个特征的向量。
- 计算x和A中的每个数据点在孤立核空间的平均内积，即平均相似度。
其中第二步可以等价为首先计算A中的每个数据点在该孤立核空间的平均特征值即)，再用该均值
去算内积。
以此类推，如果计算俩个分布或数据集之间的相似度，我们可以得到如下分布核函数公式：
这个过程可以描述为2步：
- 把数据集A和B中的每个数据点都映射到孤立核空间，即每个点都变成
- 计算A中每个点到B中每个点的平均相似度。可以简化为先对数据集A和B分别求出其在孤立核空间的特征均值，即
。然后得出
第二步如果用计算配对的平均相似度，则计算量会到，其中n和m分别为数据集A和B的大小。如果先把数据集A和B在核空间求均值，再做内积，这样计算量则减到线性即
。这样一来，就可以通过孤立分布核函数设计线性复杂的的算法来处理海量数据的相似度计算。
下图展示了，
,
分别映射到孤立核空间的三个点，即每个集合中的数据在希尔伯特空间的均值。如果要计算新数据x离哪个集合最相似，就是直接求
离哪个均值最近，这种计算过程全是线性的复杂的。基于此特性，我们目前发表了2篇聚类文章，第一个是psKC【1】，其是在静态数据上首个理论上最快的线性聚类算法。需要注意k-means并不是线性的，它是因为限制了迭代次数才能在大数据上面运行。第二个算法是StreaKHC【2】，它是在流数据上首个理论上最快的层次聚类算法。
对于异常分布检测，首先把每个分布用孤立核函数映射到希尔伯特空间并用均值作为代表。然后可以再一次用孤立核函数映射到希尔伯特空间，然后用现有的检测方法来找到异常点，这些异常点就是指代原始数据空间中的异常分布，如下图所示【3】。
此外，我们还可以把时间序列切片，每个片段当作一组数据或一种分布，然后计算每个片段到其他片段的相似度。那些和大部分其他片段相似度很低的片段就是异常片段，示例如下图。于是乎，我们开发了目前最快的时间序列异常检测方法【4】，该方法打破了100多年来在时间序列上仅有的时域和频域方法的一种范式转变。
参考文献
【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.
