Data Mining and Knowledge Discovery

 

 

وقتی میخواهیم یک کاری توسط کامپیوتری حل شود، اولین سوالی که مطرح میشود اینست که چگونه مسئله را باید به ترمهای محاسباتی نشان بدهیم . در یادگیری ماشین این بدان معناست که چگونه مفاهیم، مثالهای آموزشی و دانش اولیه را نمایش دهیم . برای تشریح مفاهیم و نمونه ها از زبانهای نمایشی (Representational Languages) استفاده میکنیم . از نظر قدرت بیان و پیچیدگی میتوان زبانها را طبقه بندی کرد و در یک ترتیب صعودی داریم : Zero-order Logic ، Attribute-value Logic ، Horn Clauses و Second-order Logic . در ادامه به معرفی کوتاهی از این چهار مدل زبان تشریحی میپردازم ولی اساس کار در این مقاله استفاده از Attribute-value Logic میباشد .

             

          1.1  Zero Order Logic: Propositional Calculus

 

در منطق رتبه صفر، مفاهیم و نمونه ها را با ترکیب عطفی از ثابتهای بولی که هر کدام نماد یک ویژگی مجزا (مقادیر ویژگیها) میباشد . در مدل ریاضی، این نوع تشریح را میتوان بصورت زیر نشان داد :

"یک شیء نمونه ای از مفهوم C میباشد هر گاه x,y,z  هر سه درست باشند ..."     

 

برای مثال یک تشریح اولیه و ابتدائی از شوهر کاندیدا برای Jane را تصور کنید :

 

 

دراین مدل تشریحی میتوان از عملگر نقیض (Negation) و یا ترکیب فصلی (Disjunction) هم استفاده کرد . 

همانطور که ملاحظه میکنید این مدل تنها میتواند مفاهیم ساده را بیان کندو بعبارت دیگر از قدرت تشریحی پائینی برخوردار میباشد .

 

          1.2  Attributional Logic

 

از نظر رسمی این مدل به مانند منطق رتبه صفر میباشد، اما ساختار و Notation آن غنی تر و با انعطاف بیشتر میباشد . ایده اساسی در این مدل تمییز دادن نمونه ها و مفاهیم از روی مقادیری است که از قبل تحت عنوان ویژگی تعریف شده است (مثل رنگ، قد و ...) . ارتقاء این مدل نسبت به منطق رتبه صفر (که مفاهیم از روی ترکیب عطفی ثابتها تمییز داده میشوند) اینست که ویژگیها متغییر میباشند و مقادیر مختلفی را بخود میگیرند . نمونه ها معمولا در یک جدول قرار میگیرند و هر ستون نماد یک ویژگی است .

 

          1.3  First Order Predicate Logic: Horn Clauses

 

منطق رتبه اول یک قالب رسمی را برای بیان و نتیجه گیری از اشیاء و روابط آنها مهیا میکند . یک زیرمجموعه مهم از منطق رتبه اول، Horn Clauses ها میباشند که هر عبارت در این مدل از دو قسمت Head  و Body تشکیل شده است :

 

                   Grandparent (X,Y) := Parent (X,Z)  Parent (Z,Y)

"فرد X جد فرد Y است اگر فرد Zی پیدا شود که X والد Z و Z والد Y باشد ... "

 

قسمت سمت چپ =: را Head  و قسمت سمت راست را Body مینامیم . همچنین به ترمهائی چون parent ، گزاره و متغیرهای داخلی آنرا آرگومان مینامیم . تعداد آرگومانها متنوع میباشد ولی برای یک گزاره داده شده این تعداد ثابت میباشد . اگر تمام گزاره ها تنها یک آرگومان داشته باشند، این زبان به Attribute-value Logic منتهی میشود و در صورتیکه تمام گزاره ها صفر آرگومان داشته باشند، منطق رتبه صفر داریم . Horn Clauses ها میتوانند یک زبان تشریحی پیشترفته ای (چون Prolog) را بسازنند که مفاهیم پیچیده را میتوان با آن نمایش داد .

 

          1.4  Second-order Logic

             

در این منطق اسم گزاره ها را هم متغیر در نظر میگیریم و خانواده بزرگتری از زبانها معرفی میشود .برای مثال شمای زیر را در نظر بگیرید :

              p(X,Y) := q(X,XW)  q(Y,YW)  r(XW,YW)

 

اگر جایگزینی= {p=Brothers , q=Son , r=Equal}  را انجام دهیم، خواهیم داشت :

              Brothers(X,Y) := Son(X,XW)  Son(Y,YW)  Equal(XW,YW)

 

و با یک جایگزینی دیگر = {p=Lighter , q=Weight , r=Less} 2 داریم :

              Lighter(X,Y) :=  Weight(X,XW) Weight(Y,YW)  Less(XW,YW)

 

بنابراین همانطور که ملاحظه میکنید اسکلت عبارت دست نخورده باقی میماند و تنها اسم گزاره ها تغییر میکند . آنچه در پشت این ایده میباشد اینست که معمولاً گروهی از مفاهیم ساختار بیانی قابل پذیرش مشترکی دارند و با این مدل بیانی میتوان کمک بزرگی به جستجو مفاهیم کرد . اما از آنجائیکه این زبان بسیار پیچیده میباشد، خیلی بندرت از آن استفاده میشود . (برای آشنائی بیشتر میتوانید به برنامه CIA که در Raedt 1992 آمده است رجوع کنید)

 

2  SEARCH THROUG THE SPACE OF GENERALIZATION

 

فرض کنید که یک زبان نمایشی انتخاب شده است . حال نوبت اینست که ماشین از روی نمونه های آموزشی و دانش اولیه میخواهد عمل یادگیری مفهوم را انجام دهد . در حالت کلی یادگیری را میتوان به دوگروه اصلی تقسیم کرد : یادگیری با نظارت (Supervised) و یادگیری بدون نظارت (Unsupervised) . در دسته بندی با نظارت (یا تحلیل تفکیکی-  Discrimination-) ما با یک کلکسیونی از نمونه های برچسب خورده (از قبل کلاسه بندی شده) مواجه هستیم . هدف برچسب زدن یک نمونه جدید میباشد که تا حال به سیستم معرفی نشده است . اما درمورد دسته بندی بدون نظارت (و یا کلاسترینگ)، هدف گروهبندی کلکسیونی از نمونه های برچسب نخورده به گروههای با معنا میباشد . برای بیان این معنا برچسبهائی را به هر گروه تخصیص میدهیم ، با این تفاوت که منشا این برچسبها منحصراٌ از خود داده گرفته شده اند - Data-Driven - .

فرض کنید که نمایش نمونه ها و مفاهیم بر اساس Attribute-value Logic  باشد . در اینصورت فضای نمایشی برای بیان تمامی مفاهیم بسیار گسترده خواهد شد . برای مثال اگر ده ویژگی داشته باشیم که هر کدام میتوانند پنج مقدار را بگیرند، پنج به توان ده ( در حدود 9764625 ) بردار ممکن برایش وجود دارد . هر زیرمجموعه ای از این بردارها را میتوان برای نمایش یک مفهوم استفاده کرد . با این تفاسیر برای این ده ویژگی میتواند دو به توان 9764625  مفهوم وجود داشته باشد . این عدد برای کامپیوترهای امروزی هم بزرگ خواهد بود و در زبانهای کمی پیچیده این مقدار خیلی بزرگتر هم خواهد شد . اما در این میان دانش اولیه از داده ها میتواند چاره ساز باشد و این مقدار را کاهش میدهد . بنابراین یادگیرها معمولا از دو تکنیک Induction (استقرا) و Heuristic Search (هوشمندی) بهره میبرند . برای روشن شدن استقرا ، خصوصیات یک گنجشک را بعنوان یک نمونه مثبت برای مفهوم پرنده در نظر بگیرید . حال برای اینکه پرنده های دیگر را تشخیص دهیم و در این گروه قرار دهیم، حفظ کردن محض ویژگیهای گنجشک مذکور ما را به جائی نمیرساند . در حقیقت تعمیمی (Generalization) از این نمونه لازم میباشد . اما تا چه اندازه ؟ برای ایجاد محدودیت (Specialization) نیازمند مثالهای آموزشی منفی میباشیم (نمونه ای که پرنده نباشد، مثلا سگ) .

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

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

 

-Inductive Essence of Learning

-Exhaustive Search

-Heuristic Search

·       Best-First Search Algorithm

·       Beam-Search Algorithm

-Classic Methods of Learning

·       Divide & Conquer Learning

Ø    TDIDT

·       AQ Learning

-Artificial discovery

 

 

 

 

