آمار , داده کاوی 5348 بازدید

از آنجایی که برخلاف عملیات «تحلیل رده‌بندی» (Classification)، «خوشه‌بندی» (Clustering) یک فرآیند «بدون نظارت» (Unsupervised) است، بررسی صحت نتیجه خوشه‌بندی به راحتی امکان‌پذیر نیست. بنابراین احتیاج به معیارهای مناسب، هم برای بررسی کارایی یک روش خوشه‌بندی در بازیابی خوشه‌ها و هم برای مقایسه‌ عملکرد روش‌های مختلف خوشه‌بندی، ضروری به نظر می‌رسد. در این میان دو گونه معیار ارزیابی نتایج خوشه‌بندی وجود دارد. معیارهای ارزیابی درونی (Internal Criteria Index) و معیارهای ارزیابی بیرونی (External Criteria index).

برای آشنایی بیشتر با شیوه خوشه‌بندی مطلب آشنایی با خوشه‌بندی (Clustering) و شیوه‌های مختلف آن و به منظور آگاهی از معیارهای بیرونی مطلب روش‌ های ارزیابی نتایج خوشه‌ بندی (Clustering Performance) — معیارهای بیرونی (External Index) را مطالعه کنید. در ادامه به بررسی معیارهای ارزیابی درونی می‌پردازیم.

ارزیابی نتایج خوشه‌بندی: معیارهای درونی

هدف از بررسی معیارهای درونی، ارزیابی ساختار خوشه‌های ایجاده شده توسط الگوریتم‌های خوشه‌بندی است. برای سنجش صحت نتایج خوشه‌بندی، ملاک‌ها و معیارهای متفاوتی معرفی شده ‌است. این شاخص‌ها سعی در اندازه‌گیری میزان شباهت اعضای درون خوشه و عدم شباهت بین خوشه‌ها دارند. بنابراین روشی که بیشترین شباهت درون خوشه‌ یا بیشترین تمایز بین خوشه‌ها را ایجاد کند، روش مناسبی در نظر گرفته می‌شود.

برای مثال بر اساس داده‌های تک بعدی، امکان تفکیک میزان پراکندگی کل داده‌ها نسبت به میانگین‌شان به دو جزء درون خوشه و بین خوشه به کمک «تحلیل واریانس» (Analysis of Variance)، وجود دارد. بنابراین هدف، به دست آوردن خوشه‌بندی است که میزان پراکندگی درون خوشه‌ای کمتری داشته باشد، یا به ‌طور مشابه میزان پراکندگی بین خوشه‌ای بیشتری داشته باشد.

در حالتی‌که بعد داده‌ها، بیشتر از 1 باشد، امکان استفاده از چنین تحلیلی به راحتی وجود ندارد. بنابراین سیاست‌های دیگری اتخاذ می‌شود. برای مثال اگر داده‌های X که p بعدی هستند را با استفاده از روش خوشه‌بندی k-میانگین به k خوشه تفکیک کرده باشیم، می‌توان میزان پراکندگی کل را با T نشان داد و به صورت زیر محاسبه کرد:

$$T=\sum_{i=1}^k\sum_{j=1}^{n_i}(x_{ij}-\overline{x})'({x}_{ij}-\overline{x})$$

در این رابطه، $$n_i$$ تعداد داده‌ها در خوشه‌ی iام و $$x_{ij}$$ نیز مشاهده‌ی jام از خوشه‌ی iام است. همچنین k نیز تعداد خوشه‌ها است. به این ترتیب اگر W میزان پراکندگی درون و B میزان پراکندگی بین خوشه‌ها باشد، روابط زیر برقرارند:

$$W=\sum_{i=1}^k\sum_{j=1}^{n_i}(x_{ij}-\overline{x})'(x_{ij}-\overline{x})$$

$$B=\sum_{i=1}^k n_i(\overline{x}_i- \overline{x})'(\overline{x}_i- \overline{x})$$

می‌توان به راحتی نشان داد که بین این سه جزء رابطه T=B+W همیشه وجود دارد.

در این میان، خوشه‌بندی که پراکندگی درون خوشه‌هایش (W) کمینه یا پراکندگی بین خوشه‌هایش (B) بیشینه باشد، مناسبترین روش خوشه‌بندی است. در ادامه به معرفی چند شاخص ارزیابی درونی می‌پردازیم که در «خوشه‌بندی تفکیکی» (Partition Clustering) کاربرد بیشتری دارند.

