标题：高维数据的最近邻：hub的产生和影响
本文还有扩展版：Hubs in Space: Popular Nearest Neighbors in High-Dimensional Data （JMLR'10）
本篇博客将两篇文章合并来讲。
编者的总结
- 对高维数据的hub出现的原因提供了一个思路：考虑高维数据是球形分布，hubs离中心点的距离比较近，因此离所有其它数据都会比较近。
- 对hub对现有数据挖掘算法的影响提供了分析：hub倾向于离其它点都比较近，因此容易误导分类/聚类/相似性检索。
2. The Skewness of k-occurrences
2.1. A Motivating Example
-
下图是在rand[0,1]数据集上精确knn图(k=5)的入度概率分布，三幅图是三个维度，不同曲线是不同的距离度量方式。可以看到维度较高（20,100）的时候，入度分布倾斜很明显，少量点的入度非常高，我们称之为hubs，其余大量点的入度则入度普遍较低。
image.png
2.2. The Causes of Skewness
-
取rand数据集中心点，计算其他点和中心点的距离，发现离数据集中心越远，入度越低，变化非常明显。
image.png - 原因：作者解释现有的一些工作认为高维数据分布在一个以数据集中心点为球心的球上，且数据距离中心的距离的方差是比较大的，因此会有一部分数据离球心比较近，这部分数据距离数据集中其它所有的点都比较近，因此会成为hub。
- 下图是rand数据集上，选择原点（中心点）作为观察点，计算和其它点的L2距离，得到的分布。随着维数增大，方差基本不变，均值差不多是
（单位球半径）
image.png - 下图虚线是一个距离中心点期望距离的点，实线代表的点比虚线代表的点距离中心点近两倍的标准差。
- 可以看到离中心点越近，分布越往距离偏小的方向移动。
- 而且维数越高，两个分布偏差的越多（见右图）。
-
另一方面，从上面图4可以看到维数越高，距离中心越近的点越少，hub点实际是非常少量的在中心点附近的稀疏区域，且它们距离其它点都非常近。
image.png - 这里面很有意思的一点是，大量的高维数据分布在离中心点比较远的边缘位置，但他们的最近邻还在中心点附近，说明它们在边缘部分没有KNN。这种现象越在高维越明显，说明数据在高维空间（单位球）上，有足够大的边缘空间，放置大量的数据点。这一点可以在几何上有印证。
- 考虑二维空间半径为1的一个单位圆，我们想找到一组尽可能多的点，他们彼此之间的距离大于等于到圆心的距离，这组点最多有6个，是单位圆的内切正六边形。
- 三维空间里，这组点最多12个；四维空间里，最多24个，这是kissing number，可以自己搜一下。
2.3. Skewness in Real Data
- 下面作者用
，偏度（三阶中心距）来表示入度分布的倾斜程度。
- 上面我们用的是rand数据做分析，在真实数据上会有两个其它特征：
- 属性不独立->因此需要本征维数
- 把真实数据集每一维的数据random permutation一下，发现偏度明显增加
- 有聚集特征，所以更好是分配若干dataset means
- 如果把偏度和数据到数据集中心距离的spearman相关系数
，与偏度和数据到聚类中心距离的Spearman相关系数
做比较，会发现后者普遍比前者大很多。
- 如果把偏度和数据到数据集中心距离的spearman相关系数
image.png
2.4. Skewness and Intrinsic Dimensionality
- 数据集的偏度，相比于原来的维数，和本征维数的相关关系更明显一些。
-
下图用PCA降维，发现取一部分维度之后，偏度就已经饱和，后续的维度不增加偏度了。
image.png
后文作者针对基于最近邻的分类，聚类，信息检索算法做了在高维空间的改良，主要思路是针对hub做额外的惩罚或者奖励以提高精度。
- 比如聚类，hubs因为离谁都近，所以簇间距就比较差；outliers互相之间也比较远，所以簇内距就会比较差。因此都会影响聚类评分。
- 比如信息检索，假设query和base同分布，那么query会更容易找到hubs，但hubs不一定相关，所以可以对hubs做一些惩罚。
5.2.1 NEAREST-NEIGHBOR GRAPH STRUCTURE
- 总共10000个点的Random数据集
- 如图a，在高维空间里，hub的5-NN更容易也是hub；
- 如图b，c，hub的入边邻居在高维空间中，更容易是非hub。
- 总的来说，随着维数增加，hubs的入边邻居，无论是从其他hub或者非hub，都在增加。
image.png
- 另外一个观察就是网络中的介数中心性(betweeness centrality)。代表的是在图上找任意两点最短路，通过某点的概率是多大。作者发现介数中心性和hubness之间关联性不低。
