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) هم
استفاده کرد .
همانطور
که ملاحظه
میکنید این
مدل تنها میتواند
مفاهیم ساده
را بیان کندو
بعبارت دیگر
از قدرت
تشریحی
پائینی
برخوردار
میباشد .
از
نظر رسمی این
مدل به مانند
منطق رتبه صفر
میباشد، اما
ساختار و 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) را
بسازنند که
مفاهیم
پیچیده را
میتوان با آن
نمایش داد .
در
این منطق اسم
گزاره ها را
هم متغیر در
نظر میگیریم و
خانواده
بزرگتری از
زبانها معرفی
میشود .برای
مثال شمای زیر
را در نظر
بگیرید :
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
کلاسترینگ
یک دسته بندی
بدون نظارت از
نمونه ها
(مشاهدات،
آیتمهای داده
و بردارهای
ویژگی) به
گروهها
(کلاسترها)
میباشد .
مسئله
کلاسترینگ در
زمینه های
مختلفی توسط
محققین به طرق
مختلفی مطرح
شده است . و این
مسئله بیانگر اینست
که کلاسترینگ
یکی از مراحل
مهم و اساسی در
تحلیل
اکتشافی داده
میباشد . رویه
های تحلیل
داده ممکن است
اکتشافی باشد
یا تائیدی (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. ترتیبی
(درجات ارتش و
یا ارزشیابی
های کیفی مثل
سرما و گرما)
ازآنجائیکه
تشابه یک رکن
اصلی از یک
کلاستر بشمار
میرود، تعیین
یک معیار
تشابه در فضای
ویژگیها امری
ضروری برای
رویه های
کلاسترینگ میباشد
. بخاطر تنوعی
که در انواع
ویژگی ها وجود
دارد، معیار
مسافت
میبایست بدقت
انجام بگیرد .
همانطور که در
قبل متذکر
شدم، استفاده
از معیار
مسافت برای
محاسبه میزان
افتراق بین دو
نمونه بکار
میرود .
معروفترین
متراژی که بر
روی ویژگیهای
پیوسته بکار
برده میشود،
فاصله
اقلیدسی است :
این
روش برای
جاهائی که بعد
فضا دو یا سه
باشد، کارآئی
خوبی دارد (در
ضمن بهتراست
که مجموعه
داده های ما
ایزوله و
متراکم باشد) .
مشکل اصلی این
روش اینست که
ویژگیهائی با
اندازه
بزرگتر بر روی
دیگر ویژگیها
حاکمیت
میکنند .
راهکارهای
بسیاری در
راستای بهبود
آن صورت گرفته
که از جمله آن نرمال
کردن
ویژگیهای
پیوسته در یک
رنج مشخص میباشد
. وابستگی خطی
میان ویژگیها
دومین مشکل این
روش بحساب می
آید که با
اعمال تبدیل
وزنی زیر میتوان
آنرا رفع کرد .
رابطه
بالا به Squared Mahalanobis Distance شهرت
دارد . نمونه
های xi و xj بصورت
بردار فرض شده
اند و ∑ ماتریس
کواریانس
میباشد . dm(0,0) وزنهای
مختلفی را به
ویژگیهای
مختلف بر اساس
واریانس آنها
و وابستگی خطی
بین هر دو
نمونه نسبت
میدهد .
بعضی
از
الگوریتمهای
کلاسترینگ
بجای مجموعه
نمونه اولیه
از یک ماتریس
مجاورت
استفاده میکنند
. با این ترفند
میتوان برای n
نمونه، فاصله
هر دو نمونه
که تعدادی
برابر n(n-1)/2
میباشد
(تعداد عناصر
بالا مثلث) را
از قبل محاسبه
کرد .
حال
اگر مقادیر
ویژگیها
پیوسته
نباشند، خود مشکل
دیگری است . در
این گونه
موارد معنای
مجاورت و
نزدیکی را
میتوان در یک
حالت ساده با مقادیر
بولی پاسخ گفت
. در این زمینه
کارهای
مختلفی انجام
گرفته است .
ξ در
این 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
بزرگتر بود
به مرحله دو
برو و در غیر
اینصورت
الگوریتم
خاتمه می یابد
.
کلاسترینگ
مفهومی از آن
جهت برای ما
مهم است که
میتوانیم
نمونه هائی را
که دسته بندی
نشده اند در
یک طبقه
معنائی مشخص
قرار دهیم و
در یک سلسله
مراتب
خصوصیات
عمومی طبقه
بالاتر را به
طبقات پائین
تر منتقل کنیم
(ارث بری) . در
حقیقت این
شبیه همان
کاری است که
دانشمندان
(بهتر است
بگوئیم بیولوژیست
ها) سعی کرده
اند در طی
قرنها طبقه ای
چون مهره
داران و
زیرگروه آن
پستانداران و
پرندگان و ... را
معرفی کنند .
حال اگر گفته
شود که اسب یک
پستاندار
است، ما به سرعت
متوجه خواهیم
شد که آیا
چنین حیوانی
تخم میگذارد و
یا اینکه پرواز
میکند یا خیر؟!...
در
تکنیکهای
آماری قدیمی
هم کاری مشابه
انجام میشود .
مثلا شکل زیر
را در نظر
بگیرید که نمونه
ها را با دو
ویژگی عددی 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) : (at1≠c) & (at2≠5) & (at3≠Small)
star (e5) : (at1≠a) & (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 هم بهبودی
حاصل نمیکند .
پس میتوان
نتیجه گرفت که
راه حل فوق
بهترین
کلاسترینگ
معنائی است که
میتوان بر روی
داده های
آموزشی مذکور
بوجود آورد .
[1] Alpaydin, E., Introduction to Machine
Learning, MIT Press 2004
[2] Michalski, R.S, Bratko,
[3] JAIN, A. K. AND DUBES, R. C. 1988. Algorithms for Clustering Data. Prentice-Hall advanced,
[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.
[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,
[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,
[18] BOLEY, D.L. 1998. Principal
direction divisive partitioning. Data Mining and Knowledge Discovery