تحليل خوشه اي

1402/06/14

دسترسی سریع

تحليل خوشه اي

هدف: تقسيم بندي n موضوع یا فرد بین $k$ خوشه به گونه أي كه

هر موضوع تنها و تنها به يك خوشه منتسب شود
مجموعه خوشه ها شامل كل موضوع ها باشد
افراد هم خوشه شبيه هم (همگن) باشند
افراد غير هم خوشه نا شبيه (نا همگن) باشند.

داده هاي اساسي براي تحليل خوشه اي در حالت كلي يك ماتريس داده اي ${X_{(n \times p)}}$ است كه در تحليل خوشه اي n سطر ماتريس X به تعدادي گروه تقسيم مي شوند.

با توجه به اين هدف، تحليل خوشه اي يك روش توصيفي است اما ممكن است براي اين توصيف حسب مورد و شرايط از آزمون هاي آماري نيز استفاده شود. بيشتر روش هاي تحليل خوشه اي با ماتريس ${X_{(n \times p)}}$ (داده ‏هاي خام) شروع نمي شوند بلكه با ماتريسی سر و كار دارند كه شامل مقاديري مي‌شوند كه نشانگر تشابه يا عدم تشابه بين دو به دوي عناصري است كه بايد خوشه بندي شوند. در ادبيات مربوط كلمه proximity (قرابت) نيز براي هر يك از دو عبارت فوق بكار برده مي شود. راه هاي مختلفي براي سنجش proximity وجود دارد كه عمدتاً بستگي به نوع داده ‏ها و مخصوصاً نوع متغيرها دارد.

لازم به توضیح است که نوع دیگری از تحلیل خوشه ای وجود دارد گه هر فرد را به بیش از یک خوشه منسوب می کند و درجه انتساب فرد به آن خوشه را با یک درجه عضویت مشخص می کند. این نوع تحلیل خوشه ای را فازی (FUZZY) می گویند که امروز کاربردهای زیادی پیدا کرده است و در ادامه مختصری راجع به آن توضیح داده می شود.

در ادبیات مربوط به تحلیل های چند متغییره نام هاي متعددی برای تحلیل خوشه ای بکار برده اند از جمله :

تاكسونومي عددي (معمولاً) در بيولوژي
تحلیل Q در علوم اجتماعي Q-Analysis
تشخيص الگوي غير نظارت شده در ادبيات هوش مصنوعي .
در ساير زمينه ها grouping,clummping گاهي اوقات معمول است.
معمولترين نام " تحليل خوشه اي".

معیارهای دوری و نزدیکی

يكي از مسائل اساسي در تحليل خوشه اي تعریف و محاسبه تشابه يا عدم تشابه بين افراد یا عناصر به لحاظ صفات مورد بررسي است. نحوه اين محاسبه بستگي به طبيعت صفات و خصوصيات آنها به لحاظ كمي، كيفي و يا تلفيقي از اين دو دارد.

ماتریس فاصله یا تشابه

ماتريسي است كه تعداد سطر و ستون آن برابر با تعداد افراد است (n) و عنصر روي سطر i ام و ستون j ام آن ميزان فاصله يا تشابه مربوط به فرد i ام با فرد j ام را نشان مي دهد. عناصر روي قطر اين ماتريس خالي گذاشته مي شود.

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

تکنیک های خوشه بندی

همانگونه که قبلا گفته شد تحلیل خوشه ای را در حالت کلی می توان به دو روش زیر انجام داد:

قطعي: هر فرد تنها به يك خوشه منسوب مي شود.
غير قطعي يا فازي(Fuzzy): هر فرد به بيش از يك خوشه منسوب مي شود هر كدام با درجه هاي خاص

در اينجا گروه اول توضيح داده مي شوند.

پس از اتخاذ تصميم بر استفاده از معيار فاصله و محاسبه فواصل بر اساس آن قدم بعدي نحوه طبقه بندي افراد بر اساس اين فواصل است كه به آن تكنيك خوشه بندي گويند. تكنيكهاي خوشه بندي به چهار گروه تقسيم مي شوند.

سلسله مراتبی Hierarchical

تقسیمی Partitioning

Q-Sort

Densityیا mode

در اينجا تنها گروه تكنيك 1 توضيح داده مي شوند.

تکنیک های سلسله مراتب

این نوع از تکنیک ها معمولترين انواع تكنيك هاي تحليل خوشه اي هستند، که شامل تشكيل مرحله به مرحله خوشه ها می شود. وجه تمايز این تکنیک ها با تكنيك هاي تجزيه آن است كه اگر در مرحله أي از مراحل خوشه بندي دو فرد در يك خوشه قرار گيرند و يا از يكديگر جدا شوند تا خاتمه مراحل گروه بندي در آن خوشه باقي خواهند ماند و يا هيچگاه ديگر با هم در يك خوشه قرار نمي گيرند و امكان تفكيك آن دو فرد در خوشه هاي متمايز وجود ندارد. اين تكنيك ها خود به دو گروه تقسيم مي شوند :

