رویه‌های خوشه‌بندی سند

رویه‌های خوشه‌بندی سند

خوشه‌بندی سند کاری مشکل در حوزه متن کاوی است و این مشکلیش دلیلش بُعد بالا بودن سند متنی است. الگوریتمی کارا لازم است که بتواند از بس خوشه‌بندی بعد بالا بر بیاد. خوشه‌بندی سند نقش مهمی در برنامه‌های کاربردی مبتنی بر وب و داده متن کاوی مانند خوشه‌بندی کارای نتایج جستجو، ناوبری، کشف مرور و بازیابی کارا بازی می‌کند.

رویه‌های استاندارد خوشه‌بندی سند شامل گام‌های زیر است:

۱: پیش‌پردازش: اسناد برای خوشه‌بندی شدن در یک فرمت ساختار نیافته قرار دارند، بنابراین بعضی از گام‌های پیش‌پردازش برای اجرا شدن قبل از شروع خوشه‌بندی فعال لازم است. پیش‌پردازش شالم توکن‌سازی، استمینگ کلمات سند، و حذف استاپ وردها است.

توکن سازی به معنای برچسپ گذاری کلماتی جایی هر توکن به یک کلمه در سند ارجاع داده می‌شود.

چون می‌خوام سریع برم انگلیسی میزارم

استیمینگ: درگیر تبدیل انواع شکل کلمات مبتنی بر ریشه کلمه است. برای مثال کامپیوتینگ و کامپوتد هر دو به ریشه کلمه کامپوت استیم می‌شوند. استیمینگ یعنی زدن شاخ و برگ کلمه و رسیدن به ریشه‌اش. الگوریتم پورتر تکنیک رایج در زمینه استیمینگ زبان انگلیسی است. اسنوبول ابزاری رایج است که از این الگوریتم استفاده می‌کند.

حذف استاپ وردها: استاپ وردها کلماتی هستند که باعث تمایز سندی از سند دیگر نمی‌شوند، یعنی چه حذف بشوند چه نشند تمایز ایجاد نمی‌کنند. این‌ها مقالات پایه، گزاره‌ها و ضمایری هستند که معمولا مکررا در سند رخ می‌دهند. مانند کلمه These

ایده: یک هو میشه و از همین استاپ وردها برای بازیابی استفاده می‌کنن …. بعید نیست

انتخاب ویژگی و مدل ارائه سند:

اسناد باید به شکلی مناسب برای خوشه‌بندی ارائه شوند. ارائه‌های رایج برای این کار «مدل فضای بردار» است که با اسناد به عنوان بسته‌هایی از کلمات، و از کلمات به عنوان سنجه‌ای برای یافتن شباهت بین کلمات استفاده می‌کند. در این مدل هر سند در نقطه‌ای در فضای بردار ام بعدی است که این بعد برابر تعداد عبارت‌های سند است. هر مولفه این بردار یک عبارت در سند را نشان می‌دهد. مقدار هر مولفه وابسته به درجه روابط بین عبارت‌های مرتط و سند مربوطه است.

The most common term weighting scheme to measure these relationship

یعنی اینکه طرح وزن‌دهی عباررت رایج‌تر برای سنجیدن این رابطه فرکانس عبارت (تی اف) و tf-idf که هر اختصار(Term Frequency-Inverse Document Frequency) است.

محاسبه tf-idf به شرح زیر است.

https://screenshots.firefoxusercontent.com/images/795627c3-8479-4528-9e6e-b5a435f3538b.png

حاشیه: این ویژگی‌ رویایی اسکرین شاپ فایرفاکس که به نسخه بتاش الان ارائه شده، اما بعد از یک مدت روز این عکس و فرمول حذف می‌شه

در این فرمول، ان آی جی فرکانس عبارت (برای مثال اینکه چه تعداد عبارت تی جی در سند آی وجود دارد)، ان جی تعداد اسناد که عبارت تی جی در آن وجود دارد نمایش می‌دهد. عبارت آخر لگاریتم ان!انجی ضریب آی دی اف است و برای وزن کلی عبارت تی جی استفاده می‌شود. چندین مطالعه  مدل فضای بردار را برای ارائه اسناد نشان دادند.

حالا گام سوم

۳: انتخاب سنجش شباهت

چندین سنجش شباهت برای محاسبه سنجش شباهت میان اسناد وجود دارد که مکررا برای خوشه‌بندی اسناد استفاده می‌شود و در زیر آمده است:

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

 

