14.2-dars: K yaqin qo'shni (KNN)

O'QITISH: ma'lumotni SAQLASH (boshqa hech narsa) — "dangasa o'qitish"

BASHORAT (x uchun):
  1. barcha o'quv nuqtalarigacha masofani hisoblash
  2. eng yaqin k tasini tanlash
  3. ular orasida ko'pchilik sinfini qaytarish
     ehtimol = qo'shnilar orasidagi sinf ulushi

KNeighborsClassifier(n_neighbors=5, weights="uniform", metric="minkowski", p=2)

Evklid (p=2):     sqrt(sum (x_i - z_i)^2)        — standart
Manhetten (p=1):  sum |x_i - z_i|                — yuqori o'lchamda barqarorroq
Kosinus:          burchak — matn va vektorlar uchun
Hamming:          kategoriyalar uchun

MASSHTABLASH — MAJBURIY:
  narx (10^6) va o'lcham (10^1) → masofani faqat narx belgilaydi
  StandardScaler yoki MinMaxScaler pipeline ichida (12.9)

k = 1      → juda moslashuvchan: o'quvda 100%, testda shovqinga sezgir (variance ↑)
k katta    → silliq chegara, mahalliy naqshlar yo'qoladi (bias ↑)
k = n      → hamma narsa ko'pchilik sinfi