3  Unsupervised Learning

 

کلاسترینگ یک دسته بندی بدون نظارت از نمونه ها (مشاهدات، آیتمهای داده و بردارهای ویژگی) به گروهها (کلاسترها) میباشد . مسئله کلاسترینگ در زمینه های مختلفی توسط محققین به طرق مختلفی مطرح شده است . و این مسئله بیانگر اینست که کلاسترینگ یکی از مراحل مهم و اساسی در تحلیل اکتشافی داده میباشد . رویه های تحلیل داده ممکن است اکتشافی باشد یا تائیدی (Confirmatory) . اما عنصر کلیدی در هر دو نوع رویه ها (چه برای شکل دهی یک فرضیه یا یک تصمیم گیری) گروهبندی میباشد . آنالیز گروهبندی در حقیقت سازماندهی کلکسیونی از نمونه ها به کلاسترها بر پایه تشابهات میباشد . یعنی اینکه نمونه هائی که دریک کلاستر قرار دارند، ویژگیهای مشابه تری نسبت بهم دارند تا به ویژگی نمونه های کلاستر دیگر . در شکل زیر یک مثالی از کلاسترینگ آمده است که نمونه های ورودی در قسمت a و کلاسترهای مطلوب در b نمایش داده شده است . شماره هائی که به هر کدام از نمونه ها داده شده است، برچسب آن کلاستر تلقی میشود . وجود تکنیکهای متعدد برای نمایش داده، اندازه گیری مجاور(تشابه) بین عناصر داده و گروه بندی آنها باعث شده است که متدهای کلاسترینگ به انواع مختلف در طبقه بندیهای مختلف معرفی شوند .

 

 

 

 

 

 

 

 

 


                                 

 

                                          

شکل 1

 

 

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

 

3.1  Components of a Clustering task

 

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

1. Pattern Representation : نمایش الگو

2. تعریف یک شاخص مجاورت برای الگو متناسب با دامنه داده

3. گروهبندی (کلاسترینگ)

4. Data Abstraction : تجرد داده (در صورت لزوم)

5. Assessment of Output : ارزیابی خروجی

 

 

 

 

 

 

 

 

 

 

 

 

Pattern Representation : معطوف به تعداد کلاسها، تعداد نمونه های موجود و تعداد، نوع و وزن ویژگیهای موجود برای آن الگوریتم کلاسترینگ میباشد . بعضی از اطلاعات ممکن است که برای فرد قابل کنترل و دستکاری نباشد . این بدان معناست که نمیتوان مستقیماٌ از آن داده استفاده کرد . بدین منظور از دو رویه مهم کمک گرفته میشود .

 1: گزینش ویژگی- Feature Selection -، فرآیندی است که برای شناسائی موثرترین زیرمجموعه از ویژگیهای اولیه برای کلاسترینگ استفاده میشود .

2: استخراج ویژگی- Feature Extraction - ، استفاده از یک یا چند مرحله تبدیل از ویژگیهای ورودی بمنظور بدست آوردن ویژگیهای برجسته جدید میباشد .

از این دو تکنیک میتوان برای بدست آوردن مجموعه مناسبی از ویژگیها در امر کلاسترینگ استفاده کرد .

 

Pattern Proximity : مجاورت میان الگوها معمولا توسط یک تابع مسافت که بروی جفتهائی از نمونه اعمال میشود، اندازه گیری میشود . ساده ترین معیار برای مسافت، فاصله اقلیدسی است که بیانگر افتراق (Dissimilarity) بین دو نمونه میباشد . این در حالیست که معیارهای تشابه هم میتوانند برای تشخیص تشابهات معنائی در میان نمونه ها استفاده شوند [Michalaski Stepp 1983] . جزئیات بیتشر این موضوع در ادامه تشریح خواهم کرد .

 

Grouping : گروهبندی به طرق مختلف قابل اجراست . بطور کلی دسته های خروجی به دو حالت ظاهر میشوند :

- Hard (سخت) میباشند، یعنی اینکه یک پارتیشنی از داده به گروهها نگاشت میشود

- Fuzzy (فازی) میباشند و هر نمونه با یک درجه عضویت به هر کدام از گروهها تعلق دارد و مانند حالت قبل این گونه نیست که نمونه ها انحصارا به یک و تنها یک گروه تعلق داشته باشند . الگوریتمهای کلاسترینگ سلسله مراتبی، یک سری از پارتیشنهای تودرتو بر اساس یک معیار برای ادغام یا شکستن کلاسترینگ بر پایه تشابه تولید میکنند . در دسته مقابل الگوریتمهای سلسله مراتبی، الگوریتمهای کلاسترینگ پارتیشنی قرار دارند که مرزهائی در میان داده ها متصور میشود که معیار دسته بندی را (معمولا بطور محلی) بهینه میکند . در قسمتهای بعدی این دو نوع الگوریتم  بهمراه دیگر الگوریتمهای کلاسترینگ از جمله متدهای احتمالی و بیزین و شبکه های عصبی و ... معرفی خواهد شد .

 

Data Abstraction : فرآیندی است از استخراج یک نمایش ساده و در عین حال غنی شده از مجموعه داده ها میباشد . در اینجا سادگی دو معنا دارد :

- Automatic Analysis ، از دیدگاه ماشین که بتواند پردازشهای جلوتر را موثرتر انجام دهد .

- Human-Oriented ، از دیدگاه انسان بدین صورت که این نمایشهای داده برای او آسان و بطور مستقیم قابل فهم باشد .

در قالب کلاسترینگ، یک تجرد داده شامل یک تشریح غنی از هر کلاستر میباشد . بطور سطحی و آسان شما میتوانید مجموعه ویژگیهای عنصر مرکزی (Centroid) یک کلاستر را بعنوان برچسب و ماهیت آن کلاستر تعریف کنید .

 

Assessment of Output : مسائلی که در زمینه ارزیابی یک الگوریتم مطرح میشوند، بدنبال این هستند که کدام نتیجه خوب میباشد و کدام ضعیف . این قدرت و ضعف بر اساس این است که دسته های خروجی چقدر به آن معیار نزدیک میباشد و برای ما معنا دار است . بر اساس اینکه داده ها چه پراکنده ای و رفتاری داشته باشند، الگوریتمها ممکن است پارامتریک، نیمه پارامتریک (semi-parametric) یا بدون پارامتریک باشند . این اطلاعات از قبل به ما کمک میکند که طبقه بندی خود را بهینه تر کنیم و در عین اگر پارامتریک باشد با مدلهای آماری موجود میتوان کلاسترینگ را ارزیابی کرد (با آزمونهای مختلف).

 

 

3.2  DEFINITIONS AND NOTATION

 

قبل از اینکه تکنیکهای مختلف را معرفی کنم، لازم است که مفاهیم زیر را بدانیم :

1- یک Pattern (یک بردار ویژگی، مشاهده، اطلاع) را با x  نشان میدهیم که شامل یک آیتم داده یگانه ایست که توسط الگورتیم کلاسترینگ استفاده میشود .

x = (x1,x2,…,xd)    

     d  بعد این الگو (یا فضای الگو) را تعین میکند و xi  هم یک عنصر مجزای اسکالری است که آنرا ویژگی -Attribute-  مینامیم .

2- یک مجموعه از الگوها - Pattern set - را با X = {x1,x2,…,xn}  نشان میدهیم و i-امین نمونه در X بفرم xi = {xi,1,xi,2,…,xi,d} میباشد . در بسیاری از مواقع مجموعه الگوئی که قرار است کلاستر شود ، با یک ماتریس n*d  از نمونه ها نمایش داده میشود .

3- یک کلاس -Class- به حالتی اشاره میشود که دلالت دارد بر فرآیند تولید آن نمونه . تکنیکهای کلاسترینگ در واقع تلاش میکنند که نمونه ها را گروهبندی کنند تا کلاسهای بدست آمده از این دسته بندی منعکس کننده فرآینده های مختلف از بوجود آمدن نمونه ها در یک  Pattern set  باشند .

4- تکنیکهای کلاسترینگ سخت یک برچسب کلاس li را به هر نمونه xi نسبت میدهند که بیانگر کلاس آنها میباشد .

    k  تعداد کلاسترها میباشد                          li =  {1,…,k}

5- رویه های کلاسترینگ فازی، به هر نمونه ورودی xi ، یک عدد کسری fij را نسبت میدهند که بیانگر درجه عضویت آن نمونه به هر کدام از j تا کلاستر خروجی میباشد .

6- معیار مسافت - Distance measure - (حالت خاصی از معیار مجاورت) یک متراژی است بر روی فضای نمونه که تشابهات بین نمونه ها را کوانتیزه میکند .

 

 

