آزمون kNN در پایتون؛ فاصلهٔ ویژگی‌ها، همسایهٔ مساوی و تساوی رأی

در یک دسته‌بندِ همسایهٔ نزدیک، «نزدیک‌تر» و «بیشترین رأی» دو تصمیمِ جدا هستند. اگر مرزِ انتخابِ همسایه یا نتیجهٔ رأی مساوی شود، یک سیاستِ پنهان می‌تواند پاسخ را عوض کند. این درس یک kNN با رأیِ یکنواخت می‌سازد که همسایه‌های منتخب و شمارِ رأی را کنار برچسب پس می‌دهد. مثال، دو کانالِ ولتاژِ ساختگی و سه نامِ الگو دارد؛ هدف آزمودنِ خودِ پیش‌بینی است، نه گزارشِ دقتِ تشخیصِ خرابی یا آموزشِ یک سامانهٔ صنعتی.

۱. دادهٔ مرجع و هندسهٔ فاصله

هر سطرِ مرجع، برداری از ویژگی‌ها و یک برچسب دارد. پرسش هم برداری با همان تعداد مؤلفه است. در مثالِ دوبعدی، هر دو مؤلفه با واحد V داده شده‌اند و فاصلهٔ اقلیدسی نیز واحد V دارد. جمعِ مربعِ ولت و درجهٔ سلسیوس، بدون تعریفِ تبدیل یا وزن، هندسهٔ همین مسئله نیست. حتی یکسان بودنِ واحد نیز مناسب بودنِ مقیاس و فاصله برای یک وظیفهٔ واقعی را تضمین نمی‌کند؛ این انتخاب باید با معنای ویژگی‌ها بررسی شود.

بخشِ کاملِ دسته‌بندی با همسایه‌ها در scikit-learn، پیش‌بینی را از رأیِ نمونه‌های نزدیک توضیح می‌دهد. ما فقط رأیِ یکنواختِ k همسایه را اجرا می‌کنیم؛ رأی با وزنِ معکوسِ فاصله، شعاعِ ثابت و ساختِ نمایهٔ درختی نداریم. دادهٔ مرجع از قبل داده شده است و تابع، پارامترِ آماری یا وزنِ ویژگی یاد نمی‌گیرد. ذخیره شدنِ نمونه‌های دارای برچسب، جای ارزیابی روی دادهٔ مستقل را نمی‌گیرد.

تابع list یا tuple غیرخالی از سطرها، یک برچسب برای هر سطر و یک پرسشِ غیرخالی می‌گیرد. تعداد سطر و ویژگی سقفِ کوچکِ قراردادی ندارد؛ همه باید در حافظه و ظرفیتِ محاسبه جا شوند. هر مؤلفه int یا float دقیقِ پایتون است و به float متناهی تبدیل می‌شود. bool، رشته و زیرکلاسِ عددی پذیرفته نیستند. k عدد صحیح از یک تا تعدادِ مرجع و برچسب، رشتهٔ غیرخالیِ بدون فاصلهٔ ابتدا و انتهاست. قالبِ کلیِ آرایه‌های کتابخانه را بازسازی نکرده‌ایم.

۲. همسایه‌های مساوی و رأیِ مساوی

ابتدا فاصلهٔ هر سطر تا پرسش حساب می‌شود. ترتیبِ انتخاب، فاصلهٔ float و سپس شمارهٔ سطرِ اصلی است. این قاعده برای k مرز می‌گذارد؛ اگر دو فاصلهٔ مساوی، یکی داخل و دیگری بیرونِ مجموعهٔ kتایی باشند، جابه‌جا کردنِ سطرهای مرجع می‌تواند پاسخ را عوض کند. پارامترها و هشدارِ KNeighborsClassifier نیز مسئلهٔ فاصله‌های برابر در مرزِ همسایه‌ها را مطرح می‌کند. ادعای انطباقِ همهٔ جزئیاتِ تابعِ ما با آن API نداریم.