Amaliy: k ni CV bilan tanlang 12.3-bob; binar vazifada TOQ k (teng bo'linishdan qochish)
Boshlang'ich: k ~ sqrt(n) yoki 5..25 oralig'ini sinash

weights="uniform"  — barcha k qo'shni teng ovoz beradi (standart)
weights="distance" — yaqinroq qo'shni ko'proq ovoz (1/masofa)

distance qachon foydali:
  · ma'lumot notekis zich bo'lsa
  · k katta bo'lsa (uzoq qo'shnilar ta'sirini kamaytiradi)
  · chegara yaqinidagi nuqtalarda aniqroq

Diqqat: distance bilan k=1 va k=50 natijalari yaqinlashadi

Yuqori o'lchamda barcha nuqtalar bir-biridan DEYARLI BIR XIL uzoqlikda bo'ladi
  → "eng yaqin qo'shni" tushunchasi ma'nosini yo'qotadi

Sabab: p o'lchamda hajmning deyarli hammasi "chekkalarda"
  eng yaqin va eng uzoq masofa nisbati 1 ga intiladi

Yechimlar:
  · belgi tanlash yoki o'lchamni kamaytirish (PCA — 10.9)
  · masofa o'lchovini almashtirish (Manhetten, kosinus)
  · KNN dan voz kechish (chiziqli model, daraxtlar)

Sodda qidiruv: O(n × p) har bashorat uchun — katta n da juda sekin

Tezlashtirish:
  algorithm="kd_tree"   — past o'lchamda (p < 20) tez
  algorithm="ball_tree" — o'rta o'lchamda
  algorithm="brute"     — yuqori o'lchamda yoki siyrak ma'lumotda
  taxminiy qidiruv (ANN: faiss, hnswlib) — millionlab vektor uchun

Xotira: butun o'quv to'plami saqlanadi

import numpy as np
from sklearn.model_selection import GridSearchCV, StratifiedKFold
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

quvur = Pipeline([("sc", StandardScaler()), ("m", KNeighborsClassifier())])
setka = {"m__n_neighbors": [1, 3, 5, 9, 15, 25, 41],
         "m__weights": ["uniform", "distance"],
         "m__p": [1, 2]}
qidiruv = GridSearchCV(quvur, setka, cv=StratifiedKFold(5, shuffle=True,
                                                        random_state=0),
                       scoring="f1_macro").fit(X_tr, y_tr)

model.predict_proba(X)          # qo'shnilar orasidagi sinf ulushi
model.kneighbors(X[:1])         # masofalar va indekslar
QOIDA: masshtabla · k ni CV bilan tanla · toq k · p > 30 bo'lsa boshqa model

O'qitish = saqlash · bashorat = k qo'shni ovozi
Masshtablash majburiy · k: kichik→variance, katta→bias
weights="distance" — ko'pincha yaxshiroq · toq k (binar)
O'lcham la'nati: p > 20-30 da samarasiz · bashorat O(n×p)

"""Birliklar masofani qanday buzadi (real numpy/sklearn)."""

import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import MinMaxScaler, StandardScaler


def yarat(seed: int = 5, n: int = 3000):
    """Mahsulot: narx (so'm), og'irlik (kg), reyting (1-5)."""
    rng = np.random.default_rng(seed)
    sinf = rng.integers(0, 2, n)                     # 0 — kundalik, 1 — premium
    narx = np.where(sinf == 1, rng.lognormal(13.8, 0.4, n),
                    rng.lognormal(12.9, 0.4, n))
    ogirlik = np.where(sinf == 1, rng.gamma(3, 0.5, n), rng.gamma(3, 0.55, n))
    reyting = np.where(sinf == 1, rng.normal(4.5, 0.4, n),
                       rng.normal(3.6, 0.6, n)).clip(1, 5)
    X = np.column_stack([narx, ogirlik, reyting])
    return X, sinf


def main() -> None:
    X, y = yarat()
    Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0,
                                          stratify=y)

    print("=== 1. Belgilar masshtabi ===")
    for nom, ustun in zip(["narx", "og'irlik", "reyting"], X.T):
        print(f"  {nom:<9}: o'rtacha {ustun.mean():12.2f}, SD {ustun.std():10.2f}")

    print("\n=== 2. KNN masshtablashsiz ===")
    m = KNeighborsClassifier(15).fit(Xtr, ytr)
    print(f"  test aniqligi = {(m.predict(Xte) == yte).mean():.4f}")

    print("\n=== 3. Masshtablash bilan ===")
    for nom, sc in [("StandardScaler", StandardScaler()),
                    ("MinMaxScaler", MinMaxScaler())]:
        q = Pipeline([("sc", sc), ("m", KNeighborsClassifier(15))]).fit(Xtr, ytr)
        print(f"  {nom:<15}: test aniqligi {(q.predict(Xte) == yte).mean():.4f}")

    print("\n=== 4. Nega: masofaga hissa ===")
    a, b = Xte[0], Xtr[0]
    xom = (a - b) ** 2
    print(f"  masshtablanmagan kvadrat hissalar: "
          f"narx {xom[0]:.3e}, og'irlik {xom[1]:.3e}, reyting {xom[2]:.3e}")
    print(f"  narxning ulushi: {xom[0] / xom.sum():.6%}")
    sc = StandardScaler().fit(Xtr)
    a2, b2 = sc.transform(a.reshape(1, -1))[0], sc.transform(b.reshape(1, -1))[0]
    std = (a2 - b2) ** 2
    print(f"  masshtablangan hissalar: {std.round(3)}, "
          f"narx ulushi {std[0] / std.sum():.1%}")
    print("  ⭐ Masshtablashsiz KNN faqat eng katta birlikli belgini ko'radi")


if __name__ == "__main__":
    main()

=== 1. Belgilar masshtabi ===
  narx     : o'rtacha    758566.12, SD  478802.82
  og'irlik : o'rtacha         1.59, SD       0.94
  reyting  : o'rtacha         4.03, SD       0.66

=== 2. KNN masshtablashsiz ===
  test aniqligi = 0.8667

=== 3. Masshtablash bilan ===
  StandardScaler : test aniqligi 0.9200
  MinMaxScaler   : test aniqligi 0.9144

