基于属性重要性的近邻算法：Python及TensorFlow库方案咨询

If you're hunting for nearest neighbor solutions that account for attribute importance (instead of treating all features equally like sklearn's KDTree), here's a breakdown of options available in standard libraries, plus a custom approach tailored to strict attribute priority ordering:

Standard Library Workarounds & Tools #

1. Weighted Feature Scaling with Scikit-Learn's KDTree #

The vanilla KDTree doesn't support per-attribute weights directly, but you can simulate this by scaling features based on their importance. Multiply high-priority attributes by larger coefficients, and lower-priority ones by smaller values—this effectively weights their contribution to the distance calculation.

Example code:

import numpy as np
from sklearn.neighbors import KDTree

# Define weights: first attribute = most important, last = least
feature_weights = [4, 2, 1, 0.5]

# Your dataset and query point
neighbors = np.array([[0, 1, 0, 1], [1, 2, 1, 2], [2, 1, 1, 1], [1, 0, 0, 0], [1, 2, 0, 2], [2, 2, 2, 2], [1, 0, 0, 1]])
query_point = np.array([[1, 1, 0, 1]])

# Apply weights to scale features
weighted_neighbors = neighbors * feature_weights
weighted_query = query_point * feature_weights

# Build KDTree on scaled data and query
tree = KDTree(weighted_neighbors, leaf_size=2)
distances, indices = tree.query(weighted_query, k=7)

This is a quick, straightforward fix, though it can run into numerical issues if weights are extremely skewed.

2. TensorFlow Custom Weighted Distance Calculation #

TensorFlow doesn't have a built-in weighted nearest neighbor module, but you can roll your own using tensor operations. This is great if you're working in a TF pipeline and need GPU acceleration.

Example code:

import tensorflow as tf

# Define weights as a tensor
feature_weights = tf.constant([4.0, 2.0, 1.0, 0.5], dtype=tf.float32)

# Convert data to tensors
neighbors_tensor = tf.convert_to_tensor(
    [[0, 1, 0, 1], [1, 2, 1, 2], [2, 1, 1, 1], [1, 0, 0, 0], [1, 2, 0, 2], [2, 2, 2, 2], [1, 0, 0, 1]],
    dtype=tf.float32
)
query_tensor = tf.convert_to_tensor([[1, 1, 0, 1]], dtype=tf.float32)

# Calculate weighted squared distance
weighted_differences = (neighbors_tensor - tf.expand_dims(query_tensor, 0)) ** 2 * feature_weights
total_distances = tf.reduce_sum(weighted_differences, axis=1)

# Get top k nearest neighbors
k = 7
sorted_indices = tf.argsort(total_distances)[:k]
top_k_distances = tf.gather(total_distances, sorted_indices)
top_k_neighbors = tf.gather(neighbors_tensor, sorted_indices)

This gives you full control over the distance metric and works seamlessly with other TF components, though it's less efficient than specialized tree structures for large datasets.

Custom Interval Halving Algorithm for Strict Attribute Priority #

If your use case requires strict attribute importance ordering (where the first attribute is the deciding factor, then the second, and so on—no weighted blending), the standard methods above won't cut it. That's where your interval halving algorithm comes in.

This approach works by iteratively narrowing down the candidate pool using each attribute in priority order:

1. Start with all neighbors.
2. For each attribute (from most to least important), filter candidates to keep those with the smallest differences from the query point (halving the pool or keeping enough to meet the k requirement).
3. Finally, sort the remaining candidates using lexicographical order of attribute differences to ensure strict priority.

A simplified implementation of the core logic looks like this:

import numpy as np

def interval_halving_nearest_neighbors(neighbors, query, k):
    candidates = neighbors.copy()
    # Track original indices if you need to map back to the original dataset
    candidate_indices = np.arange(len(neighbors))
    
    for attr_idx in range(query.shape[1]):
        if len(candidates) <= k:
            break
        
        # Calculate differences for the current attribute
        query_val = query[0, attr_idx]
        diffs = np.abs(candidates[:, attr_idx] - query_val)
        
        # Sort candidates by this attribute's difference and keep top candidates
        sorted_order = np.argsort(diffs)
        candidates = candidates[sorted_order]
        candidate_indices = candidate_indices[sorted_order]
        
        # Halve the pool (or keep at least k candidates)
        candidates = candidates[:max(k, len(candidates) // 2)]
        candidate_indices = candidate_indices[:max(k, len(candidates) // 2)]
    
    # Final sort using lex order (prioritize first attribute, then second, etc.)
    full_diffs = np.abs(candidates - query)
    lex_sort_keys = tuple(full_diffs[:, i] for i in range(full_diffs.shape[1]))
    final_sorted_order = np.lexsort(lex_sort_keys)
    
    return candidate_indices[final_sorted_order[:k]], candidates[final_sorted_order[:k]]

# Usage example
neighbors = np.array([[0, 1, 0, 1], [1, 2, 1, 2], [2, 1, 1, 1], [1, 0, 0, 0], [1, 2, 0, 2], [2, 2, 2, 2], [1, 0, 0, 1]])
query = np.array([[1, 1, 0, 1]])
top_k_indices, top_k_neighbors = interval_halving_nearest_neighbors(neighbors, query, k=7)

This method ensures that higher-priority attributes are never overshadowed by lower ones, making it perfect for scenarios where attributes have a clear hierarchical importance.

内容的提问来源于stack exchange，提问作者itsergiu