پس از انتخابِ سطرها، هر کدام یک رأی به برچسبِ خود می‌دهند. برچسبِ دارای بیشترین رأی برنده است؛ اگر چند برچسب برابر باشند، کوچک‌ترین رشته در ترتیبِ معمولِ یونیکدِ پایتون انتخاب می‌شود. این ترتیب، ترتیبِ زبانیِ فارسی، اولویتِ ایمنی یا اهمیتِ کلاس نیست. همهٔ نام‌های هم‌رأی در گزارش باقی می‌مانند تا انتخابِ قراردادی دیده شود. نزدیک‌ترین نمونه به‌تنهایی برندهٔ رأیِ مساوی را تعیین نمی‌کند.

پنج بردارِ نمونه، به ترتیب (0,0), (2,0), (0,2), (3,3), (6,6) هستند. برچسب‌هایشان به ترتیب pattern-a, pattern-b, pattern-a, pattern-b, pattern-c است؛ این نام‌ها فقط الگوهای تألیفی‌اند. برای پرسشِ دو و دو، سه همسایه سطرهای با اندیسِ صفرمبنای سه، یک و دو هستند. فاصله‌ها ریشهٔ دو، دو و دو ولت‌اند؛ دو رأی برای b و یک رأی برای a داریم، پس b برنده می‌شود.

۳. کد کاملِ پیش‌بینیِ قابل بازبینی

فایل knn_vote_contract.py با Python 3.14.5 و کتابخانهٔ استاندارد اجرا شده است. فرمانِ بازسازی python knn_vote_contract.py است. scikit-learn نصب نیست و NumPy نیز در این فایل اجرا نمی‌شود. مرجعِ کاملِ math.hypot، نرمِ اقلیدسیِ چندمؤلفه‌ای را تعریف می‌کند. از آن برای فاصله و از انتخابِ k عضوِ کوچک برای نگهداریِ شماره‌های مرجع استفاده کرده‌ایم.

"""Inspectable uniform-vote kNN; explicit float-distance and vote ties."""
from collections import Counter
from dataclasses import asdict, dataclass
from fractions import Fraction
import heapq
from itertools import product
import json
import math
import platform


def vector(value):
    if type(value) not in (list, tuple) or not value:
        raise ValueError('feature vector must be a nonempty list or tuple')
    converted = []
    for x in value:
        if type(x) not in (int, float):
            raise ValueError('features require exact Python int/float, not bool or subclass')
        try:
            x = float(x)
        except OverflowError as error:
            raise ValueError('feature cannot be represented as finite float') from error
        if not math.isfinite(x):
            raise ValueError('feature must be finite')
        converted.append(x)
    return tuple(converted)


@dataclass(frozen=True)
class Prediction:
    label: str
    neighbor_indices: tuple
    neighbor_distances: tuple
    votes: tuple
    tied_vote_labels: tuple


def classify(features, labels, query, k):
    if type(features) not in (list, tuple) or not features:
        raise ValueError('reference rows must be a nonempty list or tuple')
    if type(labels) not in (list, tuple) or len(labels) != len(features):
        raise ValueError('one label per reference row is required')
    if any(type(s) is not str or not s or s.strip() != s for s in labels):
        raise ValueError('labels must be exact nonempty trimmed strings')
    if type(k) is not int or not 1 <= k <= len(features):
        raise ValueError('k must be an exact integer from one to reference count')
    query = vector(query)
    rows = tuple(vector(row) for row in features)
    if any(len(row) != len(query) for row in rows):
        raise ValueError('feature dimensions must agree')
    distances = []
    for i, row in enumerate(rows):
        delta = tuple(a - b for a, b in zip(row, query, strict=True))
        distance = math.hypot(*delta)
        if not math.isfinite(distance):
            raise ArithmeticError('a computed float distance is nonfinite')
        distances.append((distance, i))
    # Float distances first, original row index second. Ties are exact float ties.
    neighbors = heapq.nsmallest(k, distances)
    counts = Counter(labels[i] for _, i in neighbors)
    maximum = max(counts.values())
    tied = tuple(sorted(label for label, count in counts.items() if count == maximum))
    return Prediction(tied[0], tuple(i for _, i in neighbors),
                      tuple(d for d, _ in neighbors), tuple(sorted(counts.items())), tied)