3.3  PATTERN REPRESENTATION, FEATURE SELECTION AND EXTRACTION

 

در واقع هیچ راهنمای تئوریکی وجود ندارد که به ما پیشنهاد کند که از چه نمونه ها و ویژگیهائی در امر کلاسترینگ استفاده کنیم . فی الواقع فرآیند تولید نمونه بطور مستقیم برای ما قابل کنترل نیست . نقش کاربر در یک فرآیند نمایش نمونه اینست که تا حد ممکن حدسیات و واقعیات مربوط به داده را جمع آوری کند و بطور اختیاری عملیات گزینش یا استخراج الگو را روی آنها پیاده کند و در نهایت عناصر بعدی که نیاز سیستم کلاسترینگ است را طراحی کند . بخاطر مصائبی که در نمایش الگو وجود دارد، برای سادگی فرض میشود که این نمایش الگو از قبل برای کلاسترینگ موجود میباشد . در کنار این مسئله یک بررسی دقیق حتی اگر خیلی ساده بر روی ویژگیهای موجود و اعمال یک یا چند تبدیل کمک شایانی به سطح کیفی کلاسترینگ میکند . شکل شماره 3 یک مثال ساده را نمایش میدهد .

 

 

 

 

                                                    

 

 

 

                                                                                            شکل 3

                                 

 

 

 

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

 

1. ویژگیهای کمی  

a. مقادیر پیوسته (مانند وزن)

b. مقادیر گسسته (تعداد کامپیوترها)

c. مقادیر فاصله و مدت دار - Interval - (مدت زمانی که یک رخداد طول میکشد)

 

2. ویژگیهای کیفی

a. اسمی یا بدون ترتیب (رنگ)

b. ترتیبی (درجات ارتش و یا ارزشیابی های کیفی مثل سرما و گرما)

 

 

3.4  SIMILARITY MEASURES

 

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

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

 

 

 

 

 

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

 

 

                

رابطه بالا به Squared Mahalanobis Distance  شهرت دارد . نمونه های xi و xj بصورت بردار فرض شده اند و  ماتریس کواریانس میباشد . dm(0,0) وزنهای مختلفی را به ویژگیهای مختلف بر اساس واریانس آنها و وابستگی خطی بین هر دو نمونه نسبت میدهد .

بعضی از الگوریتمهای کلاسترینگ بجای مجموعه نمونه اولیه از یک ماتریس مجاورت استفاده میکنند . با این ترفند میتوان برای n نمونه، فاصله هر دو نمونه که تعدادی برابر n(n-1)/2  میباشد (تعداد عناصر بالا مثلث) را از قبل محاسبه کرد .

حال اگر مقادیر ویژگیها پیوسته نباشند، خود مشکل دیگری است . در این گونه موارد معنای مجاورت و نزدیکی را میتوان در یک حالت ساده با مقادیر بولی پاسخ گفت . در این زمینه کارهای مختلفی انجام گرفته است . Wilson and Martinez [1997] روشی جدید را پیشنهاد داده اند که ترکیبی از فاصله اقلیدسی برای ویژگیهای پیوسته و فاصله شمردنی (ازدحام) برای ویژگیهای اسمی میباشد . Michalaski and Stepp [1983]  هم در کتاب خود از Context نام برده اند که دلالت میکند بر محیطی داده ها در آن قرار گرفته اند . حال تشابه بین دو نقطه xi و xj  بصورت زیر تعریف میشود :

 

                             

 

ξ در این Context (مفهوم)، مجموعه ای از نقاط محاطی میباشند . یک متراژ معمول برای توصیف این Context ، فاصله همسایگی دوطرفه (Mutual Neighbor Distance   یا MND ) میباشد (Gowda and Krishina [1977]) .

 

 

 

NN(xi,xj)  در عبارت بالا به تعداد همسایگان xj  با توجه به xi اشاره میکند . در شکل 4 ، نزدیکترین همسایه به A ، B میباشد و برعکس . پس NN(A,B) = NN(B,A) = 1  و MND بین A  و B برابر با دو میشود . همین طور برای دو نقطه B و C روابط زیر را داریم :

 

NN(B,C) = 1

NN(C,B) = 2

MND (B,C) = 2+1 = 3

 

 

 

 

 

 

 

                            شکل 5                                                         شکل 4

 

 

شکل 5 هم از شکل 4 گرفته شده است با این تفاوت که سه نقطه D,E,F اضافه شده اند . در این حالت MND (B,C) مانند قبل سه میباشد، اما MND (A,B) = 5 میشود . توجه داشته باشید که  NN(B,A) = 3 میباشد و F  جزء همسایگان A بشمار نمیرود .

تئوری آقای Watanabe در سال 1985 که معروف به بچه اردک زشت میباشد، به قرار زیر است که :

 

Insofar as we use a finite set of predicates that are capable of distinguishing any two objects considered, the number of predicates shared by any two such objects is constant, independent of the choice of objects.”

 

بر اساس نظریه بالا این طور بنظر میرسد که میتوان هر دو نمونه دلخواهی را تقریبا شبیه بهم کرد که این کار با کدینگ کردن آن دو با تعداد قابل توجه وکافی از ویژگیها امکانپذیر است . برای مثال در کلاسترینگ معنائی - Conceptual Clustering - که در Michalaski and stepp 1983  معرفی شده (در ادامه این تکنیک را معرفی خواهم کرد)، تشابه بین xi و xj  را اینطور بیان کرده :

   

*در عبارت بالا به مجموعه ای از مفاهیم از پیش تعریف شده اطلاق میشود . این نکته در شکل 6 نمایش داده شده است که فاصله اقلیدسی بین نقاط A  و B کمتر از B و C میباشد . اما میتوان اینطور معنا کرد که B به C بیشتر شبیه more similar - هست (مفهومی که با بیضی نشان داده شده) تا به A (مفهوم چهارضلعی) . 

 

 


                                          

 

 

 

 

 

                                                                        شکل 6

 

 

 

                                          

3.5  CLUSTERING TECHNIQUES

 

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

 


                                 

 

 

 

 

 

 

              شکل 7

 

 

 

 

 

- Agglomerative vs. Divisive : انباره ای یا تقسیم شدن به ساختار و عملکرد الگوریتم مربوط میشود . یک الگوریتم انباره ای با قرار دادن هر نمونه در یک کلاستر مجزا کار خود را شروع میکند و سعی میکند که این کلاسترها را در هم ادغام کند و در نهایت با رسیدن به یک آستانه قابل قبول به کار خود پایان میدهد . اما در حالت تقسیمی، الگوریتم همه نمونه ها را در یک کلاستر واحد قرار میدهد و بعد شروع به شکستن کلاسترها میکند تا به آن حد آستانه مطلوب برسد .

- Monothetic vs. Polythetic  : این خصیصه مربوط به آن است که در یک فرآیند کلاسترینگ، ویژگیها را بصورت دنباله ای بکار ببریم یا همزمان .

- Hard vs. Fuzzy : در الگوریتمهای کلاسترینگ سخت، هر نمونه به یک و تنها یکی از کلاسترهای خروجی تعلق دارد . اما در الگوریتمهای کلاسترینگ فازی، هر نمونه با یک درجه ای از عضویت به هر کدام از کلاسترهای خروجی تعلق دارد . در این حالت میتوان با انتخاب بزرگترین عدد عضویت برای یک نمونه، آن نمونه را به آن کلاستر نسبت داد . با این کار میتوان فازی را به سخت تبدیل کرد .

- Deterministic vs. Stochastic : این مسئله قطعیت یا تصادفی بودن بیشتر درگیر با الگوریتمای پارتیشنی است که سعی بر اینست که تابع مربع خطا بهبود یابد . این بهبودی از دو طریق قابل اعمال است : استفاده از تکنیکهای سنتی و یا از طریق جستجوی تصادفی در فضای حالت که شامل تمامی برچسبهای ممکن میباشد .

- Incremental vs. Non-Incremental : این موضوع در جاهائی که مجموعه نمونه ها خیلی بزرگ باشد، مطرح میشود و دو عامل محدود کننده زمان اجرا و حافظه مصرفی ساختار الگوریتمها را از هم متمایز میکند . الگوریتمهای قدیمی طوری طراحی شده بودند که با نمونه های خیلی بزرگ سروکار نداشتند . اما با ظهور داده کاوی این نیاز احساس شد که الگوریتمهای کلاسترینگ به سوی مینیمم کردن تعداد دفعات اسکن سوق پیدا کنند (کم کردن تعداد دفعات آزمایش نمونه ها در طول اجرا و یا کم کردن سایز ساختارهای داده در طول عملیات الگوریتمها) .

 

 