=== 4. Nega: masofaga hissa ===
  masshtablanmagan kvadrat hissalar: narx 4.419e+10, og'irlik 3.110e-01, reyting 3.960e-01
  narxning ulushi: 100.000000%
  masshtablangan hissalar: [0.195 0.344 0.926], narx ulushi 13.3%
  ⭐ Masshtablashsiz KNN faqat eng katta birlikli belgini ko'radi

"""k ning ta'siri: o'quv, CV va test (real numpy/sklearn)."""

import numpy as np
from sklearn.model_selection import StratifiedKFold, cross_val_score, train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler


def yarat(seed: int = 9, n: int = 2000):
    rng = np.random.default_rng(seed)
    X = rng.normal(0, 1, (n, 2))
    r = np.hypot(X[:, 0], X[:, 1])
    y = (r > 1.0).astype(int)
    almash = rng.random(n) < 0.10                   # 10% shovqin
    y[almash] = 1 - y[almash]
    return X, y


def main() -> None:
    X, y = yarat()
    Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0,
                                          stratify=y)
    cv = StratifiedKFold(5, shuffle=True, random_state=0)

    print("=== 1. k bo'yicha natijalar ===")
    oquv_nom = "o'quv"
    print(f"  {'k':>4} {oquv_nom:>9} {'CV':>9} {'test':>9}")
    for k in [1, 3, 5, 11, 25, 51, 101, 301]:
        q = Pipeline([("sc", StandardScaler()), ("m", KNeighborsClassifier(k))])
        q.fit(Xtr, ytr)
        oquv = (q.predict(Xtr) == ytr).mean()
        cvb = cross_val_score(q, Xtr, ytr, cv=cv).mean()
        test = (q.predict(Xte) == yte).mean()
        print(f"  {k:>4} {oquv:>9.4f} {cvb:>9.4f} {test:>9.4f}")

    print("\n=== 2. k = 1 tuzog'i ===")
    q1 = Pipeline([("sc", StandardScaler()),
                   ("m", KNeighborsClassifier(1))]).fit(Xtr, ytr)
    print(f"  o'quv aniqligi = {(q1.predict(Xtr) == ytr).mean():.4f} "
          f"(har nuqta o'zining qo'shnisi)")
    print(f"  CV aniqligi    = {cross_val_score(q1, Xtr, ytr, cv=cv).mean():.4f}")

    print("\n=== 3. weights='distance' ===")
    for k in [5, 25, 101]:
        for w in ["uniform", "distance"]:
            q = Pipeline([("sc", StandardScaler()),
                          ("m", KNeighborsClassifier(k, weights=w))])
            print(f"  k={k:>3}, {w:<8}: CV {cross_val_score(q, Xtr, ytr, cv=cv).mean():.4f}")

    print("\n=== 4. Shovqin darajasining ta'siri ===")
    for shovqin in [0.0, 0.10, 0.25]:
        rng = np.random.default_rng(3)
        Xs = rng.normal(0, 1, (2000, 2))
        ys = (np.hypot(Xs[:, 0], Xs[:, 1]) > 1.0).astype(int)
        alm = rng.random(2000) < shovqin
        ys[alm] = 1 - ys[alm]
        eng_k, eng_b = None, -1.0
        for k in [1, 5, 15, 51, 151]:
            b = cross_val_score(Pipeline([("sc", StandardScaler()),
                                          ("m", KNeighborsClassifier(k))]),
                                Xs, ys, cv=cv).mean()
            if b > eng_b:
                eng_k, eng_b = k, b
        print(f"  shovqin {shovqin:.0%}: eng yaxshi k = {eng_k}, CV = {eng_b:.4f}")
    print("  ⭐ Shovqin ko'paysa — katta k kerak (silliqroq chegara)")


if __name__ == "__main__":
    main()

=== 1. k bo'yicha natijalar ===
     k     o'quv        CV      test
     1    1.0000    0.8014    0.8117
     3    0.9064    0.8521    0.8517
     5    0.8943    0.8700    0.8717
    11    0.8907    0.8736    0.8800
    25    0.8857    0.8786    0.8817
    51    0.8879    0.8771    0.8783
   101    0.8750    0.8636    0.8800
   301    0.8193    0.7921    0.8417