def squared_distance_oracle(features, labels, query, k):
    """Exact distances for actual converted float coordinates; select by scanning."""
    rows = [[Fraction(float(x)) for x in row] for row in features]
    q = [Fraction(float(x)) for x in query]
    square = [sum((a - b) ** 2 for a, b in zip(row, q, strict=True)) for row in rows]
    remaining = set(range(len(rows)))
    chosen = []
    for _ in range(k):
        i = min(remaining, key=lambda j: (square[j], j))
        chosen.append(i)
        remaining.remove(i)
    # Count through explicit label comparisons, not Counter or main neighbors.
    counts = {label: sum(labels[i] == label for i in chosen) for label in set(labels)}
    maximum = max(counts.values())
    tied = tuple(sorted(label for label in counts if counts[label] == maximum))
    return tied[0], tuple(chosen), tied


def rejected(*args):
    try:
        classify(*args)
    except (ValueError, ArithmeticError):
        return True
    return False


def main():
    features = ((0, 0), (2, 0), (0, 2), (3, 3), (6, 6))
    labels = ('pattern-a', 'pattern-b', 'pattern-a', 'pattern-b', 'pattern-c')
    query = (2, 2)
    hand = classify(features, labels, query, 3)
    checks = {}
    checks['literal_three_neighbors_and_majority_hand_answer'] = (
        hand.label == 'pattern-b' and hand.neighbor_indices == (3, 1, 2)
        and hand.votes == (('pattern-a', 1), ('pattern-b', 2)))
    checks['literal_distances_have_same_voltage_unit_as_channels'] = (
        hand.neighbor_distances == (math.sqrt(2), 2.0, 2.0))
    four = classify(features, labels, query, 4)
    checks['vote_tie_uses_smallest_unicode_label_not_nearest_class'] = (
        four.label == 'pattern-a' and four.tied_vote_labels == ('pattern-a', 'pattern-b'))
    order = (0, 2, 1, 3, 4)
    reordered = classify(tuple(features[i] for i in order), tuple(labels[i] for i in order), query, 2)
    checks['boundary_distance_tie_can_make_row_order_change_prediction'] = (
        classify(features, labels, query, 2).label == 'pattern-b'
        and reordered.label == 'pattern-a')
    cases = 0
    for q in product(range(-1, 8), repeat=2):
        for k in range(1, len(features) + 1):
            got = classify(features, labels, q, k)
            label, indices, tied = squared_distance_oracle(features, labels, q, k)
            assert (got.label, got.neighbor_indices, got.tied_vote_labels) == (label, indices, tied)
            cases += 1
    checks['405_integer_grid_queries_and_k_exact_square_oracle_one_group'] = cases == 405
    shifted = tuple(tuple(x + 4 for x in row) for row in features)
    checks['common_channel_translation_preserves_neighbors_and_label'] = (
        classify(shifted, labels, (6, 6), 3).neighbor_indices == hand.neighbor_indices)
    scaled = tuple(tuple(-2 * x for x in row) for row in features)
    scaled_result = classify(scaled, labels, (-4, -4), 3)
    checks['common_nonzero_scale_preserves_order_and_scales_distances'] = (
        scaled_result.label == hand.label and scaled_result.neighbor_indices == hand.neighbor_indices
        and all(a * 2 == b for a, b in zip(hand.neighbor_distances, scaled_result.neighbor_distances, strict=True)))
    checks['one_neighbor_and_all_reference_neighbors'] = (
        classify(features, labels, query, 1).neighbor_indices == (3,)
        and classify(features, labels, query, 5).votes == (('pattern-a', 2), ('pattern-b', 2), ('pattern-c', 1)))
    checks['duplicate_reference_coordinates_keep_declared_row_order'] = (
        classify(((1, 1), (1, 1)), ('b', 'a'), (1, 1), 1).label == 'b')
    near = ((1, 2 ** -30), (1, 0))
    rounded = classify(near, ('b', 'a'), (0, 0), 1)
    exact = squared_distance_oracle(near, ('b', 'a'), (0, 0), 1)
    checks['rounded_norm_tie_is_not_exact_mathematical_distance_tie'] = (
        rounded.neighbor_distances == (1.0,) and rounded.label == 'b' and exact[0] == 'a')
    checks['larger_ordinary_reference_set_has_no_toy_size_cap'] = (
        classify(tuple((i, i + 1) for i in range(200)), ('a',) * 200, (100, 101), 7).label == 'a')
    checks['shape_container_and_k_contract_rejections'] = all(rejected(*args) for args in (
        ((), (), (0,), 1), (((1,),), (), (0,), 1), (((1, 2),), ('a',), (0,), 1),
        (((1,),), ('a',), (), 1), (((1,),), ('a',), (0,), True),
        (((1,),), ('a',), (0,), 0), (((1,),), ('a',), (0,), 2)))
    checks['feature_type_nonfinite_and_label_contract_rejections'] = all(rejected(*args) for args in (
        (((True,),), ('a',), (0,), 1), (((math.nan,),), ('a',), (0,), 1),
        (((math.inf,),), ('a',), (0,), 1), (((10 ** 1000,),), ('a',), (0,), 1),
        (((1,),), ('',), (0,), 1), (((1,),), (' a',), (0,), 1), (((1,),), (1,), (0,), 1)))
    checks['finite_input_can_produce_nonfinite_difference_and_is_reported'] = (
        rejected(((1e308,),), ('a',), (-1e308,), 1))
    assert all(type(value) is bool and value for value in checks.values())
    print(json.dumps({
        'python': platform.python_version(), 'dependencies': 'stdlib only',
        'sklearn_executed': False, 'numpy_executed': False,
        'example_feature_unit': 'V in both synthetic channels', 'distance_unit': 'V',
        'hand_features': features, 'hand_labels': labels, 'hand_query': query,
        'hand_k3': asdict(hand), 'hand_k4_vote_tie': asdict(four),
        'exact_square_oracle_cases_inside_one_group': cases,
        'rounded_distance_counterexample': {'main_label': rounded.label, 'exact_square_label': exact[0],
                                            'coordinates': near, 'meaning': 'float norm ties can hide exact distance order'},
        'checks': checks, 'unique_check_groups': len(checks), 'all_passed': True,
        'limits': 'Uniform votes over computed float distances; tie by row index then Unicode label. No trained scaling, accuracy estimate, calibrated probability, nearest-neighbor index or real sensor fault evidence.'
    }, ensure_ascii=False, indent=2))


