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

برای خوشه‌بندی اسناد متنی روش‌های متنوعی وجود دارد که در این پژوهش انتظار می‌رود روش‌های متداول برای خوشه‌بندی معرفی شده و یکی از آن‌ها برای خوشه‌بندی متون فارسی پیاده‌سازی شود.

۱. مقدمه

خوشه بندی یکی از مهمترین مسائل در زمینه ی یادگیری بدون ناظر می باشد.موضوع مورد بحث در خوشه بندی،یافتن یک الگو یا ساختار درون یک مجموعه داده است و همچنین خوشه به مجموعه داده هایی گفته می شود که به یکدیگر شباهت داشته باشند.در خوشه بندی سعی می شود تا شباهت بین داده های درون هر خوشه حد اکثر و شباهت بین داده های درون خوشه های متفاوت حداقل گردد.خوشه بندی از لحاظ تودرتویی( nesting) به دو دسته تقسیم میگردد:1-خوشه بندی سلسله مراتبی( Hierarchical)

2 -خوشه بندی تفکیکی (partitional)

1-خوشه بندی سلسله مراتبی( Hierarchical)
در روش خوشه بندی سلسله مراتبی، به خوشه‌های نهایی بر اساس میزان عمومیت آنها ساختاری سلسله‌ مراتبی، معمولا به صورت درختی نسبت داده می‌شود. به ا ین درخت سلسله مراتبی دندوگرام (dendogram) می‌گویند.روشهای خوشه‌بندی بر اساس ساختار سلسله مراتبی تولیدی توسط آنها معمولا به دو دستة زیر تقسیم می‌شوند:

1.بالا به پایین (Top-Down) یا تقسیم کننده (Divisive): در این روش ابتدا تمام داده‌ها به عنوان یک خوشه در نظر گرفته می‌شوند و سپس در طی یک فرایند تکراری در هر مرحله داده‌هایی شباهت کمتری به هم دارند به خوشه‌های مجزایی شکسته می‌شوند و این روال تا رسیدن به خوشه‌هایی که دارای یک عضو هستند ادامه پیدا می‌کند.

2.پایین به بالا (Bottom-Up) یا متراکم شونده (Agglomerative): در این روش ابتدا هر داده‌ها به عنوان خوشه‌ای مجزا در نظر گرفته می‌شود و در طی فرایندی تکراری در هر مرحله خوشه‌هایی که شباهت بیشتری دارند، با یکدیگر ترکیب می‌شوند تا در نهایت یک خوشه و یا تعداد مشخصی خوشه حاصل شود. از انواع الگوریتمهای خوشه‌بندی سلسله مراتبی متراکم شونده رایج می‌توان از الگوریتمهای Single-Link، Average-Link و Complete-Link نام برد. تفاوت اصلی در بین تمام این روشها به نحوة محاسبة شباهت بین خوشه‌ها مربوط می‌شود.

۲. کارهای مرتبط

در این پژوهش قصد داریم تا در ابتدا خوشه بندی سلسله مراتبی پایین به بالا را با استفاده از الگوریتم Average-Link پیاده سازی کنیم

خوشه بندی با استفاده از الگوریتم Average-link:

در الگوریتم single-link ،شباهت میان دو خوشه برابر است بامینیمم فاصله ی میان داده های موجود در دو خوشه و همچنین در الگوریتم complete-link،شباهت میان دو خوشه ،ماکزیمم فاصله ی میان داده های موجود در دو خوشه می باشد.از آنجا که این دو روش به شدت به نویز حساس می باشند، روش سومی به نام average-link پیشنهاد گردید.شباهت بین دوخوشه در این روش برابر است با میانگین فواصل بین داده های دو خوشه.به عبارت دیگر فاصله ی میان دوخوشه ی aوb برابر است با : D(a,b)= ∑ (x,y)/N(a)*N(b)
که در آن x،عضوی از مجموعه داده های موجود در aو همچنینy،عضوی از مجموعه داده های موجود در b می باشد.
خوشه هایی که میانگین فواصل بین داده های آنها مینیمم باشد دارای شباهت بیشتری بود و در یک خوشه قرار می گیرند.

۳. بهبود نتایج:

در این قسمت از پروژه قصد داریم تا الگوریتمی به نام k-means را شرح داده و پیاده سازی کنیم .
الگوریتم kmeans:
این روش علی رغم سادگی آن یک روش پایه برای بسیاری از روشهای خوشه بندی دیگر(مانند خوشه بندی فازی)محسوب می شود.این روش روشی انحصاری و مسطح(flat)محسوب می شود.برای این الگوریتم شکلهای مختلفی بیان شده است،ولی همه آنها دارای روالی تکراری هستند که برای تعدادی ثابت از خوشه ها سعی در تخمین موارد زیر را دارند:
1-به دست آوردن نقاطی به عنوان مراکز خوشه ها.این نقاط در واقع همان میانگین نقاط متعلق به هر خوشه هستند.
2-نسبت دادن هر نمونه داده به یک خوشه که آن داده کمترین فاصله تا مرکز آن خوشه را دارا باشد.
در نوع ساده ای از این روش ابتدا به تعداد خوشه های مورد نیاز نقاطی ب صورت تصادفی انتخاب می شود. سپس در داده ها با توجه با میزان نزدیکی(شباهت)به یکی از خوشه ها نسبت داده می شوند و بدین ترتیب خوشه های جدیدی حاصل می شود.با تکرار همین روال می توان در هر تکرار با میانگین گیری از داده ها مراکز جدیدی برای آنها محاسبه کرد و مجدادا داده ها را به خوشه های جدید نسبت داد. این روند تازمانی ادامه پیدا میکند که دیگر تغییری در داده ها حاصل نشود.همچنین می توان تعداد تکرار روال را خودمان به صورت یک پارامتر به الگوریتم بدهیم.