3.5.1  Hierarchical Clustering Algorithms

 

شکل 8 را در نظر بگیرید که یک الگوریتم کلاسترینگ سلسله مراتبی با استفاده از یک مجموعه داده دو بعدی نشان داده است . دراین شکل هفت نمونه A  تا G در سه کلاستر گنجانده شده اند .

 

 

 

 

 

 

 

 

 


                                  شکل 8

 

 

 

 

حاصل این گونه الگوریتمها، یک dendrogram  میباشد که نمایانگر یک گروهبندی تودرتو از نمونه ها و سطح تشابه آنها وقتی که گروهبندیها تغییر میکند، میباشد . dendrogramی که از این هفت نقطه بوجود میاید درشکل 9 نشان داده شده است (از الگوریتم single-link  بدست آمده) .

 

 

 

 

 

 

 

 


شکل 9

 

 

 

                       

                                                    

dendrogram  را میتوان در سطوح مختلف شکاند تا کلاسترهایی از داده را نشان داد .

 

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

1. single-link   [Sneath and Sokal 1973]

2. Complete-link   [King 1967]

3. minimum-variance   [Murtagh 1984]

 

دو الگوریتم single-link و Complete-link  بسیار معروف میباشند و تفاوت آنها در تشخیص تشابه بین هر دو کلاستر میباشد . در روش single-link ، فاصله بین دو کلاسترعبارت است از مینیمم ترین فاصله ای که میان تمامی جفتهای دو طرف برقرار میباشد (یک نمونه از کلاستر اول و دومی از کلاستر دوم) . اما در روش Complete-link فاصله بین دو کلاستر از روی ماکزیمم ترین فاصله دو نمونه از دو کلاستر تعیین میشود . حال که فاصله بین کلاسترها مشخص شد، هر دو روش با شروع از کمترین فاصله، کلاسترها را در هم ادغام میکنند .

 

 

 

 

 

 

 

 

 

 

 


                                                 شکل 10                                                           شکل 11

 

 

شکل 10 و 11 دو کلاستر را نشان میدهد که با پلی از نمونه های نویزی از هم جدا شده اند . همانطور که مشاهده میکنید، الگوریتمهای Complete-link بیشتر مایلند که کلاسترهائی متراکم تولید کنند . این در حالیست که کلاسترهای خروجی الگوریتم single-link پراکنده و کشیده میباشد . اینکه بگوئیم کدام بهتر است، پرسشی جالب بنظر نمیرسد . چون هر کدام از آنها میتوانند کلاسترهایی تولید کنند که دیگری توانائی آنرا ندارد . برای مثال در شکل 12 تنها الگوریتم single-link است که میتواند کلاسترهای هم مرکز استخراج کند . اما از نقطه نظر عملی، الگوریتمهای Complete-link  محبوبیت بیشتری دارند .

 

 

 

 

 

 

                                                     شکل 12

 

 

 

 

3.5.1.1  Agglomerative Single-Link Clustering Algorithm

 

1- در ابتدا هر نمونه را در یک کلاستر جداگانه گذاشته و فاصله هر دو نمونه مجزا را بدست آورید . این فاصله ها را در یک لیست قرار داده و بصورت صعودی مرتب کنید .

2- از میان لیست مرتب شده، برای هر مقدار افتراق مجزای dk نمونه های متناظر را بهم متصل کنید . این کار تا زمانی ادامه پیدا میکند که تمامی نمونه ها عضو یک گراف متصل (Connected-Graph) باشند . در غیر اینصورت این مرحله تکرار میشود .

3- خروجی این الگوریتم یک سلسله مراتب تودرتو از گرافهائی میباشد که میتوان آنرا در سطوح افتراق دلخواه شکاند و براحتی پارتیشنها (کلاسترها) را بوجود آورد .

 

 

3.5.1.2  Agglomerative Complete-Link Clustering Algorithm

 

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

الگوریتمهای سلسله مراتبی نسبت به الگوریتمهای پارتیشنی که در قسمت بعد آنها را معرفی میکنم، از تنوع بیشتری برخوردارند . برای مثال الگوریتم کلاسترینگ single-link  برای داده هائی که خواص مشترکی ندارند non-isotropic (پراکندگی خوب، زنجیره ای مانند و یا هم مرکز ) بسیار خوب عمل میکند . این در حالیست که الگوریتم پارتیشنی چون K-means  بر روی مجموعه داده هائی که isotropic هستند، کارا میباشد . اما از نظر پیچیدگی زمانی و فضا، الگوریتمهای پارتیشنی موقعیت بهتری را نسبت به سلسله مراتبی دارند . این موضوع باعث شده که در کاربردهای عملی از تلفیقی (Hybrid) از این دو نوع الگوریتم استفاده شود . 

 

3.5.1.3  Hierarchical Agglomerative Clustering Algorithm

 

1- در ابتدا ماتریس مجاورتی میسازیم که فاصله هر دو نمونه را در آن نمایش میدهیم . در واقع با هر نمونه به عنوان یک کلاستر رفتار میکنیم .

2- با استفاده از ماتریس حاصل، جفتی را پیدا میکنیم که بسیار بهم شبیه ترند (کمترین عدد در ماتریس) . آندو را در یک کلاستر ادغام میکنیم و ماتریس مجاورت را به روز میکنیم تا مبین این عمل ادغام باشد .

3- شرط خاتمه : تمامی نمونه ها در یک کلاستر باشند . در غیر اینصورت به مرحله دو میرویم .

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

 

 

3.5.2  Partitional Algorithms

 

آنچه که از یک الگوریتم کلاسترینگ پارتیشنی بدست می آید، یک پارتیشن واحدی از داده بجای یک ساختار کلاستری (چیزی شبیه dendrogramی که در تکنیکهای سلسله مراتبی حاصل میشد) میباشد . متدهای پارتیشنی از این مزایا برخوردارند که میتوانند با مجموعه وسیعی از داده ها کار کنند، و میدانیم که ساختن یک dendrogram از نظر محاسباتی مقرون به صرفه نخواهد بود . اما مشکلی که الگوریتمهای پارتیشنی را دنبال میکند، اینست که تعداد کلاسترهای خروجی چگونه انتخاب شود . روند تولید کلاسترها در تکنیکهای پارتیشنی بر این اساس است که یک تابع سنجش(criterion function) از قبل تعریف شده را بهینه کند . که این تابع ممکن است محلی باشد (بر روی زیرمجموعه ای از نمونه ها تعریف میشود) و یا سراسری (بر روی تمام نمونه ها) . محاسبه مقدار بهینه واضح است که پر هزینه میباشد . بنابراین در عمل معمولا این الگوریتمها را چندین بار با حالات شروع مختلف بر روی نمونه ها اجرا میکنند و بهترین ترکیب بدست آمده برای خروجی کلاسترینگ استفاده میگردد .

 

 

3.5.2.1  Squared Error Algorithms

 

پرکاربردترین و مستقیم ترین تابع سنجش در تکنیکهای کلاسترینگ پارتیشنی، معیار خطای مربعی میباشد که بر روی کلاسترهای متراکم و ایزوله بسیار خوب جواب میدهد . خطای مربعی روی یک عملیات کلاسترینگی چون  از یک مجموعه نمونه هائی چون  (شامل k کلاستر) بصورت زیر تعریف میشود :

در عبارت فوق i-امین نمونه متعلق به j-امین کلاستر را با  نشان داده است و  مقدار عنصر مرکزی (centroid) از j-امین کلاستر میباشد .

 

 

3.5.2.1.1  Squared Error Clustering Method

 

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

2- هر نمونه را به نزدیکترین عنصر مرکزی (متعلق به هر کلاستر) را نسبت دهید و مراکز جدید کلاسترها را محاسبه کنید و آنرا جایگزین مرکزی قبلی نمائید . این عملیات را دوباره تکرار کنید تا یک همگرائی حاصل شود (تا زمانیکه این عضویتها پایدار شوند) .

3- کلاسترها را بر اساس یکسری اطلاعات اکتشافی و ابتکارانه ادغام و بشکنید و بطور اختیاری مرحله دوم را تکرار کنید .

 

