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

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

۱. مقدمه

خوشه بندی فرایند سازماندهی عناصر به گروه هایی است که اجزای آن شبیه به هم هستند .در یک خوشه مجموعه عناصری هستند که با هم مشابهت دارند و با اجزای دیگر خوشه ها نا همگون می باشند . هدف از خوشه بندی دست یابی سریع و مطمئن به اطلاعات مشابه و شناسایی ارتباط منطقی میان انهاست.
خوشه بندی را می توان بر اساس رابطه ها به 3 نوع تقسیم کرد.

• 1-رابطه ی هم ارز که متداول ترین رابطه بوده و مترادف های واژه را ارائه می دهد در این نوع رابطه واژه هایی مورد نظر است که همپوشانی معناداری بین آن ها وجود دارد اما از لحاظ واژگانی متفاوتند مثل درد , الم ,بیماری ,تالم و . . .

• 2-رابطه ی سلسله مراتبی در این رابطه یک واژه به عنوان رده ی اصلی انتخاب شده و زیرمجموعه ها یا نمونه های خاصی از واژه ی کلی هستند مثل رایانه , پنتیوم و . . .

• 3-رابطه غیر سلسله مراتبی که انواع دیگر روابط بین واژه ها غیر از 2 مورد قبلی از قبیل موضوع و ویژگی های مربوط را در بر میگیرد مثل کارمند -> عنوان شغل

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

1- Finding Similar Documents

زمانی که کاربر داکیومنت خوبی پیدا می کند وبه دنبال موارد مشابهی از این داکیومنت است در این حالت با استفاده از خوشه بندی به راحتی می توان به داکیومنت هایی با مفهوم مشابه دست یافت نسبت به الگوریتم های مبتنی بر جستجو که موارد ی را پیدا میکنند که فقط شباهت لغوی با داکیومنت مورد نظر دارند.

2-Organizing Large Document Collections

بازیابی داکیومنت ها(document retrieval) روی پیدا کردن داکیومنت های مربوط به یک کوئری متمرکز است ولی در مقابل داکیومنت ها ی بزرگی که طبقه بندی نشده ناتوان است.

3-Duplicate Content Detection
در بسیاری از برنامه ها نیاز زیادی به پیدا کردن تکرار در داکیومنت های بزرگ است خوشه بندی برای پیدا کردن سرقت ادبی و گروه بندی گزارش های خبری و مرتب کردن رتبه بندی نتایج جستجو استفاده می شود.

4-Recommendation System

مثلا مقاله ای را بر اساس مقاله ای که قبلا کاربر خوانده به او پیشنهاد می کند . خوشه بند یمقالات استفاده از انها را در زمان کوتاه و با کیفیت بالاتر تضمین می کند.

5-Search Optimization

خوشه بندی کمک زیادی به بهتر شدن کیفیت و بهره وری از موتور های جستجو میکند در واقع این کار را با مقایسه ی کوئری کاربر با خوشه ها (به جای مقایسه با کل داکیومنت ) انجام میدهد همچنین نتایج جستجو نیز به راحتی مرتب می شوند.

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

قبل از شروع به خوشه بندی ابتدا باید متن را مرتب کنیم که این کار در بیشتر الگوریتم های خوشه بندی انجام می شود.

1- Term Filtering

حذف کردن stop word هایکی از رایج ترین روش های term filtering می باشد که لیست این stop word ها معمولا در دسترس می باشد.

تکنیک های دیگر term filtering:

حذف کردن ترم هایی با document frequency کمتر که برای بالا بردن سرعت و کتر کردن مصرف memory در برنامه ها استفاده می شود.

حذف کردن اعدادی که نقش زیادی در خوشه بندی ندارند به جز تاریخ و کد پستی.

2-Stemming

ریشه یابی فرایند کوتاه کردن کلمات به ریشه یشان است مثل کتابدار , کتابهایش که هر 2 به یک کلمه ی کتاب تبدیل می شوند.

3_ Graph Preprocessing

در برخی از الگوریتم ها که از گراف برای خوشه بندی استفاده می شود برای بهبود کیفیت و بهره وری نیازمند پیش پردازش گراف هستند.که بعضی از روش های ساده ی graph processing شامل حذف کردن نود هایی با وزن کمتر از استانه می باشد یا حذف نودهایی که به هیچ نود دیگری مرتبط نیستند.

نمره دهیTF-IDF:

