خوشهبندی به فرآیند تبدیل حجم عظیمی از دادهها به گروههای دادهای مشابه گفته میشود. به همین صورت خوشهبندی متون عبارت است از تبدیل حجم عظیمی از اسناد متنی به گروههایی از متنهای مشابه؛ که به هر کدام از این گروهها یک خوشه گفته میشود. پس مسئله خوشهبندی اسناد متنی را میتوان به صورت سادهتر، مسئله پیدا کردن اسناد مشابه و قرار دادن آنها کنار هم تعریف کرد.
برای خوشهبندی اسناد متنی روشهای متنوعی وجود دارد که در این پژوهش انتظار میرود روشهای متداول برای خوشهبندی معرفی شده و یکی از آنها برای خوشهبندی متون فارسی پیادهسازی شود.
خوشه بندی یکی از مهمترین مسائل در زمینه ی یادگیری بدون ناظر می باشد.موضوع مورد بحث در خوشه بندی،یافتن یک الگو یا ساختار درون یک مجموعه داده است و همچنین خوشه به مجموعه داده هایی گفته می شود که به یکدیگر شباهت داشته باشند.در خوشه بندی سعی می شود تا شباهت بین داده های درون هر خوشه حد اکثر و شباهت بین داده های درون خوشه های متفاوت حداقل گردد.خوشه بندی از لحاظ تودرتویی( nesting) به دو دسته تقسیم میگردد:1-خوشه بندی سلسله مراتبی( Hierarchical)
2 -خوشه بندی تفکیکی (partitional)
1.بالا به پایین (Top-Down) یا تقسیم کننده (Divisive): در این روش ابتدا تمام دادهها به عنوان یک خوشه در نظر گرفته میشوند و سپس در طی یک فرایند تکراری در هر مرحله دادههایی شباهت کمتری به هم دارند به خوشههای مجزایی شکسته میشوند و این روال تا رسیدن به خوشههایی که دارای یک عضو هستند ادامه پیدا میکند.
2.پایین به بالا (Bottom-Up) یا متراکم شونده (Agglomerative): در این روش ابتدا هر دادهها به عنوان خوشهای مجزا در نظر گرفته میشود و در طی فرایندی تکراری در هر مرحله خوشههایی که شباهت بیشتری دارند، با یکدیگر ترکیب میشوند تا در نهایت یک خوشه و یا تعداد مشخصی خوشه حاصل شود. از انواع الگوریتمهای خوشهبندی سلسله مراتبی متراکم شونده رایج میتوان از الگوریتمهای Single-Link، Average-Link و Complete-Link نام برد. تفاوت اصلی در بین تمام این روشها به نحوة محاسبة شباهت بین خوشهها مربوط میشود.
در این پژوهش قصد داریم تا در ابتدا خوشه بندی سلسله مراتبی پایین به بالا را با استفاده از الگوریتم Average-Link پیاده سازی کنیم
خوشه بندی با استفاده از الگوریتم Average-link:
الگوریتم زیر الگوریتم پایه برای این روش محسوب می شود:
مثالی از الگوریتم kmeans:
مشکلات روش خوشهبندی K-Means
در این قسمت از پروژه قصد داریم تا راهکار هایی(برای مثال راهکار هایی در زمینه ی پیش پردازش متن و کاهش ابعاد) را برای بهبود در سرعت و دقت نتایج به دست آمده از بخش قبل، ارائه داده و بخشی از این راهکار ها را پیاده سازی کنیم .همچنین در پیاده سازی ای که در این بخش ارائه می کنیم سعی شده بخش زیادی از خطاها(باگ های)پیاده سازی بخش (برای مثال خطاهایی که در بخش iteration و تابع cosine داشتیم) قبل برطرف شود.
(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)
(م.ایمانی، خوشهبندی متون فارسی، پایاننامه کارشناسی، داشگاه علم و صنعت ایران، ۱۳۹۱)
Ebbesson, Magnus, and Christopher Issal. "Document Clustering." (2010).
Berry, Michael W., ed. Survey of Text Mining I: Clustering, Classification, and Retrieval. Vol. 1. Springer, 2004.
م.ایمانی، خوشهبندی متون فارسی، پایاننامه کارشناسی، داشگاه علم و صنعت ایران، ۱۳۹۱
http://www.boute.ir/