Cleanlab 内部 neighbor 模块解析：KNN 图构建、最近邻搜索与距离度量选择

Cleanlab 内部 neighbor 模块解析KNN 图构建、最近邻搜索与距离度量选择【免费下载链接】cleanlabCleanlabs open-source library is the standard>项目地址: https://gitcode.com/GitHub_Trending/cl/cleanlabneighbor是 Cleanlab 内部cleanlab.internal提供最近邻搜索与距离计算能力的基础模块支撑着异常点检测outlier、数据估值data valuation、近重复样本识别等数据质量分析功能。本文基于 docs/source/cleanlab/internal/neighbor/index.rst 展开结合源码与测试用例系统讲解 KNN 搜索索引的建立、KNN 图稀疏距离矩阵的构建、精确重复样本修正以及默认距离度量的自动选择机制帮助读者掌握在自定义数据质量流水线中复用这些能力的完整方法。模块总览neighbor 的职责与三个组成子模块根据索引文档的描述neighbor模块为最近邻搜索以及搜索过程中的两两距离pairwise distance计算提供功能支撑。整个子模块由三个文件组成职责划分清晰子模块定位neighbor.knn_graph建立最近邻搜索索引并构建 KNN 图features_to_knn、create_knn_graph_and_index等neighbor.search包装默认最近邻搜索实现的辅助函数construct_knn可直接替换为自定义近似 KNN 库neighbor.metric为最近邻搜索自动选择距离度量decide_default_metric、decide_euclidean_metric模块的公开入口在 cleanlab/internal/neighbor/init.py 中导出from .knn_graph import features_to_knn因此可以直接通过from cleanlab.internal.neighbor import features_to_knn使用最核心的索引构建函数。三个子模块对应的 Sphinx 文档页为 knn_graph.rst、search.rst、metric.rst它们均以automodule方式自动生成 API 参考。从源码依赖关系看三者的调用链为metric.decide_default_metric决定度量 →search.construct_knn构造sklearn.neighbors.NearestNeighbors对象 →knn_graph.features_to_knn完成拟合并输出搜索索引再通过construct_knn_graph_from_index将其转换为稀疏 KNN 图。一、neighbor.metric距离度量自动选择距离度量决定了谁与谁更近是整个 KNN 体系的第一层决策。metric模块通过两个常量和两个决策函数完成自动化选择源码见 cleanlab/internal/neighbor/metric.py。1.1 两个关键截断阈值常量值含义HIGH_DIMENSION_CUTOFF3特征列数 M 3 时默认使用cosine余弦度量否则使用欧氏距离ROW_COUNT_CUTOFF100仅在默认使用欧氏距离的场景下生效行数 N 100 时使用 sklearn 的euclidean字符串度量实现高效否则使用 scipy 的euclidean可调用函数较慢但数值上更精确1.2decide_default_metric(features)主决策函数该函数根据特征数组形状(N, M)决定默认度量from cleanlab.internal.neighbor.metric import decide_default_metric import numpy as np # 高维数据M 3自动选择 cosine features_high_dim np.random.rand(100, 10) print(decide_default_metric(features_high_dim)) # cosine # 低维小样本M 3 且 N 100选择 scipy 的 euclidean 函数 features_small np.random.rand(50, 2) print(decide_default_metric(features_small)) # function euclidean ... # 低维大样本M 3 且 N 100选择 sklearn 的 euclidean 字符串 features_large np.random.rand(200, 3) print(decide_default_metric(features_large)) # euclidean设计动机余弦度量更适用于高维数据此时欧氏距离易受维度灾难影响而欧氏距离在大数据集上由 sklearn 以向量化方式实现以获得性能在小数据集上退化为 scipy 的逐点精确实现以保证数值精度。二、neighbor.search最近邻搜索对象构造与自定义扩展点search模块只暴露一个函数construct_knn(n_neighbors, metric, **knn_kwargs)其实现极简——直接返回一个 sklearn 的NearestNeighbors实例源码见 cleanlab/internal/neighbor/search.pyfrom cleanlab.internal.neighbor.search import construct_knn knn construct_knn(n_neighbors10, metriccosine, algorithmball_tree, leaf_size30)2.1 接口契约这是设计上的扩展点construct_knn的 docstring 明确说明开发者可以实现一个类似的方法用自定义的近似 KNN 库来运行 Cleanlab。返回对象只需满足以下接口契约fit(X)接收特征数组进行拟合kneighbors(XNone, n_neighbors...)给定查询数组返回其最近邻的(distances, indices)当XNone时返回每个索引点自身的邻居且不把自己算作邻居并允许临时重新指定邻居数属性n_neighbors、metric、metric_params拟合后属性n_features_in_、effective_metric_、effective_metric_params_、n_samples_fit_可选实现__sklearn_is_fitted__以支持 is_fitted 校验kneighbors_graph方法不是必需的该职责已由construct_knn_graph_from_index承担。metric参数应为可调用对象接收两个点、返回距离或 sklearn 支持的度量字符串**knn_kwargs会原样透传给底层搜索算法如algorithm、leaf_size、p、metric_params等。三、neighbor.knn_graph索引构建与 KNN 图生成这是三个子模块中功能最丰富的一个源码见 cleanlab/internal/neighbor/knn_graph.py。它对外提供三条主要 APIfeatures_to_knn、construct_knn_graph_from_index、create_knn_graph_and_index以及一组精确重复修正工具。3.1features_to_knn(features, *, n_neighborsNone, metricNone, **sklearn_knn_kwargs)一步构建搜索索引这是模块对外导出的核心函数也是实际使用最频繁的入口import numpy as np from cleanlab.internal.neighbor import features_to_knn features np.random.rand(100, 10) knn features_to_knn(features) # NearestNeighbors(metriccosine, n_neighbors10)其内部流程为若features为None则抛出ValueErrormetric未指定时调用decide_default_metric(features)自动决定调用内部函数_configure_num_neighbors决定邻居数通过construct_knn构造搜索对象并fit(features)。邻居数的默认规则DEFAULT_K 10模块顶部定义了DEFAULT_K 10注释特别说明它应当是所有需要 KNN 图的问题类型所需的最大 k 值——例如近重复检测只需 k1 而异常点检测需要 k10 时DEFAULT_K应取 10这样所有问题类型可以共享同一张 KNN 图。实际取值逻辑在_configure_num_neighbors见 knn_graph.py若用户传入的k N样本总数抛出ValueError否则取k min(DEFAULT_K, N - 1)即数据量不足 10 个样本时自动收缩到N-1。测试 tests/internal/neighbor/test_neighbor.py 中test_features_to_knn验证了这一规则knn.n_neighbors min(10, N - 1)并断言M 3时度量为cosine、M 3时度量为euclidean或 scipy 的euclidean函数。test_knn_kwargs则验证了**sklearn_knn_kwargs的透传传入metricseuclidean、metric_params{V: V}、n_neighbors6后knn.algorithm auto、knn.leaf_size 30、knn.p 2且拟合后属性n_features_in_、effective_metric_、n_samples_fit_均正确。3.2construct_knn_graph_from_index(knn, correction_featuresNone)索引转稀疏图该函数对已拟合的NearestNeighbors对象执行自查询knn.kneighbors(XNone, return_distanceTrue)将返回的distances与indices直接组装为一个(N, N)的 CSR 稀疏加权邻接矩阵权重即样本间的距离。import numpy as np from cleanlab.internal.neighbor.knn_graph import features_to_knn, construct_knn_graph_from_index features np.array([ [0.701, 0.701], [0.900, 0.436], [0.000, 1.000], ]) knn features_to_knn(features, n_neighbors1) knn_graph construct_knn_graph_from_index(knn) knn_graph.toarray() # 仅演示用大图上一般不应转为稠密矩阵 # array([[0. , 0.33140006, 0. ], # [0.33140006, 0. , 0. ], # [0.76210367, 0. , 0. ]])使用要点来自 docstring 的明确警告该函数不是用来为测试数据构建 KNN 图的它只用于为拟合NearestNeighbors对象的那份数据本身构建图correction_features参数用于按特征数组中的精确重复exact duplicates修正距离与索引但 docstring 明确建议一般情况下不要依赖此参数做修正而应使用模块中更灵活稳健的其他函数如create_knn_graph_and_index仅在确有特殊需要时才使用。测试test_construct_knn_graph_from_index对[cosine, euclidean]两种度量参数化验证了输出图的形状(N, N)、非零元素数N * k、dtype 为float64、所有距离非负、每行距离升序排列等性质。3.3create_knn_graph_and_index(features, *, n_neighborsNone, metricNone, correct_exact_duplicatesTrue, **sklearn_knn_kwargs)一站式入口这是推荐的一站式 API一次调用同时返回 KNN 图与拟合好的搜索索引且默认开启精确重复修正from cleanlab.internal.neighbor.knn_graph import create_knn_graph_and_index knn_graph, knn create_knn_graph_and_index(features, n_neighbors10, metriccosine)内部实现为三步features_to_knn建索引 →construct_knn_graph_from_index建图 → 若correct_exact_duplicatesTrue则调用correct_knn_graph(features, knn_graph)修正精确重复。若features为None会抛出ValueError。3.4 精确重复修正correct_knn_graph与correct_knn_distances_and_indices真实数据中常出现完全相同的特征向量。若不加处理KNN 图可能出现精确重复的样本之间距离不为零、重复样本未被识别为彼此最近邻等问题。模块提供了一组修正工具_compute_exact_duplicate_sets(features)借助np.unique(features, return_inverseTrue, return_countsTrue, axis0)找出所有出现次数大于 1 的完全相同特征向量返回每组重复样本的行索引列表correct_knn_distances_and_indices(features, distances, indices, exact_duplicate_setsNone)返回修正后的(distances, indices)保证精确重复样本的互距离为零且重复样本被正确纳入彼此的 k 近邻除非重复数量超过 kcorrect_knn_graph(features, knn_graph)对已构建的 CSR 图做后处理修正correct_knn_distances_and_indices_with_exact_duplicate_sets_inplace(...)原地in-place版本其 docstring 详细说明了两种处理场景重复集大小 ≥ k1所有近邻均为精确重复indices的前 k1 项用循环矩阵circulant方式填充以均匀分配邻居距离置零重复集大小 k1部分近邻非重复将非重复邻居移到列表末尾重复邻居置于前部且距离为零。辅助函数_prepare_neighborhood_of_first_k_duplicates通过scipy.linalg.circulant构造循环矩阵来为重复样本均衡分配彼此作为邻居避免与自身冲突。docstring 中的示例直观展示了修正效果当特征数组为[[0,0], [0,0], [1,1]]且 1-NN 距离为[√2, 1e-16, √2]、索引为[2, 0, 1]时修正后距离变为[[0], [0], [1.414]]、索引变为[[1], [0], [0]]——即两个重复点互指为零距离邻居。测试方面TestKNNCorrection中的两个用例分别验证修正遗漏的重复与修正重复的顺序test_create_knn_graph_correctness使用一个故意对相同点加大距离偏置的noisy_euclidean_distance度量来模拟索引漏检重复的场景证明correct_exact_duplicatesTrue时图被正确修正而False时第一个近邻错误地指向非重复点。test_create_knn_graph_properties与test_knn_graph_duplicate_handling还通过 Hypothesis 属性测试验证了无自引用、距离非负、修正后距离不大于未修正、重复样本互为最近邻且距离为零、修正后邻居均为真实重复precision1等性质。四、模块在 Cleanlab 中的真实调用场景neighbor模块并非孤立存在它是多个上层数据质量功能的基础设施。从仓库源码可以确认以下调用点cleanlab/outlier.py异常点检测通过features_to_knn(features, n_neighborsk)构建索引并使用correct_knn_distances_and_indices修正重复然后基于 KNN 距离计算异常分数cleanlab/regression/rank.py回归任务的排序找出最可能标注错误的样本通过features_to_knn(features, n_neighborsneighbors, metricneighbor_metric)建立近邻关系cleanlab/data_valuation.py数据估值data_valuation使用create_knn_graph_and_index(features, n_neighborsk, metricmetric)同时得到 KNN 图与索引用于估计每个样本对模型的影响cleanlab/datalab/internal/issue_manager/knn_graph_helpers.pyDatalab 的问题发现框架中多个 issue manager如近重复、异常点共享create_knn_graph_and_index构建的 KNN 图这正是DEFAULT_K取最大需求值的意义所在——一张图服务于多种问题类型。五、实战总结与使用建议综合文档与源码使用neighbor模块的关键要点可归纳为开箱即用from cleanlab.internal.neighbor import features_to_knn即可获得自动选择度量与邻居数、已拟合的搜索索引适合快速验证默认规则透明M 3 用 cosineN ≤ 100 且用欧氏时用 scipy 的精确实现、N 100 用 sklearn 的高效实现k min(10, N-1)需要图时优先create_knn_graph_and_index它同时返回索引与稀疏图且默认开启精确重复修正比先建索引再手动建图更稳健可替换后端通过仿照construct_knn实现满足接口契约fitkneighbors的自定义对象即可将 Cleanlab 的 KNN 底层替换为任意近似最近邻库注意稀疏性KNN 图以 CSR 稀疏矩阵形式返回docstring 反复提醒不要在大数据集上调用.toarray()转为稠密矩阵。如需深入源码细节可继续阅读 knn_graph.py、search.py、metric.py 三个实现文件以及 tests/internal/neighbor/test_neighbor.py 中覆盖上述全部行为的单元测试与属性测试。【免费下载链接】cleanlabCleanlabs open-source library is the standard>项目地址: https://gitcode.com/GitHub_Trending/cl/cleanlab创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考