if __name__ == '__main__':
    main()

بعدِ ناسازگار، نبودِ برچسب، k نامعتبر یا مقدارِ نامتناهی خطا می‌دهد. متناهی بودنِ ورودی به‌تنهایی کافی نیست: تفاضلِ مثبت و منفیِ ده به توان ۳۰۸، در float نامتناهی می‌شود؛ تابع آن فاصله را رد می‌کند و پاسخِ ظاهری نمی‌سازد. از طرف دیگر، تبدیلِ یک عدد صحیحِ بزرگ به float ممکن است اطلاعاتِ مقدارِ اولیه را کم کند. قراردادِ رتبه‌بندی روی مختصاتِ تبدیل‌شده و فاصله‌های محاسبه‌شده است، نه دقتِ دلخواهِ همهٔ اعداد حقیقی.

خروجیِ frozen شامل برچسب، اندیس و فاصلهٔ همسایه‌ها، جدولِ رأی و نام‌های هم‌رأی است. این شواهد کمک می‌کند تغییرِ داده، ترتیب یا k را بررسی کنیم. هیچ احتمالِ کالیبره‌شده‌ای گزارش نمی‌شود؛ نسبتِ دو رأی از سه، احتمالِ واقعیِ کلاسِ پرسش نیست. همچنین زمان‌سنجی، شتابِ جست‌وجو، مصرفِ حافظه یا کاراییِ نمایه اندازه‌گیری نشده است؛ تابع برای شفاف بودنِ محاسبه نوشته شده است.

