Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

ماتریس‌های نزدیکی و نامتشابهی

English · فارسی

ماتریس‌های نزدیکی و نامتشابهی

گروه علوم کامپیوتر، دانشگاه فردوسی مشهد

جای این صفحه در درس

بندهای ۱۴.۳.۱ تا ۱۴.۳.۳ از hastie2009esl (صص ۵۰۳–۵۰۷) هیچ الگوریتم خوشه‌بندی ندارند. اول آمده‌اند چون هر روشی در بقیهٔ این فصل یک ماتریس نامتشابهی را ورودی می‌گیرد: عددهای آن ماتریس جواب را تعیین می‌کنند و الگوریتم فقط تعیین می‌کند این عددها چگونه گروه شوند. کتاب دربارهٔ این اولویت صریح است (ص ۵۰۶):

تعیین یک سنجهٔ نامتشابهی مناسب، برای موفقیت در خوشه‌بندی بسیار مهم‌تر از انتخاب الگوریتم خوشه‌بندی است.

این صفحه سه بند را به ترتیب پوشش می‌دهد:

بندپرسش
۱۴.۳.۱ ماتریس‌های نزدیکیاگر خودِ داده جدولی از نزدیکی‌ها باشد چه؟
۱۴.۳.۲ نامتشابهی بر پایهٔ ویژگی‌هایک ویژگی چگونه مقایسه می‌شود؟
۱۴.۳.۳ نامتشابهی اشیاویژگی‌ها چگونه و با چه وزن‌هایی ترکیب می‌شوند؟

در پایان باید بتوانید

  • یک ماتریس نزدیکی را بخوانید و بگویید کدام‌یک از چهار قرارداد (نامنفی، قطر صفر، متقارن، متری) را برمی‌آورد و اگر یکی برنیامد چه کنید؛

  • برای متغیرهای کمّی، ترتیبی و اسمی نامتشابهی ویژگی را برگزینید و بگویید هر انتخاب چه فرضی می‌گذارد؛

  • ترکیب وزنی (۱۴.۲۴) را بنویسید و توضیح دهید چرا وزن‌های برابر تأثیر برابر نیست؛

  • نامتشابهی میانگین (۱۴.۲۷) یعنی 2⋅varj2 \cdot \mathrm{var}_j را حساب کنید و با آن تصمیم بگیرید استانداردسازی برای یک مجموعه‌دادهٔ مشخص ایدهٔ خوبی است یا نه.

۱. داده‌ای که مستقیماً ماتریس نزدیکی است