k-mean ساده ترین و معمولترین الگوریتمی است که از این معیار خطای مربعی استفاده میکند . این الگوریتم با یک پارتیشن تصادفی اولیه شروع به کار میکند و سعی میکند که هر نمونه را به یک کلاستر نسبت دهد . این کار بر اساس اینکه هر نمونه به کدامیک از عناصر مرکزی کلاسترها شبیه تر میباشد، انجام میشود و آن نمونه را به آن کلاستر نسبت میدهد . در مرحله بعد عناصر مرکزی جدید هر کلاستر محاسبه میشود و جایگزین مرکزی قبلی میشود . حال دوباره سعی میکنیم نمونه ها را با مراکز جدید بسنجیم و آنها را به کلاسترهای مربوطه جدید دوباره نسبت میدهیم .  این عملیات آنقدر ادامه پیدامیکند تا به یک معیار همگرائی برسیم . این معیار همگرائی میتواند این باشد که دیگر نتوانیم یک نمونه را از یک کلاستر به کلاستر دیگر نسبت دهیم و یا اینکه بعد از چند مرحله کاهش خطای مربعی غیر محسوس باشد . در این حالت الگوریتم متوقف میشود . علت محبوبیت این الگوریتم در اینست که بسادگی قابل پیاده سازی است و پیچیدگی زمانی آن O(n) میباشد (n تعداد نمونه ها) . اما مشکل بزرگی که k-mean را تهدید میکند اینست که احتمال دارد در مینیمم محلی (Local Minima) متوقف شود (اگر حالت اولیه را به درستی انتخاب نکنیم) . این مسئله درشکل 13 نشان داده شده است . اگر این الگوریتم را با نمونه های اولیه A,B,C  آغاز کنیم (یعنی میخواهیم در آخر تنها سه کلاستر خروجی داشته باشیم)، در آخر با پارتیشن {{A},{B,C},{D,E,F,G}} متوقف خواهیم شد . این پارتیشن بندی درشکل با بیضی نمایش داده شده است . حال مسئله را با نمونه های دیگری چون A,D,F اگر آغاز کنیم، به پارتیشن {{A,B,C},{D,E},{F,G}} میرسیم . برای اینکه بفهمیم کدامیک بهتر عمل کرده، خطای مربعی را برای دو پارتیشن بدست آمده محاسبه میکنیم و مشاهده میشود که خطای مربعی دومی کمتر از اولی میباشد . این بدان معناست که اگر راه اول را رفته باشیم در مینیمای محلی گیر خواهیم افتاد (درباره این مسئله پارتیشن دومی بهترین دسته بندی است که میتوان برای ان انجام داد مینیمم سراسری- و در شکل با چهارضلعی نشان داده شده است) .

 

 

 

 

 

 

 


                                  شکل 13

 

                                          

 

 

 

انواع مختلفی از الگوریتم k-mean در مقالات متعدد ذکر شده است . بعضی از آنها تلاش کرده اند که یک پارتیشن اولیه خوبی را انتخاب کنند تا الگوریتم بتواند به سوی پیدا کردن مقدار مینیمم سراسری متمایل شود .

انواع دیگر کلاسترهای نتیجه را ادغام و یا میشکانند . معمولا یک کلاستر شکسته میشود هرگاه واریانس آن بیشتر از یک حد تعریف شده باشد . و دو کلاستر در هم ادغام میشوند هر گاه فاصله بین دو عنصر مرکزی از دو کلاستر کمتر از یک حد آستانه تعریف شده باشد . فکر میکنم با این ابتکار بتوان با هر پارتیشن اولیه ای، به یک پارتیشن بهینه نهائی رسید (البته باید مقادیر پیش فرض آستانه را به واقع تخمین زد) . الگوریتم ISODATA که بسیار معروف میباشد [Ball and Hall 1965] از همین تکنیک شکستن و ادغام استفاده میکند . برای مثال اگر پارتیشن بیضی در شکل 13 را بعنوان پارتیشن اولیه به این الگوریتم بدهید، میتوان به سه کلاستر بهینه که با چهارضلعی نشان داده شده است، رسید . این الگوریتم در ابتدا دو کلاستر {A} و{B,C} را در یک کلاستر ادغام میکند (چون فاصله بین دو مرکز کوچک میباشد) و بعد کلاستر{D,E,F,G}  که واریانس بزرگی دارد را به دو کلاستر{D,E} و{F,G} میشکند .

بعضی دیگر از انواع الگوریتم k-mean از یک تابع سنجش دیگری استفاده میکنند . برای مثال Diday [1973] یک راهبرد کلاسترینگ دینامیکی را معرفی کرده که مسئله کلاسترینگ را با تخمین حداکثر اشتیاق (Maximum-Likelihood Estimation) پاسخ داده است .

در ضمن بسیاری از مواقع در عمل از این الگوریتم بطور غیرمستقیم استفاده میشود . همانطور که در بالا ذکرکردم پیچیدگی زمانی این الگوریتم خطی و پیاده سازی آن آسان میباشد . بهمین دلیل تلفیقی از این الگورتیم با دیگر الگوریتمها کارآئی خوبی دارد . برای مثال در قسمت بعد الگوریتمهای ژنتیکی را برای کلاسترینگ معرفی خواهم کرد . از این الگوریتمها میتوانیم برای پیدا کردن پارتیشن اولیه که ورودی الگوریتم k-mean است، استفاده کنیم .

 

 

3.5.2.2  Graph-Theoretic Clustering

 

شناخته ترین الگوریتم کلاسترینگ تقسیمی برپایه تئوری گراف، ساختن درخت مینیمال (Minimal Spanning Tree   یا MST ) از نمونه های آموزشی میباشد [Zahn 1971] که در این الگوریتم سعی میشود که یالهای با طول بزرگترین حذف میشود تا کلاسترهای دلخواه تولید شوند . شکل 14 یک MST را که از نه تا نمونه آموزشی بدست آمده را نشان میدهد . با شکستن اتصال CD با طول 6 (ماکزیمم فاصله اقلیدسی)، دو کلاستر{A,B,C} و{D,E,F,G,H,I} حاصل خواهند شد . در ادامه دومین کلاستر هم شکسته میشود، چون یال EF طولی برابر با 4.5 دارد .

 

 

 

 

 

 

 

 

 

 


                                           شکل 14

 

 

                                 

 

 

راهبردهای سلسله مراتبی را هم میتوان به این نوع کلاسترینگ (بر پایه تئوری گراف) نسبت داد . به این معنا که کلاسترهای single-link در واقع زیرگرافهائی از این درخت مینیمال بشمار میروند . کلاسترهای Complete-link هم زیرگرافهای کامل ماکزیمال از گراف هستند (گراف رنگ آمیزی بر اساس رئوس) . در واقع بر اساس ادعای Backer and Hubert [1967] این زیرگراف کامل ماکزیمال یک تعریف سخت و محکمی (Strictest) از کلاسترینگ در نظر گرفته میشود .

 

 

3.5.2.3  Mixture-Resolving and Mode-Seeking Algorithms

 

راهبرد برطرف سازی مخلوط - Mixture-Resolving -  برای عملیات کلاسترینگ به طرق مختلف تعریف شده اند . برای مثال Jain and Dubes [1988] در یک دسته بندی الگوریتمها را به دو قسمت طبقه بندی کرده اند : پارامتریک و ناپارامتریک . در تکنیکهای پارامتریک پیش فرضی که در نظر گرفته میشود اینست که نمونه ها از یک یا چندین توزیع گرفته شده است و هدف پیدا کردن پارامترهائی برای آن میباشد . در اکثر مواقع فرض میشود که اجزای مجزا از توزیع مخلوط بصورت گاوسین- Gaussian - میباشند . در اینصورت پارامترها در گاوسین های مجزا در طی یک پروسه ای تخمین زده میشوند (تخمین ماکزیمم اشتیاق) . یکی از الگوریتمهائی که برای تخمین پارامترها بکار گرفته میشود، Expectation-Maximization میباشد که شرح کامل آن در کتاب Mitchell 1997 آورده شده است . در قالب کاری EM ، پارامترهای اجزای تراکم نامعلوم میباشد (مخلوط) و از روی نمونه ها تخمین زده میشوند . پروسه EM با یک بردار احتمال اولیه از پارامترها شروع میشود و بصورت چرخه ای هر نمونه را در مقایسه با توزیع مخلوطی که توسط بردار پارامتر ساخته شده بود، امتیازدهی میکند . در مرحله بعد بردار پارامترها را تصحیح کرده و کار تکرار میشود .

 

 

3.5.2.3.1  EM Algorithm

 

فرض میکنیم هر نمونه بصورت Yi = <xi,zi1,zi2,…,zik> باشد (k تا توزیع گاوسین داریم) که zij در این عبارت بمعنای تعلق نمونه xi به توزیع گاوسین j-ام میباشد (zij مقدار بولی میگیرد) .

1- یک بردار پارامتر پیش فرض برای این توزیع مخلوط متصور میشویم .                             h = <m1,m2,…,mk> .

