خوشه‌بندی متون فارسی

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

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

# مقدمه
خوشه بندی یکی از مهمترین مسائل در زمینه ی یادگیری بدون ناظر می باشد.موضوع مورد بحث در خوشه بندی،یافتن یک الگو یا ساختار درون یک مجموعه داده است و همچنین خوشه به مجموعه داده هایی گفته می شود که به یکدیگر شباهت داشته باشند.در خوشه بندی سعی می شود تا شباهت بین داده های درون هر خوشه حد اکثر و شباهت بین داده های درون خوشه های متفاوت حداقل گردد.خوشه بندی از لحاظ تودرتویی( 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:
![مثال](http://compprag.christopherpotts.net/figures/swda/kmeans-wikipedia-ex.png)

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

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

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

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

در این قسمت از پروژه قصد داریم تا راهکار هایی(برای مثال راهکار هایی در زمینه ی پیش پردازش متن و کاهش ابعاد) را برای بهبود در سرعت و دقت نتایج به دست آمده از بخش قبل، ارائه داده و بخشی از این راهکار ها را پیاده سازی کنیم .همچنین در پیاده سازی ای که در این بخش ارائه می کنیم سعی شده بخش زیادی از خطاها(باگ های)پیاده سازی بخش (برای مثال خطاهایی که در بخش iteration و تابع cosine داشتیم) قبل  برطرف شود.

• پیش پردازش متن و کاهش ابعاد: (  [منبع](http://bayanbox.ir/id/8155819707974834975?download) )

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

• پیش پردازش

.فیلتر کردن:

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

>>>برای پیاده سازی این قسمت،لیستی از کلمات خاص که در مدل فضای بردار نمی تواند اطلاعات مفیدی در اختیار ما قرار دهد (برای مثال حروف اضافه و حروف ربط و برخی صفت هاو... در زبان فارسی)را در لیستی با نام literals ذخیره کرده و آنها را از سند های ورودی حذف می کنیم.

.نرمال سازی و اصلاح نویسه ها:

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

>>>برای پیاده سازی این بخش تابعی به نام doc_normalizer نوشته شده
 که در آن از کلاس word_tokenize موجود در کتابخانه ی  [هضم](http://www.sobhe.ir/hazm)  (به انگلیسی hazm ) استفاده شده. 

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

.ریشه یابی:
پروسه ریشه یابی کلمات را به صورت عبارت پایه آن در می آورد. برای مثال، کلمه "روش هایم"، "روشی"،
Porter "روشمند" هر سه از ریشه روش هستند. روش های ریشه یابی اغلب مبتنی بر زبان هستن. الگوریتم
یک الگوریتم ریشه یاب استاندارد برای زبان انگلیسی است.

>>>برای پیاده سازی این قسمت تابعی به نام doc_stemmer نوشته شده که در آن 
از کلاس stemmer موجود در کتابخانه ی  [هضم](http://www.sobhe.ir/hazm)  (به انگلیسی hazm ) استفاده شده.


.حذف کلمات توقف:

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

.هرس کردن:

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

•کاهش ابعاد 

داده های با ابعاد زیاد باعث پیچیدگی محاسبات خواهند شد. در طول خوشه بندی N سند ممکن است M خصوصیت مختلف را در نظر بگیریم در حالی کهM>>N .اما مسئله اینجاست که آیا واقعا نیازی به بررسی این تعداد خصوصیت هست؟ممکن است که بررسی همه ی این خصوصیات لازم نباشد؟جواب این سوال موجب ارائه ی راهکارهایی با عنوان کاهش ابعاد می شود.

در صورتی که کاهش ابعاد در یک فرآیند با ناظر انجام پذیرد،به آن انتخاب خصوصیات گوییم.در این فرآیند ناظر خصوصیاتی که معیار های مشخصی داشته باشند انتخاب می کند.
در حالت دیگر می توانیم با استفاده از یک فرآیند بدون ناظر ویژگی ها را استخراج کنیم تا معیار بهینه سازی حاصل شود.به این فرآیند استخراج خصوصیات گفته می شود.استخراج خصوصیات طی یک تبدیل از فضای M-بعدی به یک فضای K-بعدی صورت می پذیرد که k<M .این تبدیل می تواند هم به صورت خطی و هم به صورت غیر خطی انجام شود.


# آزمایش‌ها

[پروژه ی (بهبود نتایج و تکمیل گزارش) من در گیت هاب ](https://github.com/Javad-Forough/K-means-improvement)

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

![ورودی-خروجی](http://i62.tinypic.com/122j4eh.jpg)
![ورودی-خروجی](http://i58.tinypic.com/152p9p5.jpg)
![ورودی-خروجی](http://i59.tinypic.com/ek21s1.jpg)
![ورودی-خروجی](http://i58.tinypic.com/2mpx0r9.jpg)


# کارهای آینده

•پیاده سازی موارد زیر(برخی از مواردی که در بالا اشاره شده ولی پیاده سازی نشده اند):
1-تکه تکه کردن متن
2-حذف کلمات توقف
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)

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


+ 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://bayanbox.ir/id/8155819707974834975)

# پیوندهای مفید
+ [پردازش زبان فارسی در پایتون](http://www.sobhe.ir/hazm)
+ [پیکره فارسی همشهری](http://ece.ut.ac.ir/dbrg/hamshahri/fadownload.html)
+ [خوشه‌بندی با scikit-learn](http://scikit-learn.org/stable/modules/clustering.html#clustering)
+ [یک نمونه کد از K-Means](http://scikit-learn.org/stable/auto_examples/document_clustering.html)
+ [راهنمایی برای استخراج ویژگی از متن زبان طبیعی](http://pyevolve.sourceforge.net/wordpress/?p=1589)