Agglomerative

Divisive

در روش Agglomerative ابتدا هر فرد خود به تنهايي يك خوشه تشكيل مي دهد يعني به تعداد افراد خوشه داريم سپس در مراحل بعدي قدم به قدم اين خوشه ها در هم ادغام و خوشه هاي بزرگتر را تشكيل مي دهند به طوري كه در آخرين مرحله همه افراد در داخل يك خوشه قرار مي گيرند.

در روش Divisive بر عكس Agglomerative ابتدا همه افراد در يك خوشه منظور مي شوند و سپس مرحله به مرحله خوشه هاي جديد ايجاد مي شوند. این روش ها در این مطلب توضیح داده نمی شوند چون اولا در نرم افزارهای موجود امکانات محاسباتی مربوط به آنها وجود ندارد. ثانیا مزایای استفاده از تکنیک ها تبین نگردیده است. علاقمندان می توانند به منابع مربوط به تحلیل خوشه ای مراجعه نمایند.

در بخش زیر قبل از هر چیز یک تعریف آورده می شود که در تشریح روشهای agglomerative از آن استفاده می شود.

درختواره Dendrogram

درختواره نگار عبارت است از يك نمودار كه مراحل تشكيل خوشه هاي جديد اما با تعداد بیشتر افراد (روش Agglomerative) و يا با تعداد کمتر افراد (روش Divisive) را نشان مي دهد. این نمودار ضمن آنکه نحوه تشکیل خوشه ها را در طی فرایند مرحله ای نشان می دهد به عنوان یک ابزار مهم در تعیین تعداد مناسب خوشه ها مورد استفاده قرار می گیرد.

تکنیک های Agglomerative:

همانگونه كه قبلاً توضيح داده شد در اين روش ها ابتدا هر فردي به تنهایی يك خوشه را تشكيل مي دهد. سپس در مرحله بعدي براساس معیار فاصله ای و یا شباهت دو حوشه ای كه نزديكتر (شبيه تر) به هم هستند در هم ادغام شده و يك خوشه جدید را تشکیل می دهند ودر سایر خوشه ها تغیری ایجاد نمی شود . در این مرحله هر جا که ضرورت داشته باشد معیارها ی شباهت یا فاصله از نو محاسبه می شوند. سپس براساس آخرین خوشه های تشکیل شده این فرآیند تا جایی ادامه پیدا می کند که به تعداد خوشه های مورد بنظر برسیم و یا اینکه تا آخرین مرحله که به یک خوشه می رسیم ادامه پیدا می کند.

اين روش ها خود متفاوتند و تفاوت آنها در نحوه محاسبه فاصله یا تشابه دو خوشه است كه حداقل يكي از آنها شامل دو فرد يا بيشتر باشد. مهمترين و معمولترين اين روش ها عبارتند از :