گاهی هیچ مقدار ویژگی‌ای در کار نیست. در آزمایش‌های علوم اجتماعی از شرکت‌کننده‌ها می‌پرسند دو شیء چقدر تفاوت دارند و پاسخ‌ها در یک عدد میانگین می‌شوند؛ در بازیابی اطلاعات عدد شباهتی میان سندهاست؛ در روان‌شناسی از نرخ درهم‌ریختگی می‌آید. نتیجه ماتریسی N×NN \times N است به نام D\mathbf{D} که dii′d_{ii'} نزدیکی اشیای ii و i′i' است، و همان‌گونه به الگوریتم سپرده می‌شود.

چهار قرارداد تقریباً جهانی‌اند و ارزش دارد پیش از هر خوشه‌بندی هر چهار را بررسی کنید:

  1. درایه‌های نامنفی، قطر صفر: dii=0d_{ii} = 0. هر شباهت را با تابعی اکیداً نزولی به نامتشابهی تبدیل می‌کنند، مثلاً d=1−sd = 1 - s یا d=1/s−1d = 1/s - 1؛ انتخاب تابع بخشی از مدل است.

  2. تقارن: بیشتر الگوریتم‌ها dii′=di′id_{ii'} = d_{i'i} را فرض می‌کنند، پس ماتریس نامتقارن را با (D+DT)/2(\mathbf{D} + \mathbf{D}^T)/2 جانشین می‌کنند.

  3. نامساوی مثلث dii′≤dik+dki′d_{ii'} \le d_{ik} + d_{ki'}: نامتشابهی‌هایی که با قضاوت ذهنی ساخته می‌شوند به‌ندرت آن را برمی‌آورند، پس باید بررسی شود نه فرض.

  4. قابل‌مقایسه بودن مقیاس: درایه‌های یک ماتریس باید با یک مقیاس سنجیده شوند؛ آمیختن دو پیمایش یعنی مقیاس یکی را دوباره‌تنظیم کردن.

مثال زیر جدول ۱۴.۳ کتاب است: دوازده کشور، که دانشجویان علوم سیاسی جفت‌جفت درباره‌شان قضاوت کرده‌اند. در کتاب فقط مثلث پایین چاپ شده است.

       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

سه قرارداد اول آسان‌آزمای‌اند و این ماتریس هر سه را می‌گذراند.

nonnegative entries : True
zero diagonal       : True
symmetric           : True

چهارمی جالب‌تر است. آن هم می‌گذرد، و این ارزش توجه دارد چون با نحوهٔ تولید چنین عددهایی تضمین نشده است. به‌توان‌رساندن هر درایه تبدیلی اکیداً صعودی است، دقیقاً همان نوع تغییری که تحلیلگر ممکن است برای برجسته‌کردن تفاوت‌های بزرگ انجام دهد؛ سه قرارداد آسان را نگه می‌دارد و چهارمی را از بین می‌برد.

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 برای میانگین‌گیری مختصات می‌خواهد و اینجا هیچ مختصاتی نیست.

۲. نامتشابهی‌هایی که از ویژگی‌ها حساب می‌شوند

معمولاً ویژگی‌ها هستند: اندازه‌گیری‌های xijx_{ij} برای اشیای i=1,…,Ni = 1,\dots,N و متغیرهای j=1,…,pj = 1,\dots,p. دستور کتاب این است که برای هر ویژگی نامتشابهی تعریف کنیم و جمع بزنیم:

D(xi,xi′)=∑j=1pdj(xij,xi′j),(14.20)D(x_i, x_{i'}) = \sum_{j=1}^{p} d_j(x_{ij}, x_{i'j}), \qquad \text{(14.20)}

با پیش‌فرضی که با فاصلهٔ زیادی رایج است:

dj(xij,xi′j)=(xij−xi′j)2.(14.21)d_j(x_{ij}, x_{i'j}) = (x_{ij} - x_{i'j})^2 . \qquad \text{(14.21)}

این پیش‌فرض جهانی نیست و جانشین‌ها از نوع متغیر برمی‌آیند:

نوع متغیرنامتشابهی دو مقدارنکته
کمّی(⋅)2(\cdot)^2، ∣⋅∣\lvert \cdot \rvert یا 1−ρ1 - \rhoخطای مجذور تفاوت‌های بزرگ را برجسته می‌کند؛ خطای قدرمطلق نه
ترتیبیکدها را اعداد r−1/2M\frac{r - 1/2}{M} بگیرید(۱۴.۲۳)، ترتیب حفظ، فاصله‌گذاری از خود درآورده‌شده
اسمیماتریس زیان Lrr′L_{rr'} با Lrr=0L_{rr} = 0 و Lrr′=1L_{rr'} = 1زیان‌های نابرابر مجازند و دانش حوزه را رمز می‌کنند

دو هشدار همراه این جدول است. برای متغیرهای کمّی، خوشه‌بندی بر پایهٔ همبستگی (۱۴.۲۲) همان خوشه‌بندی بر پایهٔ فاصلهٔ مجذور پس از استانداردسازی هر مشاهده است: اگر سطرها مرکززدایی و مقیاس‌بندی شوند، آن‌گاه ∑j(xij−xi′j)2=2p (1−ρ(xi,xi′))\sum_j (x_{ij} - x_{i'j})^2 = 2p\,(1 - \rho(x_i, x_{i'}))، پس دو نامتشابهی تابع‌هایی یکنوا از هم‌اند. سلول زیر این اتحاد را روی دو گل زنبق بررسی می‌کند.

correlation of the two flowers              : 0.7232
squared distance between the scaled rows    : 2.2144
2 p (1 - rho)                               : 2.2144