2- با استفاده از بردار پارامتر بدست آمده، امید k تا توزیع را از رابطه زیر بدست می آوریم :

 

3- با استفاده از k توزیعی که در بالا بدست آمده، بردار پارامتر را تصحیح میکنیم . اگر به یک معیار همگرائی رسیده باشیم الگوریتم متوقف میشود و در غیر اینصورت به مرحله دو میرویم . 

 

برای جزئیات بیشتر شما را به کتاب Machine Learning نوشته Ethem Alpaydin ارجاع میدهم که نسخه ای از آن در کتابخانه مرکزی دانشگاه امیرکبیر موجود میباشد . در این کتاب علاوه بر تکنیکهای پارامتریک و ناپارامتریک،  دسته جدیدی را تحت عنوان نیمه پارامتریک - Semi-Parametric - معرفی کرده است .

 

3.5.2.4  Fuzzy Clustering

 

در راهبردهای کلاسترینگ سنتی آنچه تولید میشد، یک پارتیشنی از داده ها بود . در این پارتیشن هر نمونه به یک و تنها یک کلاستر تعلق داشت . بنابراین کلاسترها در کلاسترینگ سخت از هم جدا و منفصل میباشند . منطق فازی که توسط آقای لطفی زاده در 1965 مطرح شد، این مفهوم را به کلاسترینگ افزود که هر نمونه را میتوان با یک تابع عضویت به هر کدام از کلاسترها نسبت داد . مراحل کلی یک الگوریتم فازی بقرار زیر است :            [Jan 1999 ] A.K. Jain and M.N. Murty and P.J. Flynn

 

1- ماتریس U را با سایز N*K  عنصر اولیه مقداردهی میکنیم . (N شیء را به  K کلاستر نسبت میدهیم) . هر عنصر uij از این ماتریس بیانگر درجه عضویت شیء xi به کلاستر cj میباشد . معمولا مقدار uij  متعلق به بازه صفر تا یک میباشد .

2- با استفاده از ماتریس U بدست آمده، مقدار یک تابع سنجش فازی را پیدا میکنیم (برای مثال تابع سنجش خطای مربعی اوزان مربوط به آن پارتیشن)

 

       و       

 

         ( در واقع k-امین مقدار مرکزی کلاستر فازی میباشد)

در یک چرخه نمونه ها را دوباره به کلاسترها نسبت میدهیم تا این تابع سنجش معرفی شده در بالا را کاهش دهیم و دوباره ماتریس U را میسازیم .

3- مرحله دو را آنقدر تکرار میکنیم تا درایه های U تغییرات چشم گیری نکنند .

 

برای روشن تر شدن این مطلب به شکل 15 توجه کنید . چهار ضلعی ها دو کلاستر سخت را نشان میدهند :   H1 = {1,2,3,4,5}و  H2 = {6,7,8,9}  . اما یک الگوریتم کلاسترینگ فازی ممکن است F1 و F2 را در شکل بوجود بیاورند (بیضی) که هر نمونه دارای مقدار عضویتی بین صفر و یک میباشد .

 

 

 

 

 

 

 

 


                                           شکل 15

 

 

 

 

 

مثلا

F1 = {(1,0.9),(2,0.8),(3,0.7),(4,0.6),(5,0.55),(6,0.2),(7,0.2),(8,0.0),(9,0.0)}

 

F2 = (1,0.0),(2,0.0),(3,0.0),(4,0.1),(5,0.15),(6,0.4),(7,0.35),(8,1.0),(9,0.9)}

 

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

 

 

3.5.2.5  Artificial Neural Networks for Clustering

 

همانطور که میدانیم، شبکه های عصبی مصنوعی از الگوی شبکه های عصبی بیولوژیکی ایده گرفته است . برخی از ویژگیهائی که باعث شده از ANN ها برای کلاسترینگ استفاده کنیم، عبارتند از :

1- ANNها با بردارهای عددی کار میکنند، بنابراین نمونه های آموزشی میبایست تنها از ویژگیهای شمارشی برای نمایش استفاده کنند .

2- ANN ها ذاتا موازی هستند و از معماری پردازشی توزیعی پشتیبانی میکنند .

3- ANN ها میتوانند مقادیر وزنی فی مابین لایه ها را بطور تدریجی یاد بگیرند .

 

از شبکه های عصبی رقابتی- Competitive - [Jain & Mao 1996]  برای دسته بندی دادده های ورودی استفاده میکنیم . در یادگیری رقابتی، نمونه های مشابه هم توسط شبکه گروهبندی میشوند و با یک واحد مجزا (نرون) نمایش داده میشود . این گروهبندی بطور اتوماتیک بر اساس ارتباط داده ها انجام میگیرد . مثالهای شناخته شده از ANN ها که برای کلاسترینگ بکار رفته اند شامل Kohonen’s learning vector quantization (LVQ)  و self-organizing map (SOM) و adaptive resonance theory models میباشد [Carpenter and Grossberg 1990]  . معماری این ANN ها بسیار ساده است : آنها تک لایه ای هستند . نمونه ها در ورودی ظاهر میشوند و با نودهای خروجی پیوند خورده اند . وزنهائی که در میان نودهای ورودی و خروجی قرار گرفته اند، بطور چرخه ای آنقدر تغییر میکنند (که این عمل را یادگیری مینامیم) تا به یک معیار همگرائی برسیم .

 

 

3.5.2.6  Evolutionary Approaches for Clustering     

 

روشهای تکاملی که از روی سیر تکاملی طبیعی الگوبرداری شده اند، از عملگرهای تکوینی و جمعیتی از راه حلها استفاده میکند تا به یک تقسیم بندی سراسری بهینه ای از داده ها برسد . راه حلهای کاندید برای مسئله کلاسترینگ بصورت کروموزم رمزگذاری میشوند . معروفترین عملگرهای تکوینی هم شامل Selection ، Recombination و Mutation میباشند که هر کدام یک یا چند کروموزم را بعنوان ورودی میگیرند و در خروجی یک یا چند کروموزم حاصل میشود . تابع fitnessی که برای ارزیابی یک کروموزم بکار میرود، بیانگر میزان اشتیاق کروموزم برای نجات یافتن به نسل بعدی میباشد . شرح سطح بالای یک الگوریتم تکاملی بصورت زیر میباشد :

 

1- یک جمعیت تصادفی از راه حلها را انتخاب کنید . منظور از راه حل در اینجا بمعنای یک k-پارتیشن معتبری از داده ها میباشد . حال یک مقدار fitness را برای هر راه حل محاسبه کنید . معمولا fitness متناسب با عکس خطای مربعی میباشد . این بدین معناست که یک راه حل با خطای مربعی کوچک، یک مقدار fitness بالائی دارد .

2- از عملگرهای تکاملی Selection ، Recombination و Mutation برای تولید نسل بعدی راه حلها استفاده کنید و برای هر کدام باز مقدار fitness را محاسبه کنید .

3- مرحله دوم را آنقدر تکرار کنید تا به یک شرط خاتمه برسید .

 

از مشهورترین تکنیکهای تکاملی میتوان الگوریتهای ژنتیک (GA) ، استراتژیهای تکاملی- Evolutionary Strategies - (ES) و برنامه نویسی تکاملی- Evolutionary Programming - (EP) را نام برد . در میان سه روش فوق، GA ها از اهمیت بیشتری برخوردارند . معمولا راه حلها در این روش بصورت رشته های باینری بیان میشوند . عملگر گزینش با یک رفتار احتمالی بر روی مقدار fitness راه حلها، نسل بعدی از راه حلها را از میان راه حلهای موجود تولید میکند . انواع مختلفی از عملگرهای Recombination وجود دارند که معروفترین آنها crossover میباشد . همانطور که در شکل زیر نشان داده شده است، crossover دو جفت کروموزم (parents) را بعنوان ورودی گرفته و جفت جدیدی از کروموزمها (children or offspring) را در خروجی تولید میکند .

 

 

 

 

 

 

 

 

 

 


                                 

                                           شکل 16

 

 

 

 

در Mutation ، یک کروموزم بعنوان ورودی درنظر گرفته میشود و کروموزم خروجی با مکمل کردن تصادفی یکی از بیتهای کروموزم اولیه حاصل میشود . برای مثال رشته 1111110 بعد از اعمال این عملگر بر روی بیت دوم رشته 1011110 تولید میشود . عملگر crossover برای اکتشاف فضای جستجو بکار میرود و این در حالیست که Mutation یک ضمانت کامل بودن میدهد (یعنی ضمانت میکند که هیچ قسمتی از فضای نمونه نیست که که کشف نشده باشد) .

