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

خوشه‌بندی به فرآیند تبدیل حجم عظیمی از داده‌ها به گروه‌های داده‌ای مشابه گفته می‌شود. به همین صورت خوشه‌بندی متون عبارت است از تبدیل حجم عظیمی از اسناد متنی به گروه‌هایی از متن‌های مشابه؛ که به هر کدام از این گروه‌ها یک خوشه گفته می‌شود. پس مسئله خوشه‌بندی اسناد متنی را می‌توان به صورت ساده‌تر، مسئله پیدا کردن اسناد مشابه و قرار دادن آن‌ها کنار هم تعریف کرد. برای خوشه‌بندی اسناد متنی روش‌های متنوعی وجود دارد که در این پژوهش انتظار می‌رود روش‌های متداول برای خوشه‌بندی معرفی شده و یکی از آن‌ها برای خوشه‌بندی متون فارسی پیاده‌سازی شود. # مقدمه خوشه بندی یکی از مهمترین مسائل در زمینه ی یادگیری بدون ناظر می باشد.موضوع مورد بحث در خوشه بندی،یافتن یک الگو یا ساختار درون یک مجموعه داده است و همچنین خوشه به مجموعه داده هایی گفته می شود که به یکدیگر شباهت داشته باشند.در خوشه بندی سعی می شود تا شباهت بین داده های درون هر خوشه حد اکثر و شباهت بین داده های درون خوشه های متفاوت حداقل گردد.خوشه بندی از لحاظ تودرتویی( 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بهبود نتایج: در این قسمت از پروژه قصد داریم تا الگوریتمی به نام 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-قطعی .... # آزمایش‌ها [پروژه ی (بهبود نتایج) من در گیت هاب ](https://github.com/Javad-Forough/K-means) #نمونه هایی از ورودی و خروجی برنامه: ![ورودی-خروجی](http://pdf2jpg.net/files/09c72ae8378d9588fe6599bb20d5f05e3b498d15/IO-page-001.jpg) # کارهای آینده # مراجع ******************************************************************************************************** مقالات مورد بررسی قرار گرفته: (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)