در اینجا ام پی به توان ۲ ام جی: دات پروداکت دو بردار سند است. |.| ایندکس طول اقلیدسی این بردار است. زمانی که اسناد با هم یکی هستند کسینوس برابر ۱ است. اگر اسناد هیچ شباهتی با هم نداشته باشند کسینوسشان برابر ۰ است.

ضریب ژاکارد: مقایسه وزن مجموع عبارت‌های به اشتراک گذاشته شده با مجموع وزن عبارت‌هایی که در هر دو سند هستند اما عبارت‌های به اشتراک گذاشته شده نیستند. برای دو سند آ و بی ضریب ژاکارد با فرمول زیر محاسبه می‌شود:

گام چهارم: برنامه کاربردی الگوریتم خوشه بندی:

این برنامه مبتنی بر سنجه‌ها و الگوهای ارائه داده خوشه‌ها را تولید می کند، چندین الگوریتم خوشه‌بندی برای خوشه‌بندی اسناد ارائه شده‌اند که در بخش‌کارهای قبلی ارائه شده‌اند

۵: ارزیابی کلاستر یا خوشه‌بند

این تکنیک خوشه‌بندی پست است که کیفیت نتایج پایانی خوشه‌ها را تایید می‌کند. چندین سنجه ارزیابی برای تایید کیفیت خوشه‌بندی موجود است. معیار تایید می‌تواند خارجی یا داخلی باشد. سنجه معیار خارجی کاراییش به وسیله تطابق ساختار خوشه با بعضی از دانش خارجی مانند انتروپی،  اف سنجه، پوریتی (خلوص) و اکسریسی (دقت) است.  به وسیله تطابق ساختار خوشه با دانش قبلی

سنجه داخلی: سنجیدن خوشه‌ها بدون مراجعه به دانش خارجی. سنجه داخلی از مسئله به مسئله دیگر متفاوت است. برای مثال درجه به دست آمده از افراز یک الگوریتم خوشه‌بندی به وسیله ماتریس مجاورت تنظیم می‌شود. بعضی از ایندکس‌های داخلی رایج برای خوشه‌بندی سند در مطالعات علمی موجود است.

تعدادی از سنجه های خارجی در زیر آمده‌اند:

الان حال زیاد نوشتن ندارم فقط جا برای اضافه کردن بعد در آینده قرار می‌دهم

Purity:

Each cluster is assigned to the class which is most frequent in the cluster, and then the accuracy of this assignment is computed by counting the number of correctly assigned documents and dividing by N. Formally Purity is calculated as below:

Where Ω = {ω۱,ω۲, … ,ω۱ } is the set of clusters and C = {c1, c2,…, cj} is the set of classes. ωk is the set of documents in ωk and cj is the set of documents in cj. High purity is can be easily achieved when the number of clusters is large; purity is 1 if each document gets its own cluster.

 Accuracy:

Random Index: is the fraction of clusters that are correct (i.e. it measures the percentage of decisions that are correct) [38, 42] and depicts the fraction of clusters in the dominant category. In [38] accuracy has been used as a validation measure as follows.

Where nrr is the number of documents belonging to the category Lr a dataset, k is the total number of clusters.

F-Measure:

: It is related to the Precision and Recall measure which are widely used as information retrieval metrics [58]. For cluster j and class i:

where nij is the number of members of class i in cluster j, nj is the number of members of cluster j and ni is the number of members of class i. F-measure is computed using precision and recall as below:

It has been used for validation in numerous researches [38, 58]. In general, the higher the F-measure values, the better is the clustering solution. This measure is advantageous over purity and entropy, in a way that it measures both homogeneity and completeness of a clustering solution.

Entropy:

Entropy: This is an information theoretic measure [42]. Entropy of each cluster j is calculated as below:

Where pij is the probability that a member of cluster j belongs to nclass i. The computation of total entropy for m, a set of clusters is done as the sum of the entropies of each cluster weighted by nj the size of each cluster where the sum is taken over all classes.

Where n is the total number of data points. It has been used as a validation measure in various studies [6, 38]. It examines how the documents in all categories are distributed within each cluster. Entropy is zero if when every cluster contains documents from only a single category [38]. Some other measures are also present in the document clustering literature like NMI (Normalized Mutual Information) [42], Mirkin Metric, Partition Coefficient, Variation of Information and V-Measure.

خوب دیگه این قسمت تموم شد. قسمت بعدی به تکنیک‌های قبلی که در زمینه خوشه‌بندی سند انجام شده را اوورده، که آنها را به پست بعدی محول می کنم.

دیدگاه‌تان را بنویسید: