ماتریسهای نزدیکی و نامتشابهی
جای این صفحه در درس¶
بندهای ۱۴.۳.۱ تا ۱۴.۳.۳ از hastie2009esl (صص ۵۰۳–۵۰۷) هیچ الگوریتم خوشهبندی ندارند. اول آمدهاند چون هر روشی در بقیهٔ این فصل یک ماتریس نامتشابهی را ورودی میگیرد: عددهای آن ماتریس جواب را تعیین میکنند و الگوریتم فقط تعیین میکند این عددها چگونه گروه شوند. کتاب دربارهٔ این اولویت صریح است (ص ۵۰۶):
تعیین یک سنجهٔ نامتشابهی مناسب، برای موفقیت در خوشهبندی بسیار مهمتر از انتخاب الگوریتم خوشهبندی است.
این صفحه سه بند را به ترتیب پوشش میدهد:
| بند | پرسش |
|---|---|
| ۱۴.۳.۱ ماتریسهای نزدیکی | اگر خودِ داده جدولی از نزدیکیها باشد چه؟ |
| ۱۴.۳.۲ نامتشابهی بر پایهٔ ویژگیها | یک ویژگی چگونه مقایسه میشود؟ |
| ۱۴.۳.۳ نامتشابهی اشیا | ویژگیها چگونه و با چه وزنهایی ترکیب میشوند؟ |
در پایان باید بتوانید¶
یک ماتریس نزدیکی را بخوانید و بگویید کدامیک از چهار قرارداد (نامنفی، قطر صفر، متقارن، متری) را برمیآورد و اگر یکی برنیامد چه کنید؛
برای متغیرهای کمّی، ترتیبی و اسمی نامتشابهی ویژگی را برگزینید و بگویید هر انتخاب چه فرضی میگذارد؛
ترکیب وزنی (۱۴.۲۴) را بنویسید و توضیح دهید چرا وزنهای برابر تأثیر برابر نیست؛
نامتشابهی میانگین (۱۴.۲۷) یعنی را حساب کنید و با آن تصمیم بگیرید استانداردسازی برای یک مجموعهدادهٔ مشخص ایدهٔ خوبی است یا نه.
۱. دادهای که مستقیماً ماتریس نزدیکی است¶
گاهی هیچ مقدار ویژگیای در کار نیست. در آزمایشهای علوم اجتماعی از شرکتکنندهها میپرسند دو شیء چقدر تفاوت دارند و پاسخها در یک عدد میانگین میشوند؛ در بازیابی اطلاعات عدد شباهتی میان سندهاست؛ در روانشناسی از نرخ درهمریختگی میآید. نتیجه ماتریسی است به نام که نزدیکی اشیای و است، و همانگونه به الگوریتم سپرده میشود.
چهار قرارداد تقریباً جهانیاند و ارزش دارد پیش از هر خوشهبندی هر چهار را بررسی کنید:
درایههای نامنفی، قطر صفر: . هر شباهت را با تابعی اکیداً نزولی به نامتشابهی تبدیل میکنند، مثلاً یا ؛ انتخاب تابع بخشی از مدل است.
تقارن: بیشتر الگوریتمها را فرض میکنند، پس ماتریس نامتقارن را با جانشین میکنند.
نامساوی مثلث : نامتشابهیهایی که با قضاوت ذهنی ساخته میشوند بهندرت آن را برمیآورند، پس باید بررسی شود نه فرض.
قابلمقایسه بودن مقیاس: درایههای یک ماتریس باید با یک مقیاس سنجیده شوند؛ آمیختن دو پیمایش یعنی مقیاس یکی را دوبارهتنظیم کردن.
مثال زیر جدول ۱۴.۳ کتاب است: دوازده کشور، که دانشجویان علوم سیاسی جفتجفت دربارهشان قضاوت کردهاند. در کتاب فقط مثلث پایین چاپ شده است.
import numpy as np
names = ["BEL", "BRA", "CHI", "CUB", "EGY", "FRA",
"IND", "ISR", "USA", "USS", "YUG", "ZAI"]
lower = { # Table 14.3 of ESL: average pairwise dissimilarities, lower triangle
"BRA": [5.58],
"CHI": [7.00, 6.50],
"CUB": [7.08, 7.00, 3.83],
"EGY": [4.83, 5.08, 8.17, 5.83],
"FRA": [2.17, 5.75, 6.67, 6.92, 4.92],
"IND": [6.42, 5.00, 5.58, 6.00, 4.67, 6.42],
"ISR": [3.42, 5.50, 6.42, 6.42, 5.00, 3.92, 6.17],
"USA": [2.50, 4.92, 6.25, 7.33, 4.50, 2.25, 6.33, 2.75],
"USS": [6.08, 6.67, 4.25, 2.67, 6.00, 6.17, 6.17, 6.92, 6.17],
"YUG": [5.25, 6.83, 4.50, 3.75, 5.75, 5.42, 6.08, 5.83, 6.67, 3.67],
"ZAI": [4.75, 3.00, 6.08, 6.67, 5.00, 5.58, 4.83, 6.17, 5.67, 6.50, 6.92],
}
D = np.zeros((len(names), len(names)))
for i, country in enumerate(names[1:], start=1):
for j, value in enumerate(lower[country]):
D[i, j] = D[j, i] = value # the table is symmetric: fill both halves
print(" " + " ".join(f"{n:>5}" for n in names))
for i, n in enumerate(names):
print(f"{n:>4} " + " ".join(f"{D[i, j]:5.2f}" for j in range(len(names)))) BEL BRA CHI CUB EGY FRA IND ISR USA USS YUG ZAI
BEL 0.00 5.58 7.00 7.08 4.83 2.17 6.42 3.42 2.50 6.08 5.25 4.75
BRA 5.58 0.00 6.50 7.00 5.08 5.75 5.00 5.50 4.92 6.67 6.83 3.00
CHI 7.00 6.50 0.00 3.83 8.17 6.67 5.58 6.42 6.25 4.25 4.50 6.08
CUB 7.08 7.00 3.83 0.00 5.83 6.92 6.00 6.42 7.33 2.67 3.75 6.67
EGY 4.83 5.08 8.17 5.83 0.00 4.92 4.67 5.00 4.50 6.00 5.75 5.00
FRA 2.17 5.75 6.67 6.92 4.92 0.00 6.42 3.92 2.25 6.17 5.42 5.58
IND 6.42 5.00 5.58 6.00 4.67 6.42 0.00 6.17 6.33 6.17 6.08 4.83
ISR 3.42 5.50 6.42 6.42 5.00 3.92 6.17 0.00 2.75 6.92 5.83 6.17
USA 2.50 4.92 6.25 7.33 4.50 2.25 6.33 2.75 0.00 6.17 6.67 5.67
USS 6.08 6.67 4.25 2.67 6.00 6.17 6.17 6.92 6.17 0.00 3.67 6.50
YUG 5.25 6.83 4.50 3.75 5.75 5.42 6.08 5.83 6.67 3.67 0.00 6.92
ZAI 4.75 3.00 6.08 6.67 5.00 5.58 4.83 6.17 5.67 6.50 6.92 0.00
سه قرارداد اول آسانآزمایاند و این ماتریس هر سه را میگذراند.
print("nonnegative entries :", D.min() >= 0)
print("zero diagonal :", np.allclose(np.diag(D), 0))
print("symmetric :", np.allclose(D, D.T))nonnegative entries : True
zero diagonal : True
symmetric : True
چهارمی جالبتر است. آن هم میگذرد، و این ارزش توجه دارد چون با نحوهٔ تولید چنین عددهایی تضمین نشده است. بهتوانرساندن هر درایه تبدیلی اکیداً صعودی است، دقیقاً همان نوع تغییری که تحلیلگر ممکن است برای برجستهکردن تفاوتهای بزرگ انجام دهد؛ سه قرارداد آسان را نگه میدارد و چهارمی را از بین میبرد.
import itertools
def triangle_violations(M, tol=1e-12):
"""All ordered triples (a, b, c) with d(a, b) > d(a, c) + d(c, b)."""
out = []
for a, b, c in itertools.permutations(range(len(M)), 3):
if M[a, b] > M[a, c] + M[c, b] + tol:
out.append((a, b, c))
return out
print("violations in Table 14.3 :", len(triangle_violations(D)))
violations = triangle_violations(D ** 2)
print("violations after squaring them:", len(violations))
for a, b, c in violations[:3]:
print(f" d({names[a]},{names[b]}) = {D[a, b] ** 2:.2f} > "
f"d({names[a]},{names[c]}) + d({names[c]},{names[b]}) = "
f"{D[a, c] ** 2 + D[c, b] ** 2:.2f}")violations in Table 14.3 : 0
violations after squaring them: 56
d(BEL,BRA) = 31.14 > d(BEL,USA) + d(USA,BRA) = 30.46
d(BEL,CHI) = 49.00 > d(BEL,USA) + d(USA,CHI) = 45.31
d(BEL,CHI) = 49.00 > d(BEL,YUG) + d(YUG,CHI) = 47.81
پس «آیا این یک فاصله است؟» خاصیتی است مربوط به عددهایی که به الگوریتم میدهید، نه به اشیایی که خوشهبندی میشوند. الگوریتمی که فقط از ترتیب درایهها بهره میبرد تفاوت را نمیبیند؛ الگوریتمی که آنها را جمع و ضرب میکند میبیند. این تمایز در صفحهٔ خوشهبندی سلسلهمراتبی بازمیگردد، جایی که پیوند تک و کامل تنها به ترتیب وابستهاند.
همین است که K-medoids روی دادههایی مانند جدول ۱۴.۳ کار میکند و K-means نه: K-means برای میانگینگیری مختصات میخواهد و اینجا هیچ مختصاتی نیست.
۲. نامتشابهیهایی که از ویژگیها حساب میشوند¶
معمولاً ویژگیها هستند: اندازهگیریهای برای اشیای و متغیرهای . دستور کتاب این است که برای هر ویژگی نامتشابهی تعریف کنیم و جمع بزنیم:
با پیشفرضی که با فاصلهٔ زیادی رایج است:
این پیشفرض جهانی نیست و جانشینها از نوع متغیر برمیآیند:
| نوع متغیر | نامتشابهی دو مقدار | نکته |
|---|---|---|
| کمّی | ، یا | خطای مجذور تفاوتهای بزرگ را برجسته میکند؛ خطای قدرمطلق نه |
| ترتیبی | کدها را اعداد بگیرید | (۱۴.۲۳)، ترتیب حفظ، فاصلهگذاری از خود درآوردهشده |
| اسمی | ماتریس زیان با و | زیانهای نابرابر مجازند و دانش حوزه را رمز میکنند |
دو هشدار همراه این جدول است. برای متغیرهای کمّی، خوشهبندی بر پایهٔ همبستگی (۱۴.۲۲) همان خوشهبندی بر پایهٔ فاصلهٔ مجذور پس از استانداردسازی هر مشاهده است: اگر سطرها مرکززدایی و مقیاسبندی شوند، آنگاه ، پس دو نامتشابهی تابعهایی یکنوا از هماند. سلول زیر این اتحاد را روی دو گل زنبق بررسی میکند.
from sklearn.datasets import load_iris
iris = load_iris()
X = iris.data
y = iris.target
# each observation centred and scaled to unit variance, so that sum_j x_ij^2 = p
Z = (X - X.mean(axis=1, keepdims=True)) / X.std(axis=1, keepdims=True)
i, k = 0, 60
a, b = Z[i], Z[k]
rho = np.corrcoef(a, b)[0, 1]
p = X.shape[1]
print(f"correlation of the two flowers : {rho:.4f}")
print(f"squared distance between the scaled rows : {((a - b) ** 2).sum():.4f}")
print(f"2 p (1 - rho) : {2 * p * (1 - rho):.4f}")correlation of the two flowers : 0.7232
squared distance between the scaled rows : 2.2144
2 p (1 - rho) : 2.2144
برای متغیرهای ترتیبی کدها با عددهای با فاصلهٔ یکسان در جانشین و سپس کمّی تلقی میشوند. این تبدیل تصمیمی مدلسازی است: تصریح میکند که گام از «بدم میآید» به «دوست ندارم» هماندازهٔ گام از «دوست دارم» به «عالی است» است.
grades = ["A", "B", "C", "D", "F"]
M = len(grades)
scale = {g: (r + 1 - 0.5) / M for r, g in enumerate(grades)}
print({g: round(v, 2) for g, v in scale.items()}){'A': 0.1, 'B': 0.3, 'C': 0.5, 'D': 0.7, 'F': 0.9}
برای متغیرهای اسمی ماتریس زیان میگوید هر درهمریختگی چه هزینهای دارد. پیشفرض «هر دو مقدار متفاوت بهاندازهٔ ۱ تفاوت دارند» است، که همان شمارش سادهٔ ناهمخوانی است؛ ماتریس مناسب حوزه میتواند مثلاً بگوید اشتباه گرفتن سیاه با قرمز خطای کوچکتری است تا سیاه با بلوند.
colours = ["black", "blond", "red"]
index = {c: r for r, c in enumerate(colours)}
L = np.array([[0.0, 1.0, 0.5], # black
[1.0, 0.0, 1.0], # blond
[0.5, 1.0, 0.0]]) # red
print("d(black, red) =", L[index["black"], index["red"]],
" (the default would be 1)")
print("d(black, blond)=", L[index["black"], index["blond"]])d(black, red) = 0.5 (the default would be 1)
d(black, blond)= 1.0
۳. نامتشابهی اشیا: ترکیب ویژگیها¶
پس از آنکه هر ویژگی نامتشابهی خودش را یافت، با میانگین وزنی ترکیب میشوند. وزنها به یک جمع میشوند تا در مقیاس بماند:
برابر گذاشتن همهٔ وزنها تأثیر برابر همهٔ ویژگیها را نمیدهد. تأثیر ویژگی برابر است، که
نامتشابهی میانگین روی آن ویژگی است؛ ویژگیای که مقدارهایش در بازهٔ پهنی پخشاند، هرچه وزنش بگوید، بیشتر سهم میگذارد. تأثیر برابر میخواهد، و برای خطای مجذور اتحاد
وزن را صریح میکند: . این دقیقاً همان کاری است که استانداردسازی هر ویژگی میکند. سلول زیر (۱۴.۲۷) را روی دادهٔ زنبق بررسی میکند.
X = iris.data
n = len(X)
dbar = np.zeros(X.shape[1])
for j in range(X.shape[1]):
diffs = (X[:, j][:, None] - X[:, j][None, :]) ** 2
dbar[j] = diffs.sum() / n ** 2
print("dbar_j :", np.round(dbar, 3))
print("2 * var_j :", np.round(2 * X.var(axis=0), 3))
print("ratio :", np.round(dbar / (2 * X.var(axis=0)), 12))dbar_j : [1.362 0.377 6.191 1.154]
2 * var_j : [1.362 0.377 6.191 1.154]
ratio : [1. 1. 1. 1.]
پس استانداردسازی گامی پیشپردازشی بیطرف نیست: گزارهای است که هر ویژگی سزاوار تأثیر یکسان بر فاصله است. وقتی گروهها را ویژگیای جدا میکند که بیشترین واریانس را هم دارد، این گزاره نادرست است و برابرکردن ویژگیها میتواند گروههایی را که پیشتر آشکار بودند مبهم کند. شکل ۱۴.۵ کتاب ESL تصویر استاندارد این شکست است: دو گروه بهخوبی جدا، ویژگی دومی در مقیاسی بسیار بزرگتر، و خوشهبندیای که از مقیاس پیروی میکند نه از گروهها.
آزمایش زیر K-means را دوبار روی دادهٔ زنبق اجرا میکند، یکبار روی ویژگیهای خام و یکبار روی استانداردشده، و توافق با برچسب گونهها را گزارش میدهد. دو سطر را چنین بخوانید: «مقیاسبندی اینجا چقدر مهم بود؟»
import warnings
from sklearn.cluster import KMeans
from sklearn.metrics import adjusted_rand_score
warnings.filterwarnings("ignore", message="KMeans is known to have a memory leak")
Z_std = (X - X.mean(axis=0)) / X.std(axis=0)
for name, Z in [("raw", X), ("standardised", Z_std)]:
km = KMeans(n_clusters=3, n_init=10, random_state=0).fit(Z)
print(f"{name:>13}: within-cluster SS {km.inertia_:8.2f} "
f"ARI with species {adjusted_rand_score(y, km.labels_):.3f}") raw: within-cluster SS 78.85 ARI with species 0.730
standardised: within-cluster SS 139.82 ARI with species 0.620
دو نکتهٔ عملی دیگر از این بند:
وزنهای متفاوت تصمیمی مدلسازی است، نه جزئیات فنی. اگر پرسش «کدام تومورها شبیه هماند؟» باشد، ژنهایی مهماند که زیستشناسانه مهماند؛ تأثیر برابر دادن به همهٔ ۶۸۳۰ ژن یک انتخاب است، و معمولاً انتخاب بدی.
مقدارهای گمشده. دستور رایج این است که را از ویژگیهایی حساب کنیم که هر دو مشاهده دارند و جفتی را که هیچ ویژگی مشترک اندازهگیریشدهای ندارد بیندازیم. جانشینش پرکردن با میانگین یا میانه است، و برای متغیرهای اسمی میتوان «گمشده» را خود یک مقدار گرفت — اگر معقول باشد که دو شیء شبیهاند چون هر دو همان متغیر را گزارش نکردهاند.
خلاصه¶
هر روش خوشهبندی در این فصل تابعی از یک ماتریس نامتشابهی است؛ گاهی خود داده بهصورت همان ماتریس میآید و آنگاه مختصاتی برای میانگینگیری نیست.
قراردادها را بررسی کنید: نامنفی، قطر صفر، متقارن، و — جدا — اینکه درایهها مانند یک متری رفتار کنند. بهتوانرساندن سه تای اول را نگه میدارد و میتواند چهارمی را بشکند.
نامتشابهی ویژگی به نوع متغیر بستگی دارد: خطای مجذور یا قدرمطلق، همبستگی، مقیاسبندی ترتیبی، یا ماتریس زیان برای مقدارهای اسمی.
ویژگیها در ترکیبی محدب (۱۴.۲۴) با هم میآیند و تأثیر مؤثر ویژگی برابر است، نه . وزنهای برابر تأثیری متناسب با واریانس میدهند؛ استانداردسازی آن را برابر میکند، که گاهی دقیقاً همان چیزی است که نمیخواهید.
تمرینها¶
ماتریس شباهت را با معکوس کردن تبدیل به جدول ۱۴.۳ برگردانید. کدام روش خوشهبندی این درس میتواند مستقیماً روی شباهتها کار کند و کدام نمیتواند؟
تبدیل یکنوای را به جدول ۱۴.۳ اعمال کنید و جواب ۳-مدوئید را با جواب صفحهٔ K-medoids مقایسه کنید. مدوئیدها جابهجا شدند؟
را برای چهار ویژگی زنبق و وزنهای متناظر حساب کنید. کدام ویژگی پس از استانداردسازی بیشترین تأثیر را دارد و کدام پیش از آن داشت؟
سه شیء و دو ویژگی کمّی بسازید چنان که K-means روی دادهٔ خام دو گروه آشکار را بازیابد و K-means روی دادهٔ استانداردشده نه. (راهنما: ویژگی جداکننده را همان ویژگیِ پر واریانس بگیرید.)
با یک مقدار گمشده در یک مختصهٔ یکی از مشاهدهها، ماتریس نامتشابهی را هم با انداختن آن جفت و هم با پرکردن با میانگین حساب کنید و خوشهبندی کنید. تفاوت دیده میشود؟
ماتریس زیان سه رنگ چشم را بنویسید چنان که آبی/سبز خطای کوچکتری از آبی/قهوهای باشد، و توضیح دهید این ماتریس چه ادعایی دربارهٔ حوزه میکند.
منابع¶
قراردادها، (۱۴.۲۰)–(۱۴.۲۵)، بحث استانداردسازی و نقلقول: بندهای ۱۴.۳.۱–۱۴.۳.۳ از hastie2009esl، صص ۵۰۳–۵۰۷.
جدول ۱۴.۳ و پیمایش کشورها: Kaufman and Rousseeuw (1990)، همانجا ارجاع داده شده؛ داده در صفحهٔ K-medoids دوباره به کار میرود.
دادهٔ زنبق:
sklearn.datasets.load_iris، همان مجموعهدادهای که در Clustering-Part1 به کار رفت.
