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

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

۱. مقدمه

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

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

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

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

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

2. 1- Finding Similar Documents

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

3. 2-Organizing Large Document Collections

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

4. 3-Duplicate Content Detection

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

5. 4-Recommendation System

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

6. 5-Search Optimization

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

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

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

8. 1- Term Filtering

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

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

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

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

9. 2-Stemming

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

10. 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 را میدهد.

12. 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 رفته و الگوریتم تکرار می‌شود .

۱۳. خوشه بندی آیات قرآن

برای خوشه بندی آیات قرآن از تعدادی از کتابخانه های زبان پایتون که به همین منظور هستند استفاده کردم مثل :sicitik_learn و hazmو scipyو nump و . . .
برای خوشه بندی متون فارسی زبان پایتون لایبرری scikit_learn را دارد که از چند طریق مختلف می توان (با چند الگوریتم مختلف) متون را خوشه بندی کرد:
در جدول زیر خلاصه ای از الگوریتم های خوشه بندی با استفاده از کتابخانه ی scikit_learn پایتون میبینید:

14. kmeans

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

15. Affinity propagation

خوشه ها را با فرستادن پیام هایی بین جفت نمونه ها تا زمانی که همگرا شوند ایجاد می کند.
در اینجا مهم ترین پارامترها یکی میزان عملکرد است که تعداد نمونه هایی که استفاده می شوند را کنترل می کند و دوم فاکتور تعدیل است.
اصلی ترین اشکال این روش پیچیدگی آن است که o(n^2*t) می باشد.

16. MeanShift

داده ها را با تخمین حبابی در مناطق متراکم ماتریس نقاط خوشه بندی می کند.
در مقیاس گذاری برای هزاران نمونه دچار مشکل می شود.

17. Spectal Clustering

یک ماتریس وابستگی کم بعد از بین نمونه ها درست می کند و بسیار موثر است اگر ماتریس وابستگی بسیار نادر باشد و ماژول pyamg نصب شده باشد. برای خوشه بندی در تعداد کم خوب است ولی برای تعداد داده های زیاد پیشنهاد نمی شود

18. Hierarichical

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

19. Dbscan

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

لینککد من در گیت هاب.
لینککد اصلی در گیت هاب.

۲۰. آزمایش‌ها

ارزیابی عملکرد الگوریتم ها ی خوشه بندی به سادگی شمارش تعداد خطاها یا prescision و recall الگوریتم خوشه بندی نیست.

در خود کتابخانه ی scikitlearn ماژول ارزیابی الگوریتم ها ی خوشه بندی وجود دارد به صورت زیر:

Sklearn.metrics.adjusted_rand_score
در بخش اعتبار خوشه بندی باید اولاَمیزان تراکم یعنی داده های موجود در یک خوشه باید تا حد زیادی به یکدیگر نزدیک باشند که معیار رایج برای تعیین میزان تراکم داده ها واریانس داده هاست و دوماَ جدایی یعنی خوشه های متفاوت باید به اندازه ی کافی از همدیگر متمایز باشند.

۲۱. یک روش اعتبار سنجی

شاخص دون که از رابطه ی :

D=\min_{i=1,\dots,n_c} \lbrace \min_{j=i+1,\dots,n_c} (\dfrac{ d(c_i,c_j) } {\max_{k=I,\dots , n_c} (diam(c_k)) )} \rbrace

به دست می آید
که در این رابطه داریم :

و

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

که در این رابطه ها :

۲۱.۱. جدول

n_c	تعداد خوشه ها
d	تعداد ابعاد
(d(x,y	فاصله بین دو داده
c_i	خوشه ی i ام

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

۲۳. مراجع

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

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

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

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

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

• [6] http://www.civilica.com .

• [7]Ebbesson, Magnus, and Christopher Issal. "Document Clustering." (2010).

• [8]Berry, Michael W., ed. Survey of Text Mining I: Clustering, Classification, and Retrieval. Vol. 1. Springer, 2004.

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

• [10]https://docs.python.org/2/library/csv.html#examples

• [11]https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/cluster/spectral.py

• [12]https://docs.python.org/2/library/json.html

۲۴. پیوندهای مفید

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

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

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

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

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

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

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