الگوریتم زیر الگوریتم پایه برای این روش محسوب می شود:

1-در ابتدا k نقطه به صورت تصادفی به عنوان مراکز خوشه ها انتخاب می شوند.
2-هر نمونه داده به خوشه ای که مرکز آن خوشه کمترین فاصله تا آن داده را داراست ،نسبت داده می شود
3-بعد از تعلق تمام داده ها به یکی از خوشه ها ،برای هر خوشه یک نقطه جدید به عنوان مرکز محاسبه می شود(میانگین نقاط متعلق به هر خوشه)
4-مراحل 2و3 را به اندازه ی تعداد تکرار های خواسته شده از الگوریتم تکرار می کنیم.

مثالی از الگوریتم kmeans:

مثال

مشکلات روش خوشه‌بندی K-Means

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

مقایسه ی برخی ویژگی های الگوریتم kmeans و الگوریتم های سلسله مراتبی:
kmeans
1-مقدار حافظه ی مورد استفاده ی کم
2-زمان اجرا :(o (n
3-نمایش خروجی توسط لیست
4-غیر قطعی
....

سلسله مراتبی
1-مقدار حافظه ی مورد استفاده ی زیاد(ذخیره ی ماتریس n*n)
2-زمان اجرا : (3^ o ( n
3-نمایش خروجی توسط نمودار دندروگرام
4-قطعی
....

۴. آزمایش‌ها

پروژه ی (بهبود نتایج) من در گیت هاب

۵. نمونه هایی از ورودی و خروجی برنامه:

ورودی-خروجی

۶. کارهای آینده

۷. مراجع


مقالات مورد بررسی قرار گرفته:
(Data Clustering: A Review-- by A.K. JAIN ,M.N. MURTY and P.J. FLYNN)

(A Comparison of Document Clustering-- by Michael Steinbach,George Karypis and Vipin Kumar)

(An iterative improvement procedure for hierarchical clustering by Andrew Rabinovich)

(Knowledge Based Systems for Bioinformatics Lecture 1 2010 Professor Jan Komorowski)

(An Efficient k-Means Clustering Algorithm Analysis and Implementation by Tapas Kanungo, Senior Member, IEEE, David M. Mount, Member, IEEE,Nathan S. Netanyahu, Member, IEEE, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu, Senior Member, IEEE)

(م.ایمانی، خوشه‌بندی متون فارسی، پایان‌نامه کارشناسی، داشگاه علم و صنعت ایران، ۱۳۹۱)



۸. پیوندهای مفید

تایید شده

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

تایید شده

سلام :)
در قسمت خوشه بندی سلسله مراتبی( Hierarchical) متاسفانه در هنگام نوشتار متن دقت نکرده اید
با اینکه readme کوتاهی داشتید ولی به نکته خوبی اشاره کرده اید اگر کتابخانه های مورد استفاده خودتون را لینک در گیت میگذاشتید بهتر بود
مراجع که استفاده کرده اید شماره ندارند و به همین دلیل اگر خواننده نگاه گذرایی داشته باشد متوجه ارتباط انها با قسمت های مختلف گزارش شما نمیشود
در قسمت کارهای مرتبط نوشته های تو در تویی دارید و اگر جدا جدا به توضیح این روش ها میپرداختید بهتر بود
و از طرفی راه های مختلف پیاده سازی قسمت مهمی از پروژه شماست که باید بیشتر روی ان کار کنید
امیدوارم در فاز نهایی تکمیل کنید
در قسمت ازمایش ها باید انواع کارهایی که انجام داده اید را ذکر میکردید و نتایج بیشتری را مقایسه میکردید
موفق باشید:)

تایید شده

با عرض سلام و خسته نباشید خدمت شما دوست عزیز
در مورد پروژتون چندتا نکته به ذهنم می رسه:

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

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

  3. گفته بودید که قصد دارید الگوریتم Average-link رو پیاده سازی کنید. اما این کار رو نکردید. پس عنوان "بهبود نتایج" هم یه کم نامربوط به نظر می رسه.

محسن ایمانی

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

کار انجام شده توسط شما با موضوع خوشه‌بندی مناسب است ولی برای پروژه ای با نام خوشه‌بندی متون فارسی جامع نبوده و دچار ضعف است.