۴. مرجع فاصلهٔ مربعی و پاسخ دستی

مرجع مستقل، مؤلفه‌های floatشده را به Fraction تبدیل می‌کند و مجموعِ دقیقِ مربعِ تفاضل‌ها را می‌سازد. ریشه گرفتن برای ترتیبِ فاصله‌های دقیقِ نامنفی لازم نیست. انتخابِ مرجع با اسکنِ تکراریِ کمینه انجام می‌شود؛ تابعِ hypot، انتخابِ heap و Counter مسیرِ اصلی را فراخوانی نمی‌کند. روی شبکهٔ کوچکِ صحیح، ۸۱ پرسش و پنج مقدارِ k، ۴۰۵ مورد در یک گروه‌اند؛ برچسب، ترتیبِ همسایه و همهٔ نام‌های هم‌رأی مقایسه می‌شوند.

با k چهار، سطرِ صفر هم اضافه می‌شود و دو رأی برای هر یک از a و b داریم؛ a طبق سیاستِ نام انتخاب می‌شود، با آنکه نزدیک‌ترین نمونه برچسب b دارد. با k دو، سطرِ سه و سپس سطرِ یک انتخاب می‌شوند و b می‌برند. اگر جای سطرهای یک و دو را عوض کنیم، دومین همسایه برچسب a می‌گیرد؛ رأی یک‌به‌یک می‌شود و a برنده است. این شاهد، اثرِ ترتیب در مرزِ فاصله را از تساویِ رأی جدا می‌کند.

{
  "python": "3.14.5",
  "dependencies": "stdlib only",
  "sklearn_executed": false,
  "numpy_executed": false,
  "example_feature_unit": "V in both synthetic channels",
  "distance_unit": "V",
  "hand_features": [
    [
      0,
      0
    ],
    [
      2,
      0
    ],
    [
      0,
      2
    ],
    [
      3,
      3
    ],
    [
      6,
      6
    ]
  ],
  "hand_labels": [
    "pattern-a",
    "pattern-b",
    "pattern-a",
    "pattern-b",
    "pattern-c"
  ],
  "hand_query": [
    2,
    2
  ],
  "hand_k3": {
    "label": "pattern-b",
    "neighbor_indices": [
      3,
      1,
      2
    ],
    "neighbor_distances": [
      1.4142135623730951,
      2.0,
      2.0
    ],
    "votes": [
      [
        "pattern-a",
        1
      ],
      [
        "pattern-b",
        2
      ]
    ],
    "tied_vote_labels": [
      "pattern-b"
    ]
  },
  "hand_k4_vote_tie": {
    "label": "pattern-a",
    "neighbor_indices": [
      3,
      1,
      2,
      0
    ],
    "neighbor_distances": [
      1.4142135623730951,
      2.0,
      2.0,
      2.8284271247461903
    ],
    "votes": [
      [
        "pattern-a",
        2
      ],
      [
        "pattern-b",
        2
      ]
    ],
    "tied_vote_labels": [
      "pattern-a",
      "pattern-b"
    ]
  },
  "exact_square_oracle_cases_inside_one_group": 405,
  "rounded_distance_counterexample": {
    "main_label": "b",
    "exact_square_label": "a",
    "coordinates": [
      [
        1,
        9.313225746154785e-10
      ],
      [
        1,
        0
      ]
    ],
    "meaning": "float norm ties can hide exact distance order"
  },
  "checks": {
    "literal_three_neighbors_and_majority_hand_answer": true,
    "literal_distances_have_same_voltage_unit_as_channels": true,
    "vote_tie_uses_smallest_unicode_label_not_nearest_class": true,
    "boundary_distance_tie_can_make_row_order_change_prediction": true,
    "405_integer_grid_queries_and_k_exact_square_oracle_one_group": true,
    "common_channel_translation_preserves_neighbors_and_label": true,
    "common_nonzero_scale_preserves_order_and_scales_distances": true,
    "one_neighbor_and_all_reference_neighbors": true,
    "duplicate_reference_coordinates_keep_declared_row_order": true,
    "rounded_norm_tie_is_not_exact_mathematical_distance_tie": true,
    "larger_ordinary_reference_set_has_no_toy_size_cap": true,
    "shape_container_and_k_contract_rejections": true,
    "feature_type_nonfinite_and_label_contract_rejections": true,
    "finite_input_can_produce_nonfinite_difference_and_is_reported": true
  },
  "unique_check_groups": 14,
  "all_passed": true,
  "limits": "Uniform votes over computed float distances; tie by row index then Unicode label. No trained scaling, accuracy estimate, calibrated probability, nearest-neighbor index or real sensor fault evidence."
}