قبل از اینکه قادر به اجرای الگوریتم k-means روی مجموعه ای از داکیومنت ها باشیم باید بتوان اسناد و مدارک را به عنوان بردار های دو به دو مقایسه کرد برای این کار می توان از تکنیک نمره دهی TF-IDF استفاده کرد. Tf-idf یا ( term frequency-inverse document frequency) ترم ها را بر اساس اهمیتشان وزن دهی می کند term frequency نسبت تعداد تکرار یک کلمه در سند به تعداد کل کلمات موجود در سند است. معکوس document frequency لگاریتم نسبت تعداد داکیومنت ها در کورپوس به تعداد داکیومنت هایی است که ترم مورد نظر را داراست.

ضرب این 2 مقدار در هم مقدار TF-IDF را میدهد.

K-MEANS CLUSTRING:

برای خوشه بندی آیات قرآن باید علاوه بر ظاهر آیات ترجمه و تفسیر آیات هم در نظر گرفته شود و برای هر کدام از آن ها الگوریتم پیشنهادی را پیاده کرد در زیر به 2 الگوریتم موجود برای خوشه بندی اشاره شده .
روش k-means : این روش روشی پایه برای بسیاری از روش های دیگر محسوب می شود در نوع ساده‌ای از این روش ابتدا به تعداد خوشه‌‌های مورد نیاز نقاطی به صورت تصادفی انتخاب می‌شود. سپس در داده‌ها با توجه با میزان نزدیکی (شباهت) به یکی از این خوشه‌ها نسبت داده‌ می‌شوند و بدین ترتیب خوشه‌های جدیدی حاصل می‌شود. با تکرار همین روال می‌توان در هر تکرار با میانگین‌گیری از داده‌ها مراکز جدیدی برای آنها محاسبه کرد و مجدادأ داده‌ها را به خوشه‌های جدید نسبت داد. این روند تا زمانی ادامه پیدا می‌کند که دیگر تغییری در داده‌ها حاصل نشود .
همان‌گونه که گفته شد الگوریتم خوشه‌بندی K-Means به انتخاب اولیة خوشه‌ها بستگی دارد و این باعث می‌شود که نتایج خوشه‌بندی در تکرارهای مختلف از الگوریتم متفاوت شود. برای رفع این مشکل الگوریتم خوشه‌بندی LBG پیشنهاد می شود که قادر است به مقدار قابل قبولی بر این مشکل غلبه کند.
در این روش ابتدا الگوریتم تمام داده‌ها را به صورت یک خوشه‌ در نظر می‌گیرد و سپس برای این خوشه یک بردار مرکز محاسبه می‌کند.(اجرای الگوریتم K-Means با تعداد خوشة 1K=). سپس این بردار را به 2 بردار می‌شکند و داده‌ها را با توجه به این دو بردار خوشه‌بندی می‌کند (اجرای الگوریتم K-Means با تعداد خوشة K=2 که مراکز اولیه خوشه‌ها همان دو بردار هستند). در مرحلة بعد این دو نقطه به چهار نقطه شکسته می‌شوند و الگوریتم ادامه پیدا می‌کند تا تعداد خوشة مورد نظر تولید شوند .
الگوریتم زیر را می‌توان برای این روش خوشه‌بندی در نظر گرفت :
1-شروع: مقدار M(تعداد خوشه‌ها) با عدد 1 مقدار دهی اولیه می‌شود. سپس برای تمام داده‌ها بردار مرکز محاسبه می‌شود .
2-شکست: هر یک از M بردار مرکز به 2 بردار جدید شکسته می‌شوند تا 2Mبردار مرکز تولید شود. هر بردار جدید بایستی درون همان خوشه قرار داشته باشد و به اندازة کافی از هم دور باشند .
3-K-Means: با اجرای الگوریتم K-Means با تعداد خوشة 2M و مراکز اولیه خوشه‌های محاسبه شده در مرحلة ii خوشه‌های جدیدی با مراکز جدید تولید می‌شود .
4-شرط خاتمه: در صورتی که M برابر تعداد خوشة مورد نظر الگوریتم LBG بود الگوریتم خاتمه می‌یابد و در غیر این صورت به مرحلة ii رفته و الگوریتم تکرار می‌شود .

۳. آزمایش‌ها

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

۵. مراجع

• http://www.kdd.org/sites/default/files/issues/4-1-2002-06/estivill.pdf

• http://www.jonathanzong.com/blog/2013/02/02/k-means-clustering-with-tfidf-weights.

• pankaj jajoo, "document clustring", ,indian institue of technology kharagpur , 2008

• http://en.wikipedia.org/wiki/Tf%E2%80%93idf

• " Christos Bouras and Vassilis Tsogkas ,"W-kmeans: Clustering News Articles Using WordNet

• http://www.civilica.com .

• 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

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

• نمونه‌ای از کشف آیات مشابه با استفاده از تفسیر ابن کثیر

• پیکره قرآن تنزیل

• پیکره تفاسیر اهل سنت

لطفا برای ارزیابی، آخرین ویرایش پروژه را نگاه کنید.