提出两种新指标，判断高维数据能否用聚类方法高效找最近邻。
Neighborhood Stability as a Measure of Nearest Neighbor Searchability
- 基于近邻关系设计内部聚类质量评估指标，预测搜索精度。
- 定义数据本身可聚类性指标，与聚类精度高度相关。
- 适用于内积等非距离度量，不依赖具体距离函数。
基于聚类的近似最近邻搜索（ANNS）将点集划分为若干簇，仅搜索其中少数簇以定位查询点的最近邻。尽管该方法广泛应用，但缺乏分析工具来判断特定数据集是否适合此类搜索——即“可搜索性”。为此，本文针对欧氏空间中的高维点集提出两种扁平聚类的衡量指标：一是聚类-近邻稳定性度量（clustering-NSM），作为聚类质量的内在指标，可预测ANNS精度；二是点-近邻稳定性度量（point-NSM），反映数据本身的可聚类性，能预测clustering-NSM。两者结合，仅凭数据点即可判断数据是否适合聚类式ANNS。重要的是，二者均基于点之间的近邻关系而非距离，因此适用于内积等各类距离函数。
原文摘要 · Abstract (English)
Clustering-based Approximate Nearest Neighbor Search (ANNS) organizes a set of points into partitions, and searches only a few of them to find the nearest neighbors of a query. Despite its popularity, there are virtually no analytical tools to determine the suitability of clustering-based ANNS for a given dataset -- what we call "searchability." To address that gap, we present two measures for flat clusterings of high-dimensional points in Euclidean space. First is Clustering-Neighborhood Stability Measure (clustering-NSM), an internal measure of clustering quality -- a function of a clustering of a dataset -- that we show to be predictive of ANNS accuracy. The second, Point-Neighborhood Stability Measure (point-NSM), is a measure of clusterability -- a function of the dataset itself -- that is predictive of clustering-NSM. The two together allow us to determine whether a dataset is searchable by clustering-based ANNS given only the data points. Importantly, both are functions of nearest neighbor relationships between points, not distances, making them applicable to various distance functions including inner product.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。