خوشه‌بندی آیات قرآن(تحقیقاتی)

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

*در این پروژه شما باید آیات قرآن را با استفاده از **ظاهر آیات به همراه ترجمه و تفسیر آنها** خوشه‌بندی کنید.*
# مقدمه
داده‫کاوی، فرایند یا پروژه‪ ای نسبتاً پیچیده برای شناسایی الگوها و مدل‫های صحیح، قابل استناد و مفید در حجم وسیعی از داده است؛ به گونه‫ای که این الگو‪ها و مدل‫ها برای انسان‫ها قابل درک باشند. خوشه بندی یکی از پرکاربردترین کارها در حوزه داده کاوی است. خوشه‌بندی به فرآیند تبدیل حجم عظیمی از داده‌ها به گروه‌های داده‌ای مشابه گفته می‌شود. به همین صورت خوشه‌بندی متون عبارت است از تبدیل حجم عظیمی از اسناد متنی به گروه‌هایی از متن‌های مشابه؛ که به هر کدام از این گروه‌ها یک خوشه گفته می‌شود. [1]
برای خوشه‫بندی کاربرد هایی نظیر کاهش داده(فشرده و یکجاسازی اطلاعات) و تولید فرضیه(استنتاج و کشف فرضیه‫های پنهان) وجود دارد. این مهم، از لوازم اولیه پژوهش‫هاست. زمانی که محقق می خواهد در مورد موضوعی تحقیق کند، جمع‫آوری و دسته‫بندی متونی که جهت پژوهش خود به آن نیاز دارد، برای او ضروری است. 
استخراج اطلاعات و دانش از قرآن مجید، کتاب مرجع بیش از ۱.۶ میلیارد مسلمان در اقصی نقاط دنیا، هم برای عموم مردم و هم برای متخصصان مطالعات اسلامی بسیار سودمند است. 
**خوشه‫بندی در مقابل طبقه‫بندی** [9]
در طبقه‌بندی هر داده به یک طبقه (کلاس) از پیشین مشخص شده تخصیص می‌یابد ولی در خوشه‌بندی هیچ اطلاعی از کلاسهای موجود درون داده‌ها وجود ندارد و به عبارتی خود خوشه‌ها نیز از داده‌ها استخراج می‌شوند. در شکل زیر تفاوت بین خوشه‌بندی و طبقه‌بندی بهتر نشان داده شده است.
![در طبقه‌بندی با استفاده  یک سری اطلاعات اولیه داده‌ها به دسته‌های معلومی نسبت داده‌ می‌شوند.](https://boute.s3.amazonaws.com/264-image002.jpg)
![در خوشه‌بندی داده‌ها با توجه به الگوریتم انتخاب شده به خوشه‌هایی نسبت داده‌ می‌شوند.](https://boute.s3.amazonaws.com/264-image003.jpg)

# کارهای مرتبط 
## پیش‫پردازش و مراحل آن [9]
پیش از مراحل انتخاب ویژگی و خوشه‫بندی نیازمند پردازش‫های مقدماتی بر روی متون هستیم. هدف از این پیش‫پردازش ارائه ورودی قابل فهم و قابل تفسیر برای ماشین است. این مرحله اهمیت به‫سزایی در افزایش صحّت نتایج و کاهش مرتبه زمانی دارد. 
### حذف حرکه‫ها 
این گام مختص زبان‫هایی مانند زبان عربی هستند که حرکات نقش مهمی ایفا می‫کنند. علی رغم اینکه امروزه در عربی همانند فارسی از ذکر حرکات صرف نظر می‫شود، با توجه به اینکه حوزه عمل پژوهش حاضر آیات مبارکه قرآن است، نیاز به حذف حرکات و اعراب داریم. این گام اگرچه از ریزبینی اعجاز‫آمیز کلام وحی می‫کاهد اما پژوهش‫گر را در مراحل ابتدایی، یاری می‫رساند. 
### نشانه‫گذاری
در گام نخست، متن را به عباراتی جدا از هم تقسیم می کنیم. هر عبارت ممکن است مشتمل بر یک کلمه یا چند کلمه که یک اصطلاح را تشکیل می‫دهند باشد. نشانه‫گذاری مطلوب تأثیر شگرفی در پردازش متن دارد اگر چه ما در آزمایش پژوهش حاضر، همه عبارات را تک کلمه‫ای فرض کرده ایم. 
### حذف کلمات بی‫اثر
تعداد این کلمات در زبان انگلیسی معمولا کمتر از ۶۰۰ عدد است و لیست‫های مختلف و متغیر مربوط به آن موجود است. در مورد زبان عربی، در پیاده‫سازی‫های موجود از ۲۰۰ تا ۸۰۰ عدد متغیر است. از جمله می‫توان از کلماتی نظیر «فی، من، هو، منذ، هناک، وکانت» نام برد که طی این مرحله از پیش‫پردازش متن، حذف می‫شوند. 
### ریشه‫یابی 
در زبان انگلیسی، معمولا کلمات هم خانواده در چندین حرف انتهایی مختلف اند و هم‫خانوادگی کلمات با تطبییق حرف به حرف ممکن است. این فرایندِ بسیار کاربردی شامل حذف پیشوندها و پسوندهای کلمات، تبدیل افعال و مشتقات به مصادر اصلی خود، حذف حروف بی‫بار از متن، تبدیل جمع ها به مفردات و مؤنت‫ها به مذکّر است. یک مثال کاربردی از آن تبدیل کلمه «استغفار» به ریشه آن یعنی «غفر» و یافتن کلمات با ریشه یکسان مانند «لیستغفر»، «یستغفرون» و ... است. 
### هرس کردن
در این مرحله کلماتی که تکرار آن‫ها در سند بسیار نادر است حذف می‫کنیم. همچنین کلماتی که تکرار بسیار زیادی دارند هم حذف می‫شوند. پیش‫فرض انجام این عملیت این است که این کلمات، حتی اگر قدرت تمایز زیادی داشته باشد، کمک حال خوشه‫بندی نخواهند بود. مثلاً عبارت «فَبِأَیِّ آلَاءِ رَبِّکُمَا تُکَذِّبَانِ» در سوره مبارکه الرحمن تاثیرگذاری مطلوب بر فرایند خوشه‫بندی ندارد. 
### کاهش ابعاد
ابعاد زیاد داده‫ها پیچیدگی محاسبات را سبب می‫شود. در خوشه بندی `N` سند ممکن است `M` خصوصیت مختلف استخراج شود اما اگر `M >> N` غیرمنطقی است. در پاسخ به این مشکل نیاز به کاهش ابعاد پیدا می‫کنیم. 
این عمل یا با ناظر انجام می‫شود که به آن انتخاب خصوصیات گفته می‫شود یا بی‫ناظر که فرایند تبدیل فضای `M`-بعدی به `K`-بعدی به صورت خطی یا غیر خطی است به طوری که `K < M`.
### انتخاب خصوصیت
در این روش از ادبیات بهره می‫گیریم و کلماتی غیرمؤثر را کنار می‫گذاریم. طی این فرایند از قواعد و دیدگاه زبان‫شناسانه به بررسی اجزاء جمله مانند عبارت فعلی و عبارت اسمی می‫پردازیم و دیگر بخش ها که تنها فعل و نقش‫هایی مثل فاعل یا مفعول یا ... را نگه می‫داریم. 
مثلا از عبارت «أَفَلَمْ یَسِیرُوا فِی الْأَرْضِ فَیَنظُرُوا کَیْفَ کَانَ عَاقِبَةُ الَّذِینَ مِن قَبْلِهِمْ دَمَّرَ اللَّهُ عَلَیْهِمْ وَ لِلْکَافِرِینَ أَمْثَالُهَا» پس از هرس کردن مثل حذف «اللَّهُ» و حذف کلمات بی‫اثر مثل «کَیْفَ» به چنین عبارتی می رسیم:«یَسِیرُوا الْأَرْضِ یَنظُرُوا عَاقِبَةُ قَبْلِهِمْ دَمَّرَ الکَافِرِینَ أَمْثَالُهَا». حال با توجه به مفاهیم ادبی می‫توانیم کلماتی چون «الْأَرْضِ» را کنار بگذاریم و خروجی‫ای پیراسته‫تر داشته باشیم: «یَسِیرُوا عَاقِبَةُ دَمَّرَ الکَافِرِینَ»

## روش‌های شباهت‌یابی [11]
خوشه‌بندی متن در بیانی ساده، به معنای تقسیم کردن مجموعه‌ای از اسناد درهم در چند دسته مجزا است. این تقسیم‌بندی نیازمند تعیین کردن میزان شباهت یا افتراق بین دو سند است. این شباهت همیشه واضح نیست و بنابر شرایط مسئله متغیر است. خوشه‌بندی دقیق وابسته به تعریف مشخص از میزان شباهت بین دو شیء است. 
ابزارهای شباهت‌یابی متنوعی ارائه شده اند. به علت ناهم‌خوانی ابزار‌های اندازه‌گیری شباهت و افتراق هنوز کارابودن آن‌ها در خوشه‌بندی متن واضع نیست. 
در این بخش به معرفی ابزار‌های اندازه‌گیری شباهت می‌پردازیم. این روش‌ها سعی دارند تا فهم انسان در تشخیص شباهت را بازآفرینی کنند. این تقسیم‌بندی بر اساس مقاله‌ی «گذاری در مشی‌های شباهت متن» است. 
### شباهت رشته‌محور
این روش با توالی رشته‌ها و تلفیق کاراکتر‌ها سروکار دارد. معیار رشته‌ای‌، میعیاریست که شباهت یا افتراق بین رشته‌های متن را برای ماشین‌های مقایسه‌گر رشته محاسبه می‌کند. این معیار‌ها خود بر دو دسته هستند. 
#### شباهت‌سنج‌های کاراکترمحور
**طولانی‌ترین زیررشته‌ی مشترک**(LCS) :سنجش بر اساس طولانی‌بودن کاراکترهای پشت‌سرهم موجود در دو رشته
**Damerau-Levenshtein**: افتراق دو رشته را بر اساس کمینه تعداد اعمال جابجایی، زدودن و افزودن که برای یکی شدن دو رشته لازم است، محاسبه می‌کند.
**Jaro**: بر اساس تعداد و ترتیب کاراکتر‌های مشترک بین دو رشته است و همچنین تفاوت‌های املائی رایج را در نظر می‌گیرد.
**Needleman-Wunsch**: الگوریتمی که با برنامه‌نویسی پویا پیاده‌سازی می‌شود و اولین برنامه از این سنخ است که برای مقایسه رشته‌های بیولوژیک مورد استفاده قرار گرفت. این الگوریتم برای رشته‌هایی با طول تقریبا یکسان و مشابهت بسیار مناسب است. با طراز کردن و هم‌ردیف کردن دو رشته سعی در رسیدن به بهترین طراز بین دو رشته دارد. 

#### شباهت‌سنج‌های عبارت‌محور
**شباهت ثلثاتی**: سنجه‌ایست که شباهت میان دو بردار را با بدست آوردن مقادیر مثلثاتی از ضرب داخلی محاسبه می‌کند. 
**ضریب تاس**(Dice's coefficient): برابر است با دو برابر تعداد عبارات مشترک دو رشته تقسیم بر مجموع عبارات هر دو. 
**فاصله‌ی اقلیدسی**: برابر است با جذر مجموع مربعات تفاوت‌های میان عناصر مرتبط در دو بردار. 
**شباهت ژاکارد**: شباهت را با نسبت تعداد عبارات مشترک بر کل عبارات منحصربفرد دو رشته محاسبه می‌کند. 
**ضریب همبستگی**: یک مشی بسیار ساده که تعداد عبارات مشابه را در دو بردار -که هیچ یک صفر نیستند- می‌شمارد. 

#### شباهت‌سنج‌های پیکره‌محور
** Hyperspace Analogue to Language (HAL)**: یک فضای معنایی از کلماتی که با هم رخ می‌دهند می‌سازد. یک ماتریس کلمه به کلمه شکل می‌گیرد که هر عنصر از آن نمایانگر پیوستگی بین آن کلمه با کلمه در خط و ستون موردنظر است. الگوریتم می‌تواند ستون یا سطر‌هایی که ارتباط کمتری را دارند از محاسبات خارج کند. 
با تحلیل متن، یک کلمه کانونی(focus word) انتخاب می‌شود و همسایگان آن کلمه به عنوان هم‌رخداد‌هایش مورد بررسی قرار می‌گیرد. با ادامه‌ی روند و وزن‌دهی به این رخداد‌ها، ماتریس‌ها تغییر می‌کنند و در نهایت نزدیک‌ترین همسایه به عنوان کلمه‌ای که بیشترین ارتباط معنایی با کلمه کانونی را دارد مشخص می‌شود.
این الگوریتم همچنین به منظور برخورد متفاوت با رخداد کلمات بعد یا قبل از کلمه‌ی کانونی، اطلاعات ترتیبی کلمات را هم نگاه می‌دارد. 
**تحلیل معنایی پنهان** یا LSA) Latent Semantic Analysis): محبوب‌ترین تکنیک در شباهت‌سنجی پیکره‌محور است. [11]
این روش فرضیاتی دارد:
+ کلماتی که به طور همزمان در یک سند(با موضوع مشخص) می‌آیند، از نظر معنایی به هم مرتبط هستند.
+ سند هایی که دارای موضوع مشابهی هستند، حاوی کلمات مشابهی هستند. 

این روش ماتریسی از تعداد رخداد کلمه در هر پاراگراف را از سندی بسیار حجیم، با روشی ریاضی به نام (singular value decomposition(SVD ایجاد و تعداد ستون‌‌ها را با حفظ ساختار شباهت میان خطوط تشکیل می‌دهد. سپس مقایسه کلمات با کوسینوس‌گیری از زاویه‌ی بین بردار‌های تشکیل‌یافته از هر دو سطری انجام می‌پذیرد. 
**(Explicit Semantic Analysis (ESA**: سنجه‌ایست برای محاسبه وابستگی بین دو متن دلخواه. تکنیک ویکی‌پدیا‌محور، عبارات را با برداری با ابعاد بزرگ نمایش می‌دهد که وزن بستگی میان آن عبارت با یک مقاله‌ی ویکی‌پدیا را مشخص می‌کند. ارتباط معنایی بین دو عبارت با محاسبه کوسینوس بردارهای مربوط به آن دو میسر است. 
**(Normalized Google Distance (NGD**: یک شباهت‌سنج معنایی است که از دل تعداد بار تکرار در موتور جستجوی گوگل از یک مجموعه کلیدواژه‌ی داده‌شده که معنای مشابهی دارند، استخراج شده‌است. در تابع مربوط به این الگوریتم از تعداد بار جستجوی عبارت اول و عبارت دوم و ترکیبی از عبارت اول همراه عبارت دوم استفاده می‌شود 
#### شباهت‌سنج‌های دانش‌محور
شباهت معنایی سنجه‌ایست که بر مجموعه‌ای از اسناد و با این ایده که فاصله‌ی بین آن ها از نظر شباهت معنایی و مفهومی محتوا را مدنظر قرار می‌دهد که بدون توجه به نحو نمایش(قالب رشته‌ها) قابل تحقق است. [3]
شباهت‌سنجی دانش‌محور یکی از سنجه‌های شباهت معنایی است که بر مبنای شناسایی درجه‌ی شباهت میان کلمات به واسطه‌ی اطلاعاتی که از یک شبکه‌ی معنایی به دست آمده، استوار است. 
شبکه معنایی، یک شبکه است که ارتباطات معنایی میان مفاهیم را نشان می‌دهد. این شبکه اغلب به عنوان یک نوع از نمایش دانش استفاده می‌شود. این شبکه یک گراف جهت‌دار یا بدون‌جهت است که رئوس آن مفاهیم و یال‌های آن نمایانگر ارتباط معنایی میان مفاهیم هستند. [4]
![یک نمونه از شبکه معنایی](https://upload.wikimedia.org/wikipedia/commons/6/67/Semantic_Net.svg)
معروف‌ترین بسته‌هایی که شباهت‌سنجی دانش‌محور را پوشش می‌دهند WordNet::Similarity و NLTK است. 

#### شباهت‌سنجی ترکیبی
روش‌های ترکیبی از چندین روش شباهت‌سنجی استفاده می‌کنند. تحقیقات متعددی در این روش انجام شده است. به عنوان مثال در مقاله‌ی [14] از هشت روش استفاده شده است که دو مورد پیکره‌محور و بقیه دانش‌محور هستند. بهترین نتیجه از برآیند همه روش‌ها بدست آمد. یک روش برای شباهت‌سنجی برای متن‌های خیلی کوتاه یا جملات به کمک معنا و اطلاعات ترتیبی کلمات در [15] معرفی شده است. نویسنده‌ی [16] یک مشی از ترکیب سنجه‌ی معنایی پیکره‌محور در کل جمله با امتیاز شباهت حاصل از سنجه‌ی دانش‌محور بدست آمده است. تمام امتیاز‌های به مدل‌های یادگیری ماشین سپرده می‌شود تا در نهایت امتیازی واحد حاصل شود. 

## روش‫های خوشه‫بندی [12]
### `K`-معدل‫های پایه
ایده پایه معرفی نقاطی گرانیگاهی بر اساس فاصله‫ی تمام عناصر خوشه مورد نظر است. با هر انتصاب جدید نقاط گرانیگاه جابجا شده و بر دقت می‫افزایند. تصویر زیر چند مرحله از این الگوریتم در خوشه‫بندی فرضی را به تصویر می‫کشد. 
![چند مرحله از یک الگوریتم K-معدل در خوشه‫بندی](https://upload.wikimedia.org/wikipedia/commons/e/ea/K-means_convergence.gif)

الگوریتم K-معدل‫های پایه به این شرح است: 
~~~ sudo
Initialize k centroids 
Repeat 
	For all objects in input do
		Assign each element to its closest centroid
	End for 
	For all centroids do 
		Compute the mean of the assigned points 
		This mean now becomes the new centroid 
	End for 
Until all centoids remains unchanged or other termination criteria
		~~~

با توجه به الگوریتم، بیشترین زمان اجرایی برای این الگوریتم محاسبه‫ی بردار فاصله است. در هر مرحله تمام فاصله ها یک بار محاسبه می‫شود و پس از آن به بهترین نقطه ممکن منتسب می‫شود. در آخر نقاط گرانیگاه نسبت به تمامی اعضای مجموعه‫ی خود تجدید می‫شوند. پیچیدگی زمانی این الگوریتم `O(iknd(` خواهد بود که `i` تعداد تکرار و `k` تعداد گرانیگاه‫هاست. این پیچیدگی در عمل برای خوشه‫بندی اسناد بسیار سبک است چرا که بردارها بسیار تنک هستند و ابعاد هر بردار بسیار کمتر از `d` خواهد بود. 
اگر انتساب شعاع محور باشد، این الگوریتم خوشه‫هایی کروی تشکیل می‫دهد. در این روش در خوشه‫هایی که شکل کروی ندارند موفق نیست. 
این الگوریتم هیچ تضمینی برای خوشه‫بندی بهینه ندارد اما مقدار دهی اولیه می‫تواند بهینگی محلی بدهد. به همین منظور بعضا پیشنهاد می‫شود که یک خوشه‫بندی سلسله‫مراتبی با تعداد محدودی از ورودی ها انجام شود و نقاط مرکزی خوشه‫های به‫دست‫آمده گرانیگاه‫های پایه الگوریتم اصلی در نظر گرفته شوند. 
### `K`-معدل‫های میانی 
شاخه ای از الگوریتم k-معدل است به این صورت که ابتدا همه‫ی داده‫ها را در یک خوشه فرض می‫کند سپس شروع به تقسیم کردن آن می‫کند. در هر مرحله بد‫ترین خوشه انتخاب شده و به دو قسمت تقسیم می‫شود. 
الگوریتم k-معدل‫های میانی
~~~ sudo
Repeat 
	pick a cluster to split according to a criterion
		for I = 1 to N do
				Bisect into two sub-cluster using k-means for k=2
				Keep track of best candidate
		End for
		~~~
پیچیدگی این الگوریتم در بدترین حالت `O(nk(` است اما در عمل معمولا الگوریتم کمی سریع‫تر از حالت عادی اجرا می‫شود

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

### خوشه‫بندی متراکم سلسله‫مراتبی
هر عنصر را به عنوان یک شیء فرض می‫کند و طی چند ادغام به یک ریشه می‫رسد. در این مسیر، داده‫ها درختی را تشکیل می‫دهند. برای ادغام نیازمند محاسبه‫ی مشابهت هستیم. برای دوری از پیچیدگی `O(n^2(` عوض محاسبه مشابهت در هر مرحله، شباهت ها را در هر دور به یاد می‫سپاریم. 
~~~ sudo
Compute the similarity matrix
Repeat
	Find two best candidates according to criterion
	Save these two in the hierarchy as sub clusters
	Insert new cluster containing elements of both clusters
	Remove the old two from the list of active clusters
Until k or one cluster remains
~~~
خوشه بندی پیوند یگانه ارزان‫ترین معیار ادغام است. به صورت محلی و با در نظر گرفتن نزدیک ترین نقاط بین خوشه‫ها، میزان مشابهت آن‫ها مشخص می‫شود. زمان کل خوشه‫بندی پیوند یگانه به وسیله‫ی ماتریس مشابهت از `O(n^2)` است. 
خوشه بندی پیوند کامل حریصانه به دنبال کمینه کردن قطر خوشه‫هاست. در نتیجه دور‫ترین نقاط هر خوشه بیشتر مورد توجه باشند. این قاعده در نهایت باعث مقداری محاسبات اضافی در فاز ادغام می‫شود و پیچیدگی زمانی `O(n^2logn)` را منجر می‫شود. 
برگ برنده‫ی این الگوریتم قطعی بودن آن است بطوری که با ورودی یکسان همیشه خروجی یکسان بازگردانده خواهد شد. 
![نمونه خوشه‫بندی دادگان پرتقال توسط الگوریتم متراکم سلسله‫مراتبی](https://upload.wikimedia.org/wikipedia/commons/9/97/Orange-data-mining-hierarchical-clustering.png)

روشهای خوشه‌بندی بر اساس ساختار سلسله مراتبی تولیدی توسط آنها معمولا به دو دستة زیر تقسیم می‌شوند:
+  بالا به پایین (Top-Down) یا تقسیم کننده (Divisive)
در این روش ابتدا تمام داده‌ها به عنوان یک خوشه در نظر گرفته می‌شوند و سپس در طی یک فرایند تکراری در هر مرحله داده‌هایی شباهت کمتری به هم دارند به خوشه‌های مجزایی شکسته می‌شوند و این روال تا رسیدن به خوشه‌هایی که دارای یک عضو هستند ادامه پیدا می‌کند.
+ پایین به بالا (Bottom-Up) یا متراکم شونده (Agglomerative)
 در این روش ابتدا هر داده‌ها به عنوان خوشه‌ای مجزا در نظر گرفته می‌شود و در طی فرایندی تکراری در هر مرحله خوشه‌هایی که شباهت بیشتری با یکدیگر با یکدیگر ترکیب می‌شوند تا در نهایت یک خوشه و یا تعداد مشخصی خوشه حاصل شود. از انواع الگوریتمهای خوشه‌بندی سلسله مراتبی متراکم شونده رایج می‌توان از الگوریتمهای Single-Link، Average-Link و Complete-Linkنام برد. تفاوت اصلی در بین تمام این روشها به نحوة محاسبة شباهت بین خوشه‌ها مربوط می‌شود.

## اندازه‌گیری اعتبار خوشه‫ها [8]
نتایج حاصل از اعمال الگوریتمهای خوشه‌بندی روی یک مجموعه داده با توجه به انتخاب‌های پارامترهای الگوریتمها می‌تواند بسیار متفاوت از یکدیگر باشد. هدف از اعتبارسنجی خوشه‌ها یافتن خوشه‌هایی است که بهترین تناسب را با داده‌های مورد نظر داشته باشند. دو معیارِ پایة اندازه‌گیری پیشنهاد شده برای ارزیابی و انتخاب خوشه‌های بهینه عبارتند از:
+ تراکم (Compactness) 
داده‌های متعلق به یک خوشه‌ بایستی تا حد ممکن به یکدیگر نزدیک باشند. معیار رایج برای تعیین میزان  تراکم داده‌ها واریانس داده‌ها است.
+ جدایی (Separation) 
خوشه‌ها خود بایستی به اندازه کافی از یکدیگر جدا باشند. سه راه برای سنجش میزان جدایی خوشه‌ها مورد استفاده قرار می‌گیرد که عبارتند از:
+ فاصلة بین نزدیک‌ترین داده‌ها از دو خوشه
+ فاصلة بین دور‌ترین داده‌ها از دو خوشه
+ فاصلة بین مراکزخوشه‌ها

همچنین روش‌های  ارزیابی خوشه‌های حاصل از خوشه‌بندی را به صورت سه دسته تقسیم می‌کنند که عبارتند از:
+ معیارهای خروجی (External Criteria)
+ معیارهای درونی (Internal Criteria)
+ معیارهای نسبی (Relative Criteria)

هم معیارهای خروجی و هم معیارهای درونی بر مبنای روش‌های آماری عمل می‌کنند و پیچیدگی محاسباتی بالایی را نیز دارا هستند. معیارهای خروجی عمل ارزیابی خوشه‌ها را با استفاده از بینش خاص کاربران انجام می‌دهند. معیارهای درونی عمل ارزیابی خوشه‌ها را با استفاده از مقادیری که از خوشه‌ها و نمای آنها محاسبه می‌شود، انجام می‌دهند.
پایه معیارهای نسبی، مقایسة بین شما‌های خوشه‌بندی (الگوریم به علاوة پارامترهای آن) مختلف است. یک و یا چندین روش مختلف خوشه‌بندی چندین بار با پارامترهای مختلف روی یک مجموعة داده اجرا می‌شوند و بهترین شمای خوشه‌بندی از بین تمام شماها انتخاب می‌شود. در این روش مبنای مقایسه، شاخص‌های اعتبارسنجی (Validity-Index) هستند. شاخص‌های ارزیابی بسیار متنوعی پیشنهاد شده‌اند که به معرفی آن‫ها می‫پردازیم اما ارائه معادلات ریاضی از مجال پژوهش حاضر بیرون است. 

### شاخص دون (Dunn Index)
اگر مجموعة داده‌ای، دارای خوشه‌هایی جداپذیر باشد، انتظار می‫رود فاصلهٔ بین خوشه‌ها زیاد و قطر خوشه‌های (Diameter) آن کوچک باشد. در نتیجه مقداری بزرگ‌تر برای رابطهٔ این معیار مقداری مطلوب‌تر است. 
#### معایب
این معیار معایبی دارد که عبارتند از:
+ محاسبهٔ زمان‫بر
+ حساسیت به نویز (قطر خوشه‌ها در صورت وجود یک دادة نویزی می‫تواند بسیار تغییر کند.)

### شاخص دیویس بولدین (Davies Bouldin Index)
این شاخص در واقع میانگین شباهت بین هر خوشه با شبیه‌ترین خوشهٔ به آن را محاسبه می‫کند. می‫توان دریافت که هرچه مقدار این شاخص بیشتر باشد، خوشه‌های بهتری تولید شده است.
### شاخص‌های  اعتبارسنجی ریشة میانگین مربع انحراف از معیار (RMSSDT)
هرچند این شاخص‌ها معمولا در اعتبار‌سنجی الگوریتم‌های سلسله‌ مراتبی مورد استفاده قرار می‫گیرند ولی قابلیت ارزیابی نتایج سایر تکنیک‌های خوشه‌بندی را نیز دارا می‌باشند. در شاخص اعتبار‌سنجی RMSSDT (root – mean– square standard deviation) از واریانس خوشه‌ها استفاده می‫شود. هرچه مقدار آن کمتر باشد نشان‌ دهندهٔ خوشه‌بندی بهتر داده‌ها است.
### شاخص اعتبار‌سنجی SD
اساس شاخص اعتبارسنجی SD، میاگین پراکندگی (Average Scattering) و جدایی کلی (Total Separation) خوشه‌ها است. پراکندگی از طریق محاسبهٔ واریانس خوشه‌ها و واریانس کل محموعهٔ داده‌ها بدست می‫آید. با توجه به اینکه این معیار هم از میزان هم‫گنی داده‌ها و هم از میزان تراکم خوشه‌ها بهره می‫برد معیار مناسبی برای ارزیابی خوشه‌ها محسوب می‌شود. مقدار محاسبه شده توسط این معیار هرچه کوچک‌تر باشد به معنی خوشه‌بندی بهتر است.
### شاخص اعتبارسنجی S_Dbw
همانند شاخص SD این معیار هم بر اساس تراکم درون‌خوشه‌ای و میزان جدایی خوشه‌ها اما در این شاخص سعی شده تا چگالی خوشه‌ها نیز دخیل شود. به شکل رسمی می‌توان گفت که شاخص  S_Dbw از واریانس بین خوشه‌ای و واریانس درون خوشه‌ای استفاده می‌کند.
در شاخص S_Dbw سعی شده هر دو معیار خوبی خوشه‌ها با هم ترکیب شوند و تخمینی دقیق از خوشه‌های حاصل بدست آید. مقدار کم برای این شاخص به معنی خوشه‌بندی بهتر است.
## آزمایش و مقایسه کارایی شاخص‌های اعتبارسنجی
در اینجا با آزمایش سعی می‌شود کارایی 4 شاخص از شاخص‌های خوشه‌بندی بالا با هم مقایسه شوند. برای این منطور از سه دسته داده با ویژگی‌های متفاوت استفاده می‌شود.

+ خوشه‌های کاملا جدا: داده‌های متعلق به هر خوشه در کاملا به هم نزدیک هستند. 
![خوشه‫های کاملا جدا](https://boute.s3.amazonaws.com/264-image083.gif)
طبق آزمایش‫ها چهار شاخص اعتبارسنجی دون، دیویس بلودین، SD و D_Dbw نتایج صحیح ارائه می‫دهند. 
+ خوشه‌های حلقه‌ای شکل: خوشه‌ای که خوشه‌ای دیگر درون آن قرار دارد.
![خوشه‫های حلقوی‫شکل](https://boute.s3.amazonaws.com/264-image085.gif)
طبق آزمایش‫ها تنها با شاخص دون و S_Dbw مقادیر صحیحی به‫دست می‫آوریم. 
+ خوشه‌های با شکل دلخواه: دو خوشه با شکلی دلخواه.
![خوشه‫های با شکل دلخواه](https://boute.s3.amazonaws.com/264-image087.gif)
طبق آزمایش‫ها تنها شاخص دون مقادیر صحیحی را محاسبه می‫کند. 

## خوشه‌بندی قرآن در مقام پیاده‌سازی
در مقاله [12] مؤلف فهم ساختار قرآن را در کنار دانش زبانی برای یافتن مسیر راه از قرآن کمک حال عنوان می‌کند. در این مقاله از الگوریتم K-Means برای آزمایش به مثابه چهارچوب کاری متن‌کاوی استفاده کرده است و ۶۲۳۶ آیه را در اختیارش قرار داده و در سه خوشه نتیجه را استخراج کرده است. 
در تحقیقات موجود در سایت [کاوش قرآن](https://sites.google.com/site/miningthequran/) برخلاف مقاله فوق، از اطلاعات الگویی با الگوریتم CLOPE استفاده شده است. که البته اطلاعات از ترجمه‌ی قرآن به انگلیسی توسط آقای یوسف علی استفاده شده است. تصویر زیر نمایش رسمی نتایج مربوط به خوشه‌بندی جزء ۲۶ است و تصویر بعدی نمایش نتایج در قالب ابرکلیدواژه.
![نمایش نتایج خوشه‌بندی در قالب رسمی](https://8404b1c8-a-62cb3a1a-s-sites.googlegroups.com/site/miningthequran/text-mining-of-qur-an/experimental-results/formal-representation/Juz%2026.jpeg?attachauth=ANoY7crhX-Igb-sgISgeFHV1GApSto0apd9To8Ln--pRy-UkLannevK60p2VN-WQZ-mJchVPCls8UVoHGqcV1hWGxVkpsBH9Lg_EZDYZnPtZnRejB9tj8O72rYKPM7JY8F8ZGxCq6-zo8I5AJzb2s6KtmDMFj_DAhD_kTT0_ArX2LtKQWIo8-keWQtWmRqmgcMFIo0ZuwzvpKEbD_9qQ7qIGnYSiG-x4eSwkqCW0N-14P8e4Ji62CNQoIyVwnw5mG6G53D4XAmHGy1b30wj_0oeampRkvufn-cbQWCjoy_xLFTLyQnec2A8=&attredirects=0)
![نمایش نتایج خوشه‌بندی در قالب غیررسمی ابرکلیدواژه](https://8404b1c8-a-62cb3a1a-s-sites.googlegroups.com/site/miningthequran/text-mining-of-qur-an/experimental-results/informal-representations/Juz%2026.png?attachauth=ANoY7cryMEHjt_5ZQC2kfRP9PPsPV2qKH4d_fcRuhrfMi2JAEp1-F86tfmBjkm-EB5vWmPzbAHEj9jewqwzYL05lYPpHZ0ASV19lc7eJp1IuBNVZAwavIINpCqmWdRmsZ1C8f7gUE4f07oLi0mIQnfmoC_xzByLN5fLm1Iy6c205PeHKACCibyv9I2KFAbTa3mLXqmaCZqspp3nU1q1kIhVi60D2Jev0nqdQWM4C4K5B-DGnhgAFguFfB-SIGH9lthAfDBf8OOkazk1sv5HSmYCbZyqCC27Fn7fEbQUWcIm5ufB4aWVeVN7jsbGpcPiBy8rrwTiWxo86&attredirects=0)


# آزمایش‌ها
## پیش‫پردازش
### حذف اعراب
با استفاده از [پروژه متن باز](https://github.com/motazsaad/process-arabic-text) ورودی و خروجی مدنظر را می‫بینیم:
*ورودی:* قُلْ إِنَّما أَنَا بَشَر مِثْلُکُمْ یوحی إلَی أَنَّما إلهُکُمْ إِله واحِد فَمَن کانَ یرْجُوا لِقاءَ رَبِّهِ فَلْیعْمَلْ عَمَلاً صالِحاً وَ لا یشْرِکْ بِعِبادةِ رَبِّهِ أَحَدا 
*خروجی:* قل إنما أنا بشر مثلکم یوحی إلی أنما إلهکم إله واحد فمن کان یرجوا لقاء ربه فلیعمل عملا صالحا و لا یشرک بعبادة ربه أحدا

# کارهای آینده
## دقت‫افزایی در مرحله پیش‫پردازش
شاید مهم‫ترین گام پژوهش‫گران آتی افزایش دقت در مرحله پیش‫پردازش باشد. در این مرحله آن‫گونه که در مقدمه بیان شد، از بسیاری از ظرایف زبان فصیح عربی چشم‫پوشی شد؛ ظرایفی که تفاوت‫هایی عمیق در فهم قرآن مجید و خوشه‫بندی دقیق آن را سبب می‫شوند. 
### حذف اعراب
اعراب و حرکات حروف در زبان عربی تأثیر قابل‫توجهی دارند، علی الخصوص کلام وحی که جزئیات مهمی را دارد. 
### نشانه‫گذاری
هر عبارت در نشانه‫گذاری این پژوهش یک کلمه‫ای فرض شد. دخیل کردن اصطلاحات و عبارات چند کلمه‫ای دقت ما را به‫خوبی می‫افزاید. ناکارآمدی بیشتر نشانه‫گذاری در زبان عربی، خروجی کاملا یکسان برای الگوریتم‫های متنوع نشانه‫گذاری است بطوری که از پنج روش آن شامل  TreebankWordTokenizer،  WordPunctTokenizer،  PunktWordTokenizer WhitespaceTokenizer و pattern خروجی یکسان حاصل می‫شود.[2]  پس نیاز به نشانه‫گذاری تخصصی متناسب با ویژگی‫های زبان عربی داریم. 
#### فراهم‫آوردن داده‫های آموزشی
با طراحی یک سیستم خبره و در نظر گرفتن قوانین با هم‫آیی کلمات می‫توان متون مشابه را به صورت ماشینی شناسایی کرد. در ادامه این پژوهش می‫توان با ضمیمه نمودن بخش قواعد معنوی و بانک‫های مترادفات و مشترکات بر صحّت پاسخ ها افزود. 
### حذف کلمات بی‫اثر
لیست‫های موجود کلمات بی‫اثر در زبان عربی با بیان بلیغ قرآنی بهینه نیستند. مثلا کلماتی نظیر «الیوم، دون ،نفسه» جزو کلمات محذوف اند در حالی که در معنی تأثیر قابل توجه دارند.
### ریشه‫یابی
ماهیت و روش ریشه‫یابی در زبان عربی با زبان انگلیسی بسیار متفاوت است. با دست‫یابی به الگوریتمی بهینه و کارا در این زمینه نه تنها موضوع پژوهش ما، بلکه دیگر استفاده‫های داده‫کاوی در علوم اسلامی نیز جهش خواهد داشت. مقاله «بهبود فرایند ریشه‫یابی عربی با استفاده از منابع و ابزارهای محک‫زنی» که در بخش پیوندهای مفید ذکر شده است بهره برد.
## امنیت حداکثری در کاهش ابعاد 
کاهش ابعاد علی الخصوص هنگامی که تفاسیر و روایات هم مورد پردازش قرار می‫گیرند الزامی است. کاهش بعد مناسب با رجوع به مقاله «راهی کارا برای روش انتخاب خصوصیت برای طبقه‫بندی متن عربی» که در مراجع ذکر شده است راه‫گشاست.
### انتخاب خصوصیت 
مثالی که از انتخاب خصوصیت در بخش مقدمه ذکر شد حالت ایده‫آل بود. اما در حقیقت روش‫های فعلی از چنین هوشمندی‫ای بهره‫مند نیستند و نیاز است تحقیقی خاص منحصرا ناظر بر این بخش صورت پذیرد. 
## وسعت‫بخشیدن به دامنه داده‫ها
علاوه بر این پردازش متون روایی و تفاسیر و دخیل کردن همه نتایج، ما را در رهیابی به تصویری یکپارچه از قرآن یاری‫گر است. 
## پیاده‫سازی الگوریتم امید ریاضی بیشینه
تصویر زیر که مقایسه بین k-معدل‫های میانگین و امید ریاضی بیشینه است گویای برتری و هوشمندی بیشتر این الگوریتم است. پیاده‫سازی و بهره‫گیری از این الگوریتم در خوشه بندی اثر بهبودی قابل توجهی خواهد داشت. 
![مقایسه الگوریتم k-معدل‫های میانگین و امید ریاضی بیشینه](https://upload.wikimedia.org/wikipedia/commons/0/09/ClusterAnalysis_Mouse.svg)

# پاورقی

[2] ر.ک: [Word Tokenization with Python NLTK](http://text-processing.com/demo/tokenize/)

# مراجع

+ حسین عابدینی، دکتر بهروز مینایی. «کاربرد‫های داده‫کاوی در علوم اسلامی» (ویژه‫نامه سمینار فناوری‫های پردازش هوشمند متون اسلامی)
+ حمید محمودی، دکتر اقبال منصوری. «ارائه یک مدل آماری برای خوشه‫بندی متون» (پایان‫نامه کارشناسی ارشد، دانشگاه شیراز) 
+ Bilal Hawashin, Ayman M Mansour, Shadi Aljawarneh. "An Efficient Feature Selection Method for Arabic Text Classification" (International Journal of Computer Applications Volume 83 – No.17, December 2013)
+ [محتوای آموزشی درس یادگیری ماشین، دکتر شیری](http://ceit.aut.ac.ir/~shiry/lecture/machine-learning/tutorial/clustering/TOC.htm) دانشگاه امیرکبیر تهران (۱۳۸۵)
+ [مبانی خوشه‫بندی](http://ce.aut.ac.ir/~shiry/lecture/machine-learning/tutorial/word%20files/Clustering.pdf) دانشگاه امیرکبیر
+ 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)


# پیوندهای مفید

+ قُطوف [Arabic Morphological Analyzer (with Stemmer)](https://github.com/Muhammad-Altabba/Qutuf)
+ تاشفین [Tashaphyne Arabic Light Stemmer](https://pypi.python.org/pypi/Tashaphyne)
+ [Hierarchical clustering](https://en.wikipedia.org/wiki/Hierarchical_clustering)
+ [_k_-means clustering](https://en.wikipedia.org/wiki/K-means_clustering)
+ [Adapt Clustering Methods for Arabic Documents](http://pubs.sciepub.com/ajis/1/1/4/index.html)
+ [اسلایدهای درس یادگیری ماشین، دانشگاه شهید بهشتی](http://facultymembers.sbu.ac.ir/a_mahmoudi/ML_93_1/ML_93_1_Chap7_Clustering&EM.pdf) (۱۳۹۳)مراجع

[1] حسین عابدینی، دکتر بهروز مینایی. «کاربرد‫های داده‫کاوی در علوم اسلامی» (ویژه‫نامه سمینار فناوری‫های پردازش هوشمند متون اسلامی)
[2] ر.ک: [Word Tokenization with Python NLTK](http://text-processing.com/demo/tokenize/)
[3] [Knowledge Network](https://en.wikipedia.org/wiki/Knowledge_Network)
[4] Semantic Networks". In Stuart C Shapiro. _Encyclopedia of Artificial Intelligence
[6] حمید محمودی، دکتر اقبال منصوری. «ارائه یک مدل آماری برای خوشه‫بندی متون» (پایان‫نامه کارشناسی ارشد، دانشگاه شیراز) 
[7] [محتوای آموزشی درس یادگیری ماشین، دکتر شیری](http://ceit.aut.ac.ir/~shiry/lecture/machine-learning/tutorial/clustering/TOC.htm) دانشگاه امیرکبیر تهران (۱۳۸۵)
[8] [مبانی خوشه‫بندی](http://ce.aut.ac.ir/~shiry/lecture/machine-learning/tutorial/word%20files/Clustering.pdf) دانشگاه امیرکبیر
[9] [م.ایمانی، خوشه‌بندی متون فارسی، پایان‌نامه کارشناسی، دانشگاه علم و صنعت ایران، ۱۳۹۱](http://bayanbox.ir/id/8155819707974834975)
[10] Processing the Text of the Holy Quran: a Text Mining Study, Mohammad Alhawarat
[11] [درس روش‌های آماری در پردازش زبان طبیعی - دانشگاه تهران](http://dsp.ut.ac.ir/en/wp-content/uploads/2015/09/StatNLP-Lecture3-Similarity-IR-.pdf)
[12] Ebbesson, Magnus, and Christopher Issal. "Document Clustering." (2010).
[13] [Clustering the verses of holy quran using K-Means algorithm](http://docsdrive.com/pdfs/medwelljournals/ajit/2016/5159-5162.pdf) 
[14] Mihalcea, R., Corley, C. & Strapparava, C. (2006). Corpus based and knowledge-based measures of text semantic similarity. In Proceedings of the American Association for Artificial Intelligence.(Boston, MA).
[15] Li, Y., McLean, D., Bandar, Z., O’Shea, J., & Crockett, K. (2006). Sentence similarity based on semantic nets and corpus statistics. IEEE Transactions on Knowledge and Data Engineering, 18(8), 1138–1149.
[16] Nitish, A., Kartik, A. & Paul, B. (2012). DERI&UPM: Pushing Corpus Based Relatedness to Similarity: Shared Task System Description. First Joint Conference on Lexical and Computational Semantics (*SEM), pages 643–647, Montreal, Canada, June 7-8, 2012 Association for Computational Linguistics.


# پیوندهای مفید

+ [پوشه‌ی شامل مقالات و سایت‌ها و کتاب‌خانه‌های مربوط به پروژه](https://drive.google.com/drive/folders/1Qmd5iIZqH-Sgi2dMk08X3GD__5Ai4jm6?usp=sharing)
+ قُطوف [Arabic Morphological Analyzer (with Stemmer)](https://github.com/Muhammad-Altabba/Qutuf)
+ تاشفین [Tashaphyne Arabic Light Stemmer](https://pypi.python.org/pypi/Tashaphyne)
+ [Hierarchical clustering](https://en.wikipedia.org/wiki/Hierarchical_clustering)
+ [_k_-means clustering](https://en.wikipedia.org/wiki/K-means_clustering)
+ [Adapt Clustering Methods for Arabic Documents](http://pubs.sciepub.com/ajis/1/1/4/index.html)
+ [اسلایدهای درس یادگیری ماشین، دانشگاه شهید بهشتی](http://facultymembers.sbu.ac.ir/a_mahmoudi/ML_93_1/ML_93_1_Chap7_Clustering&EM.pdf) (۱۳۹۳)
+ Younes Jaafar, Driss Namly, Karim Bouzoubaa, Abdellah Yousfi. ["Enhancing Arabic stemming process using resources and benchmarking tools"](http://www.sciencedirect.com/science/article/pii/S1319157816301239)
+ Berry, Michael W., ed. Survey of Text Mining I: Clustering, Classification, and Retrieval. Vol. 1. Springer, 2004.
+ [Similarity Measures for Text Document Clustering, Anna Huang, New Zealand](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.332.4480&rep=rep1&type=pdf)
+ Bilal Hawashin, Ayman M Mansour, Shadi Aljawarneh. "An Efficient Feature Selection Method for Arabic Text Classification" (International Journal of Computer Applications Volume 83 – No.17, December 2013)

**پیوند‌های بیشتر**
+ [پردازش زبان فارسی در پایتون](http://www.sobhe.ir/hazm)
+ [خوشه‌بندی با 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)
+ [نمونه‌ای از کشف آیات مشابه با استفاده از تفسیر ابن کثیر](http://textminingthequran.com/apps/similarity.php)
+ [پیکره قرآن تنزیل](http://tanzil.net/wiki/Resources)
+ [پیکره تفاسیر اهل سنت](http://www.textminingthequran.com/wiki/Tasir_corpus)
+ Younes Jaafar, Driss Namly, Karim Bouzoubaa, Abdellah Yousfi. ["Enhancing Arabic stemming process using resources and benchmarking tools"](http://www.sciencedirect.com/science/article/pii/S1319157816301239)