=== 2. k = 1 tuzog'i ===
  o'quv aniqligi = 1.0000 (har nuqta o'zining qo'shnisi)
  CV aniqligi    = 0.8014

=== 3. weights='distance' ===
  k=  5, uniform : CV 0.8700
  k=  5, distance: CV 0.8543
  k= 25, uniform : CV 0.8786
  k= 25, distance: CV 0.8779
  k=101, uniform : CV 0.8636
  k=101, distance: CV 0.8829

=== 4. Shovqin darajasining ta'siri ===
  shovqin 0%: eng yaxshi k = 1, CV = 0.9860
  shovqin 10%: eng yaxshi k = 15, CV = 0.8775
  shovqin 25%: eng yaxshi k = 15, CV = 0.7265
  ⭐ Shovqin ko'paysa — katta k kerak (silliqroq chegara)

"""Yuqori o'lchamda masofa ma'nosini yo'qotadi (real numpy/sklearn)."""

import numpy as np
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler


def main() -> None:
    rng = np.random.default_rng(6)

    print("=== 1. Masofalar yuqori o'lchamda ===")
    for p in [2, 5, 20, 100, 500]:
        X = rng.normal(0, 1, (1000, p))
        nuqta = rng.normal(0, 1, p)
        masofa = np.sqrt(((X - nuqta) ** 2).sum(axis=1))
        print(f"  p = {p:>3}: eng yaqin {masofa.min():7.3f}, "
              f"eng uzoq {masofa.max():7.3f}, "
              f"nisbat {masofa.max() / masofa.min():.2f}, "
              f"SD/o'rtacha {masofa.std() / masofa.mean():.4f}")
    print("  (nisbat 1 ga intiladi — 'eng yaqin' ma'nosini yo'qotadi)")

    print("\n=== 2. Faqat 2 ta belgi ma'noli, qolgani shovqin ===")
    def yarat(p: int, n: int = 2000, seed: int = 4):
        r = np.random.default_rng(seed)
        X = r.normal(0, 1, (n, p))
        y = (1.5 * X[:, 0] + 1.2 * X[:, 1] + r.normal(0, 0.5, n) > 0).astype(int)
        return X, y

    print(f"  {'p':>4} {'KNN(15)':>10} {'LogReg':>10}")
    for p in [2, 5, 20, 100, 400]:
        X, y = yarat(p)
        Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0,
                                              stratify=y)
        knn = Pipeline([("sc", StandardScaler()),
                        ("m", KNeighborsClassifier(15))]).fit(Xtr, ytr)
        log = Pipeline([("sc", StandardScaler()),
                        ("m", LogisticRegression(max_iter=2000))]).fit(Xtr, ytr)
        print(f"  {p:>4} {(knn.predict(Xte) == yte).mean():>10.4f} "
              f"{(log.predict(Xte) == yte).mean():>10.4f}")

    print("\n=== 3. Yechim: belgi tanlash ===")
    X, y = yarat(400)
    Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0,
                                          stratify=y)
    knn_toliq = Pipeline([("sc", StandardScaler()),
                          ("m", KNeighborsClassifier(15))]).fit(Xtr, ytr)
    knn_2 = Pipeline([("sc", StandardScaler()),
                      ("m", KNeighborsClassifier(15))]).fit(Xtr[:, :2], ytr)
    print(f"  400 belgi bilan: {(knn_toliq.predict(Xte) == yte).mean():.4f}")
    print(f"  2 ta to'g'ri belgi bilan: {(knn_2.predict(Xte[:, :2]) == yte).mean():.4f}")

    print("\n=== 4. Masofa o'lchovini almashtirish ===")
    X, y = yarat(100)
    Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0,
                                          stratify=y)
    for p_norm, nom in [(2, "Evklid"), (1, "Manhetten")]:
        q = Pipeline([("sc", StandardScaler()),
                      ("m", KNeighborsClassifier(15, p=p_norm))]).fit(Xtr, ytr)
        print(f"  {nom:<10}: {(q.predict(Xte) == yte).mean():.4f}")
    print("  ⭐ Yuqori o'lchamda KNN o'rniga chiziqli model yoki belgi tanlash")


