خوشه­یابی ^[1]

  1-خوشه­یابی یا طبقه­بندی ^[2] عبارت است از یافتن تناظر چند به یک بین فضای ویژگی­ها و نماینده خوشه. به عبارت دیگر در قالب خوشه­یابی یا طبقه­بندی برای یکسری موجودیت ^[3] در فضای ویژگی، یک برچسب تعیین می­شود که به آن نماینده خوشه اطلاق می­گردد. نماینده خوشه می­تواند از هر جنسی که برای آن فاصله تعریف شده باشد ^[4] ، درنظر گرفته شود (از جنس داده­ها، مرز(دایروی، بیضوی، محدب پیوسته)، شاخص هندسی(خط یا منحنی) ^[5]، تابع چگالی و غیره). خوشه­یابی را می­توان از دیدگاه جزئی استخراج قاعده ^[6] یا از دیدگاه کلی، بهینه­سازی ملاک تلقی نمود. همچنین خوشه­یابی را می­توان یافتن رابطه تناظر بین دو مجموعه منظور کرد. همچنین خوشه­یابی را می­توان تفکیک ^[7] فضای ویژگی­ها تصور کرد که می­تواند بصورت شبکه­ای ^[8] ، درختی ^[9] یا پراکنده ^[10] انجام شود.

  2-معمولا لفظ خوشه­یابی با طبقه­بندی این تفاوت را دارد که وقتی تعداد خوشه­ها یا طبقه­ها از پیش معین است، از لفظ طبقه­بندی و وقتی تعداد آن مشخص نیست از لفظ خوشه­یابی استفاده می­گردد. به بیان دیگر طبقه­بندی یک یادگیری باسرپرست و خوشه­یابی یک یادگیری بدون سرپرست می­باشد.

  3-خوشه­یابی می­تواند بصورت فازی یا ترد ^[11] انجام شود. بدین معنا که تعلق یک موجودیت به یک خوشه یا طبقه می­تواند صفر یا یک و یا اینکه عددی بین صفر و یک باشد. به عنوان نمونه الگوریتم FCM خوشه­یابی فازی ^[12]، که توسط آقای بزدک ^[13] توسعه داده شده را ملاحظه کنید. شبکه کوهونن ^[14] (نگاشت خود سازمانده) را می­توان یک تقریب آماری از FCM دانست.

  4-خوشه­ها به قسمی انتخاب می­شوند که عضوهای موجود در یک خوشه، بیشترین شباهت (نزدیکی) بهم و بیشترین تفاوت (فاصله) را از اعضای سایر خوشه­ها داشته باشند. که معمولا معیار تصمیم­گیری داخلی (شباهت) بصورت صریح و معیار تصمیم­گیری خارجی (تفاوت) بصورت ضمنی تامین می­شود. بنابراین خوشه­بندی متناظر با یک رابطه شباهت یا دوگان آن عدم شباهت (فاصله) است. وقتی این رابطه، یک رابطه هم­ارزی ^[15] باشد، موجودیت­ها به یکسری طبقات هم­ارز افراز می­شوند.

  مفهوم رابطه هم­ارزی در نظریه مجموعه­های فازی توسعه داده شده است. از میان پیشنهادات مطرح شده می­توان به رابطه‌ی شباهت ^[16] (پیشنهاد آقای زاده ^[17] )، رابطه‌ی همانندی ^[18] (پیشنهاد آقای راسپنی ^[19] ) ^[20] و رابطه تمیزناپذیری ^[21] یا دوگان آن متریک دروغین (پیشنهاد آقای والورد ^[22] ) اشاره کرد.

  طبق تعریف والورد، رابطه­ی تمیزناپذیری E به شکل ذیل تعریف می­شود. که T یک عملگر "و" است.

  همچنین طبق تعریف والورد، متریک دروغین ^[23] m ، دوگان رابطه­ی تمیزناپذیری، به شکل ذیل تعریف می­شود. که S یک عملگر "یا" است.

  5-متاالگوریتم خوشه­یابی بصورت تکراری یا با بهینه­سازی ملاک قابل پیاده­سازی است. در یک مساله خوشه­یابی یکسری موجودیت در فضای ویژگی­ها ( e_i , i=1…N )، چند نماینده خوشه یا طبقه ( V_j , j=1…k ) و میزان تعلق موجودیت i ام به خوشه j ام ( X_ji ) وجود دارد. اگر میزان تعلق موجودیت­ها به خوشه­ها صفر و یا یک باشد، خوشه­بندی غیرفازی است و اگر میزان تعلق، عددی بین صفر و یک باشد، خوشه­یابی غیرفازی خواهد بود.

  اگر جواب غیرفازی مورد نیاز باشد، باید خوشه­یابی به روش غیرفازی انجام شود و جواب غیرفازی شده یک خوشه­یابی فازی، پاسخ بهینه نخواهد بود.

  6- متاالگوریتم خوشه­یابی با بهینه­سازی یک ملاک

  q ، توان میزان تعلق هر موجودیت به هر یک از خوشه­هاست که عددی بزرگتر مساوی یک است و هرچه بزرگتر باشد، به خوشه­یابی غیرفازی نزدیکتر می­شویم.

  7-متاالگوریتم خوشه­یابی به روش تکراری (روش ISODATA ):

  متاالگوریتم زیر باید به اندازه کافی تکرار شود تا مساله همگرا شود. این روش به حالت آغازین و نقاط پرت ^[24] حساس است. همچنین اگر یکی از خوشه­ها بزرگ و دیگری کوچک باشد، خوب کار نمی­کند. حساسیت به حالت آغازین را می­توان با چندین بار تکرار الگوریتم، کاهش داد

  الف) بصورت تصادفی میزان تعلق موجودیت­ها به خوشه­ها تعیین شود( X_ji ) و از روی آن نماینده خوشه­ها از روی میانگین­گیری تعیین گردد( V_j ).

  ب) از روی نماینده خوشه تعیین شده و بر مبنای فاصله، میزان تعلق موجودیت­ها به خوشه­ها تعیین شود(هرچه فاصله موجودیت به نماینده خوشه نزدیکتر باشد، میزان تعلق آن به خوشه بیشتر خواهد بود).

  ج) نماینده خوشه­ها از روی میانگین­گیری، از روی میزان تعلق موجودیت­ها به خوشه­ها تعیین گردد.

  د) تکرار از گام ب

  8-متاالگوریتم خوشه­یابی به روش تکراری (روش پیروی از رهبر):

  الف) به اولین موجودیت، برچسب شماره یک می­دهیم و آنرا نماینده خوشه اول فرض می­نماییم.

  ب) فاصله نماینده خوشه­های موجود را با موجودیت­ بعدی مقایسه می­کنیم. اگر از یک آستانه مفروض فراتر بود، آن موجودیت را نماینده خوشه جدید می­کنیم. و اگر از آستانه کوچکتر بود، آنرا متعلق به خوشه برنده می­کنیم و نماینده خوشه برنده را قدری به آن نزدیک می­کنیم. تا یادگیری انجام شود.

  ج) تکرار گام ب برای تمامی موجودیت­ها تا نهایتا مساله همگرا شود.

  این الگوریتم به ترتیب دادن اطلاعات حساس است و ممکن است یک نماینده خوشه بقدری حرکت کند که برخی از موجودیت­های قبلی از خوشه خارج شود.

  9-متاالگوریتم خوشه­یابی به روش تکراری (روش نزدیکترین همسایه):

  الف) به تمامی موجودیت­ها و بصورت تصادفی، برچسب می­دهیم.

  ب) بصورت تصادفی یک موجودیت انتخاب می­کنیم و برچسب همسایه ^[25] (نزدیکترین موجودیت) را به آن می­دهیم.

  ج) تکرار گام ب برای تک­تک موجودیت­ها تا نهایتا مساله همگرا شود.

  10- متاالگوریتم خوشه­یابی به روش ^[26] تکراری kmeans

  متاالگوریتم زیر باید به اندازه کافی تکرار شود تا مساله همگرا شود. این روش به حالت آغازین و نقاط پرت حساس است و همان الگوریتم روش ISODATA می­باشد.

  الف) بصورت تصادفی نماینده خوشه­ها تعیین می­گردد( V_j ) و موجودیت­هایی که به نماینده خوشه نزدیکترند، در آن خوشه قرار می­گیرند و میزان تعلق هر موجودیت به نماینده­های خوشه تعیین می­گردد.

  ب) از روی نماینده خوشه تعیین شده و بر مبنای فاصله، میزان تعلق موجودیت­ها به خوشه­ها تعیین شود(هرچه فاصله موجودیت به نماینده خوشه نزدیکتر باشد، میزان تعلق آن به خوشه بیشتر خواهد بود).

  ج) نماینده خوشه­ها از روی میانگین­گیری، از روی میزان تعلق موجودیت­ها به خوشه­ها تعیین گردد.

  د) رجوع به گام ب

  [1] clustering

  [2] classification

  [3] entity

  [4] مثلا فاصله یک نقطه از یک شکل، فاصله از نزدیکترین نقطه آن شکل تعریف می­شود.

  [5] در این حالت، خوشه­یابی شبیه تقریب تابعی (function approximation) خواهد شد.

  [6] Classifier: if x is A then class is

  [7] partitioning

  [8] grid

  [9] tree

  [10] scatter

  [11] crisp

  [12] Fuzzy C-mean

  [13] bezdek

  [14] Self Organizing Map: SOM

  [15] رابطه دارای خواص انعکاسی، تقارنی و انتقالی باشد.

  [16] similarity measure

  [17] Min, Max

  [18] likeness relation

  [19] rusppini

  [20] Bounded product, bounded sum

  [21] indistinguishability

  [22] L. V alverde

  [23] pseudometric

  [24] outlier

  [25] یا میانگین برچسب k نزدیکترین همسایه

  [26] نام دیگر آن روش C-mean است.

  [27] اگر فضا متریک باشد، کفایت می­کند، لازم نیست نرم داشته باشد (فاصله بر اساس نرم باشد).