مقدمه ای از خوشه بندی

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

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

معمولا در خوشه بندی مستندات متنی، با ابعاد بسیار بالای فضای داده مواجه هستیم که انجام خوشه بندی به این شکل، مشکل به نظر می رسد.

اساسا، سیستمهای خوشه بندی همراه با نظارت یا بدون نظارت هستند..

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

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

البته کیفیت نتایج خوشه بندی:

به روش اندارگیری شباهت و توانایی و قدرت الگوریتم در کشف الگوهای مخفی میان داده ها بستگی دارد .

خوشه بندی در زمینه های بسیاری کاربرد دارد از جمله:

1) در زمینه مهندسی ( یادگیری ماشین، هوش مصنوعی، تشخیص الگو، مهندسی مکانیک و الکترونیک )

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

3) علوم پزشکی ( ژنتیک، زیست شناسی ، میکروب شناسی ، فسیل شناسی ، روان شناسی ، بالین ، آسیب شناسی )

4) علوم زمین شناسی ( جغرافیا، زمین شناسی، نقشه برداری از زمین )

5) علوم اجتماعی ( جامعه شناسی، روان شناسی، تاریخ، آموزش وپرورش)

6) اقتصاد (بازاریابی، تجارت )

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

2) رویه خوشه بندی

معمولا خوشه بندی الگوها شامل مراحل زیر می باشد :

۱) نمایش الگو (می تواند شامل استخراج و یا انتخاب معیار و مشخصه نیز باشد)

۲) تعریفی از اندازگیری نزدیکی (شباهت) الگوها برای دامنه داده ها

۳) خوشه بندی یا گروه بندی

۴) انتزاع داده (در صورت نیاز)

۵) ارزیابی یا اعتبارسنجی خروجی (در صورت نیاز)

1. انتخاب مشخصه ها،فر ایند تعیین موثرترین زیرمجموعه از مشخصه ها ی اصلی، بر ای استفاده در خوشه بندی می باشد .

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

هر کدام از این تکنیکها (یا هر دو آنها ) می تواند بر ای بدست آوردن یک مجموعه مناسب، در خوشه بندی استفاده شوند.

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

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

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

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

3) معیارهای تست خروجی الگوریتم

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

در کل سه دسته معیار تست وجود دارد :

1) شاخص ها ی خار جی 2)شاخص ها ی داخلی 3)شاخص ها ی نسبی

این دسته بند ی سه نوع ساختار اصلی از الگوریتمهای خوشه بندی را بوجود می آورد :

1)خوشه بندی افرازی 2) خوشه بندی سلسله مراتبی 3)خوشه بندی های خاص

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

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

2) شاخص ها ی داخلی: تست داخلی به اطلاعات خار جی (دانش پیشین) وابستگی ندارند . آنها مستقیما ساختار خوشه بندی را از روی داده ها ی اصلی آزما یش می کنند .

3) شاخص ها ی نسبی : معیارهای نسبی برروی مقایسه بین تفاوتها ی ساختارهای خوشه بند ی تاکید می کنند، بطوری که مرجعی بر ای تصمیم گیری اینکه، کدام مشخصه از ا شیا می تواند شایستگی خوشه ها را بهتر از همه آشکار نماید.

4) چالشهای الگوریتمهای خوشه بندی

به طور کلی الگوریتم های خوشه بندی داده ها با چالشهای زیر روبرو هستند :

1) مقیاس پذیری : چگونه می توان الگوریتمهای خوشه بندی را تنظیم نمود تا برای پایگاه داده های با حجم بالا کارایی مناسب داشته باشند.

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

3) حداقل نیازمندی به دانش دامنه که با پارامترهای ورودی مشخص می شود : بسیاری از انواع الگوریتمهای خوشه بندی نیاز دارند تا کاربر پارامترهای ورودی خاصی را به عنوان ورودی تحلیل خوشه ها مشخص کند. (مثل تعداد خوشه های مورد نظر ) مشخص نمودن بسیاری از این پارامترها مسئله دشواری خواهد بود.