ریشه میانگین مربعات انحراف استاندارد (RMSSTD)

برای مشخص کردن تعداد خوشه‌ها در خوشه‌بندی تفکیکی می‌توان از شاخص ریشه میانگین مربعات انحراف استاندارد (Root-mean-square standard deviation) استفاده کرد. این شاخص میزان شباهت مقدارهای درون خوشه‌ها را اندازه‌گیری می‌کند. برای محاسبه شاخص RMSSTD ابتدا باید با بعضی از مفاهیم آشنا شویم.

مجموع مربعات (Sum of Square)

فرض کنید مجموعه D شامل n‌ نقطه p بعدی باشد. یعنی $$D=\{X_1,X_2,\ldots,X_n\}$$.

آنگاه منظور از مجموع مربعات مقدارهای X، محاسبه رابطه زیر است:

$$SS=\sum_{i=1}^n(x_i-\overline{x})^2$$

به این ترتیب علامت‌های زیر را تعریف می‌کنیم.

  • $$SS_w$$: مجموع مربعات درون گروه = W
  • $$SS_b$$: مجموع مربعات بین گروه‌ها = B
  • $$SS_t$$: مجموع مربعات مقادیر = T

حال اگر k تعداد خوشه‌ها و p نیز بُعد داده‌ها باشد، آنگاه شاخص RMSSTD به صورت زیر محاسبه می‌شود:

$$V_{RMSSTD}=(\dfrac{SS_w}{p(n-k)})^\tfrac{1}{2}$$

همانطور که از اسم این شاخص نیز پیدا بود، مقدار ریشه (توان 1/2) میانگین مربعات درون گروه‌ها را نشان می‌دهد.

برای تعیین بهترین تعداد خوشه، برای مثال در روش خوشه‌بندی k-میانگین، کافی است RMSSTD را به ازای مقدارهای مختلف k محاسبه و در یک نمودار به صورت زیر ترسیم کنیم. در نقطه‌ای از محور افقی که شیب منحنی دارای تغییر محسوسی باشد، مناسب‌ترین خوشه‌بندی صورت گرفته است زیرا بعد از این شکستگی، با افزایش تعداد خوشه‌ها، تغییر زیادی در شاخص RMSSTD رخ نمی‌دهد. این نمودار را با نام «آرنج» (Elbow) می‌شناسند زیرا خمیدگی آن شبیه آرنج دست است.

نمودار RMSSTD و بازو

این نمودار نشان می‌دهد که اگر تعداد خوشه‌ها (k) را برابر با ۲ انتخاب کنیم، به تعداد خوشه‌های بهینه رسیده‌ایم. البته با افزایش تعداد خوشه‌ها، شاخص RMSSTD باز هم کمتر خواهد شد ولی تغییر آن خیلی محسوس نیست و ممکن است با افزایش تعداد خوشه‌ها تفسیرپذیری آن‌ها کاهش بیابد و یا دچار بیش‌برازش شویم.

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

شاخص ارزیابی دیویس-بولدین (Davies-Bouldin)

این شاخص توسط دیویس و بولدین دو دانشمند در رشته برق در سال 1979 معرفی شد و وابسته به تعداد خوشه‌ها و یا الگوریتم خوشه‌بندی نیست. برای محاسبه این شاخص ابتدا باید با دو معیار «اندازه پراکندگی» (Dispersion measure) و «عدم شباهت بین خوشه‌ها» (Cluster dissimilarity) آشنا شویم.

اندازه پراکندگی درون خوشه

فرض کنید $$S_i$$ میزان پراکندگی مربوط به خوشه $$C_i$$ و d نیز یک تابع فاصله باشد. آنگاه میزان پراکندگی برای این خوشه توسط رابطه زیر قابل محاسبه است:

$$S_i=[\dfrac{1}{|C_i|}\sum_{x\in c_i$$} d^r(x,c_i)]^{(\tfrac{1}{r})},\;\;\;\;\;r>0$$

این رابطه در حقیقت شبیه فاصله مینکوفسکی نقطه‌های هر خوشه از مراکز آن است.

عدم شباهت (فاصله) بین خوشه‌ها

فاصله بین دو خوشه نیز بر اساس فاصله بین دو نقطه مرکزی آن‌ها سنجیده می‌شود. اگر $$V_i$$‌ و $$V_j$$‌ مراکز خوشه‌های i و j باشند، فاصله بین این دو خوشه با $$D_{ij}$$ نشان داده شده و توسط رابطه زیر بدست می‌آید:

$$D_{ij}=[\sum d(V_i,V_j)^t]^{\tfrac{1}{t}}$$

باز هم به نظر می‌رسد از فاصله مینکوفسکی برای سنجش فاصله بین دو خوشه استفاده شده است.

حال با توجه به این دو مفهوم می‌توان میزان فاصله بین دو خوشه $$C_i$$ و $$C_j$$ را که با $$R_{ij}$$ نشان می‌دهیم به صورت زیر محاسبه کنیم:

$$R_{ij}=\dfrac{S_i+S_j}{D_{ij}}$$

همانطور که دیده می‌شود در صورت کسر، میزان پراکندگی دو خوشه با یکدیگر جمع شده و در مخرج نیز میزان عدم شباهت بین خوشه‌ها قرار گرفته است. هر چه خوشه‌‌ها دارای پراکندگی بیشتری باشند، مقدار $$R_{ij}$$ بزرگتر می‌شود. از طرفی اگر دو خوشه با یکدیگر فاصله کمتری داشته‌ باشند باز هم $$R_{ij}$$ بزرگ می‌شود.

به این ترتیب برای محاسبه شاخص دیویس-بولدین برای یک روش خوشه‌بندی کافی است ابتدا بیشنیه فاصله هر خوشه‌ را نسبت به خوشه‌های دیگر بدست آورد. یعنی برای خوشه iام خواهیم داشت:

$$R_i=\displaystyle \max_{j\neq i}R{ij}$$

سپس میانگین بیشینه فاصله‌های محاسبه شده برای همه خوشه‌های ایجاد شده توسط الگوریتم را محاسبه می‌کنیم. این شاخص را با $$V_{DB}$$ نشان می‌دهند.

$$ٰV_{DB}=\frac{\sum_{i=1}^k R_i}{k}$$

در حقیقت این شاخص، میانگین حداکثر نسبت پراکندگی درون به پراکندگی بین خوشه‌ها را محاسبه می‌کند. هر چه مقدار شاخص $$V_{DB}$$ کمتر باشد، عمل خوشه‌بندی بهتر صورت گرفته است.

شاخص دیوس-بولدین

نکته: مقدار t و r از یکدیگر مستقل هستند. انتخاب تابع فاصله نیز در این شاخص براساس داده‌ها و رفتار آن‌ها انجام می‌شود.

شاخص دان (Dunn’s Index)

«خانواده شاخص‌های دان» (Dunn family indices) در سال 1974 طی مقاله‌ای با توجه به مفهوم «فشردگی» (Compactness) و «تفکیک‌پذیری» (Separation) توسط دان معرفی شدند. او با دو معیار «فاصله» (Cluster Distance) و قطر (Diameter)، میزان فشردگی و تفکیک‌پذیری را محاسبه کرد.

شاخص Dunn

حال اگر فاصله بین دو خوشه $$C_i$$ و $$C_j$$ را با $$D(C_i,C_j)$$ نشان دهیم، می‌توانیم میزان تفکیک‌پذیری در خوشه‌بندی را به صورت زیر محاسبه کنیم:

$$D(C_i,C_j)=\displaystyle \min_{x\in C_i, y\in C_j} d(x,y)$$

همینطور برای اندازه‌گیری فشردگی خوشه‌ها، از قطر هر خوشه استفاده می‌شود. برای خوشه $$C_l$$‌ مقدار قطر توسط رابطه زیر بدست می‌آید.

$$diam(C_l)= \displaystyle \max_{x,y \in C_l}d(x,y)$$

حال شاخص دان به صورت زیر تعریف می‌شود.

$$V_D=[\dfrac{\displaystyle \min_{i=1\leq j\leq k} D(C_i,C_j)}{\displaystyle \max_{1\leq l \leq k} diam (C_l)}]$$

در صورت این کسر، فاصله بین دو خوشه به عنوان معیاری برای تفکیک‌پذیری دیده می‌شود و در مخرج نیز قطر هر خوشه دیده می‌شود. نسبت این دو، مقیاسی برای سنجش فاصله بین دو خوشه خواهد بود. بنابراین کوچکترین مقدار این نسبت برای همه خوشه‌ها، می‌تواند شاخصی برای ارزیابی خوشه‌بندی باشد. هر چه مقدار این شاخص بزرگتر باشد، بیانگر تفکیک‌پذیری بهتر و در نتیجه خوشه‌بندی موثرتر است. بر همین اساس اگر نسبت میزان تفکیک‌پذیری به قطر خوشه‌ها مقدار بزرگی باشد، خوشه‌بندی به خوبی انجام شده است.

