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

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

مقدمه

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

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

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

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

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

1-پیدا کردن سندهای مشابه¹

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

2-سازماندهی مجموعه سند های بزرگ²

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

3-تشخیص محتوای تکراری⁴

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

4-سیستم های توصیه گر⁵

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

5-جستجوی بهینه⁶

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

کارهای مرتبط

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

1- فیلتر کردن عنصرها⁷

حذف کردن stop word هایکی از رایج ترین روش های فیلتر کردن عنصر ها[^7] می باشد که لیست این stop word ها معمولا در دسترس می باشد.

تکنیک های دیگر فیلتر کردن عنصرها[^7] :

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

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

2-ریشه یابی⁹

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

3_ پیش پردازش گراف¹⁰

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

نمره دهیTF-IDF:

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

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

خوشه بندی به روش K_MEANS:

برای خوشه بندی آیات قرآن باید علاوه بر ظاهر آیات ترجمه و تفسیر آیات هم در نظر گرفته شود و برای هر کدام از آن ها الگوریتم پیشنهادی را پیاده کرد در زیر به 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 پایتون میبینید:

kmeans

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

انتشار میل¹²

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

متوسط تغییر¹³

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

Spectal Clustering

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

سلسله مراتبی¹⁴

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

Dbscan

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

لینک کد اولیه در گیت هاب.
لینک کد فاز سوم در گیت هاب.
لینک کد فاز چهارم در گیت هاب.

آزمایش‌ها

ارزیابی عملکرد الگوریتم ها ی خوشه بندی به سادگی شمارش تعداد خطاها یا دقت¹⁵ و یادآوری¹⁶ الگوریتم خوشه بندی نیست.

در خود کتابخانه ی 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 ام

نتایج

در فاز قبل روشی با استفاده از کتابخانه ی Scikitlearn و روش KMeans پیاده سازی شد(بدون انجام بهینه سازی روی داده های ورودی از جمله حذف stopword ها و . . .) که برای یک فایل متنی 1.26 مگابایتی در مدت زمانی حدود 1 ثانیه انجام شد.
در این فاز برای بهبود بخشیدن به سرعت اجرا کلمات هر آیه ریشه یابی شد و کلمات بیهوده حذف شدند که این کار باعث شد برای یک فایل متنی 1.26 مگابایتی
زمانی در حدود 0.017 صرف شد که همانطور که میبینید در مقایسه با فاز قبل در زمان صرفه جویی شد , همچنین به علت حذف کلمات اضافه فایل خروجی کم حجم تر وآیات موجود در هر خوشه به هم نزدیکتر شدند.

کارهای آینده

در میان تمامی راه هایی که تا به امروز برای خوشه بندی متون وجود دارد الگوریتم kmeans بهترین و سریعترین روش برای این کار می باشد که توسط کتابخانه ی scikitlearn پشتیبانی می شود.
الگوریتم هایی دیگری که برای خوشه بندی می شود از آن ها استفاده کرد در قسمت کارهای مرتبط امده است مانند:Affinity propagation,MeanShift. . .
که این الگوریتم ها هم توسط کتابخانه ی scikit learn پشتیبانی می شوند.
برای بهینه تر کردن خوشه بندی متون اولویت های اصلی در سرعت و دقت خوشه هاست که برای این کار میتوان مثلا در قسمت ریشه یابی سرعت و دقت را افزایش داد یا برای دقیق تر شدن نزدیکی آیه های یک خوشه از معنا و تفسیر آنها نیز استفاده کرد.

مراجع

• [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

• [13]Journal of Information & Computational Science 10: 1 (2013) 193–199,An Improved K-means Clustering Algorithm,Chunfei Zhang∗, Zhiyi Fang∗,College of Computer Science and Technology, Jilin University, Changchun 130012, China

• [14]Improved K-means Clustering Algorithm Based on User Tag,Jun Tang ,
  Department of Information Engineering, Hunan Urban Construction College, Hunan

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

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

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

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

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

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

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

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