4) کشف خوشه ها با اشکال مختلف : اغلب الگوریتم های خوشه بند ی بر پایه فاصله اقلیدسی یا مانهاتان کار می کنند . پس خوشه های کروی شکل با اندازه یا چگالی مشابه را پیدا می کنند . پس مهم است که الگوریتم خوشه بندی بتواند خوشه هایی متناسب با توزیع داده ها بیابد.

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

6) عدم حساسیت به ترتیب داده های ورودی : نباید الگوریتم خوشه بند ی با ترتیب متفاوت ورود داده ها، خروجی های مختلفی ایجاد نماید.

7) ابعاد بالای داده ورودی : یک پایگاه داده یا انبار داده ممکن است شامل صدها صفت یا بعد باشد . برای مطلوب است که الگوریتم مستقل از تعداد ابعاد، کارایی مناسبی داشته باشد.

8) خوشه بندی همراه با اعمال محدودیتهای کاربر : گاهی نیاز داریم تا برخی از محدودیتها مثل تعداد خوشه ها، را برای الگوریتم تعریف نماییم.

9) قابلیت تفسیر و استفاده : نتایج خوشه بندی باید برای کاربر قابل تفسیر، جامع و مفید باشد.

5) خوشه بندی متن

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

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

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

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

در این مدل سعی می شود تا یک مجموعه لغت مرجع از لغات نگهداری شود. سپس برای هر متن، برداری با تعداد مولفه به اندازه تعداد کلمات این مجموعه در نظر می گیریم. هر مولفه می تواند تعداد تکرار کلمه متناظر با کلمه درون مجموعه لغت را در متن را نشان دهد یا اینکه هر مولفه به شکل دودویی وجود یا عدم وجود کلمه متناظر در مجموعه لغت درون متن موجود را مشخص نماید.

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

6) الگوریتم خوشه بندی Bi-Section-K Means

الگوریتم خوشه بندی Bi-Section-K Means بر اساس الگوریتم K Means است و به صورت تجمعی و با سرعت بالا اجرا می شود. این الگوریتم می تواند برای حجم بالای داده های ورودی که ابعاد زیادی دارند به سرعت اجرا گردد. پس الگوریتم Bi-Section-K Means برای خوشه بندی مستندات متنی بسیار مناسب است. این الگوریتم K بار (به اندازه تعداد خوشه ها) تکرار می شود و در هر بار تکرار یک خوشه بدست می آید. در ابتدا تمام مستندات متنی در یک خوشه که بیشترین تعداد متن را دارد انتخاب می شود. سپس دو نقطه تصادفی در آن خوشه در نظر گرفته می شود و مشابه الگوریتم K Means عملیات خوشه بندی انجام می شود. به این ترتیب خوشه انتخاب شده به دو خوشه شکسته می شود. این عملیات با K-1 بار تکرار درون حلقه، K خوشه بدست می آورد.

شبه کد الگوریتم Bi-Section-K Means به صورت زیر می باشد:

Input: The Number Of K Desired Clusters.

Output: A partitioning of the set D of documents.

(1)Let P :={ D}.

(2)For I :=1 to K-1 do

Select p ∈ P with maximal cardinality.

Choose randomly two data points in p as starting centroids tp1 and tp2.

Assign each point of p to the closest centroid , splitting thus

p in two clusters p1 and p2. 

(Re-)Calculate the cluster centroids tp1 and tp2 of p1 and p2.

Repeat the last two steps until the centroids do not change anymore.

Let P:=(P\{p}U{p1,p2}.

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

دقت مشخص میکند که چه میزان از مستندات بدست آمده، درست انتخاب شده و مناسب هستند.

یادآوری مشخص می نماید که چه میزانی از مستندات مناسب انتخاب شده اند.

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

هدف رسیدن به رابطه ای است که بتواند تعادل مناسبی میان این دو متغیر برقرار سازد.

7) خوشه بندی مستندات متنی با کمک از آنتولوژی

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