ES و EP ها در طرز نمایش راه حلها و همچنین عملگرهای تحولی متفاوت از GA ها میباشند . مثلا EP از عملگر Recombination استفاده نمیکند . اما تمام این روشها برای حل مسئله کلاسترینگ بدنبال می نیمم کردن تابع خطای مربعی میباشند .

مهمترین ویژگی GA ها جستجوی سراسری آنها میباشد . این در حالیست که روشهائی چون  k-means ، fuzzy clustering algorithms ، شبکه های عصبی و جستجوهای simulated annealing و tabu search (که در ادامه معرفی خواهند شد) همگی بصورت محلی میباشند . این ویژگی GA از آنجا ناشی میشود که از عملگرهای تحولی چون crossover و mutation استفاده میکنند و راه حلهای کاملا متفاوت را ارائه میدهند . این رفتار متفاوت را میتوانید در شکل زیر مشاهده کنید .

 

 

 

 

 

 

 

                                           شکل 17

 

 

 

 

 

 

 

 

فرض کنید اسکالری چون X با یک رشته باینری پنج بیتی کد شده است . S1 و S2 دو کروموزم (یا نقطه) در فضای جستجو یک بعدی میباشند و مقادیر دسیمال آنها بترتیب 8 و 31 میباشد . (S1= 01000 , S2=11111 ) . حال با اعمال crossover روی بیت پرارزش دوم و سوم میتوان S3 و S4 را بدست آورد (S3=01111 , S4=11000) . بطور مشابه میتوان Mutation را بر روی پرارزش ترین بیت 01111 اعمال کرد و رشته باینری 11111 که معادل 31 دسیمال است را بدست آورد . این پرشها در میان نقطه های مختلف فضای جستجو بسیار بزرگتر از آنهائی است که در روشهای قبل معرفی شد .   

در مقاله ای که توسط Raghavan and Birchand [1979] نوشته شده است (شاید یکی از اولین مقاله هائی است که درباره استفاده از GA برای کلاسترینگ وجود دارد)، هر نقطه را برای نمایش یک پارتیشنی از N  شیء به K کلاستر تعریف کرده است . برای مثال 6 نمونه A,B,C,D,F  را در نظر بگیرید که میخواهیم با دو کلاستر آنها را از هم جدا کنیم . رشته بیت 101001 که یک نقطه (کروموزم) را نشان میدهد، بیان میکند که کلاستر اول شامل نمونه های اولی ، سومی و ششمی است و کلاستر دوم شامل بقیه نمونه هاست (هم ارز  010110) . پس میتوانیم کلاسترها را بفرم زیر نمایش دهیم : {A,C,F} , {B,D,E} . اگر K کلاستر داشته باشیم، K ! (فاکتوریل) کروموزمهای مختلف داریم که هر کدام به K پارتیشن از داده اشاره میکند . این فضای بزرگ باعث شد که محققین بدنبال طراحی بهینه ای از شمای نمایش و عملگرهای crossover باشند . یکی از این طرحها بکار بردن عملگر اضافی چون * میباشد، بدین معنی که کروموزمی چون BDE*ACF  دو پارتیشن {A,C,F} , {B,D,E} را نمایش میدهد . حال میتوان مسئله کلاسترینگ را به مسائلی چون فروشنده دوره گرد نگاشت کرد و آنرا ادامه داد [Bhuyan 1991] .

یکی دیگر از این بهبودها که توسطJones and Beltramo  معرفی شد، بکار بردن عملگر edge-based crossover میباشد . در اینجا فرض میشود که تمام نمونه ها از یک کلاستر، یک گراف کاملی را تشکیل میدهند . کروموزمهای جدید که از والد خود بوجود می آیند، یالهای والد خود را نیز به ارث میبرند . و بعد در همین مقاله ارزیابی کرده که در مواردی که تعداد کلاسترها بیش از 10 باشد پیچیدگی زمانی این نوع عملگر crossover برابر است با :                 O(+N)

 

 

3.5.2.7  Search-Based Approaches

 

تکنیکهای جستجو برای پیدا کردن مقدار بهینه ای از تابع ارزیابی بکار میروند و به دو دسته تکنیکهای قطعی و تصادفی تقسیم میشوند . در تکنیکهای قطعی با اجرای یک محاسبه کامل و زمان گیر، یک پارتیشن بهینه ای از داده ها را تضمین میکند . در طرف دیگر تکنیکهای تصادفی یک پارتیشن تقریبا بهینه را تولید میکنند که در نهایت به یک پارتیشن بهینه میل میکند . در میان تکنیکهائی که تا حال معرفی شدند همگی قطعی بودند بغیر از الگوریتمهای تکاملی . تکنیکهای قطعی معمولا بصورت Greedy عمل میکنند و این در حالیست که در تکنیکهای تصادفی اجازه داده میشود که انحرافات راه حلها در سوی بهینگی غیر محلی با احتمالت غیر صفر سوق پیدا کند . تکنیکهای تصادفی میتوانند موازی (الگوریتمهای تکاملی) و یا ترتیبی باشند . یک نمونه آشنای تکنیک تصادفی ترتیبی، جستجوی شبه تابکاری (Simulated Annealing) یا به اختصار SA  میباشد . شبه تابکاری فرآیندی است که برای ایجاد تغییرات در فلزات و شیشه ها بکار میرود . در این کار آنها را تا درجه بالائی داغ کرده و آنگاه به تدریج سردشان میکنند تا مولکولهای مواد در یک حالت کم انرژی کریستالی به یکدیگر بچسبند . مشکل اصلی ما گیر افتادن در مینیماهای محلی است . پس احتیاج به نیروئی داریم که بتوانیم از این مینیمای محلی بیرون بیائیم . اما این تکان نباید به اندازه ای باشد که حتی از مینیمای سراسری هم بگذریم . بر همین اساس همانند روش شبه تابکاری، از تکانهای سخت شروع میکنیم (در درجه حرارت بالا) و بعد به تدریج شدت تکانها را کم میکنیم (با کاهش درجه حرارت) . در این روش در یک حلقه تکرار بجای آنکه بهترین حرکت بعدی را برگزینیم، یک حرکت بعدی را بطور تصادفی انتخاب میکنیم . اگر این حرکت موقعیت ما را بهتر کرد آنرا بعنوان حرکت بعدی میپذیریم و در غیر اینصورت این حرکت را با احتمال p=e^(E/T)  بعنوان حرکت بعدی میپذیریم . E اختلاف بدی وضعیت حاصل از حرکت مورد نظر با وضعیت جاری را نشان میدهد که دارای علامتی منفی است . این احتمال با کاهش درجه حرارت نیز کاهش می یابد . اثبات شده است که اگر کاهش تدریجی حرارت به اندازه کافی کند باشد، این الگوریتم بهینه سراسری را با احتمالی که به یک نزدیک میشود خواهد یاافت (مثلا T را هر بار در 0.98 ضرب کنیم ) . یک الگوریتم سطح بالای SA  برای کلاسترینگ بصورت زیر خواهد بود :

 

 1- بطور تصادفی یک پارتیشن اولیه ای چون P0 را انتخاب کرده و مقدار خطای مربعی EP0  را برای آن محاسبه کند . برای پارامترهای کنترلی T0 و Tf  (درجه حرارت اولیه و نهائی) مقادیری را نسبت دهید .

2- همسایه ای از P0 چون P1 را انتخاب و EP1 را برایش محاسبه کنید . اگر این مقدار از EP0  بیشتر بود با همان احتمالی که شرح آن رفت P1 را به P0  نسبت دهید . ودر غیر اینصورت P1 را به P0  نسبت دهید . این مرحله را برای تعداد مشخصی از تکرار انجام دهید .

3- T0 را کاهش دهید : T0=cT0 . اگر T0 از Tf  بزرگتر بود به مرحله دو برو و در غیر اینصورت الگوریتم خاتمه می یابد .

 

 

3.6  Conceptual Clustering

 

کلاسترینگ مفهومی از آن جهت برای ما مهم است که میتوانیم نمونه هائی را که دسته بندی نشده اند در یک طبقه معنائی مشخص قرار دهیم و در یک سلسله مراتب خصوصیات عمومی طبقه بالاتر را به طبقات پائین تر منتقل کنیم (ارث بری) . در حقیقت این شبیه همان کاری است که دانشمندان (بهتر است بگوئیم بیولوژیست ها) سعی کرده اند در طی قرنها طبقه ای چون مهره داران و زیرگروه آن پستانداران و پرندگان و ... را معرفی کنند . حال اگر گفته شود که اسب یک پستاندار است، ما به سرعت متوجه خواهیم شد که آیا چنین حیوانی تخم میگذارد و یا اینکه پرواز میکند یا خیر؟!...