برای متغیرهای ترتیبی کدها با عددهای با فاصلهٔ یکسان در [0,1][0, 1] جانشین و سپس کمّی تلقی می‌شوند. این تبدیل تصمیمی مدل‌سازی است: تصریح می‌کند که گام از «بدم می‌آید» به «دوست ندارم» هم‌اندازهٔ گام از «دوست دارم» به «عالی است» است.

{'A': 0.1, 'B': 0.3, 'C': 0.5, 'D': 0.7, 'F': 0.9}

برای متغیرهای اسمی ماتریس زیان می‌گوید هر درهم‌ریختگی چه هزینه‌ای دارد. پیش‌فرض «هر دو مقدار متفاوت به‌اندازهٔ ۱ تفاوت دارند» است، که همان شمارش سادهٔ ناهم‌خوانی است؛ ماتریس مناسب حوزه می‌تواند مثلاً بگوید اشتباه گرفتن سیاه با قرمز خطای کوچک‌تری است تا سیاه با بلوند.

d(black, red)  = 0.5   (the default would be 1)
d(black, blond)= 1.0

۳. نامتشابهی اشیا: ترکیب ویژگی‌ها

پس از آن‌که هر ویژگی نامتشابهی خودش را یافت، با میانگین وزنی ترکیب می‌شوند. وزن‌ها به یک جمع می‌شوند تا DD در مقیاس djd_j بماند:

D(xi,xi′)=∑j=1pwj dj(xij,xi′j),∑jwj=1.(14.24)D(x_i, x_{i'}) = \sum_{j=1}^{p} w_j \, d_j(x_{ij}, x_{i'j}), \qquad \sum_j w_j = 1 . \qquad \text{(14.24)}

برابر گذاشتن همهٔ وزن‌ها تأثیر برابر همهٔ ویژگی‌ها را نمی‌دهد. تأثیر ویژگی jj برابر wjdˉjw_j \bar d_j است، که

dˉj=1N2∑i=1N∑i′=1Ndj(xij,xi′j)(14.25)\bar d_j = \frac{1}{N^2} \sum_{i=1}^{N} \sum_{i'=1}^{N} d_j(x_{ij}, x_{i'j}) \qquad \text{(14.25)}

نامتشابهی میانگین روی آن ویژگی است؛ ویژگی‌ای که مقدارهایش در بازهٔ پهنی پخش‌اند، هرچه وزنش بگوید، بیشتر سهم می‌گذارد. تأثیر برابر wj=1/dˉjw_j = 1/\bar d_j می‌خواهد، و برای خطای مجذور اتحاد

dˉj=1N2∑i∑i′(xij−xi′j)2=2⋅varj(14.27)\bar d_j = \frac{1}{N^2} \sum_i \sum_{i'} (x_{ij} - x_{i'j})^2 = 2 \cdot \mathrm{var}_j \qquad \text{(14.27)}

وزن را صریح می‌کند: wj=1/(2 varj)w_j = 1/(2\,\mathrm{var}_j). این دقیقاً همان کاری است که استانداردسازی هر ویژگی می‌کند. سلول زیر (۱۴.۲۷) را روی دادهٔ زنبق بررسی می‌کند.

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 را دوبار روی دادهٔ زنبق اجرا می‌کند، یک‌بار روی ویژگی‌های خام و یک‌بار روی استانداردشده، و توافق با برچسب گونه‌ها را گزارش می‌دهد. دو سطر را چنین بخوانید: «مقیاس‌بندی اینجا چقدر مهم بود؟»

          raw: within-cluster SS    78.85   ARI with species 0.730
 standardised: within-cluster SS   139.82   ARI with species 0.620