تعریف هسته آنتولوژی : یک هسته آنتولوژی یک سیستم نشان گذاری است که با نماد

O := (L,F,C,H,ROOT) مشخص می شود و شامل بخش های زیر است:

1) یک لغت نامه، L که شامل مجموعه لغات است.

2) یک مجموعه از مفاهیم ، C

3) یک تابع ارجاع ( RefC(t) ) تابع ارجاع یک یا چند کلمه از لغت نامه ({Li Ì L}) را به چند مفهوم معادل کلمات ورودی، نگاشت می دهد .(F: 2L → 2C) در حالت کلی یک کلمه به چندین مفهوم ارجاع می شود و به طور مشابه یک مفهوم هم می تواند به چندین کلمه ارجاع داشته باشد. تابع معکوس F به صورت F- 1 تعریف می شود.

4) سلسله مراتب H ، مفاهیم در آنتولوژی با یک رابطه جهتدار، بدون سیکل، تعدی و انعکاسی طبقه بندی می شوند. H(HOTEL, ACCOMODATION) یعنی مفهوم HOTEL زیرمفهومی از ACCOMODATION است.

5) یک مفهوم سطح بالا به نام ریشه (Root ÎL ) بطوری که برای هر مفهوم (C ÎL )داشته باشیم: H(C,ROOT).

8) کامپایل کردن دانش پس زمینه درون متن

دانش پس زمینه را می توان از طریق یک آنتولوژی مرجع مثل WordNet استخراج نمود. دو مشکل اساسی برای مجتمع سازی دانش و کامپایل دانش پس زمینه درون پروسه خوشه بندی متن وجود دارد :

۱- نیاز به پیش پردازش مستندات متنی، برای غنی کردن آنها بوسیله دانش پس زمینه درون هسته آنتولوژی نیاز تحمل سربار پیش پردازش مستندات، داریم. برخی از عملیات متداول پیش پردازش در بخش قبل توضیح داده شد.

۲- می خواهیم تعداد زیادی از مستندات را درون تعداد نسبتا کمی خوشه معنادار تقسیم بندی نماییم، که احتمالا نیاز به تحلیل خوشه بندی مفهومی دارد. خوشه بندی های مفهومی شناخته شده برای اینکه مستقیمًا (بدون واسطه) بخواهند صدها متن را خوشه بندی نمایند، بسیار کند هستند. این روشها اجازه می دهند تا توصیفات مشخصه های مشترک متن ها را خلاصه سازی نماییم و خوشه های مختلف را از هم جدا کنیم. با استفاده از دانش پس زمینه حتی می توان انتزاع ها را نیز پیدا نمود مثلا corn یا beef به جای food .

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

برای مثال الگوریتم های خوشه بندی نمی توانند رابطه ای بین دو کلمه beef و pork در بردار کلمه دو متن پیدا نمایند. حال اگر از مفهوم سطح بالای meat به جای pork در بردار کلمه دو متن استفاده می کردیم، رابطه معنایی دو متن به راحتی قابل تشخیص بود.

9) استراتژی های استفاده از کلمه در مقابل مفهوم

استراتژی های متفاوتی از قبیل استراتژی افزودن ، استراتژی جایگزین نمودن و استراتژی محض برای افزودن و یا جایگزینی مفاهیم به جای کلمات وجود دارد.

در استراتژی افزودن تمام مفاهیم معادل هر کلمه در آنتولوژی به را نیز بردار کلمات آن متن افزوده می شود. (مثلا همراه با کلمه beef مفهوم meat در بردار کلمات تکرار می نماید.)

در استراتژی جایگزین نمودن عبارتهایی که مفهوم مرتبط با آنها وجود دارد را با مفاهیم معادلشان جایگزین می نماید. (مثلا به جای beef مفهوم Meat را می آورد.)

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

10) نتیجه گیری

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