تساویِ فاصلهٔ float الزاماً تساویِ ریاضی نیست. برای پرسشِ صفر و صفر، دو نقطهٔ (1,2**-30) و (1,0) را با برچسب‌های b و a می‌گذاریم. hypot هر دو فاصله را یک می‌دهد؛ با k یک، سطرِ اول و b انتخاب می‌شود. مرجعِ کسری، نقطهٔ دوم را دقیقاً نزدیک‌تر می‌داند و a می‌دهد. این تفاوتِ عمدی در آزمون ثبت شده است؛ از توافقِ شبکهٔ صحیح، صحتِ رتبه‌بندیِ دقیقِ تمام فاصله‌های بسیار نزدیک را نتیجه نمی‌گیریم.

۵. چهار پرسش و مرز ادعای طبقه‌بندی

پرسش اول: چرا با k چهار، نزدیک‌ترین کلاس برنده نشد؟ پاسخ: معیارِ این روش شمارِ رأی است. a و b هر کدام دو رأی دارند و قاعدهٔ رشته، a را انتخاب می‌کند؛ وزنِ فاصله در رأی وارد نشده است.

پرسش دوم: با ضربِ همهٔ کانال‌ها و پرسش در منفی دو چه می‌شود؟ پاسخ: در مثال، فاصله‌ها دو برابر و ترتیب و رأی ثابت می‌مانند. اما ضربِ تنها یک کانال، هندسه را عوض می‌کند؛ آن تغییر، ویژگیِ ناورداییِ همین مسئله نیست.

پرسش سوم: چرا حالتِ فاصله‌های تقریباً برابر را به زور همسان نکنیم؟ پاسخ: چنین سیاستی به تلورانس و مقیاسِ روشن نیاز دارد و قراردادِ دیگری می‌سازد. این کد فقط برابریِ float را تساوی می‌داند و شاهدِ محدودیتِ آن را آشکار نگه می‌دارد؛ خروجیِ مرجعِ دقیق نیز بی‌صدا جایگزینِ مسیرِ اصلی نمی‌شود.

پرسش چهارم: گذشتنِ چهارده گروه، دقتِ تشخیصِ عیب را ثابت می‌کند؟ پاسخ: خیر؛ دادهٔ ارزیابیِ واقعی نداریم. مرزِ برازشِ مقیاس فقط روی آموزش و تعریفِ معیارهای دسته‌بندی مسئولیت‌های مکمل‌اند. منابع در ۲۶ مهر ۱۴۰۵ خوانده شدند؛ مستندات scikit-learn نسخهٔ 1.9.1 و Python نسخهٔ 3.14.8 از اجرای 3.14.5 جدا ثبت شده‌اند. تاریخِ اصلِ صفحات نامعلوم است و این آموزش، خبرِ تازه یا مجوزِ استقرار نیست.

منابع و مطالعهٔ بیشتر

• scikit-learn؛ تعریف دسته‌بندی با رأی همسایه‌ها
• scikit-learn؛ پارامترها و هشدار تساویِ همسایه‌ها
• Python؛ تعریف و محدودیت دقت math.hypot

بررسی منابع: ۲۶ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.