Single Linkage يا Nearest Neighbour
Complete Linkage يا Furthest Neighbour
Average يا Baverage Average linkage between groups يا UPGMA (Unweighted Pair Group Method using arithmetic Average
Ward
Waverage
Centriod
Median

لازم به توضيح است كه روشهاي Agglomerative تنها شامل آنچه به آن اشاره شد، نمي شود.

در ادامه برخی از این روش ها توضيح داده مي شوند:

مرحله اول كه شامل محاسبه تشابه (يا دوري) بين افراد است در همه روش هاي فوق دقيقاً يكسان است. مرحله دوم نيز كه شامل اتصال دو فرد از افراد و تشكيل يك خوشه واحد است تفاوتي بين آنها وجود ندارد. در مرحله سوم نحوه محاسبه فاصله بين دو خوشه كه در آن يكي حداقل داراي دو فرد است، روش ها به شرح زير عمل مي كنند و از اين مرحله است كه روش ها از يكديگر متمايز مي شوند.

روش (Single Linkage (SL

در اين روش فاصله بين دو خوشه را حداقل فاصله دو به دوي افراد يكي از خوشه اول و ديگري از خوشه دوم در نظر مي گيرد. یعنی ${d_{{I_,}II}} = \min ({d_{ij}};i \in I,j \in II)$

مثلاً گيريم ، خوشه I شامل افراد (A,B) و خوشه II شامل سه فرد (C,D,E) باشد در اين صورت بر اساس اين روش فاصله دو خوشه II,I $({d_{{I_,}II}})$ به طريق زير محاسبه مي شود:

${d_{{I_,}II}} = \min \{ {d_{AC}},d{}_{AD},{d_{AE}},{d_{BC}},{d_{BD}},{d_{BE}}\}$

پس اين روش فاصله بين دو خوشه را فاصله بين نزديكترين افراد از دو خوشه در نظر مي گيرد و علت اطلاق نزديكترين همسايه (Nearest Neighbour) به اين روش به همين دليل است.

بديهي است در صورتي كه از ماتريس تشابه به جاي ماتريس فاصله استفاده مي كرديم ميزان تشابه دو خوشه بر مبناي اين روش تشابه نزديكترين افراد از دو خوشه منظور مي شود. بنابراين گيريم ${s_{ij}}$ ميزان تشابه فردi ام وj ام باشد سپس تشابه دو خوشه II,I مثال فوق به طريق زير تعيين مي شود :

${s_{{I_,}II}} = \max ({s_{ij}},i \in I,j \in II)$

${s_{{I_,}II}} = \max \{ {s_{AC}},{s_{AD}},{s_{AE}},{s_{BC}},{s_{BD}},{s_{BE}}\}$

روش (Complete Linkage (CL

در این روش، بر خلاف روش (SL)، فاصله بين دو خوشه حداكثر فاصله دوبدوي افراد يكي از خوشه اول و ديگري از خوشه دوم را در نظر مي گيرد. يعني براي حالت فوق داريم :

${d_{{I_,}^{}II}} = \max ({d_{ij}},i \in I,j \in II)$

${d_{{I_,}^{}II}} = \max \{ {d_{AC}},{d_{AD}},{d_{AE}},{d_{BC}},{d_{BD}},{d_{BE}}\}$

پس در اين روش فاصله بين دو خوشه را فاصله بين دورترين افراد از دو خوشه در نظر مي گيرد. علت اطلاق دورترين همسايه (Furthest Neighbout) به اين روش به همين دليل است. بديهي است در صورتي كه از ماتريس تشابه به جاي ماتريس فاصله استفاده كنيم ميزان تشابه دو خوشه بر مبناي اين روش، تشابه دورترين افراد از دو خوشه منظور مي شود. بنابراين بر مبناي مثال قبلي خواهيم داشت :

${s_{{I_,}^{}II}} = \min ({s_{ij}},i \in I,j \in II)$

${s_{{I_,}^{}II}} = \min \{ {s_{AC}},{s_{AD}},{s_{AE}},{s_{BC}},{s_{BD}},{s_{BE}}\}$

روش (Average Linkage (AL

در اين روش متوسط فاصله دو به دوي افراد، يكي از خوشه اول و ديگري از خوشه دوم را به عنوان فاصله دو خوشه بكار مي برد يعني:

${d_{{I_,}^{}II}} = \frac{1}{{{n_1}{n_2}}}\sum\limits_i {\sum\limits_j {{d_{ij}}} }$

و برای مثال مذکور داریم:

${d_{{I_,}^{}II}} = \frac{1}{6}[{d_{AC}} + {d_{AD}} + {d_{AE}} + {d_{BC}} + {d_{BD}} + {d_{BE}}]$

روش ward :

اين روش گرچه از روش هاي Agglomerative است، اما از لحاظ نحوه ادغام خوشه ها در يكديگر متفاوت از سه روش توضيح داده شده قبلي است. اين روش بر ss مشاهدات در داخل خوشه ها استوار است و در هر مرحله آن دو خوشه اي را در هم ادغام مي كند كه داراي ss كمتري باشد؛ به همين دليل آن را روش كمترين واريانس (Minimum Variance) نيز مي گويند.

بنابراين از جنبه ديگر انجام مراحل تحليل خوشه اي دراين روش مبتني بر مشاهدات است و نه ماتريس هاي فاصله يا تشابه، منظور از كلمه واريانس در عبارت فوق، واريانس كل (Total Variance) است كه برمبناي مجموع ss صفات مختلف در داخل خوشه ها محاسبه مي شود. اين روش از لحاظ آماري داراي خواص بهينه است. اما اين خاصيت بهينگي بطور كامل (global) نيست چرا که اين روش اجازه نمي دهد افراد در داخل يك خوشه از يكديگر جدا شده و در داخل خوشه هاي متفاوت قرارگيرند.

در اين روش حجم محاسبات لازم در مقايسه با سه روش ديگر به مراتب بيشتر است مخصوصاً آنكه اگر تعداد صفات نيز زياد باشد. در سه روش قبلي و روش هاي مشابه كه تنها با داشتن ماتريس فاصله يا تشابه خوشه بندي مي تواند انجام شود، تعداد صفات تنها در محاسبه ماتريس هاي فاصله يا تشابه ایفای نقش می کنند، در حالي كه در روش Ward بايد SS مربوط به هر مرحله محاسبه شود که دليل حجم زياد محاسبات عددي در اين روش است. به طوري كه در بعضي مواقع اين نوع تجزيه به دليل كمبود حافظه فعال (RAM) كامپيوترها انجام نمي شود.

در حالت كلي شايد بتوان گفت كه روش (SL) كمتر توصيه مي شود و روش Ward در صورت امكان انجام محاسبات، بيشتر توصيه مي شود و پس از آن نیز روش UPGMA مناسب است.

نظرات

هیچ نظری وجود ندارد.

تحليل خوشه اي

دسترسی سریع

نظرات

افزودن نظر

آخرین مقالات