if __name__ == "__main__":
    main()

=== 1. Masofalar yuqori o'lchamda ===
  p =   2: eng yaqin   0.053, eng uzoq   4.574, nisbat 85.50, SD/o'rtacha 0.4974
  p =   5: eng yaqin   0.512, eng uzoq   6.086, nisbat 11.89, SD/o'rtacha 0.2685
  p =  20: eng yaqin   3.453, eng uzoq   9.301, nisbat 2.69, SD/o'rtacha 0.1424
  p = 100: eng yaqin  10.739, eng uzoq  17.566, nisbat 1.64, SD/o'rtacha 0.0607
  p = 500: eng yaqin  28.472, eng uzoq  33.966, nisbat 1.19, SD/o'rtacha 0.0276
  (nisbat 1 ga intiladi — 'eng yaqin' ma'nosini yo'qotadi)

=== 2. Faqat 2 ta belgi ma'noli, qolgani shovqin ===
     p    KNN(15)     LogReg
     2     0.9200     0.9233
     5     0.9017     0.9167
    20     0.8250     0.9117
   100     0.7100     0.9167
   400     0.5833     0.8267

=== 3. Yechim: belgi tanlash ===
  400 belgi bilan: 0.5833
  2 ta to'g'ri belgi bilan: 0.8883

=== 4. Masofa o'lchovini almashtirish ===
  Evklid    : 0.7100
  Manhetten : 0.7067
  ⭐ Yuqori o'lchamda KNN o'rniga chiziqli model yoki belgi tanlash

"""GridSearchCV, ehtimollar va bashorat tezligi (real numpy/sklearn)."""

import numpy as np
from sklearn.datasets import load_digits
from sklearn.metrics import accuracy_score, f1_score
from sklearn.model_selection import GridSearchCV, StratifiedKFold, train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler


def main() -> None:
    X, y = load_digits(return_X_y=True)
    Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0,
                                          stratify=y)
    cv = StratifiedKFold(5, shuffle=True, random_state=0)

    print("=== 1. Vazifa ===")
    print(f"  {len(X)} rasm, {X.shape[1]} piksel, {len(np.unique(y))} sinf")

    print("\n=== 2. Giperparametrlarni sozlash ===")
    quvur = Pipeline([("sc", StandardScaler()), ("m", KNeighborsClassifier())])
    setka = {"m__n_neighbors": [1, 3, 5, 9, 15, 25],
             "m__weights": ["uniform", "distance"],
             "m__p": [1, 2]}
    qidiruv = GridSearchCV(quvur, setka, cv=cv, scoring="f1_macro",
                           n_jobs=1).fit(Xtr, ytr)
    print(f"  eng yaxshi: {qidiruv.best_params_}")
    print(f"  CV F1 macro = {qidiruv.best_score_:.4f}")

    print("\n=== 3. Test natijasi ===")
    eng = qidiruv.best_estimator_
    pred = eng.predict(Xte)
    print(f"  aniqlik = {accuracy_score(yte, pred):.4f}")
    print(f"  F1 macro = {f1_score(yte, pred, average='macro'):.4f}")
    proba = eng.predict_proba(Xte[:3])
    print(f"  ehtimollar (birinchi 3 namuna, maksimal): {proba.max(axis=1).round(3)}")
    print("  (ehtimol = k qo'shni orasidagi sinf ulushi — diskret qiymatlar)")

    print("\n=== 4. O'qitish va bashorat narxi ===")
    q = Pipeline([("sc", StandardScaler()),
                  ("m", KNeighborsClassifier(5))])
    q.fit(Xtr, ytr)
    print(f"  o'qitishda saqlangan namunalar: {len(Xtr)}")
    print(f"  har bashorat uchun masofa hisoblari: "
          f"{len(Xtr)} x {Xtr.shape[1]} = {len(Xtr) * Xtr.shape[1]:,}")
    print(f"  {len(Xte)} namuna uchun jami: "
          f"{len(Xte) * len(Xtr) * Xtr.shape[1] / 1e6:.1f} mln amal")
    print(f"  saqlangan ma'lumot: {Xtr.nbytes / 1024:.0f} KB")
    print("  ⭐ KNN: o'qitish bepul, bashorat qimmat — boshqa modellarning teskarisi")


