Document Clustering Based On Ontology and Fuzzy Approach
Subject Areas : Information and Knowledge TechnologyMaryam Amiri 1 , hasan khatan Lo 2
1 -
2 -
Keywords:
Abstract :
Data mining, also known as knowledge discovery in database, is the process to discover unknown knowledge from a large amount of data. Text mining is to apply data mining techniques to extract knowledge from unstructured text. Text clustering is one of important techniques of text mining, which is the unsupervised classification of similar documents into different groups. The most important steps in document clustering are how documents are represented and the measurement of similarities between them. By giving a new ontological representation and a similarity measure, this research focuses on improving the performance of text clustering. The text clustering algorithm has been investigated in three aspects: ontological representation of documents, documents similarity measure, fuzzy inference system to measuring the final similarities. Ultimately, the clustering is carried out by bottom-up hierarchical clustering. In the first step, documents are represented as ontological graph according to domain knowledge. In contrast to keywords method, this method is based on domain concepts and represents a document as subgraph of domain ontology. The extracted concepts of document are the graph nodes. Weight is measured for each node in terms of concept frequency. The relation between documents’ concepts specifies the graph edges and the scope of the concepts’ relation determines the edge’s weight. In the second step, a new similarity measure has been presented proportional to the ontological representation. For each document, main and detailed concepts and main edges are determined. The similarity of each couple of documents is computed in three amounts and according to these three factors. In the third step, the fuzzy inference system with three inputs and one output has been designed. Inputs are the similarities of main concepts, detailed concepts and the main edges of two documents and the output is final similarities of the two documents. In final step, a bottom-up hierarchical clustering algorithm is used to clustering the documents according to final similarity matrix. In order to evaluate, the offered method has been compared with the results of Naïve Bayes method and ontology based algorithms. The results indicate that the proposed method improves the precision, recall, F-measure and accuracy and produces more meaningful results.
فصلنامه علمي- پژوهشي فناوري اطلاعات و ارتباطات ایران | سال پنجم، شمارههاي 17 و 18، پاییز و زمستان 1392 صص: 96- 73 |
|
خوشهبندی اسناد، مبتنی بر آنتولوژی و رویکرد فازی
*مریم امیری *حسن ختنلو
*کارشناس ارشد، دانشگاه بوعلیسینا، گروه کامپیوتر، همدان
**هیئت علمی، دانشگاه بوعلیسینا، گروه کامپیوتر، همدان
تاریخ دریافت: 15/01/1392 تاریخ پذیرش:22/03/1392
چكيده
دادهکاوی، شناسایی و پردازش اطلاعات مفید از اسناد است که اساس آن بر مدل نمایش مفهومی اسناد، محاسبة شباهت بین اسناد و استفاده از آنها در خوشهبندی و دستهبندی اسناد، بازیابی و استخراج اطلاعات استوار است. در این مقاله روش نوینی برای نمایش آنتولوژیکال و مفهومی اسناد به صورت سلسله مراتبی ارائه شده است. با توجّه به آنتولوژی دامنة مورد نظر، گراف مفهومی از سند ایجاد میشود. بر اساس این گراف آنتولوژیکال معیار شباهت متناسبی نیز ارائه شده است که فاصله و شباهت بین اسناد را بر اساس این نوع نمایش مشخص مینماید. در گام سوم سيستم استنتاج فازي با سه ورودي و يک خروجي طراحي شده است. این سیستم بر اساس سه شباهت ورودي، مقدار شباهت نهايي را تخمين ميزند. در نهايت بر اساس ماتريس شباهت اسناد، الگوريتم خوشهبندي سلسله مراتبي پايين به بالا به منظور خوشهبندي اسناد اعمال میشود. براي ارزيابي الگوريتم پيشنهادي، نتايج با نتايج حاصل از روشهاي naïve Bayes ، دو الگوريتم مبتنی بر آنتولوژی و يک الگوريتم آماری مقايسه شده است. نتايج به دست آمده نشان ميدهند که روش پيشنهاد شده مقادير F-measure و Accuracy را بهبود ميدهد. همچنين مقادير FP و Error به ميزان قابل توجّهي کاهش مييابد.
واژههای کلیدی: گراف مفهومی اسناد، ساختار آنتولوژیکال، آنتولوژی، معیار شباهت، ساختار سلسله مراتبی.
مقدمه
با رشد روز افزون اسناد روی وب، نیاز به مدیریت اسناد نیز بیشتر میشود. از نتایج رشد بیش از حدّ اسناد، مشکل بازیابی بیش از حدّ اطلاعات است. حل مشکل بازیابی بیش از حدّ اطلاعات شامل پردازشهایی نظیر جمعآوری اطلاعات، فیلتر کردن اطلاعات، بازیابی اطلاعات، استخراج اطلاعات، خلاصهسازی، خوشهبندی و دستهبندی اسناد است. هدف این پردازشها کمک به کاربران برای یافتن اسناد مورد نیاز آنها است. این پردازشها وظایف اساسی را در زمینة دادهکاوی ایجاد مینمایند ]1[. دادهکاوی، استخراج اطلاعات ضمنی، ناشناخته و مفید، تعریف شده است ]2[.
نویسندة عهدهدار مکاتبات: مریم امیریmaryam_amiri2005_1365@yahoo.com |
دادهکاوی، آنالیز داده از جنبههای مختلف و خلاصهسازی آنها به صورت اطلاعات مفید تعریف شده است.
کاوش اسناد، شناسایی اطلاعات ناشناخته و استخراج آنها از متون است ]3[. کاربردهای متعددی در زمینة بازیابی اطلاعات وجود دارد که یکی از این کاربردها دستهبندی اسناد است. هدف از خوشهبندی1 تقسیم یک مجموعة بدون ساختار از اشیاء به داخل خوشهها است، به گونهای که اشیاء داخل خوشه تا جای ممکن به یدیگر مشابه باشند و از اشیاء داخل خوشههای دیگر متفاوت باشند.
خوشهبندی اسناد یک رویکرد مهم برای سازماندهی بدون سرپرست اسناد، استخراج خودکار موضوعات و بازیابی سریع اطلاعات است. برای مثال، موتورهای جستجوی وب هزاران صفحه را در پاسخ به یک پرسوجو بر میگردانند و کاربر را برای یافتن اطلاعات مرتبط دچار مشکل میسازند. خوشهبندی اسناد میتواند برای گروهبندی خودکار اسناد بازیابی شده به گروههای با معنی استفاده شود. به طور مشابه دستهبندی می تواند از قبل صورت گیرد و پردازش پرس وجو را آسانتر نماید بدین صورت که تنها نزدیکترین خوشهها به پرسوجو، جستجو می شوند ]4[. مدیریت مجموعهای بزرگ از اسناد به تعدادی از خوشهها، تأثیر و کارایی کاربردهای مبتنی بر متون که به سرعت و کیفیت بالایی نیاز دارند را بهبود میبخشد و مکمل خوبی برای موتورهای جستجو که اسناد بسیاری را برمیگردانند است ]5[.
چارچوب این مقاله روشی جدید در تولید یک گراف مفهومی از اسناد بر اساس آنتولوژی دامنة مورد نظر است. بر اساس این نمایش یک معیار اندازهگیری شباهت جدید تعریف شده است تا سطوح مشترک و متفاوت اسناد به طور دقیقتری شناسایی شوند تا در نهایت بتوان دقت روالهای کاوش اسناد مبتنی بر مفهوم و آنتولوژی را بهبود داد.
در ادامة مقاله در بخش 2، مروری بر مدلهای نمایش اسناد و معیارهای شباهت و در بخش 3 به نمایش نوین آنتولوژیکال پیشنهادی پرداخته شده است. بخش 4 به معیار شباهت متناسب با نمایش آنتولوژیکال پرداخته است. سیستم استنتاج فازی در بخش 5 مطرح شده است. ارزیابی روش پیشنهادی، کارهای آتی و نتیجهگیری به ترتیب در بخش های 6 و 7 بیان گردیدهاند.
· مروری بر مدلهای نمایش اسناد و معیارهای شباهت
روشهای بازیابی اطلاعات به دو دستة عمده تقسیم میشوند: روشهای آماری و روشهای معنایی. در روشهای معنایی تا حدّی آنالیز معنایی و نحوی صورت میپذیرد. به عبارت دیگر، سعی بر این است که متون زبان طبیعی که کاربر فراهم کرده است تا حدّی فهمیده شود. در روشهای آماری اسنادی که بازیابی میشوند یا رتبهبندی بالایی دارند، اسنادی هستند که از لحاظ اندازهگیری آماری بررسی میشوند.
در روشهای آماری فرض میشود کلمات میتوانند نمایش معقولی از محتوای اسناد ارائه دهند. هیچ اطلاعی از ترتیب کلمات وجود ندارد. بنابراین به این روشها مدلهای bag of words گفته میشود. البته محتوای واقعی یک سند چیزی غیر از کلمات ظاهر شده است. روشهای آماری به چندین دسته تقسیم میشوند: دودویی2، دودویی بسط یافته3، فضای بردار4 و احتمالاتی5. روشهای آماری اسناد را به چندین کلمه6 تجزیه میکنند. کلمات جمعیتی هستند که شمرده میشوند و به صورت آماری اندازهگیری میشوند. کلمات غالباً متحمّل پیش پردازش میشوند. آنها معمولاً برای استخراج ریشه، ریشهیابی میشوند ]6 [که هدف آن حذف تغییراتی است که به دلیل رخداد حالات مختلف دستوری در یک کلمه ایجاد میشود. روش دیگر پیش پردازش، حذف کلمات مشترک است که توانایی کمی برای جداسازی اسناد مرتبط و غیر مرتبط دارد. بنابراین موتورهای جستجو لیستی از کلمات توقف7 یا نویز تهیّه مینمایند. هر دو پیشپردازش اشاره شده وابسته به زبان هستند. معمولاً اوزان عددی به کلمات موجود در اسناد و پرسوجو نسبت داده میشود. اوزان به یک کلمه مشخص در هر سند تخصیص مییابد. اوزان تخصیص یافته به کلمات، میزان اهمّیت آن نشانه8 را برای محاسبة شباهت بین اسناد مشخص مینماید. بنابراین کلمات یکسان در اسناد مختلف اوزان مختلفی دریافت میکنند.
یک روش معمول نمایش اسناد و اندیسگذاری برای روشهای آماری، نمایش اسناد متنی به صورت مجموعهای از کلمات (عبارات یا n-grams) است. معمولاً کلمات از اسناد استخراج میشوند و در نهایت مجموعهای از کلمات در دسترس میباشند که کل مجموعة اسناد را نمایش میدهند. این مجموعه فضایی را تعریف میکند که هر کلمة مجزا، یک بعد محسوب میشود ]7[. به هرکدام از کلمات موجود در سند، وزنی اختصاص مییابد که اهمّیت آن کلمه را برای جدا کنندگی سند مشخص مینماید. معمولاً در این حالت محتوای سند غیر از کلمات داخل بردار است. کارایی و سادگی این روش باعث شده است که اکثر موتورهای جستجو از این روش استفاده نمایند. واسط کاربری موتورهای جستجو، اغلب کلمات جستجو را در اسناد بازیابی شده با رنگ روشن نمایش میدهد که نشان دهندة روش سادة تناظر کلمات است.
روش دیگر نمایش اسناد، نمایش آنها به صورت مجموعهای از نشانهها است. پایهترین روش استفاده شده برای نمایش منابع متنی، مدل فضای بردار9 (VSM) است. در این مدل هر سند با یک بردار مشخص میشود. هر درایه از بردار منعکس کنندة یک مفهوم خاص است. مقدار هر عنصر اهمّیت آن نشانه در نمایش معنایی سند است. پایگاه دادهای شامل سند است که با ترم10 توصیف شدهاند، بنابراین به صورت یک ماتریس نمایش داده میشود. هر سطر از ماتریس متناظر با بردار اسناد است. بدین گونه عناصر ماتریس، فرکانس وزنداری است که نشانه در سند اتفاق میافتد. در حالت دیگر از VSM، ستونهای ماتریس بردار اسناد هستند و سطرهای ماتریس نشانهها میباشند. مضمون معنایی پایگاه داده در فضای ستونهای ماتریس گنجانده شده است به این معنا که بردارهای اسناد، آن مضمون را ایجاد کردهاند. در این نوع نمایش هر نشانه یک بعد مستقل است و در این فضا میتوان هر سند را به صورت نقطهای نمایش داد ]8[. شباهتها یا تفاوتهای بین اسناد را میتوان فاصلة بین نقاط تعریف نمود. در این نوع نمایش، شباهتها بر اساس ظهور ترمهای مشترک اندازهگیری میشوند یعنی اسنادی که ترمهای مشترک بیشتری دارند شبیهتر از اسنادی هستند که ترمهای مشترک کمتری دارند.اگرچه غالباً نمایش مبتنی بر مجموعة کلمات برای خوشهبندی اسناد استفاده میشود، این روش نامناسب است به این دلیل که ارتباط بین کلماتی که با هم تکرار نمیشوند را نادیده میگیرد. بدیهی است که جملات بامعنی از کلمات بامعنی تشکیل شده است و هر سیستمی که بخواهد کار پردازش زبان طبیعی (NLP) را شبیه انسان انجام دهد باید دربارة کلمات و معانی آنها اطلاعات داشته باشد. این اطلاعات معمولاً از طریق فرهنگ لغتها به خصوصWordNet ]9[ فراهم میشود. نمایش مرسوم متون، مبتنی بر کلماتی هستند که در اسناد اتفاق افتادهاند و روشهای دستهبندی، شباهت بین بردارها را محاسبه مینماید. ممکن است تعدادی از اسناد با اینکه کلمة مشترکی ندارند، شامل اطلاعات معنایی مشابه باشند. برای حلّ چنین مشکلی استفاده از مدل مبتنی بر مفاهیم ]10[ با استفاده از آنتولوژی ضروری است. روشهای زیادی برای تعریف آنتولوژی وجود دارد. در ]11[، آنتولوژی یک چارچوب مفهومی برای تعریف کلاسهای پایه از موجودیتهای دامنة دانش میباشد، رابطة این نمونهها با یکدیگر و مدیریت مفاهیم برحسب مفاهیم سطوح بالاتر همان طبقهبندی در طبیعت است. اصطلاح آنتولوژی برای ارجاع به محدّودهای از منابع مفهومی و زبانی برای طبقهبندی و نمایش رسمی دانش که ممکن است استنتاج اتوماتیک و یا انواع خاصی از استدلال را پشتیبانی کند، استفاده شده است. مطابق با تعریف، آنتولوژی مجموعهای از مفاهیم و روابط بین آنها است که یک دیدگاه خلاصه از دامنه موضوع را فراهم مینماید ]11[. استفاده از آنتولوژی در دادهکاوی برای خوشهبندی و دستهبندی اسناد و یادگیری الکترونیک است. شکل1 آنتولوژی مردم را نشان میدهد که شامل مفاهیم، نمونهها، روابط مابین آنها است. در ]12[ یک نمایش مفهومی مبتنی بر آنتولوژی ارائه شده است که معنی هر متن را به یک گراف بدون حلقة مستقیم نگاشت میکند. ]13[ پس از ساختن آنتولوژی دامنة مورد نظر، سیستم با مجموعهای از اسناد آموزش داده میشود. جملات برای استخراج POS (part of speech) و Chunk برچسبگذاری میشوند. پس از آن کارشناسان دامنة کلمات را به مفاهیم آنتولوژی نگاشت میکنند. به کمک این مجموعة آموزشی میتوان نمایش مفهومی مجموعة اسناد تست را نیز ساخت.
[1] . Clustering
[2] . Boolean
[3] .Extended Boolean
[4] .Vector Space
[5] .Probabilistic
[6] .Term
[7] .Stop Word
[8] .Token
[9] .Vector Space Model
[10] . Term
شکل 1- نمایش آنتولوژی شامل مفاهیم، نمونهها و روابط ]14[
|
روشهای مهمی برای محاسبة شباهت بین دو سند پیشنهاد شده است. یکی از متداولترین روشها ضرب داخلی دو بردار است. ضرب داخلی تابع کوسینوسی است که در رابطة 1 نشان داده شده است
| (1) |
ضرب داخلی بیان کنندة زاویة بین آنها است. اگر حاصل یک باشد، زاویه صفر درجه است و بیشترین تطابق در این حالت وجود دارد. اگر حاصل صفر شود زاویة بین آنها نود درجه است و کمترین تطابق وجود دارد. این اندازهگیری مشکلات خاصی برای اسناد با طول بلند ایجاد میکند.
به جز ضرب داخلی یا شباهت کسینوسی، توابع دیگری نیز برای اندازهگیری شباهت وجود دارد، خانوادهای از فاصلهها ]15[ به صورت رابطة 2 بیان شدهاند. این تابع، فاصله را بر حسب اجزای دو سند محاسبه مینماید. جدا از این معیارهای فاصله، توابعی هستند که تنها تعداد کلمات مشترک و تعداد کلمات غیر مشترک را شمارش میکنند. یکی از این توابع معروف ضریب Dice است ]16[ که در رابطة 3 نشان داده شده است:
| (2) |
| (3) |
که مقدار تعداد کلمات مشترک بردارهای اسناد است،تعداد کلمات با فرکانس غیر صفر در اولین سند و تعداد کلمات با فرکانس غیر صفر در دومین سند است. مخرج کسر نوعی نرمالسازی است. یک تابع معمول دیگر برای اندازهگیری شباهت، ضریب Jaccard است ]16[. این تابع شباهت در رابطة 4 ذکر شده است:
| (4) |
| (4) |
که تعداد کلمات مشترک اسناد و است و تعداد کل کلمات مجزا در فضای برداری و تعداد کلمات مجزایی هستند که نه در و نه در است. بنابراین مخرج کسر تعداد کلماتی را نشان میدهند که در یا در و یا در هر دو رخ میدهند. توابع محاسباتی بالا برای محاسبة شباهت اسناد، فرض میکنند که مجموعة اسناد ایستا هستند. در حالت "routing"، اسناد دارای یک جریان ورودی متغیر هستند و هر سند باید برای یکی ازگروه متناظر با موضوع از پیش تعریف شده، "routed" (مسیریابی)، شود.
محاسبة شباهتها در خوشهبندی به طور مکرر انجام میگیرد. بنابراین با سریع انجام دادن آن میتوان به کل روال سرعت بخشید. تعیین شباهتها نیز بستگی به تعداد کلمات به کار رفته دارد، پس با کاهش تعداد کلمات در نمایش میتوان سرعت را افزایش داد ]17[. روشهای پیچیدهای برای کاهش تعداد کلمات وجود دارد. در ]18[ روشهای انتخاب نشانه، مبتنی بر تغییرات فرکانس نشانه، در متن پیشنهاد شده است. در ]19[ روال کاهش نشانهها افکنش1 نامیده میشود که فضای برداری به یک فضای جدید با تعداد ابعاد کمتر تصویر میشود. همچنین دادههای متنی مشکل بزرگی دارند: مشکل ابعاد زیاد. در فضاهایی با ابعاد بالا، فاصلة بین هر جفت از نقاط تقریباً برای انواع گوناگون توزیع دادهها و توابع فاصله یکسان است ]20[ که این انگیزهای برای کاهش ابعاد دادة ورودی است. تعدادی از روشهای انتخاب ویژگی، به جستجوی زیر مجموعههای ویژگی و ارزیابی هر کدام از این مجموعهها با استفاده از معیارهایی پرداختهاند ]21[. همبستگی در میان ابعاد، اغلب مخصوص محل و موقعیت داده است، به این معنی که تعدادی از نقاط داده با یک مجموعه از ویژگیها و سایر آنها با ویژگیهای متفاوت وابسته هستند. یعنی در فضایی با ابعاد بالا شبیه دادههای متنی، هر خوشه ساختار زیر فضایی خاص خودش را دارا است.
یادگیری با هر دو دادة برچسب خورده و بدون برچسب، یادگیری نیمه سرپرست نامیده میشود. این روش اخیراً با توجّه زیادی مورد مطالعه قرار گرفته است و اساساً به صورت یک روش استخراج اطلاعات در دادههای بدون برچسب، برای بهبود کارایی مدل خوشهبندی استفاده شده است ]5[. در نمایش گرافی و آنتولوژیکال اسناد روشی که برای اندازهگیری شباهت به صورت معمول استفاده شده است بر اساسعبارت سادهی است که در آن تعداد مفاهیم مشترک و مجموع کل مفاهیم دو سند است ]13[.
· نمایش نوین آنتولوژیکال
روش پیشنهادی به تولید یک گراف وزندار آنتولوژیکال میپردازد. با توجّه به مضمون و مفهوم اسناد، مفاهیم اصلی شناسایی میشوند و با توجّه به اهمّیتشان در سند اوزانی دریافت میکنند. سپس ساختار مفهومی سند شناسایی میشود و مفاهیم شناسایی شده در مرحلة قبل با توجّه به این ساختار با یالهای جهتدار و وزندار به یکدیگر متصل میگردند. در ادامه روش پیشنهادی با جزئیات بیشتری مطرح میشود.
1. پیش پردازش اولیه
یک پاراگراف مجموعهای از چند جمله است که راجع به یک مفهوم خاص بحث مینماید. اساس روش پیشنهادی با توجّه به این نکته است. در مرحلة پیش پردازش، پاراگرافها واحدّهای پردازشی هستند. ابتدا متن به پاراگرافهایش تجزیه میشود. سپس برای هر پاراگراف عملیات پیشپردازشی نظیر نشانهگذاریی2، حذف کلمات نویزی و ریشهیابی صورت میگیرد. در نهایت برای هر پاراگراف دو مجموعه از نشانهها نگهداری میشود: مجموعة نشانههای اصلی و مجموعة ریشهیابی شدة نشانههای اصلی.
2. نگاشت کلمات به مفاهیم آنتولوژی
مسئلهاي که هميشه به عنوان يک چالش مطرح بوده است چگونگي استخراج اطلاعات از آنتولوژی است. يکي از روشهايي که ميتوان از آن استفاده کرد اين است که به طور مستقيم با استفاده از يک زبان پرسوجوي آنتولوژی، اطلاعات را از آنتولوژی استخراج نمود. روش دوم تبديل آنتولوژی به نوعي پایگاه دادهاي مانند RDBMS است تا بتوان با استفاده از زبانهاي پرسوجو، اطلاعات را از اين انباره بيرون کشيد. در الگوریتم پیشنهادی از روش دوم يعني نگاشت آنتولوژی به پايگاه داده براي استخراج اطلاعات استفاده شده است. به اين ترتيب که آنتولوژی از يک فايل OWL استخراج میشود و سپس در يک پايگاه داده رابطهاي ذخيره میشود.جدول ایجاد شده به چندین جدول کوچکتر شامل کلاسها، نمونهها، ماتریس کلاس- کلاس و ماتریس کلاس- نمونه تبدیل میشود. جدول کلاس، شامل مفاهیم موجود در گراف آنتولوژی است. جدول نمونهها، تمامی نمونههای موجود در آنتولوژی را در بر میگیرد. شکل 2 نمونهاي از يک گراف آنتولوژی را با چهار مفهوم نمايش ميدهد که در آن گرههاي ،،، نمايانگر مفاهیم آنتولوژی هستند. ارتباط بين کلاسها با ها نمايش داده شده است. براي تجزيه و تحليل آنتولوژی ميتوان گراف آنتولوژیکال را توسط يک ماتريس مجاورت3 با سطر و ستون مساوي نمايش داد که در آن سطرها و ستونها نمايانگر نودهاي گراف يا همان کلاسهاي آنتولوژی هستند. اعداد قرار گرفته در هر درایه ماتريس نيز نشان دهنده تعداد ارتباطات بين کلاسهاي مربوطه خواهند بود ]22[.با استفاده از دیکشنری معکوس4 جدول دیگری از مفاهیم – کلمات ساخته شده است. به ازای مفاهیم موجود در آنتولوژی، صد کلمة مرتبط با هر کدام از این مفاهیم از دیکشنری یافت میشود و در پایگاه داده ذخیره میشوند. کلمات استخراج شده از دیکشنری مجدداً توسط کارشناسان دامنه بررسی میشوند و مرتبطترین کلمات برای هر مفهوم انتخاب میشوند.برای نگاشت کلمات به مفاهیم، با توجّه به مفاهیم موجود در آنتولوژی، تا چندین سطح از مفاهیم بررسی میشوند. در ابتدا مفاهیم مستقیم بررسی میشوند. منظور از مفاهیم مستقیم مفاهیمی هستند که عبارت (نشانه) موجود در سند، مفهومی در آنتولوژی است. به ازای مفاهیم مستقیم تا چند سطح از فرزندان و پدران مفهوم یافت شده نیز در نظر گرفته میشوند. به این مفاهیم، مفاهیم غیرمستقیم نوع 1 گفته میشود.
شکل 2- نمونهای از یک گراف آنتولوژی
اگر عبارت جزء مفاهیم مستقیم نبود به عنوان یک نمونه بررسی میشود که در این صورت تا چند سطح از پدران این نمونه نیز به مجموعة مفاهیم غیرمستقیم-1 (مفاهیم غیرمستقیم نوع 1) اضافه میشوند. در صورتی که عبارت مورد نظر مفهوم مستقیم یا نمونه نبود مفاهیم غیرمستقیم نوع 2 (مفاهیم غیرمستقیم-2) بررسی میشوند. این نوع مفاهیم غیرمستقیم از جستجو در جدول مفاهیم- کلمات حاصل میشوند. برای این مفاهیم نیز پدران و فرزندان تا چند سطح به مفاهیم غیرمستقیم-1 اضافه میشوند. در نهایت برای هر پاراگراف مجموعهای از مفاهیم مستقیم و غیرمستقیم نوع 1و2 با تعداد دفعات ارجاع به آنها موجود است. برای مفاهیم غیرمستقیم-1 فاصله تا مفهوم مستقیم و همچنین تعداد دفعاتی که به عنوان والد یا فرزند انتخاب شده است نیز در نظر گرفته میشود.
3. رفع ابهام از مفاهیم
در بخش قبل به مفاهیم غیرمستقیم نوع 1و2 اشاره شد. مشکلی که ممکن است در رابطه با این مفاهیم پیش آید ابهام است. یک مفهوم مستقیم ممکن است چندین والد یا فرزند به عنوان مفهوم غیرمستقیم نوع 1 داشته باشد. همچنین یک کلمه ممکن است متناظر با چندین مفهوم باشد. در کلیة این حالات مشکل ابهام پیش میآید. برای این مفاهیم تعداد دفعاتی که به صورت مبهم شناسایی شدهاند نگهداری میشود. پس از استخراج تمام مفاهیم یک پاراگراف، باید مفاهیم مبهم بررسی شوند و مناسبترین آنها باقی بمانند. روشی که برای رفع ابهام در این الگوریتم پیشنهاد شده است بدین ترتیب است که با توجّه به سایر مفاهیم مستقیم و غیرمستقیم غیرمبهم هر پاراگراف، مفاهیم مبهم پاراگراف رفع ابهام میشوند و مناسبترین مفاهیم انتخاب میشوند. روش رفع ابهام بدین ترتیب است که ابتدا اهمّیت مفهوم مبهم در پاراگراف مزبور مشخص میشود. اگر تعداد ارجاعات بدون ابهام به یک مفهوم از 7/0 کل تعداد ارجاعات کمتر باشد، آنگاه از این مفهوم باید رفع ابهام کرد. در رابطه 5، اهمّیت مفهوم مبهم را مشخص میکند. اگر مفهومی باشد که برچسب مبهم داشته باشد، آنگاهکل تعداد دفعات ارجاع به این مفهوم، تعداد دفعاتی که این مفهوم به صورت مبهم شناسایی شده و فاصلة این مفهوم غیرمستقیم مبهم تا مفاهیم مستقیم اصلی است.
| (5) |
اگر مفهومی کاملا مبهم باشد یعنی ، به آن مقدار حدّاقلی غیر از صفر نسبت داده میشود. سپس این مفهوم نسبت به سایر مفاهیم مستقیم و غیرمستقیم غیرمبهم ارزیابی میشود. رابطة 6 ارزیابی نسبت به مفاهیم مستقیم را نشان میدهد که در آن منظور از مفهوم مستقیم و مفهوم غیرمستقیم مبهم است. تابع فاصلة بین دو مفهوم در آنتولوژی را مییابد و تابع تعداد مسیرهای ممکن بین دو مفهوم را مشخص مینماید. رابطة 6 برای تمامی مفاهیم مستقیم محاسبه میشود و نتایج با یکدیگر جمع میشوند.
| (6) |
رابطة 7 ارزیابی مفاهیم مبهم نسبت به مفاهیم غیرمستقیم غیرمبهم را نشان میدهد. که مفهوم غیرمستقیم غیرمبهم و مفهوم غیرمستقیم مبهم است. این رابطه برای تمامی مفاهیم غیرمستقیم غیرمبهم محاسبه میشود و نتایج با یکدیگر جمع میشوند.
نتایج حاصل از رابطة 6 و 7 با یکدیگر جمع میشوند، اگر مقدار به دست آمده از یک آستانه بیشتر بود از این مفهوم رفع ابهام میشود در غیر این صورت مفهوم مورد نظر حذف میشود. اگر نسبت مفاهیم رفع ابهام شده به کل مفاهیم مبهم پاراگراف از یک آستانه مشخص کمتر باشد مفاهیم غیرمبهم یک پاراگراف قبل و یک پاراگراف بعد نیز بررسی میشوند و راجع به مفاهیم مبهم پاراگراف فعلی تصمیم گرفته میشود. این امر سبب میشود، اگر پاراگراف فعلی از لحاظ مفاهیم غیرمبهم ضعیف باشد مفاهیم بیسبب حذف نشوند و با دقت بیشتری بررسی شوند.
| (7) |
4. استخراج ساختار سلسله مراتبی مفهومی اسناد
پس از انجام مراحل فوق در نهایت برای هر پاراگراف مجموعهای از مفاهیم مستقیم و غیرمستقیم و اطلاعاتی راجع به آنها در دسترس است. مرحلة آخر وزندهی به مفاهیم و ترسیم شمای گرافی سند است. به دلیل اهمّیت مفاهیم مستقیم و مفاهیم غیرمستقیم-2 در مضمون سند این مفاهیم با ضرایب بیشتری نسبت به سایر مفاهیم در نظر گرفته میشوند. برای وزندهی به مفاهیم سند، تعداد ارجاعات هر مفهوم به تعداد کل ارجاعات نوع مفهوم مورد نظر تقسیم میشود و برای هر مفهوم با توجّه به نوع آن، وزن منحصر به فردی در نظر گرفته میشود. پس از آن مفاهیم مستقیم و نمونههایی که در سند بودهاند انتخاب میشوند و به کمک ماتریسهای کلاس- کلاس و کلاس- نمونه، روابط بین آنها استخراج میشود و ماتریس روابط نظیر هر سند ایجاد میشود. بنابراین نودهای گراف و اوزان مربوط به آنها ایجاد میشود.
به منظور ترسیم یالهای گراف و محاسبة اوزان آنها، کلیة مفاهیم غیرمستقیم-2 به صورت مفهوم مستقیم در نظر گرفته میشوند و مفاهیم غیرمستقیم-1 که همنام با مفاهیم مستقیم هستند، بررسی میشوند. اگر این مفاهیم غیرمستقیم همنام به عنوان فرزند انتخاب شده باشند بنابراین جهت یالها باید از مفاهیم مستقیم پدر این مفهوم به مفهوم مستقیم مورد نظر باشد. اگر مفاهیم غیرمستقیم به عنوان پدر انتخاب شدهاند، جهت یالها باید از فرزندان مستقیم این مفهوم به مفهوم مربوطه باشند. برای محاسبة اوزان نظیـر یالهای ترسیم شده در گراف، از ماتریس روابط
نظیر سند استفاده میشود. اوزان مفاهیم غیرمستقیم همنام، در تعداد رابطة بین دو مفهوم مورد نظر ضرب میشود و بر تعداد ارتباط گره مورد نظر با پدرانش (یا فرزندانش) تقسیم میشود. همچنین متناسب با فاصلة مفاهیم همنام غیرمستقیم، ضریبی در نظر گرفته میشود. در رابطة 8 هدف بررسی پدران با فاصلة یک است. اگر مفهوم مستقیمی باشد که همنام با آن، مفهوم پدر غیرمستقیم با فاصلة یک نیز وجود داشته باشد، برای تمامی فرزندان آن،، یالهای به به صورت زیر محاسبه میشود که بیانگر تعداد فرزندان مفهومبا فاصلة یک است، وزن مفهوم غیرمستقیم همنام با مفهوم اصلی است و بیانگر تعداد ارتباط بین و است. ضریب را نیز میتوان با توجّه به فاصلة مفاهیم غیرمستقیم مقدار داد. رابطة 8 برای فرزندان نیز به طریق مشابه نوشته میشود.
| (8) |
در نهایت پس از محاسبة حالات مختلف از فرزندان و پدران با فواصل متفاوت، گراف جهت داری تولید میشود که نودهای آن مفاهیم مستقیم هستند. اوزان این مفاهیم و یالهای مربوطه نیز از طریق توضیحات بیان شده و رابطة 8 محاسبه شدهاند. گراف ایجاد شده برای هر سند به صورت ماتریس در پایگاه داده ذخیره میشود تا در مراحل محاسبة ماتریس شباهت بین اسناد و کاوش آنها، به راحتی قابل بازیابی باشند.
به عنوان یک مثال، شکل 3 یک سند دلخواه در زمینة هتل است. از آنتولوژی دامنه مورد نظر جداول و ماتریسهای مذکور ساخته شدهاند و طبق روال توضیح داده شده، شکل 4 گراف آنتولوژیکال تولید شده را نمایش میدهد که شامل مفاهیم، اوزان و یالهای آنها است. با توجّه به اوزان مفاهیم، کلیت سند راجع به مفاهیم hotel و luxury hotel است. با توجّه به این اوزان میتوان به سادگی مفاهیم کلی و پراهمّیت و مفاهیم جزئی را مشخص نمود. به عبارت دیگر این اوزان را میتوان همانند درجة عضویت فازی تفسیر نمود که سند با چه درجه عضویتی به هر مفهوم متعلق است. در مورد اوزان و جهات یالها نیز میتوان چنین تفسیری ارائه داد. در واقع با توجّه به آنتولوژی موجود، شمای گرافی سند، زیر مجموعهای از همان آنتولوژی است که اوزان یالها و نودها در آنتولوژی اصلی 0.100 است اما در اسناد با توجّه به مضمون و مفهوم سند این اوزان مقادیر مختلفی میگیرند.
شکل 2- نمایش یک سند در زمینه هتل
· معیار شباهت متناسب با نمایش آنتولوژیکال
مهمترین گامها برای بهبود روالهای کاوش اسناد، نمایش مفهومی مناسب و معیار شباهت متناسب با این نمایش است. هرچه معیار شباهت توانایی بیشتری برای تقریب سطوح اختلاف و تشابه بین اسناد داشته باشد، مناسبتر و کاربردیتر است. روش آنتولوژیکال پیشنهادی، دارای چهار جزء با معنی است که برای تعیین شباهت و تفاوت بین اسناد کلیدی میباشند: مفاهیم و اوزان هر مفهوم، یالها و اوزان منتسب به هر یال. معیار پیشنهاد شده برای مفاهیم و یالها به صورت مجزا محاسبه میشود و خروجی آن ماتریسهای شباهت مجزا برای مفاهیم و یالها است. در مراحـل بعد مبتـنی بر ماتریس شبـاهت محاسبـه شده و با
[1] . Projection
[2] .Tokenization
[3] . Adjacency Matrix
[4] .Inverse Dictionary
شکل 3- گراف آنتولوژیکال سند در شکل (3)
|
استفاده از سیستم استنتاج فازی، قوانین فازی و یک الگوریتم خوشهبندی مناسب میتوان نتایج کاوش اسناد را بهبود داد.
معیار پیشنهادی، درجة عضویت، اولویت و اهمّیت هر مفهوم را در نظر میگیرد و براساس مفاهیم مشترک (یالهای مشترک) هر دو سند میزان شباهت بین دو سند را تقریب میزند. برای هر مفهوم مشترک در هر دو سند، دو وزن و محاسبه میشود و در نهایت به کمک این اوزان میزان شباهت دو سند تقریب زده میشود. رابطههای 9 و 10 به ترتیب محاسبه اوزان و را بیان مینمایند که وزن مربوط به تفاوت اولویت و اهمّیت مفاهیم و مربوط به اختلاف اوزان مفاهیم مشترک دو سند است. در رابطة 9 مفهوم مشترک در سند است، اولویت مفهوم را در سند مشخص مینماید، و دو سند دلخواه هستند که هدف محاسبه شباهت بین آن دو است و حدّاکثر اختلاف اهمّیت مفاهیم مشترک بین دو سند تعریف شده است. در رابطة 10 وزن مفهوم مشترک در سند است.
| (9) |
| (10) |
رابطة 11 بیانگر معیار شباهت برای اندازهگیری شباهت بین دو سند و است. در این رابطه، بیانگر تعداد مفاهیم مشترک دو سند است، نماد بیانگر اندازة مجموعه (تعداد مفاهیم) بوده و است.
| (11) |
· سیستم استنتاج فازی
سيستمهاي فازي، سيستمهاي مبتني بر دانش يا قواعد هستند؛ قلب يك سيستم فازي يك پايگاه دانش است كه از قواعد اگر ـ آنگاه فازي تشكيل شده است. يك قاعده اگر ـ آنگاه فازي، يك عبارت اگر ـ آنگاه است كه بعضي كلمات آن به وسيلة توابع عضویت پيوسته مشخص شدهاند. موتور استنتاج فازي، اين قواعد را با يك نگاشت از مجموعههاي فازي در فضاي ورودي به مجموعههاي فازي و در فضاي خروجي بر اساس اصول منطق فازي تركيب ميكند.
سیستم استنتاج فازی متشکل از سه بخش فازیسازی، موتور استنتاج فازی و غیرفازیسازی است. در بخش فازیسازی یک متغیر crisp با استفاده از توابع عضویت تعریف شده به یک متغیر زبانی تبدیل میشود. در بخش دوم با استفاده از قوانین فازی (قوانین اگر-آنگاه) مقدار خروجی فازی تولید میشود. بخش غیرفازیسازی مقدار خروجی فازی از موتور استنتاج را با استفاده از توابع عضویت تعریف شده، به یک مقدار crisp تبدیل مینماید. این روند در شکل 5 نشان داده شده است. سیستم استنتاج طراحی شده در این بخش دارای سه ورودی است: میزان شباهت مفاهیم کلی، میزان شباهت مفاهیم جزئی و میزان شباهت یالهای موجود در شمای گرافی اسناد. مفاهیم جزئی و کلی هر سند به صورت نسبی مشخص میشود.
برای تعیین مفاهیم کلی و جزئی، ابتدا بیشترین وزن موجود شناسایی میشود. سپس با استفاده از رابطة (12) مفاهیم جزئی و کلی برای هر سند مشخص میشوند که منظور از مقدار وزن بیشینه در سند است و مقدار وزن مفهوم را مشخص مینماید.
برای هر یک از ورودیهای سیستم استنتاج، سه تابع عضویت، مطابق با شکل 6 مشابه با توابع عضویت در ]13[، تعریف شده است. محور افق بیانگر میزان شباهت بین اسناد و محور عمودی درجه عضویت را نشان میدهد. موتور استنتاج فازی ممدانی برای فازیسازی مقادیر ورودی استفاده شده است. مدل سیستم استنتاج فازی ممدانی از عملگر استفاده مینماید.
| (12) |
شکل 4- ساختار سیستم استنتاج فازی ]23[
|
شکل 5- توابع عضویت ورودی فازی
|
موتور استنتاج طراحی شده به منظور خوشهبندی از بیست و هفت قانون فازی که در جدول 1 بیان شده است، استفاده مینماید. هر سطر از این جدول بدین گونه تفسیر میشود (قانون1):
اگر خوشهبندی اسناد فقط در یک دامنة مشخص باشد و هدف خوشهبندی دقیقی از اسناد یک دامنه باشد، ساختار مفهومی این اسناد در تعیین شباهت بین آنها دارای اهمّیت است. اگر خوشهبندی در چند دامنه صورت گیرد و هدف یافتن یک خوشهبندی کلی بر اساس موضوعات دامنه باشد، ساختار مفهومی اسناد تأثیر چندانی در تعیین شباهت بین اسناد ندارند و در عوض مفاهیم کلی دارای اهمّیت بیشتری هستند. بنابراین اگر هدف خوشهبندی جزئی اسناد باشد، جدول similaity1 و اگر هدف خوشهبندی کلی باشد similaity2، به کار گرفته میشوند. خروجی سیستم فازی دارای سه تابع عضویت با مقادیر شباهت است. در نهایت با استفاده از روش
غیرفازیسازی مقدار شباهت نهایی بین دو سند تخمین زده میشود. بنابراین میتوان مراحل زیر را برای محاسبة شباهت بین اسناد بیان نمود:
محاسبة شباهت بین مفاهیم جزئی، کلی و یالهای اسناد استفاده از سیستم استنتاج فازی و تولید خروجی فازی غیرفازیسازی خروجی و محاسبة مقدار نهایی شباهت دو سند خوشهبندی سلسله مراتبی اسناد بر اساس ماتریس شباهت نهایی برای غیرفازی کردن مقادیر شباهت خروجی دو مرحله وجود دارد. مرحلة اول مشخص نمودن میزان شباهت بین اسناد (High,Low,Medium) است. دومین مرحله غیرفازی کردن مقدار این شباهت است. سیستم ممدانی برای مشخص نمودن میزان شباهت بین اسناد از روش Max گیری استفاده مینماید. در سیستم استنتاج فازی مطرح شده، پنج حالت ممکن است بین توابع عضویت متغیر خروجی رخ دهد که در رابطة 13 بیان شدهاند. منظور از میزان درجه عضویت به شباهت High، منظور از میزان درجه عضویت به شباهت Low و منظور از میزان درجه عضویت به شباهتMedium است.
جدول 1- قوانین مربوط به سیستم استنتاج فازی |
Similarity2 | Similarity1 | Main Edge | Detailed concept | Main concept | No |
---|---|---|---|---|---|
High | High | High | High | High | 1 |
High | High | Medium | High | High | 2 |
High | High | Low | High | High | 3 |
High | Medim | High | Medium | High | 4 |
High | High | Medium | Medium | High | 5 |
High | High | Low | Medium | High | 6 |
High | Medium | High | Low | High | 7 |
High | Medium | Medium | Low | High | 8 |
High | High | Low | Low | High | 9 |
Medium | Low | High | High | Low | 10 |
Medium | Medium | Medium | High | Low | 11 |
Medium | Medium | Low | High | Low | 12 |
Medium | Low | High | Medium | Low | 13 |
Low | Low | Medium | Medium | Low | 14 |
Low | Medium | Low | Medium | Low | 15 |
Low | Low | High | Low | Low | 16 |
Low | Low | Medium | Low | Low | 17 |
Low | Low | Low | Low | Low | 18 |
High | Medium | High | High | Medium | 19 |
High | High | Medium | High | Medium | 20 |
High | High | Low | High | Medium | 21 |
High | Medium | High | Medium | Medium | 22 |
High | Medium | Medium | Medium | Medium | 23 |
High | Medium | Low | Medium | Medium | 24 |
Medium | Low | High | Low | Medium | 25 |
Medium | Medium | Medium | Low | Medium | 26 |
Medium | Medium | Low | Low | Medium | 27 |
|
شکل 6- روال محاسبة درجة عضویت به شباهت Low با ورودیهای ( 15%، 75%،25%) |
به عنوان مثال، فرض میشود میزان شباهت دو سند، بین مفاهیم اصلی مقدار 25/0، بین مفاهیم جزئی 75/0 و بین ساختار دو سند 15/0 است. برای مشخص نمودن درجة عضویت شباهت بین دو سند به میزان شباهت High، میزان شباهت Medium و میزان شباهتLow، ابتدا قوانین فازی جدول2 بررسی میشود. برای مشخص نمودن درجة عضویت به میزان شباهتLow، قوانینی بررسی میشوند که میزان شباهت دو سند را Low تخمین زدهاند. در قوانین 14، 15، 16، 17 و 18 در جدول 2، میزان شباهت Lowاست.
بنابراین سیستم استنتاج فازی برای تخمین درجة عضویت به شباهت Low از این پنج قانون استفاده مینماید. شکل 7 روال سیستم استنتاج فازی برای مشخص نمودن درجة عضویت به میزان شباهت Low را نشان میدهد. مشابه همین روال برای مشخص نمودن درجة عضویت به شباهت High و Medium نیز انجام میشود.
پس از مشخص نمودن درجة عضویت Low، High و Medium بیشترین درجه عضویت انتخاب میشود و عمل غیرفازیسازی برای تخمین میزان شباهت نهایی دو سند انجام میشود. شکل 8 روال پایانی غیرفازیسازی را نمایش میدهد. همانطور که در شکل نیز مشخص است مقدار شباهت نهایی این دو سند 16% تقریب زده شده است. 1. خوشهبندی اسناد
پس از محاسبة ماتریس شباهت نهایی بین اسناد، با استفاده از الگوریتم خوشهبندی سلسله مراتبی پایین به بالا خوشهبندی انجام میشود. الگوریتم خوشهبندی در گامهای زیر صورت میپذیرد: هر سند به عنوان یک خوشه در نظر گرفته میشود. ترکیب دو خوشة بر اساس بیشترین شباهت بین این اسناد محاسبة شباهت بین خوشة جدید و سایر خوشهها بر اساس روش centroid-linkage و ترکیب نزدیکترین خوشهها در ادامه، مرحلة سوم تا زمانی که تنها یک خوشه باقی بماند، تکرار میشود.
شکل 7- روال غیرفازیسازی برای ورودیهای شکل 7
روش centroid-linkage از فاصلة بین مراکز خوشهها استفاده مینماید. اگر یک شی در خوشه و یک شی در خوشه و به ترتیب تعداد اشیاء در خوشههای و باشند، آنگاه فاصلة بین دو خوشه از طریق رابطة 14 محاسبه میشود که،امین شی در خوشة است. شکل 9 این اندازهگیری را برای دو خوشهی L,K نشان میدهد.
| (14) |
شکل 8- خوشهبندی سلسله مراتبی به روش Centroid
· ارزیابی روش پیشنهادی
الگوريتم خوشهبندی پيشنهادي در محيط NET. و با استفاده از C# توسعه داده شده است. همچنين از پايگاه داده رابطهاي MySql براي ذخيرهسازي مفاهیم و نمونهها و روابط بین آنها، شمای آنتولوژیکال اسناد و ماتریس شباهت اسناد استفاده شده است. برای پیادهسازی سیستم استنتاج فازی در محیط NET. از چارچوب Aforge.net بهره گرفته شده است. جهت پيادهسازي و اجراي آنتولوژی از زبان OWL که به صورت گرافهاي جهتدار، روابط و منطق بين مفاهيم را تشريح ميکند، استفاده شده است. نرم افزار به کار رفته براي پيادهسازي آنتولوژی، نرم افزار Protégé، محصول دانشگاه استنفورد است. اين نرمافزار با پشتيباني از زبانهاي RDF، OWL و قدرت تبديل آنها به يکديگر، اين امکان را فراهم ميسازد که در صورت نياز با استفاده از منطق توصيفي منطبق بر گزارهها که OWL ارائه ميدهد، آنتولوژی را براي استفاده در وب معنايي آماده کند.
همانطور که ميدانيم زباني که آنتولوژی آن را ميشناسدOWL است چرا که مجموعهاي از RDF است. در الگوریتم پیشنهادی از روش نگاشت آنتولوژی به پايگاه داده براي استخراج اطلاعات استفاده شده است. به اين ترتيب که آنتولوژی از يک فايل OWL استخراج شده و سپس در يک پايگاه داده رابطهاي ذخيره ميشود. پايگاه داده رابطهاي اغلب به عنوان پايهاي براي ذخيرهسازي آنتولوژی جهت کمک به سرعت بخشيدن به عملياتي از قبيل جستجو و بازيابي و همچنين استفاده از مزاياي سيستم مديريت پايگاه داده رابطهاي مانند کنترل امنيت و يکپارچگي استفاده ميشود. پیاده سازی طرح پیشنهاد شده به گونهای صورت گرفته است که به صورت خودکار از جدول ایجاد شده از آنتولوژی، جداول کلاسها و نمونهها و ماتریسهای کلاسها و کلاس- نمونه ساخته میشود. بنابراین پیادهسازی انجام شده قابل تطبیق با هر آنتولوژی است. به منظور کاهش مصرف حافظه، روابط بین کلاسها به صورت ماتریس کامل ذخیره نمیشود. تنها کلاس پدر، کلاس فرزند و تعداد روابط بین این دو کلاس ذخیره میشوند. برای ذخیرهسازی ماتریس کلاس- نمونه نیز بدین صورت عمل میشود.
برای بررسی روش پیشنهادی، دو ارزیابی انجام شده است. در ارزیابی اول هدف خوشهبندی اسناد به صورت کلی و در چند دامنه است. در ارزیابی دوم خوشهبندی جزئی اسناد، در یک دامنه صورت میپذیرد. کارایی روش پیشنهادی در ارزیابی اول با چهار الگوریتم دیگر مقایسه میشود. الگوریتم اول، خوشهبندی مبتنی بر Naive Bayes است که یک خوشهبند کننده ساده احتمالاتی است که مبتنی بر تئوری Bayes و فرضیههای Naive است. در این الگوریتم هر سند با فرکانس کلمات (روش فضای بردار) نمایش داده میشود ]24[. الگوریتم دوم در مقالة ]25[ ارائه شده است. این روش از یک چارچوب مبتنی بر آنتولوژی استفاده مینماید. این چارچوب شامل پیش پردازش، استخراج ویژگی و کاهش ابعاد است. بخش آنتولوژی، مهمترین بخش در این چارچوب است و دانش پسزمینة مورد نظر را فراهم میسازد. بخش آخر بخش خوشهبندی نهایی اسناد است که با استفاده از آنتولوژی، مفاهیم از اسناد استخراج میگردند و با کمک الگوریتم خوشهبندی مناسب، اسناد دستهبندی میشوند.
در مقالة ]25[ برای هر سند، برداری مطابق با روش فضای برداری ساخته میشود. برای هر دامنه نیز برداری از مفاهیم ساخته میشود که به هر مفهوم با توجّه به اهمّیتش در دامنه وزنی تعلق میگیرد. در نهایت شباهت بین بردارهای اسناد و بردارهای ساخته شده از آنتولوژی، به صورت کسینوسی محاسبه میشوند. این مقاله برای ارزیابی از دویست و پنجاه سند از سه دامنة مختلف پیتزا1، نوشیدنیها2 و کامپیوتر3 استفاده نموده است. صد و شش سند به دامنة کامپیوتر، شصت و چهار سند به دامنة پیتزا و هشتاد سند به دامنة نوشیدنی متعلق است. نتایج خوشهبندی آن نیز با روش Bayes مقایسه شده است.
الگوریتم خوشهبندی سوم، روش خوشهبندی تکرار کننده مبتنی بر روش Bayes4 (IBC) است که از روش مزیت نسبی5، CA برای برچسبگذاری اولیه اسناد استفاده مینماید ]24[. این الگوریتم با نام CA-IBC شناخته میشود. با توجّه به فرضیههای ساده روش Bayes، از این روش نمیتوان به صورت مستقیم برای خوشهبندی اسناد بدون برچسب استفاده نمود. برای حل این مشکل، الگوریتم IBC مطرح میشود. این الگوریتم در سه گام انجام میپذیرد: مشخص نمودن برچسب اولیة اسناد به روز رسانی برچسب همة اسناد مبتنی بر روش BC پایان الگوریتم در صورت عدم تغیییر برچسب اسناد در گام دوم، در غیر این صورت برگشت به گام دوم.
الگوریتم برای برچسبگذاری اولیة اسناد از روش CA استفاده مینماید. روش CA فرض میکند هر سند یک انسان است و هر کلمه فعالیتی است که میتواند هر انسان انجام دهد. خوشهبندی اسناد روال دستهبندی افراد است تا سود، بیشینه گردد. الگوریتم CA ابتدا به صورت تصادفی اسناد را برچسبگذاری مینماید. سپس به خوشهبندی اسناد میپردازد. این روال تا هنگامی که برچسب اسناد تغییر کند ادامه مییابد. الگوریتم CA-IBC، ابتدا از طریق الگوریتم CA اسناد را برچسبگذاری مینماید و سپس الگوریتم IBCبه خوشهبندی نهایی اسناد میپردازد. روالCA، به تعداد خوشهها، اسنادی را به صورت تصادفی انتخاب مینماید و به عنوان بردار میانگین اولیه خوشه در نظر میگیرد.
الگوریتم چهارم در مقالة ]26[ ارائه شده است. در این مقاله روش خوشهبندی اسناد با نام CCAG6 ارائه شده است. در این روش پس از انجام پیش پردازشهای متعارف اسناد، کلمات به مفاهیم آنتولوژی نگاشت میشوند. در واقع یک فضای ویژگی با ابعادی برابر با تعداد مفاهیم موجود در آنتولوژی در نظر گرفته میشود و هر سند در این فضا نمایش داده میشود.الگوریتم خوشهبندی ارائه شده بر روی مجموعة اسناد ]25[ اعمال میشود و نتیجة آن با چهار الگوریتم فوق مقایسه میشود. در الگوریتم پیشنهادی ابتدا آنتولوژیهای مورد نظر به پایگاه داده نگاشت ارائه میشوند. شکلهای 10و 11 آنتولوژیهای مورد استفاده را نشان میدهد.
جداول و ماتریس نمونهها، کلاسها و روابط بین آنها به صورت خودکار استخراج میشوند. برای پیش پردازش اسناد از حذف کلمات نویزی، نشانهگذاری و ریشهیابی استفاده شده است. نشانهگذار تمامی علائم نقطهگذاری را حذف مینماید و نشانههای صحیح را برمیگرداند. سپس نوبت به مرحلة حذف کلمات نویزی میرسد. دویست و دوازه کلمه، به عنوان واژههای نویزی زبان انگلیسی در نظر گرفته شدهاند و در صورت مشاهده در سند حذف میشوند. برای تمامی نشانههای باقیمانده ریشهیابی صورت میگیرد. الگوریتم مورد استفاده Porter Stemmer است. این الگوریتم برای تمامی کلمات، ریشه را به درستی تشخیص نمیدهد. بنابراین هر کلمه پس از ریشهیابی با لغات موجود در دیکشنری کاملی از زبان انگلیسی مقایسه میشود و به شبیهترین و صحیحترین کلمه نگاشت میشود.
پس از مراحل فوق شمای آنتولوژیکال اسناد استخراج میشود. برای هر مفهوم مستقیم در سند، چهار سطح مفهوم غیرمستقیم-1، شامل فرزندان و پدران، نیز استخراج میشود. برای استخراج مفاهیم غیرمستقیم-2 از دیکشنری مفهومی استفاده میشود. این دیکشنری از دیکشنری معکوس Onelook 7 ساخته شده است. دیکشنری معکوس برای هر مفهوم مرتبطترین کلمات را به ترتیب اهمّیت برمیگرداند. برای هر مفهوم صد کلمه بدین صورت انتخاب میشود. همچنین برای هر مفهوم صفحات اینترنتی مرتبط جستجو شده و کلمات متناسب با مفهوم انتخاب میشوند. سرانجام برای هر مفهوم کلمات یافت شده مورد بازبینی نهایی قرار میگیرند و مناسبترین کلمات در دیکشنری مفهومی باقی میماند. همانگونه که قبلاً توضیح داده شد، برای هر سند به صورت نسبی مفاهیم کلی، جزئی و یالهای اصلی استخراج میشوند. برای هر یک از این اجزا سه ماتریس شباهت تولید میشود. برای تخمین شباهت پایانی از سیستم استنتاج فازی استفاده میشود. خروجی سیستم استنتاج فازی، ماتریس شباهت نهایی است که ورودی الگوریتم خوشهبندی سلسله مراتبی پایین به بالا است.
مقایسه نتایج الگوریتم پیشنهادی و دو الگوریتم دیگر از طریق شش معیار ارزیابی صورت میپذیرد. از معیارهای ارزیابی precision (رابطة15)، recall (رابطة16)، F-measure (رابطة17) و Accuracy (RI) (رابطة18) و همچنین از دو معیار دیگر با نامهای Error و FP (False Positive rate) استفاده شده است که به ترتیب در روابط 19 و 20 بیان شدهاند. مقدار ، تعداد جفت متونی است که در خوشه و دستة یکسانی ظاهر شدهاند. مقاد به ترتیب false positive، false negative و true negative هستند.آزمايشهای انجام شده براي ارزيابي الگوریتم پیشنهادی بر روي يک سيستم با ويندوز ویستا، با پردازندة دو هستهای 2.53 گيگا هرتز اينتل همراه با 4 گيگا بايت حافظه، براي اسناد انگلیسی انجام گرفته است. مقدار آستانه برای رفع ابهام از یک مفهوم، به دست آوردن نمرهای بیشتر از 80 است. برای هر مفهوم مستقیم تعداد چهار سطح از فرزندان و چهار سطح از پدران اضافه میگردد.همچنین در مرحلة رفع ابهام در صورتی از مفاهیم پاراگرافهای قبل و بعد استفاده میشود که نسبت مفاهیم رفع ابهام شده پاراگراف فعلی به کل مفاهیم مبهم
[1] . Pizza
[2] . Drink
[3] . Computer
[4] . Iterative Bayes Clustering
[5] . Comparative Advantage
[6] . Concept Choice And Grand Total
[7] . http://www.onelook.com/reverse-dictionary.shtml
شکل 9- بخشی از آنتولوژی پیتزا
شکل 10- بخشی از آنتولوژی کامپیوتر
پاراگراف از 15% کمتر باشد. برای خوشهبندی تمامی اسناد از 1 تا 250 شمارهگذاری میشوند و در یک مسیر مشخص قرار میگیرند. همانگونه که اشاره شد از پنج الگوریتم برای خوشهبندی دویست پنجاه سند در سه دامنة پیتزا، کامپیوتر و نوشیدنیها استفاده شده است. برای خوشهبندی اسناد با روش CA-IBC، الگوریتم صد مرتبه با حالات برچسبگذاری اولیة مختلف اجرا میشود و نتیجة نهایی به صورت میانگین این نتایج اعلام میشود. برای این الگوریتم دو حالت در نظر گرفته شده است: 1- روش برچسبگذاری اولیه کاملاً تصادفی انجام شود (random). 2- فرض میشود که در صد مرتبه اجرا، اسناد مناسب به عنوان مرکز اولیة خوشه در نظر گرفته شوند (best). شکلهای 12، 13، 14، 15، 16و17 نتایج ارزیابی پنج الگوریتم را نشان میدهند. شکل 20 به صورت میانگین شش معیار فوق را در پنج الگوریتم بررسی میکند.
شکل 11- مقایسة پنج روش با معیار Precision
| (15) |
| (16) |
| (17) |
| (18) |
| (19) |
| (20) |
شکل 12-مقایسة پنج روش با معیار Recall
شکل 13-مقایسة پنج روش با معیار Fmeasure
شکل 14- مقایسة پنج روش با معیار Accuracy
شکل 15- مقایسة پنج روش با معیار FP
کل 16- مقایسة پنج روش با معیار Error
شکل 17- مقایسة پنج روش به صورت میانگین
همانگونه که از نتایج برمیآید خوشهبندی CA-IBC به دلیل برچسبگذاری تصادفی اولیه در مقایسه با روشهای مفهومی نتایج بسیار ضعیفی تولید مینماید. حتی با فرض اینکه در تمامی صد بار اجرا، اسناد اولیه از خوشههای مناسب انتخاب شوند، نتایج تولید شده در مقایسه با روشهای مفهومی چندان مناسب نیستند. در واقع این الگوریتم یک الگوریتم غیر قطعی است و طبق مقالة ]24[ این روش در مقایسه با سایر روشهای آماری، با ورودیهای یکسان، بهتر عمل مینماید. الگوریتم CCAG در مقایسه با روش IC-IBC بهتر عمل نموده است. روش پیشنهادی به دلیل رفع ابهام از مفاهیم و پردازش دقیقتر مفاهیم استخراج شده از سند، نمایش جامعتر و دقیقتر از اسناد ایجاد مینماید. استفاده از سیستم استنتاج فازی و ساختار مفهومی دقیقتر باعث میشود خوشهبندی صحیحتری نیز تولید شود. الگوریتم پیشنهادی تنها یک سند را به صورت نادرست خوشهبندی کرده است: سندی در دستة نوشیدنیها، وارد خوشة پیتزا شده است. با بررسی مفهومی این سند مشخص شد که مضمون این سند راجع به بیماریهای حاصل از نوشیدنیها است و به مفاهیم مربوط به دامنة نوشیدنیها به صورت جزئی و غیرمستقیم اشاره شده است. خوشهبندی ایجاد شده با روش Bayes یک روش احتمالاتی است و بر کلمات تکیه دارد. با توجّه به نمایش ضعیف اسناد، نتایج خوشهبندی این روش نسبت به دو روش مفهومی چندان قابل توجّه نیست. روش مقالة ]25[ نیز یک روش مبتنی بر آنتولوژی است. این روش از روش فضای برداری و کاهش ابعاد برای نمایش اسناد استفاده مینماید. همانگونه که اشاره شد کاهش ابعاد لزوماً روابط مفهومی اسناد را استنتاج نمینماید. این مقاله تنها از مفاهیم آنتولوژی برای نمایش دانش پس زمینة هر خوشه استفاده نموده است و ویژگیها و روابط بین مفاهیم آنتولوژی را نیز نادیده گرفته است. با فرض داشتن یک آنتولوژی جامع و کامل و همچنین یک لغت نامة مفهومی مناسب میتوان با استفاده از الگوریتم پیشنهادی، روالهای کاوش اسناد که مبتنی بر نمایش اسناد هستند را بهبود داد. در ارزیابی دوم هدف انجام خوشهبندی جزئی در یک دامنة خاص است. روش پیشنهادی به علّت دقت ساختار مفهومی اسناد، میتواند در یک دامنة خاص نیز برای خوشهبندی استفاده شود. برای خوشهبندی جزئی دامنه travel در نظر گرفته شده است. بیست و پنج سند به صورت کاملاً تصادفی از این دامنه انتخاب شده است. یک سند به زیر دامنة Adventure، بیست سند به زیر دامنة Hotel و چهار سند به زیر دامنة Sport مرتبط هستند. شکل 19 بخشی از آنتولوژی travel را نمایش میدهد. خوشهبندی این مجموعه اسناد با دو روش برتر ارزیابی قبل، الگوریتم پیشنهادی و روش CCAG، انجام شده است. نتایج خوشهبندی با این دو روش در جدولهای 2 و 3 مشاهده میشوند. در شکل 20 نتایج حاصل از دو روش به صورت میانگین با یکدیگر مقایسه شدهاند.
همانطور که از نتایج مشخص است روش پیشنهادی در مقایسه با روش CCAG، در خوشهبندی جزئی با موفقیت بیشتری عمل کرده است. نمایش دقیق مفهومی اسناد، معیار شباهت متناسب با این نمایش و سیستم استنتاج فازی باعث برتری روش پیشنهادی شده است. البته به علّت تشابه بیشتر ساختار مفهومی اسناد، این خوشهبندی کمی مشکلتر از خوشهبندی کلی است.
نتیجهگیری
در این مقاله یک الگوریتم خوشهبندی اسناد مبتنی بر نمایش آنتولوژیکال و سیستم استنتاج فازی ارائه شده است. در ابتدا مفاهیم پایه و الگوریتمهای خوشهبندی اسناد، مدلهای خوشهبندی، کاربردهای نمایش اسناد و سیستمهای خوشهبندی اسناد مطرح شد. در ادامه الگوریتم خوشهبندی اسناد پیشنهادی ارائه شد. این الگوریتم در پنج مرحله صورت میپذیرد. در مرحلة اول پیش پردازشهای لازم بر مجموعة اسناد انجام میشود. نشانهگذاری و ریشهیابی از مهمترین پیش پردازشهای انجام شده هستند. پس از انجام پیشپردازش برای هر سند مجموعهای از نشانههای اصلی و ریشههایشان نگهداری میشود. مرحلة بعد تولید شمای آنتولوژیکال اسناد است. نمایش آنتولوژیکال پیشنهادی یک گراف وزندار و جهتدار است که ساختار مفهومی اسناد را مشخص مینماید.
شکل 18- بخشی از آنتولوژی Travel
جدول 2- نتایج خوشهبندی جزئی با روش پیشنهادی
Average | Hotel | Sport | Adventure |
|
---|---|---|---|---|
0.9841 | 0.9523 | 100% | 100% | Precision |
0.9166 | 100% | 0.75 | 100% | Recall |
0.9600 | 0.9200 | 0.9600 | 100% | Accuracy |
0.3333 | 1 | 0 | 0 | FP |
0.04 | 0.0800 | 0.0400 | 0 | Error |
0.9442 | 0.9755 | 0.8571 | 100% | F1-measure |
جدول 3- نتایج خوشهبندی جزئی با روش CCAG
Average | Hotel | Sport | Adventure |
|
0.9565 | 0.8695 | 100% | 100% | Precision |
0.75 | 100% | 0.25 | 100% | Recall |
0.9200 | 0.8800 | 0.8800 | 100% | Accuracy |
0.3333 | 1 | 0 | 0 | FP |
0.08 | 0.1200 | 0.1200 | 0 | Error |
0.7767 | 0.9301 | 0.4000 | 100% | F1-measure |
شکل 19- مقایسة دو روش با تمامی معیارها به صورت میانگین
در واقع نمایش پیشنهادی برای هر سند زیر گرافی از آنتولوژی دامنه تولید میکند. در این نمایش مفهومی روال رفع ابهامی برای حذف مفاهیم مبهم در نظر گرفته شده است. این روال باعث نمایش دقیقتر اسناد میشود. گام سوم محاسبة شباهت بین هر دو سند است. بر اساس نمایش آنتولوژیکال، معیار شباهت متناسبی نیز ارائه شده است. این معیار شباهت مفاهیم مشترک هر دو سند را بررسی مینماید و بر اساس وزن و اولویت این مفاهیم، شباهت بین دو سند را تخمین میزند. به منظور تخمین دقیقتر شباهت بین اسناد، در سه جزء بامعنی (مفاهیم اصلی، مفاهیم جزئی و یالهای اصلی) شباهت دو سند تخمین زده میشود. در گام چهارم سیستم استنتاج فازی طراحی شده است که دارای سه ورودی و یک خروجی است. ورودیهای این سیستم شباهت محاسبه شده در سه جزء و خروجی مقدار شباهت نهایی بین دو سند است. سیستم استنتاج فازی تولید شده ماتریس شباهت نهایی بین اسناد را ایجاد مینماید. مرحلة آخر خوشهبندی سلسله مراتبی اسناد است که از مدل پایین به بالا با روش centroid استفاده شده است. در نهایت به ارزیابی روش پیشنهادی پرداخته شده است. نتایج حاصل از این خوشهبندی در مقایسه با روشهای دیگر نشان میدهد که الگوریتم پیشنهادی نتایج بهتری تولید مینماید. موفقیت این الگوریتم نسبت به سایر الگوریتمها، به دلیل استفاده از نمایش آنتولوژیکال است. این نمایش نسبت سایر روشهای مرسوم نمایش اسناد، مضمون هر سند را به درستی درک و استخراج مینماید. همچنین معیار شباهت متناسب با این نوع نمایش و سیستم استنتاج فازی پیشنهادی باعث ایجاد خوشهبندی دقیقتری میشوند.
از مزیتهای روش پیشنهادی، استخراج نمایش مفهومی دقیق اسناد است. این نوع نمایش همانند روشهای قبل از یک فضای ویژگی برای همة اسناد استفاده نمینماید که این امر سبب کاهش حافظه مصرفی و پرهیز از مشکلات ابعاد بالا میشود. همچنین در نظر گرفتن اولویت مفاهیم در محاسبة شباهت اسناد، نسبت به سایر معیارهای شباهت، سبب میشود که شباهت دو سند با دقت بیشتری تخمین زده شود. نمایش مفهومی و معیار شباهت ارائه شده سبب میشوند این الگوریتم در خوشهبندی جزئی نیز نتایج قابل قبولی تولید نماید. از محدّودیتهای این روش این است که الگوریتم پیشنهادی به آنتولوژی وابسته است. برای انجام یک خوشهبندی دقیق باید آنتولوژی دامنه مورد نظر موجود باشد. هرچه لغتنامه مفهومی در آنتولوژی دقیقتر و جامعتر باشد، نتایج خوشهبندی با کیفیت بیشتری همراه خواهد بود. ناقص بودن لغتنامه و آنتولوژی دامنه سبب کاهش کیفیت نتایج خوشهبندی میشود. در فعالیتهای آتی سعی در ایجاد خوشهبندی فازی مبتنی بر نمایش آنتولوژیکال پیشنهادی است. همچنین تعیین خودکار تعداد سطوحی که باید در آنتولوژی برای هر مفهوم بررسی شوند، بهروزرسانی لغتنامههای مفهومی بر اساس خوشههای ایجاد شده در هر دامنه و انجام آزمایشهای بیشتر در زمینة خوشهبندیهای یک دامنة خاص میتواند مورد مطالعه و بررسی قرار گیرد.
منابع
1.G. Salton, M. J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, 1984.
2.W. Frawley, G. Piatetsky-Shapiro and C. Matheus, Knowledge Discovery in Databases: An Overview, AI Magazine, Fall 1992, pp. 213-228.
3.L.Yanjun, HIGH PERFORMANCE TEXT DOCUMENT CLUSTERING, M.S., Wright State University, 2003.
4.D.Q. Zhang and S.C. Chen, Clustering incomplete data using kernel-based fuzzy c-means algorithm, Neural Processing Letters, 18(3):155–162, 2003.
5.L. Jing, Survey of text clustering, 2006. On website: http://www.alphaminer.org/document/downloads/TextMining/survey%20of%20text%20clustering.pdf
6.M. Porter, An Algorithm for Suffix Stripping, Program, 14(3), pp. 130-137, 1980.
7.G. Salton, E.A. Fox, H. Wu, Extended Boolean information retrieval, Communications of the ACM, 26(11), pp. 1022-1036, 1983.
8.W.R. Hersch, D.L. Elliot, D.H. Hickam, S.L. Wolf, A. Molnar, C. Lechtenstien, Towards new measures of information retrieval evaluation, Proceedings of the 18th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 164-170, 1995.
9.Miller, Wordnet: A lexical database for english, CACM, vol. 38, no. 11, pp. 39-41, 1995.
10.L. Khan and D. McLeod, Audio structuring and personalized retrieval using ontology, Proc. of IEEE Advances in Digital Libraries, 2000.
11.T. Gruber, A translation approach to portable ontology specifications, Knowledge Acquisition, vol. 5, no. 2, pp. 199-220, 1993.
12.Muresan, Learning to Map Text to Graph-based Meaning Representations via Grammar Induction, 3 Proceedings of the 3rd Textgraphs Workshop on Graph-Based Algorithms for Natural Language Processing, 2008.
13.P. Ljungstrand, H. Johansson, Intranet indexing using semantic document clustering. Master Thesis, Department of Informatics, Gteborg University, 1997.
14.B. Solheim,K. Vågsnes, Ontological Representation of Texts, and its Applications in Text Analysis, Agder University College,2003.
15.R.R. Korfhage, Information Storage and Retrieval, John Wiley and Sons, New York, 1997.
16.C.J. Van Rijsbergen, Information Retrieval (2nd ed.), Butterworths, London, 1979.
17.M. Rosell, M. Hassel, and V. Kann, Global evaluation of random indexing through Swedish word clustering compared to the people’s dictionary of synonyms, Submitted, 2009.
18.D. Zeimpekis and E. Gallopoulos, PDDP(l): towards a flexible principal direction divisive partitioning clustering algorithm, In D. Boley, I. Dhillon, J. Ghosh, and J. Kogan, editors, Proc. Workshop on Clustering Large Data Sets (held in conjunction with the Third IEEE Int’l. Conf. Data Min.), pages 26–35, Melbourne, FL, November 2003.
19.H. Schütze and C. Silverstein, Projections for efficient document clustering, In Proc. 20th annual int. ACM SIGIR conf. on Research and development in information retrieval, pages 74–81, New York, NY, USA. ACMPress. ISBN 0-89791-836-3, 1997.
20.K. Beyer, J. Goldstein, R. Ramakrishnan, and U. Shaft, When is nearest neighbors meaningful?, Proc. of 7th International Conference on Database Theory (ICDT'99), pp. 217- 235, 1999.
21.L. Yu and H. Liu, Feature selection for high-dimensional data: a fast correlation-based filter solution, Proc. of the 20th International Conference on Machine Learning, pp. 856-863, 2003.
22.F. Lamberti, A. Sanna, C. Demartini, A Relation-Based Page Rank Algorithm for Semantic Web Search Engines, IEEE Transactions on Knowledge and Data Engineering, vol. 21, no. 1, 2009.
23.http://aimm02.cse.ttu.edu.tw/class/92-2/ANNs/04-Apr-19-2.ppt
24.J. Ji and Q. Zhao, Applying Naive Bayes Classifier to Document Clustering, Journal of Advanced
Computational Intelligence and Intelligent Informatics, Vol.14 No.6, 2010.
25.X. Yang, N. Sun, Y. Zhang, D. Kong, General Framework for Text Classification based on Domain Ontology, In SAMP 08: Proceedings of the 2008 Third International Workshop on Semantic Media Adaptation and Personalization. IEEE Computer Society. Washington DC, USA. pp. 147-152, 2008.
26.Ding. Y., Fu. X., A Text Document Clustering Method Based on Ontology, ISNN'11 Proceedings of the 8th international conference on Advances in neural networks, Volume Part II, Springer-Verlag Berlin, Heidelberg, 2011