در تکنیکهای آماری قدیمی هم کاری مشابه انجام میشود . مثلا شکل زیر را در نظر بگیرید که نمونه ها را با دو ویژگی عددی x و y نمایشداده است . پر واضح است که با یک الگوریتم ساده کلاسترینگ که از similarity (میزان تشابه) بهره میبرد، میتوان نمونه ها را بدو گروه تقسیم کرد . و از آنجائیکه ویژگیهای مذکور عددی میباشند، براحتی از فاصله اقلیدسی بعنوان معیار تشابه میتوان استفاده کرد (جزئیات این روش را در قبل مشاهده کردیم) . اما مسئله ای که وجود دارد اینست که تشابه هر نمونه ای را نمیتوان با ارزیابی های عددی انجام داد . برای مثال فاصله بین سگ و زرافه را با گربه و فیل بدست آورید؟!... حتی اگر بتوان این فاصله ها را بفرم عددی تبدیل کرد، خود این تبدیلات کاری سخت و دشوار خواهد بود .

 

 

 

 

                                                                         شکل 18

 

                                          

 

 

 

 

 

کلاسترینگ مفهومی را بعنوان یک فرم Novel (داستانی و حکایت) از عمل کلاسترینگ معرفی کرده اند که تنها کلکسیونی از اشیاء نمیباشد که دارای میزانی از تشابهات باشد (Michalski and Stepp 1983) . با این تعریف میتوان نتیجه گرفت که کلاسترینگ مفهومی نه تنها کلاسترها را تولید میکند، بلکه شرحی از مفاهیم مرتبط با آن را تولید میکند . در یک سطح انتزاعی بالا میتوان مراحل الگوریتم کلاسترینگ معنائی را بفرم زیر خلاصه کرد : (R.S. Michalski, I. Bratko, M. Kubat 1998)

 

1- انتخاب k  هسته که توسط کاربر تعریف میشود .

2- تعداد k  ستاره بسازید . هر ستاره مجموعه ای از شرح عمومی ترین توصیفات یک هسته میباشد که این عمومی سازی (Generalization) آنقدر افزایش می یابد تا در مقابل هسته های دیگر محدود شود (Specialization) . 

3- برای هر ستاره یک و تنها یک قانون (Rule) تولید کنید که اولا حداقل تداخل منطقی را با دیگر قوانین مربوط به ستاره های دیگر داشته باشد و ثانیا اجتماع منطقی تمام قوانین، بیشترین تعداد نمونه ها را پوشش دهد .

4- اگر هنوز نمونه ای باقی مانده اند که پوشش داده نشده است، مناسبترین (Fine) قوانین را برای آنها پیدا کنید . در تخصیص قوانین میبایست بازنگری بعمل بیاید (Refine) تا قوانین حاصل تمام نمونه های باقیمانده را پوشش دهد و بطور منطقی جدا از هم باشند . نمونه هائی که متعلق به اشتراک چند قانون هستند را دوباره توزیع کنید تا هر نمونه دقیقا به یک قانون نسبت داده شود . در این لحظه هر قانون مجموعه ای از نمونه ها را نمایش میدهد . حال برای هر کدام از این مجموعه ها هسته جدید را انتخاب کنید .

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

برای آنکه الگوریتم فوق را متوجه شویم، جدول زیر را در نظر بگیرید که متشکل از سه ویژگی میباشد . ویژگی اول سمبلیک، ویژگی دوم مقادیر صحیح و ویژگی سوم مقادیر صحیحی میباشد که میتوان آنرا با سه سمبلSmall  ،Medium  و Large گسسته وار نمایش داد .

 

 

Example

Attribute1

Attribute2

Attribute3

     e1

        a

         2

       110

     e2

        b

         4

       100 

     e3

        b

         2

         9     

     e4

        b

         3

        10  

     e5

        c

         5

        20 

     e6

        c   

         4

        15

     e7

        b     

         5

       200

     e8

        b

         4

        50        

 

 

           

 

 

 

 

 

 

 

 

این الگوریتم را با K=2 آغاز میکنیم . بنابراین بطور تصادفی دو هسته را انتخاب میکنیم . مثلاe1  و e5 . و داریم :

dest (e1) : (at1=a) & (at2=2) & (at3=Large)

dest (e5) : (at1=c) & (at2=5) & (at3=Small)

 

و ستاره های اولیه عبارتند از :

star (e1) : (at1c) & (at2≠5) & (at3≠Small)

star (e5) : (at1a) & (at2≠4) & (at3≠Large)

 

هر ستاره سه قانون تک شرطی دارد و قوانین متعلق به ستاره های مختلف با هم متقاطع میباشند . از هر ستاره یک قانون انتخاب میشود و بنحوی اصلاح میشود که قوانین داخل مجموعه_قوانین (Rule-Set) بدست آمده بطور منطقی از هم جدا باشند و اجتماع آنها تمامی نمونه ها را پوشش دهد (این عمل با رویه های NID و PRO انجام میگیرد و در Michalski and Stepp 1983 آمده است) . نتیجه حاصل از عملیات فوق، راه حل زیر میباشد :

 

CLUSTER 1 : (at1=ab) & (at2=23)

              instances: e1,e3,e4

 

CLUSTER 2 : (at1=bc) & (at2=45)

              instances: e2,e5,e6,e7,e8

 

این راه حل را میتوان بعنوان بهترین جواب برای K=2 در نظر گرفت . زیرا انتخاب هسته های دیگر از قوانین فوق، ارتقائی در جواب بوجود نمی آورد . حتی تکرار الگوریتم برای مقادیر دیگر K هم بهبودی حاصل نمیکند . پس میتوان نتیجه گرفت که راه حل فوق بهترین کلاسترینگ معنائی است که میتوان بر روی داده های آموزشی مذکور بوجود آورد .

 

 

 

 

 

 

Bibliography

 

[1]  Alpaydin, E., Introduction to Machine Learning, MIT Press 2004

 

[2]  Michalski, R.S, Bratko, I., Kubat, M., Machine Learning and Data Mining: Methods and Applications, Wiley Edition, 1998

 

[3]  JAIN, A. K. AND DUBES, R. C. 1988. Algorithms for Clustering Data. Prentice-Hall advanced,Saddle River, NJ.

 

[4]  MICHALSKI, R., STEPP, R. E., AND DIDAY, E. 1983. Automated construction of classifications: conceptual clustering versus numerical taxonomy.

 

[5]  AL-SULTAN, K. S. AND KHAN, M. M. 1996. Computational experience on four algorithms for the hard clustering problem.

 

[6]  CAN, F. 1993. Incremental clustering for dynamic information processing.

 

[7]  FISHER, D. 1987. Knowledge acquisition via incremental conceptual clustering.

 

[8]  AUGUSTSON, J. G. AND MINKER, J. 1970. An analysis of some graph theoretical clustering techniques.

 

[9]  BABU, G. P. AND MURTY, M. N. 1993. A nearoptimal initial seed value selection in K-means algorithm using a genetic algorithm (Oct. 1993)

 

[10]  BABU, G. P. AND MURTY, M. N. 1994. Clustering with evolution strategies.

 

[11]  BALL, G. H. AND HALL, D. J. 1965. ISODATA, a novel method of data analysis and classification. Technical Report. Stanford University, Stanford, CA

 

[12]  BENTLEY, J. L. AND FRIEDMAN, J. H.  June 1978. Fast algorithms for constructing minimal spanning trees in coordinate spaces.

 

[13]  CHOUDHURY, S. AND MURTY, M. N. 1990. A divisive scheme for constructing minimal spanning trees in coordinate space. (Jun. 1990)

[14]  BISWAS, G., WEINBERG, J., AND LI, C. 1995. A Conceptual Clustering Method for Knowledge Discovery in Databases.

 

[15]  AGGARWAL, C.C., PROCOPIUC, C., WOLF, J.L., YU, P.S., and PARK, J.S. 1999a. Fast algorithms for projected clustering. In Proceedings of the ACM SIGMOD Conference, Philadelphia, PA.

 

[16]  BABU, G.P. and MURTY, M.N. 1993. A near-optimal initial seed value selection in Kmeans algorithm using a genetic algorithm.

 

[17]  BEYER, K., GOLDSTEIN, J., RAMAKRISHNAN, R., and SHAFT, U. 1999. When is nearest neighbor meaningful? In Proceedings of the 7th ICDT, Jerusalem, Israel.

 

[18]  BOLEY, D.L. 1998. Principal direction divisive partitioning. Data Mining and Knowledge Discovery