معیار نیم‌رخ (Silhouette)

یکی دیگر از روش‌های ارزیابی خوشه‌بندی، معیار «نیم‌رخ» (Silhouette) است. این معیار هم به پیوستگی (Cohesion) درون خوشه‌ها و هم به میزان تفکیک‌پذیری آن‌ها بستگی دارد. مقدار نیم‌رخ برای هر نقطه، میزان تعلق آن را به خوشه‌اش در مقایسه با خوشه مجاور اندازه‌ می‌گیرد.

فرض کنید نقطه‌ای مانند $$x_i$$ در میان داده‌هایی که خوشه‌بندی کرده‌اید وجود دارد و در طی مراحل خوشه‌بندی نیز k خوشه ($$C_1,C_2,\ldots,C_k$$) ایجاد شده است. برای محاسبه معیار نیم‌رخ احتیاج به آشنایی با دو مفهوم اصلی داریم:

میانگین فاصله یک نقطه از خوشه با نقاط دیگر آن خوشه‌: این مقدار را با $$a(i)$$ نشان داده و به صورت زیر محاسبه می‌کنیم.

$$a(i)=\frac{1}{n_i}\sum_{l=1}^{n_i}d(x_i,x_l)$$

این معیار را می‌توان ملاکی برای ارزیابی تعلق نقطه $$x_i$$‌ در خوشه‌اش در نظر گرفت. هر چه مقدار $$a(i)$$ کوچکتر باشد، میزان تعلق این نقطه به خوشه‌اش بیشتر است.

نکته: این معیار می‌تواند براساس بیشتر توابع فاصله،‌ مانند فاصله اقلیدسی و منهتن نیز محاسبه شود.

حداقل میانگین فاصله نقطه با خوشه‌های دیگر: فرض کنید نقطه $$x_i$$ به خوشه $$C_j$$‌ تعلق دارد. حال میانگین فاصله این نقطه را با نقاط خوشه‌های دیگر (مثلا $$C_k$$) اندازه می‌گیریم. خوشه‌ای که دارای کمترین میانگین فاصله برای نقطه $$x_i$$ باشد، به عنوان خوشه مجاور با این نقطه نامیده می‌شود. مقدار میانگین فاصله نقطه $$x_i$$ با نقاط خوشه مجاور را با $$b(i)$$‌ نشان می‌دهیم.

$$b(i)=\displaystyle \min_{1\leq l \leq k} \frac{1}{n_l} \sum_{y_m\in C_l}(d(x_i,y_m))$$

به این ترتیب میزان معیار نیم‌رخ برای نقطه $$x_i$$ بوسیله رابطه زیر اندازه‌گیری می‌شود:

$$s(i)=\dfrac{b(i)-a(i)}{max(b(i),a(i))}$$

در نتیجه اگر $$a(i)$$ کوچکتر از $$b(i)$$ باشد، مقدار شاخص نیم‌رخ مثبت می‌شود و برعکس اگر $$b(i)$$ کوچکتر از $$a(i)$$ باشد، مقدار شاخص نیم‌رخ منفی شده و نشانگر خوشه‌بندی ضعیف است زیرا نقطه $$x_i$$ بیش از آنکه شبیه خوشه خودش باشد به خوشه مجاور شباهت دارد. با توجه به رابطه بالا مقدار این شاخص بین ۱- تا ۱+ تغییر می‌کند. مقدار نزدیک به ۱ بیانگر انطباق خوب بین نقطه و خوشه‌اش نسبت به خوشه مجاور است. اگر معیار نیم‌رخ برای همه نقاط درون خوشه‌ها نزدیک به ۱ باشد، عمل خوشه‌بندی به درستی انجام شده است. در حالیکه کوچک بودن مقدار نیم‌رخ برای خوشه‌ها، بیانگر ضعیف بودن نتایج خوشه‌بندی است که ممکن است به علت انتخاب نامناسب تعداد خوشه‌ها (k) نیز باشد.

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

