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

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

۱. مقدمه

خوشه بندی یکی از مهمترین مسائل در زمینه ی یادگیری بدون ناظر می باشد.موضوع مورد بحث در خوشه بندی،یافتن یک الگو یا ساختار درون یک مجموعه داده است و همچنین خوشه به مجموعه داده هایی گفته می شود که به یکدیگر شباهت داشته باشند.در خوشه بندی سعی می شود تا شباهت بین داده های درون هر خوشه حد اکثر و شباهت بین داده های درون خوشه های متفاوت حداقل گردد.خوشه بندی از لحاظ تودرتویی( 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 می باشد.
خوشه هایی که میانگین فواصل بین داده های آنها مینیمم باشد دارای شباهت بیشتری بود و در یک خوشه قرار می گیرند.

۳. آزمایش‌ها

https://github.com/Javad-Forough/average_linkage

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

۵. مراجع

مقالات مورد بررسی قرار گرفته:
(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)

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

• 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.

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

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

• پردازش زبان فارسی در پایتون

• پیکره فارسی همشهری

• خوشه‌بندی با scikit-learn

• یک نمونه کد از K-Means

• راهنمایی برای استخراج ویژگی از متن زبان طبیعی