دو نکتهٔ عملی دیگر از این بند:

  • وزن‌های متفاوت تصمیمی مدل‌سازی است، نه جزئیات فنی. اگر پرسش «کدام تومورها شبیه هم‌اند؟» باشد، ژن‌هایی مهم‌اند که زیست‌شناسانه مهم‌اند؛ تأثیر برابر دادن به همهٔ ۶۸۳۰ ژن یک انتخاب است، و معمولاً انتخاب بدی.

  • مقدارهای گمشده. دستور رایج این است که D(xi,xi′)D(x_i, x_{i'}) را از ویژگی‌هایی حساب کنیم که هر دو مشاهده دارند و جفتی را که هیچ ویژگی مشترک اندازه‌گیری‌شده‌ای ندارد بیندازیم. جانشینش پرکردن با میانگین یا میانه است، و برای متغیرهای اسمی می‌توان «گمشده» را خود یک مقدار گرفت — اگر معقول باشد که دو شیء شبیه‌اند چون هر دو همان متغیر را گزارش نکرده‌اند.

خلاصه

  • هر روش خوشه‌بندی در این فصل تابعی از یک ماتریس نامتشابهی است؛ گاهی خود داده به‌صورت همان ماتریس می‌آید و آن‌گاه مختصاتی برای میانگین‌گیری نیست.

  • قراردادها را بررسی کنید: نامنفی، قطر صفر، متقارن، و — جدا — اینکه درایه‌ها مانند یک متری رفتار کنند. به‌توان‌رساندن سه تای اول را نگه می‌دارد و می‌تواند چهارمی را بشکند.

  • نامتشابهی ویژگی به نوع متغیر بستگی دارد: خطای مجذور یا قدرمطلق، همبستگی، مقیاس‌بندی ترتیبی، یا ماتریس زیان برای مقدارهای اسمی.

  • ویژگی‌ها در ترکیبی محدب (۱۴.۲۴) با هم می‌آیند و تأثیر مؤثر ویژگی jj برابر wjdˉjw_j \bar d_j است، نه wjw_j. وزن‌های برابر تأثیری متناسب با واریانس می‌دهند؛ استانداردسازی آن را برابر می‌کند، که گاهی دقیقاً همان چیزی است که نمی‌خواهید.

تمرین‌ها

  1. ماتریس شباهت sii′=1/(1+dii′)s_{ii'} = 1/(1 + d_{ii'}) را با معکوس کردن تبدیل به جدول ۱۴.۳ برگردانید. کدام روش خوشه‌بندی این درس می‌تواند مستقیماً روی شباهت‌ها کار کند و کدام نمی‌تواند؟

  2. تبدیل یکنوای d↦d3d \mapsto d^3 را به جدول ۱۴.۳ اعمال کنید و جواب ۳-مدوئید را با جواب صفحهٔ K-medoids مقایسه کنید. مدوئیدها جابه‌جا شدند؟

  3. dˉj\bar d_j را برای چهار ویژگی زنبق و وزن‌های متناظر 1/dˉj1/\bar d_j حساب کنید. کدام ویژگی پس از استانداردسازی بیشترین تأثیر را دارد و کدام پیش از آن داشت؟

  4. سه شیء و دو ویژگی کمّی بسازید چنان که K-means روی دادهٔ خام دو گروه آشکار را بازیابد و K-means روی دادهٔ استانداردشده نه. (راهنما: ویژگی جداکننده را همان ویژگیِ پر واریانس بگیرید.)

  5. با یک مقدار گمشده در یک مختصهٔ یکی از مشاهده‌ها، ماتریس نامتشابهی را هم با انداختن آن جفت و هم با پرکردن با میانگین حساب کنید و خوشه‌بندی کنید. تفاوت دیده می‌شود؟

  6. ماتریس زیان سه رنگ چشم را بنویسید چنان که آبی/سبز خطای کوچک‌تری از آبی/قهوه‌ای باشد، و توضیح دهید این ماتریس چه ادعایی دربارهٔ حوزه می‌کند.

منابع

  • قراردادها، (۱۴.۲۰)–(۱۴.۲۵)، بحث استانداردسازی و نقل‌قول: بندهای ۱۴.۳.۱–۱۴.۳.۳ از hastie2009esl، صص ۵۰۳–۵۰۷.

  • جدول ۱۴.۳ و پیمایش کشورها: Kaufman and Rousseeuw (1990)، همان‌جا ارجاع داده شده؛ داده در صفحهٔ K-medoids دوباره به کار می‌رود.

  • دادهٔ زنبق: sklearn.datasets.load_iris، همان مجموعه‌داده‌ای که در Clustering-Part1 به کار رفت.