خوشه‌بندی به فرآیند تبدیل حجم عظیمی از داده‌ها به گروه‌های داده‌ای مشابه گفته می‌شود. به همین صورت خوشه‌بندی متون عبارت است از تبدیل حجم عظیمی از اسناد متنی به گروه‌هایی از متن‌های مشابه؛ که به هر کدام از این گروه‌ها یک خوشه گفته می‌شود. پس مسئله خوشه‌بندی آیات قرآن را نیز میتوان به صورت گروه‌بندی آیات قرآن به صورت خودکار در گروه آیه‌های هم‌معنی معرفی نمود. برای درک این رابطه‌ی شباهت معنایی بین آیات میتوان از روش‌های مختلفی از جمله شباهت‌یابی بر مبنای واژه‌های آیه، واژه‌های ترجمه، تفسیر آیه و ... استفاده نمود.
در این پروژه شما باید آیات قرآن را با استفاده از **ظاهر آیات به همراه ترجمه و تفسیر آنها** خوشه‌بندی کنید.
# مقدمه
خوشه بندی فرایند سازماندهی عناصر به گروه هایی است که اجزای آن شبیه به هم هستند .در یک خوشه مجموعه عناصری هستند که با هم مشابهت دارند و با اجزای دیگر خوشه ها نا همگون می باشند . هدف از خوشه بندی دست یابی سریع و مطمئن به اطلاعات مشابه و شناسایی ارتباط منطقی میان انهاست.
خوشه بندی را می توان بر اساس رابطه ها به 3 نوع تقسیم کرد.
+ 1-رابطه ی هم ارز که متداول ترین رابطه بوده و مترادف های واژه را ارائه می دهد در این نوع رابطه واژه هایی مورد نظر است که همپوشانی معناداری بین آن ها وجود دارد اما از لحاظ واژگانی متفاوتند مثل درد , الم ,بیماری ,تالم و . . .
+ 2-رابطه ی سلسله مراتبی در این رابطه یک واژه به عنوان رده ی اصلی انتخاب شده و زیرمجموعه ها یا نمونه های خاصی از واژه ی کلی هستند مثل رایانه , پنتیوم و . . .
+ 3-رابطه غیر سلسله مراتبی که انواع دیگر روابط بین واژه ها غیر از 2 مورد قبلی از قبیل موضوع و ویژگی های مربوط را در بر میگیرد مثل کارمند -> عنوان شغل
که در اینجا از رابطه ی سلسله مراتبی برای خوشه بندی ایات استفاده می کنیم.
خوشه بندی وسیله ی اصلی در بسیاری از برنامه ها در زمینه های علمی و تجاری می باشد.
کاربردهای اصلی این روش در زیر به اختصار توضیح داده شده.
#1- Finding Similar Documentsپیدا کردن سندهای مشابه[^1]
زمانی که کاربر داکیومنت خوبی پیدا می کند وبه دنبال موارد مشابهی از این داکیومنت است در این حالت با استفاده از خوشه بندی به راحتی می توان به داکیومنت هایی با مفهوم مشابه دست یافت نسبت به الگوریتم های مبتنی بر جستجو که موارد ی را پیدا میکنند که فقط شباهت لغوی با داکیومنت مورد نظر دارند.
#2-Organizing Large Document Collectionsسازماندهی مجموعه سند های بزرگ[^2]
بازیابی داکیومنت ها(document retrieval)[^3] روی پیدا کردن داکیومنت های مربوط به یک کوئری متمرکز است ولی در مقابل داکیومنت ها ی بزرگی که طبقه بندی نشده ناتوان است.
#3-Duplicate Content Detectionتشخیص محتوای تکراری[^4]
در بسیاری از برنامه ها نیاز زیادی به پیدا کردن تکرار در داکیومنت های بزرگ است خوشه بندی برای پیدا کردن سرقت ادبی و گروه بندی گزارش های خبری و مرتب کردن رتبه بندی نتایج جستجو استفاده می شود.
#4-Recommendation Systemسیستم های توصیه گر[^5]
مثلا مقاله ای را بر اساس مقاله ای که قبلا کاربر خوانده به او پیشنهاد می کند . خوشه بند یمقالات استفاده از انها را در زمان کوتاه و با کیفیت بالاتر تضمین می کند.
#5-Search Optimization جستجوی بهینه[^6]
خوشه بندی کمک زیادی به بهتر شدن کیفیت و بهره وری از موتور های جستجو میکند در واقع این کار را با مقایسه ی کوئری کاربر با خوشه ها (به جای مقایسه با کل داکیومنت ) انجام میدهد همچنین نتایج جستجو نیز به راحتی مرتب می شوند.
# کارهای مرتبط
قبل از شروع به خوشه بندی ابتدا باید متن را مرتب کنیم که این کار در بیشتر الگوریتم های خوشه بندی انجام می شود.
#1- Term Filtering فیلتر کردن عنصرها[^7]
حذف کردن stop word هایکی از رایج ترین روش های term filteringفیلتر کردن عنصر ها[^7] می باشد که لیست این stop word ها معمولا در دسترس می باشد.
تکنیک های دیگر term filteringفیلتر کردن عنصرها[^7] :
حذف کردن ترم هایی با document frequencyفرکانس سند[^8] کمتر که برای بالا بردن سرعت و کمتر کردن مصرف memoryحافظه در برنامه ها استفاده می شود.
حذف کردن اعدادی که نقش زیادی در خوشه بندی ندارند به جز تاریخ و کد پستی.
#2-Stemmingریشه یابی[^9]
ریشه یابی فرایند کوتاه کردن کلمات به ریشه یشان است مثل کتابدار , کتابهایش که هر 2 به یک کلمه ی کتاب تبدیل می شوند.
#3_ Graph Preprocessingپیش پردازش گراف[^10]
در برخی از الگوریتم ها که از گراف برای خوشه بندی استفاده می شود برای بهبود کیفیت و بهره وری نیازمند پیش پردازش گراف هستند.که بعضی از روش های ساده ی graph processingپردازش گراف[^10] شامل حذف کردن نود هایی با وزن کمتر از استانه می باشد یا حذف نودهایی که به هیچ نود دیگری مرتبط نیستند.
#نمره دهیTF-IDF:
قبل از اینکه قادر به اجرای الگوریتم k-means روی مجموعه ای از داکیومنت ها باشیم باید بتوان اسناد و مدارک را به عنوان بردار های دو به دو مقایسه کرد برای این کار می توان از تکنیک نمره دهی TF-IDF استفاده کرد. Tf-idf یا ( term frequency-inverse document frequency) ترم ها را بر اساس اهمیتشان وزن دهی می کند term frequencyفرکانس ترم[^11] نسبت تعداد تکرار یک کلمه در سند به تعداد کل کلمات موجود در سند است. معکوس document frequency فرکانس سند[^8] لگاریتم نسبت تعداد داکیومنت ها در کورپوس به تعداد داکیومنت هایی است که ترم مورد نظر را داراست.
ضرب این 2 مقدار در هم مقدار TF-IDF را میدهد.
#K-MEANS CLUSTRING خوشه بندی به روش 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
این الگوریتم قبلا توضیح داده شده و به نسبت بقیه ی الگوریتم ها کارایی بهتری دارد به همین دلیل در این پروژه از این الگوریتم استفاده می کنیم.
#Affinity propagationانتشار میل[^12]
خوشه ها را با فرستادن پیام هایی بین جفت نمونه ها تا زمانی که همگرا شوند ایجاد می کند.
در اینجا مهم ترین پارامترها یکی میزان عملکرد است که تعداد نمونه هایی که استفاده می شوند را کنترل می کند و دوم فاکتور تعدیل است.
اصلی ترین اشکال این روش پیچیدگی آن است که o(n^2*t) می باشد.
#MeanShift متوسط تغییر[^13]
داده ها را با تخمین حبابی در مناطق متراکم ماتریس نقاط خوشه بندی می کند.
در مقیاس گذاری برای هزاران نمونه دچار مشکل می شود.
#Spectal Clustering
یک ماتریس وابستگی کم بعد از بین نمونه ها درست می کند و بسیار موثر است اگر ماتریس وابستگی بسیار نادر باشد و ماژول pyamg نصب شده باشد. برای خوشه بندی در تعداد کم خوب است ولی برای تعداد داده های زیاد پیشنهاد نمی شود
#Hierarichicalسلسله مراتبی[^14]
خوشه بندی سلسله مراتبی خوشه های تو در تو با ادغام کردن پی در پی آن ها می سازد این سلسله مراتب از خوشه ها به عنوان یک درخت نشان داده می شود که ریشه ی درخت خوشه ی منحصر به فردی است که تمام نمونه های را جمع می کند.
#Dbscan
خوشه ها را به عنوان مناطق با تراکم بالا که از مناطق با تراکم پایین جدا شده اند نشان می دهد.
لینک [کد](https://github.com/shahrzadav/clustering4) مناولیه در گیت هاب.
لینک [کد](https://github.com/shahrzadav/AIProject.git) اصلیphase3) فاز سوم در گیت هاب.
لینک [کد](https://github.com/shahrzadav/phase4) فاز چهارم در گیت هاب.
# آزمایش‌ها
ارزیابی عملکرد الگوریتم ها ی خوشه بندی به سادگی شمارش تعداد خطاها یا prescision و recallدقت[^15] و یادآوری[^16] الگوریتم خوشه بندی نیست.
در خود کتابخانه ی 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$
به دست می آید
که در این رابطه داریم :
$$D(c_i,c_j) = \min_{x\in{c_i}, y\in{c_j}} \lbrace d(x,y) \rbrace$$
و
$$Diam(c_i) = \max_{x,y\in{c_i} }\lbrace(x,y)\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]: Finding Similar Documents
[^2]:Organizing Large Document Collections
[^3]:document retrieval
[^4]:Duplicate Content Detection
[^5]: Recommendation System
[^6]: Search Optimization
[^7]:Term Filtering
[^8]:document frequency
[^9]:Stemming
[^10]:Graph Preprocessing
[^11]:term frequency
[^12]:affinity propagation
[^13]:MeanShift
[^14]:Hierarchical
[^15]:precision
[^16]:recall
# مراجع
+ [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][م.ایمانی، خوشه‌بندی متون فارسی، پایان‌نامه کارشناسی، داشگاه علم و صنعت ایران، ۱۳۹۱](http://bayanbox.ir/id/8155819707974834975)
+ [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