برای تفسیر این معیار، از نموداری استفاده می‌شود که میزان انطباق هر نقطه را با خوشه‌ خودش نمایش می‌دهد. در تصویر زیر این نمودار دیده می‌شود. محور افقی نقطه‌ها و ستون‌ها، مقدار معیار نیم‌رخ برای آن نقطه است. همچنین میانگین شاخص نیم‌رخ برای همه نقاط نیز در نمودار مشخص می‌شود. همانطور که در نمودار دیده می‌شود، برای خوشه شماره ۲ بعضی نقاط دارای مقدار نیم‌رخ منفی هستند که نشان می‌دهد ممکن است به درستی خوشه‌بندی نشده باشند و به خوشه مجاور تعلق داشته باشند. همچنین میانگین کل شاخص نیم‌رخ نیز برابر با 0.46 محاسبه شده است.

اگر به یادگیری مباحث مشابه این مطلب علاقه‌مند هستید، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

آرمان ری بد (+)

«آرمان ری‌بد» دکتری آمار در شاخه آمار ریاضی دارد. از علاقمندی‌های او، یادگیری ماشین، خوشه‌بندی و داده‌کاوی است و در حال حاضر نوشتارهای مربوط به آمار و یادگیری ماشین را در مجله فرادرس تهیه می‌کند.

بر اساس رای 6 نفر

آیا این مطلب برای شما مفید بود؟

5 نظر در “روش‌ های ارزیابی نتایج خوشه‌ بندی (Clustering Performance) — معیارهای درونی (Internal Index)

  1. سلام. وقت شما بخیر، ممنون از مطالب خوبتون..
    ببخشید میشه لطفا معیار ارزیابی و طریقه محاسبه Avg SSQ رو توضیح بدین؟
    خیلی ممنون میشم ازتون..

    1. سلام و وقت بخیر.
      یکی از روش‌های ارزیابی خوشه‌بندی، پیدا کردن کمترین مربعات درون خوشه است. البته این شیوه بیشتر در زمانی که از فاصله اقلیدسی یا مربع فاصله اقلیدسی (مانند روش k-میانگین) استفاده می‌کنید استفاده می‌شود. بنابراین میانگین مربعات فاصله درون گروهی در بین دو شیوه خوشه بندی محاسبه شود، روشی را برتر انتخاب می‌کنیم که Avg SSQ آن از دیگری کمتر باشد. این کار درست به مانند روش RMSSTD است. منحنی ترسیمی نزولی بوده و اولین مقدار k که کمترین Avg SSQ را داشته باشد به عنوان بهترین مقدار برای تعداد خوشه ها در نظر گرفته شده و ارزیابی خوشه بندی براساس آن صورت می گیرد.
      برای توضیحات بیشتر بهتر است مطلب (+) را مطالعه کنید. البته به زودی ترجمه این نوشتار نیز در مجله فرادرس منتشر خواهد شد.
      شاد، تندرست و پیروز باشید.

  2. عالی بود – معیار سیلوئت یا نیم رخ یا همان سایه روشن را به بهترین نحو ممکن توضیح دادید.
    خیلی خیلی خیلی ممنون

  3. باسلام
    یک سوال از خدمتتان داشتم. اگر در خوشه بندی جهت سنجش اعتبار از فواصل درون وبرون خوشه ای استفاده شود، از انجاییکه تمایل داریم فاصله درون خوشه ای کمتر شده و فاصله برون خوشه ای افزایش یابد، اگر فاصله درون خوشه ای برای یک نمونه خوشه بندی کمتر از نمونه دوم ولی فاصله برون خوشه ای نمونه دوم بیشتر از نمونه اول باشد، در این شایط اولویت تصمیم گیری براساس کدام معیار فاصله ایست؟ برون خوشه ای نسبت به درون خوشه ای ااولویت دارد یا برعکس؟

    1. با سلام خدمت شما همراه همیشگی فرادرس.
      همانطور که فرمودید، روش‌های خوشه بندی براساس کمینه‌سازی فاصله درون خوشه‌های و بیشینه‌سازی فاصله بین خوشه‌ها ساخته می‌شوند. به همین دلیل در اکثر مواقع برای ارزیابی روش خوشه‌بندی از هر دو این فاصله‌ها استفاده می‌شود. به همین دلیل در شاخص‌های معرفی شده در نوشتار روش‌های ارزیابی نتایج خوشه‌بندی (معیارهای درونی) از نسبتی‌هایی استفاده می‌شود که در صورت فاصله بین خوشه‌ها و در مخرج فاصله درون خوشه وجود دارد. به این ترتیب روشی که دارای مقدار شاخص بزرگتری است، مناسب‌تر است (البته در بعضی از موارد مثل شاخص دیویس-بولدین این کسر برعکس است و کوچک بودن این شاخص به معنی مناسب‌تر بودن شیوه خوشه‌بندی است).

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

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *