بازشناخت الگو ^[1]

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

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

  3-خوشه­یابی یا طبقه­بندی می­تواند بصورت فازی یا ترد ^[8] انجام شود. بدین معنا که تعلق یک موجودیت به یک خوشه یا طبقه می­تواند صفر یا یک و یا اینکه عددی بین صفر و یک باشد.

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

  5- در فرآیند بازشناخت الگو، استفاده از طبقه­بندی کننده، پس از انجام دو گام برای پیش­پردازش اطلاعات انجام می­شود که انجام مناسب آن در نتیجه نهایی طبقه­بندی بسیار اهمیت دارد. گام اول استخراج ویژگی ^[10]، گام دوم شایسته­سازی ویژگی ^[11] و گام نهایی بکارگیری طبقه­بندی کننده ^[12] به منظور طبقه­بندی بردار ویژگی­های منقح شده می­باشد.

  6-شایسته­سازی ویژگی با نرمالیزه کردن اطلاعات (میانگین صفر و واریانس یک، بین صفر و یک یا منفی یک و یک) و کاهش ابعاد اطلاعات با تحلیل اجزاء اصلی ^[13] (مثلا حذف وابستگی بین اطلاعات بکمک تجزیه مقادیر تکین) قابل انجام است. مثلا مطابق رابطه ذیل، عملیات محدودکردن دامنه با ضرب ماتریس A₁ ، عملیات حذف وابستگی خطی با ضرب ماتریس A₂ ، عملیات کاهش بعد با حداقل کاهش جداپذیری با ضرب ماتریس A₃ انجام می­شود و بردار اطلاعات x با شایسته­سازی تبدیل به بردار اطلاعات y می­گردد و آماده اعمال الگوریتم­های طبقه­بندی می­شود.

                                                                        شایسته­سازی ویژگی                     

  7-ویژگی­ای بهتر است که جداپذیری بیشتری داشته باشد. میزان جدایی­پذیری با سنجش فاصله بیرونی و درونی با محاسبه نسبت جدایی­پذیری فیشر ^[14] یا ماتریس پراکندگی ^[15] قابل سنجش است. واریانس معیاری برای فاصله درونی و فاصله نماینده دو خوشه، معیاری از فاصله بیرونی می­باشد.

نسبت جدایی­پذیری فیشر                        

  8-کلاسه کننده­ها، به کلاسه کننده­های آماری و شبکه عصبی تقسیم می­شود. کلاسه­کننده­های آماری، به کلاسه کننده بیزی، کلاسه کننده نزدیکترین همسایه، کلاسه کننده k نزدیکترین همسایه، کلاسه کننده حداقل فاصله میانگین ^[16] ، کلاسه کننده­های خطی و شبکه عصبی به شبکه پرسپترون چندلایه MLP ، شبکه RBF ، شبکه­های رقابتی قابل تقسیم است.

  9-کلاسه­کننده آماری بیزی با تعیین تابع تخمین توزیع تمامی طبقه­ها انجام­پذیر است. تخمین تابع توزیع از روش پارامتریک یا غیرپارامتریک (روش پارزن ^[17] ، k نزدیکترین همسایه) قابل انجام است. از روش­های پارامتریک فرض تابع توزیع گوسی (برای اطلاعات تک­مدولار ^[18] متقارن)، فرض تابع توزیع نمایی یا پواسن (برای اطلاعات تک­مدولار غیرمتقارن)، روش حداکثر شباهت ^[19] و روش MAP  قابل ذکر است^[20].

  10-نماینده خوشه می­تواند نماینده جرمی ^[21] (میانگین، میانه،مرکز جرم)، نماینده خطی ^[22] (ابرخط)، نماینده پوسته ^[23] (ابرصفحه، ابرکره) باشد.

  11-برای تعیین فاصله درونی ^[24] و بیرونی هر طبقه باید مفهوم فاصله برای فاصله نقطه از نقطه، فاصله نقطه از مجموعه و فاصله مجموعه از مجموعه تعریف گردد.

  تعاریف ذیل برای تعریف فاصله نقطه از نقطه وجود دارد.

           فاصله اقلیدسی                             

  تعاریف ذیل برای تعریف فاصله نقطه از مجموعه وجود دارد.

  فاصله مجموعه از مجموعه با محاسبه نماینده دو مجموعه، می­نیمم فاصله هر x از نماینده y ها، می­نیمم فاصله نماینده x از هر y ، می­نیمم فاصله هر x از هر y قابل محاسبه است.

  12-فاصله لزوما نباید یک عدد اسکالر باشد. همچنین می­توان فاصله جهت­دار ^[25] تعریف نمود.

  13-الگوریتم­های خوشه­یابی به سه خانواده مبتنی بر ملاک بهینه­سازی ^[26] (الگوریتم ISODATA ، C-means )، سلسله­مراتبی ^[27] (با شروع از خوشه بدیهی و حرکت به سمت جواب با جدا کردن و ترکیب کردن) و متوالی ^[28] تقسیم می­شود.

  شروان عطایی

  ویرایش اول 7/5/86

  مرجع­ها

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

  [1] Pattern recognition, S. Theodoridis, K. Koutroumbas, Academic Press,1999.

  [2] Pattern classification, 2^nd Ed, R.O. Duda, P.E. Hart, D.G. Stork, Wiley, 2000.

  [3] Neural Networks for pattern recognition, C.M. Bishop, ITRC Library, 1996.

  [4] Fuzzy models for pattern recognition :methods that search for structures in data, C. Bezdek, S.K. Pal, editors,1992.

  [1] Pattern recognition

  [2] clustering

  [3] classification

  [4] classifier

  [5] entity

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

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

  [8] crisp

  [9] separability

  [10] Feature extraction

  [11] Feature conditioning

  [12] classifier

  [13] Principle Component Analysis (PCA)

  [14] Fisher discriminate ratio

  [15] Scatter matrix

  [16] Minimum mean distance classifier

  [17] parzen

  [18] unimodular

  [19] Maximum likelihood

  [20] Maximum apostriori

  [21] Mass cluster

  [22] Linear cluster

  [23] Shell cluster

  [24] Intra-set-distance

  [25] Signed distance

  [26] Optimization based

  [27] Hierarchical based

  [28] Sequential based