if __name__ == "__main__":
    main()

=== 1. Vazifa ===
  1797 rasm, 64 piksel, 10 sinf

=== 2. Giperparametrlarni sozlash ===
  eng yaxshi: {'m__n_neighbors': 3, 'm__p': 1, 'm__weights': 'distance'}
  CV F1 macro = 0.9728

=== 3. Test natijasi ===
  aniqlik = 0.9778
  F1 macro = 0.9777
  ehtimollar (birinchi 3 namuna, maksimal): [1. 1. 1.]
  (ehtimol = k qo'shni orasidagi sinf ulushi — diskret qiymatlar)

=== 4. O'qitish va bashorat narxi ===
  o'qitishda saqlangan namunalar: 1257
  har bashorat uchun masofa hisoblari: 1257 x 64 = 80,448
  540 namuna uchun jami: 43.4 mln amal
  saqlangan ma'lumot: 628 KB
  ⭐ KNN: o'qitish bepul, bashorat qimmat — boshqa modellarning teskarisi

KNeighborsClassifier(5).fit(X, y)                                 # ⚠️
Pipeline([("sc", StandardScaler()), ("m", KNeighborsClassifier(5))]) # ✅

X = StandardScaler().fit_transform(X); cross_val_score(knn, X, y) # ⚠️
cross_val_score(Pipeline([...]), X, y, cv=5)                      # ✅

KNeighborsClassifier()                 # k = 5 standart            # ⚠️
GridSearchCV(pipe, {"m__n_neighbors": [1,3,5,9,15,25,41]}, cv=5)  # ✅

KNeighborsClassifier(n_neighbors=10)                              # ⚠️
KNeighborsClassifier(n_neighbors=11)                              # ✅

KNeighborsClassifier().fit(X_300_belgi, y)                        # ⚠️
# belgi tanlash, PCA yoki chiziqli model                          # ✅

print(knn1.score(X_train, y_train))    # k=1 da har doim 1.0      # ⚠️
cross_val_score(pipe, X, y, cv=5)                                 # ✅

KNeighborsClassifier(25)               # 2% musbat sinf           # ⚠️
# kichikroq k, weights="distance", chegara moslash 12.7-bob         # ✅

1.  # KNN o'qitishda nima qiladi?
2.  # bashorat qadamlari?
3.  # nega masshtablash?
4.  # k kichik bo'lsa?
5.  # k katta bo'lsa?
6.  # binar vazifada k qanday?
7.  # weights variantlari?
8.  # o'lcham la'nati nima?
9.  # p chegarasi taxminan?
10. # predict_proba nima beradi?
11. # bashorat murakkabligi?
12. # katta ma'lumotda nima ishlatiladi?

1.  KNeighborsClassifier(5).fit(X, y)   # narx va reyting belgilari

2.  KNeighborsClassifier(n_neighbors=10)   # binar vazifa

3.  print(knn.score(X_train, y_train))   # k=1

4.  KNeighborsClassifier().fit(X, y)   # 250 belgi

5.  X = StandardScaler().fit_transform(X); cross_val_score(knn, X, y)