• صفحه اصلی
  • خوشه‌بندی اسناد مبتنی بر آنتولوژی و رویکرد فازی

اشتراک گذاری

آدرس مقاله


کد مقاله : 202005061208 بازدید : 13318 صفحه: 73 - 96

نوع مقاله: پژوهشی

خوشه‌بندی اسناد مبتنی بر آنتولوژی و رویکرد فازی

محورهای موضوعی : فناوری اطلاعات و دانش

مریم امیری 1 * , حسن‌ ختن‌ لو 2

1 -
2 -

تاریخ دریافت : 1391/08/02 تاریخ انتشار : 1398/08/17

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

چکیده مقاله :

داده‌کاوی که به عنوان استخراج دانش از پایگاه داده‌ها نیز شناخته می‌شود، روالی برای استخراج دانش ناشناخته از داده است. کاوش اسناد بر اساس روش‌های داده کاوی به استخراج اطلاعات و دانش از اسناد می‌پردازد. خوشه‌بندی اسناد یکی از مهمترین روش‌های کاوش اسناد است که دسته‌بندی بدون سرپرست اسناد به گروه‌های مختلف می‌باشد. سیستم‌های رایج بازیابی اطلاعات و خوشه‌بندی اسناد بر کلمات کلیدی استوار می‌باشند. با توجه به اینکه کلمات کلیدی مختلف می‌توانند برای توصیف یک مفهوم استفاده شوند، این سیستم‌ها می‌توانند نتایج نادرست و ناقصی را ایجاد نمایند. همچنین روابط معنایی ممکن است بین کلمات موجود باشد که شناسایی آنها نیاز به استخراج دانش دامنه مورد نظر دارد. مهمترین گام‌ها در خوشه‌بندی اسناد نحوه‌ی نمایش اسناد و معیار اندازه‌گیری شباهت بین آنها است. این تحقیق بر بهبود کارایی خوشه‌بندی اسناد تمرکز دارد. الگوریتم خوشه‌بندی اسناد در سه گام پیشنهاد شده است: نمایش اسناد، اندازه‌گیری شباهت بین اسناد، سیستم استنتاج فازی به منظور اندازه‌گیری شباهت نهایی بین اسناد. در نهایت پس از انجام این سه گام، با استفاده از الگوریتم خوشه‌بندی پایین به بالا خوشه‌بندی اسناد صورت می‌پذیرد. در گام اول، اسناد بر اساس دانش دامنه به صورت یک گراف آنتولوژی نمایش داده می‌شوند. این روش بر خلاف روش مبتنی بر کلمات کلیدی، بر مفاهیم دامنه استوار می‌باشد و یک سند را بر اساس مفاهیم موجود در آن، به صورت زیرگرافی از آنتولوژی دامنه نمایش می‌دهد. مفاهیم استخراج شده گره‌های گراف را تشکیل می‌دهند. برای هر گره با توجه به فرکانس مفهوم، وزن محاسبه می‌گردد. روابط موجود بین مفاهیم سند، یال‌های گراف و میزان این ارتباط اوزان یال‌ها را مشخص می‌نماید. در گام دوم برای هر سند بر اساس نمایش گرافی استخراج شده از مرحله‌ی اول، مفاهیم کلی و جزئی و یال‌های اصلی مشخص می‌گردند. شباهت بین هر جفت از اسناد در سه مقدار و بر اساس این سه عامل محاسبه می‌شود. در گام سوم سیستم استنتاج فازی با سه ورودی و یک خروجی طراحی شده است. ورودی‌ها مفاهیم کلی، مفاهیم جزئی و یال‌های اصلی می‌باشند و خروجی میزان شباهت بین دو سند است. مجموعه‌ای از قوانین فازی برای موتور استنتاج فازی در نظر گرفته شده است که بر اساس سه شباهت ورودی مقدار شباهت نهایی را تخمین می‌زند. در نهایت بر اساس ماتریس شباهت اسناد، الگوریتم خوشه‌بندی سلسله مراتبی پایین به بالا به منظور خوشه‌بندی اسناد اعمال می‌گردد. برای ارزیابی الگوریتم پیشنهادی، نتایج با نتایج حاصل از روش‌های naïve Bayes ، دو الگوریتم مبتنی بر هستان شناسی و یک الگوریتم آماری مقایسه شده است. نتایج به دست آمده نشان می‌دهند که روش پیشنهاد شده مقادیر F-measure و Accuracy را بهبود می‌دهد. همچنین مقادیر FP و Error به میزان قابل توجهی کاهش می‌یابد.

چکیده انگلیسی:

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

E:\E Drive\logo\iicta Logo0.JPG 

خوشه‌بندی اسناد، مبتنی بر آنتولوژی و رویکرد فازی

*مریم امیری *حسن ختن‌لو

*کارشناس ارشد، دانشگاه بوعلی‌سینا، گروه کامپیوتر، همدان

**هیئت علمی، دانشگاه بوعلی‌سینا، گروه کامپیوتر، همدان

تاریخ دریافت: 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) است. در این مدل هر سند با یک بردار مشخص می­شود. هر درایه از بردار منعکس کنندة یک مفهوم خاص است. مقدار هر عنصر اهمّیت آن نشانه در نمایش معنایی سند است. پایگاه داده­ای شاملimg0 سند است که باimg0 ترم10 توصیف شده­اند، بنابراین به صورت یک ماتریس img0نمایش داده می­شود. هر سطر از ماتریس متناظر با بردار اسناد است. بدین گونه عناصر ماتریس، img0 فرکانس وزن­داری است که نشانهimg0 در سندimg0 اتفاق می­افتد. در حالت دیگر از 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

img0 

 

 

 

 

 

 

 

 

 

 

شکل 1- نمایش آنتولوژی شامل مفاهیم، نمونه‌ها و روابط ]14[

 

 

 

 

روش­های مهمی برای محاسبة شباهت بین دو سند img0 پیشنهاد شده است. یکی از متداول­ترین روش­ها ضرب داخلی دو بردار است. ضرب داخلی تابع کوسینوسی است که در رابطة 1 نشان داده شده است

img0 

(1)

ضرب داخلی بیان کنندة زاویة بین آن‌ها است. اگر حاصل یک باشد، زاویه صفر درجه است و بیش‌ترین تطابق در این حالت وجود دارد. اگر حاصل صفر شود زاویة بین آن‌ها نود درجه است و کم‌ترین تطابق وجود دارد. این اندازه­گیری مشکلات خاصی برای اسناد با طول بلند ایجاد می‌کند.

به جز ضرب داخلی یا شباهت کسینوسی، توابع دیگری نیز برای اندازه­گیری شباهت وجود دارد، خانواده­ای از فاصله­ها ]15[ به صورت رابطة 2 بیان شده­اند. این تابع، فاصله را بر حسب اجزای دو سند محاسبه می­نماید. جدا از این معیارهای فاصله، توابعی هستند که تنها تعداد کلمات مشترک و تعداد کلمات غیر مشترک را شمارش می­کنند. یکی از این توابع معروف ضریب Dice است ]16[ که در رابطة 3 نشان داده شده است:

img0 

(2)

img0 

(3)

که مقدارimg0 تعداد کلمات مشترک بردارهای اسناد است،img0تعداد کلمات با فرکانس غیر صفر در اولین سند و img0 تعداد کلمات با فرکانس غیر صفر در دومین سند است. مخرج کسر نوعی نرمال‌سازی است. یک تابع معمول دیگر برای اندازه­گیری شباهت، ضریب Jaccard  است ]16[. این تابع شباهت در رابطة 4 ذکر شده است:

img0 

(4)

img0 

(4)

کهimg0 تعداد کلمات مشترک اسناد img0 و img0 است وimg0 تعداد کل کلمات مجزا در فضای برداری وimg0 تعداد کلمات مجزایی هستند که نه در img0 و نه در img0 است. بنابراین مخرج کسر تعداد کلماتی را نشان می­دهند که در img0 یا در img0 و یا در هر دو رخ می­دهند. توابع محاسباتی بالا برای محاسبة شباهت اسناد، فرض می­کنند که مجموعة اسناد ایستا هستند. در حالت "routing"، اسناد دارای یک جریان ورودی متغیر هستند و هر سند باید برای یکی ازimg0گروه متناظر باimg0 موضوع از پیش تعریف شده،   "routed" (مسیریابی)، شود.

محاسبة شباهت­ها در خوشه­بندی به طور مکرر انجام می­گیرد. بنابراین با سریع انجام دادن آن می­توان به کل روال سرعت بخشید. تعیین شباهت­ها نیز بستگی به تعداد کلمات­ به کار رفته دارد، پس با کاهش تعداد کلمات در نمایش می­توان سرعت را افزایش داد ]17[. روش­های پیچیده­ای برای کاهش تعداد کلمات وجود دارد. در ]18[ روش­های انتخاب نشانه، مبتنی بر تغییرات فرکانس نشانه، در متن پیشنهاد شده است. در ]19[ روال کاهش نشانه­ها افکنش1 نامیده می­شود که فضای برداری به یک فضای جدید با تعداد ابعاد کم‌تر تصویر می­شود. همچنین داده­های متنی مشکل بزرگی دارند: مشکل ابعاد زیاد. در فضاهایی با ابعاد بالا، فاصلة بین هر جفت از نقاط تقریباً برای انواع گوناگون توزیع داده­ها و توابع فاصله یکسان است ]20[ که این انگیزه­ای برای کاهش ابعاد دادة ورودی است. تعدادی از روش­های انتخاب ویژگی، به جستجوی زیر مجموعه­های ویژگی و ارزیابی هر کدام از این مجموعه­ها با استفاده از معیارهایی پرداخته­اند ]21[. همبستگی در میان ابعاد، اغلب مخصوص محل و موقعیت داده است، به این معنی که تعدادی از نقاط داده با یک مجموعه از ویژگی­ها و سایر آن‌ها با ویژگی­های متفاوت وابسته هستند. یعنی در فضایی با ابعاد بالا شبیه داده­های متنی، هر خوشه ساختار زیر فضایی خاص خودش را دارا است. 

یادگیری با هر دو دادة برچسب خورده و بدون برچسب، یادگیری نیمه سرپرست نامیده می­شود. این روش اخیراً با توجّه زیادی مورد مطالعه قرار گرفته­ است و اساساً به صورت یک روش استخراج اطلاعات در داده­های بدون برچسب، برای بهبود کارایی مدل خوشه­بندی استفاده شده است ]5[. در نمایش گرافی و آنتولوژیکال اسناد روشی که برای اندازه‌گیری شباهت به صورت معمول استفاده شده است بر اساس‌عبارت ساده­یimg0 است که در آنimg0 تعداد مفاهیم مشترک وimg0 مجموع کل مفاهیم دو سند است ]13[.

·       نمایش نوین آنتولوژیکال

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

 1. پیش پردازش اولیه

یک پاراگراف مجموعه­ای از چند جمله است که راجع به یک مفهوم خاص بحث می­نماید. اساس روش پیشنهادی با توجّه به این نکته است. در مرحلة پیش پردازش، پاراگراف­ها واحدّهای پردازشی هستند. ابتدا متن به پاراگراف­هایش تجزیه می‌شود. سپس برای هر پاراگراف عملیات پیش­پردازشی نظیر نشانه­گذاریی2، حذف کلمات نویزی و ریشه‌یابی صورت می­گیرد. در نهایت برای هر پاراگراف دو مجموعه از نشانه­ها نگهداری می‌شود: مجموعة نشانه­های اصلی و مجموعة ریشه­یابی شدة نشانه­های اصلی.

   2. نگاشت کلمات به مفاهیم آنتولوژی

مسئله­اي که هميشه به عنوان يک چالش مطرح بوده است چگونگي استخراج اطلاعات از آنتولوژی است. يکي از روش­هايي که مي­توان از آن استفاده کرد اين است که به طور مستقيم با استفاده از يک زبان پرس‌وجوي آنتولوژی، اطلاعات را از آنتولوژی استخراج نمود. روش دوم تبديل آنتولوژی به نوعي پایگاه داده­اي مانند RDBMS است تا بتوان با استفاده از زبان‌هاي پرس‌وجو، اطلاعات را از اين انباره بيرون کشيد. در الگوریتم پیشنهادی از روش دوم يعني نگاشت آنتولوژی به پايگاه داده براي استخراج اطلاعات استفاده شده است. به اين ترتيب که آنتولوژی از يک فايل OWL استخراج می­شود و سپس در يک پايگاه داده رابطه‌اي ذخيره می‌شود.جدول ایجاد شده به چندین جدول کوچک‌تر شامل کلاس­ها، نمونه­ها، ماتریس کلاس- کلاس و ماتریس کلاس- نمونه تبدیل می‌شود. جدول کلاس، شامل مفاهیم موجود در گراف آنتولوژی است. جدول نمونه‌ها، تمامی نمونه‌های موجود در آنتولوژی را در بر می‌گیرد. شکل 2 نمونه­اي از يک گراف آنتولوژی را با چهار مفهوم نمايش مي‌دهد که در آن گره­هاي img0،img0،img0،img0 نمايانگر مفاهیم آنتولوژی هستند. ارتباط بين کلاس­ها با img0ها نمايش داده شده است. براي تجزيه و تحليل آنتولوژی مي‌توان گراف آنتولوژیکال را توسط يک ماتريس مجاورت3 با سطر و ستون مساوي نمايش داد که در آن سطرها و ستون­ها نمايانگر نودهاي گراف يا همان کلاس­هاي آنتولوژی هستند. اعداد قرار گرفته در هر درایه ماتريس نيز نشان دهنده تعداد ارتباطات بين کلاس­هاي مربوطه خواهند بود ]22[.با استفاده از دیکشنری معکوس4 جدول دیگری از مفاهیم – کلمات ساخته شده است. به ازای مفاهیم موجود در آنتولوژی، صد کلمة مرتبط با هر کدام از این مفاهیم از دیکشنری یافت می­شود و در پایگاه داده ذخیره می‌شوند. کلمات استخراج شده از دیکشنری مجدداً توسط کارشناسان دامنه بررسی می­شوند و مرتبط­ترین کلمات برای هر مفهوم انتخاب می‌شوند.برای نگاشت کلمات به مفاهیم، با توجّه به مفاهیم موجود در آنتولوژی، تا چندین سطح از مفاهیم بررسی می‌شوند. در ابتدا مفاهیم مستقیم بررسی می­شوند. منظور از مفاهیم مستقیم مفاهیمی هستند که عبارت (نشانه) موجود در سند، مفهومی در آنتولوژی است. به ازای مفاهیم مستقیم تا چند سطح از فرزندان و پدران مفهوم یافت شده نیز در نظر گرفته می­شوند. به این مفاهیم، مفاهیم غیرمستقیم نوع 1 گفته می­شود. 

img0 

 

 

شکل 2- نمونه‌ای از یک گراف آنتولوژی

 اگر عبارت جزء مفاهیم مستقیم نبود به عنوان یک نمونه بررسی می‌شود که در این صورت تا چند سطح از پدران این نمونه نیز به مجموعة مفاهیم غیرمستقیم-1 (مفاهیم غیرمستقیم نوع 1) اضافه می‌شوند. در صورتی که عبارت مورد نظر مفهوم مستقیم یا نمونه نبود مفاهیم غیرمستقیم نوع 2 (مفاهیم غیرمستقیم-2) بررسی می­شوند. این نوع مفاهیم غیرمستقیم از جستجو در جدول مفاهیم- کلمات حاصل می­شوند. برای این مفاهیم نیز پدران و فرزندان تا چند سطح به مفاهیم غیرمستقیم-1 اضافه می‌شوند. در نهایت برای هر پاراگراف مجموعه­ای از مفاهیم مستقیم و غیرمستقیم نوع 1و2 با تعداد دفعات ارجاع به آن‌ها موجود است. برای مفاهیم غیرمستقیم-1 فاصله تا مفهوم مستقیم و همچنین تعداد دفعاتی که به عنوان والد یا فرزند انتخاب شده است نیز در نظر گرفته می‌شود.

 3. رفع ابهام از مفاهیم

در بخش قبل به مفاهیم غیرمستقیم نوع 1و2 اشاره شد. مشکلی که ممکن است در رابطه با این مفاهیم پیش آید ابهام است. یک مفهوم مستقیم ممکن است چندین والد یا فرزند به عنوان مفهوم غیرمستقیم نوع 1 داشته باشد. همچنین یک کلمه ممکن است متناظر با چندین مفهوم باشد. در کلیة این حالات مشکل ابهام پیش می­آید. برای این مفاهیم تعداد دفعاتی که به صورت مبهم شناسایی شده‌اند نگه‌داری می‌شود. پس از استخراج تمام مفاهیم یک پاراگراف، باید مفاهیم مبهم بررسی شوند و مناسب‌ترین آن‌ها باقی بمانند. روشی که برای رفع ابهام در این الگوریتم پیشنهاد شده است بدین ترتیب است که با­ توجّه به سایر مفاهیم مستقیم و غیرمستقیم غیرمبهم هر پاراگراف، مفاهیم مبهم پاراگراف رفع ابهام می­شوند و مناسب­ترین مفاهیم انتخاب می‌شوند. روش رفع ابهام بدین ترتیب است که ابتدا اهمّیت مفهوم مبهم در پاراگراف مزبور مشخص می‌شود. اگر تعداد ارجاعات بدون ابهام به یک مفهوم از 7/0 کل تعداد ارجاعات کم‌تر باشد، آنگاه از این مفهوم باید رفع ابهام کرد. در رابطه 5، img0 اهمّیت مفهوم مبهم را مشخص می­کند. اگرimg0 مفهومی باشد که برچسب مبهم داشته باشد، آنگاهimg0کل تعداد دفعات ارجاع به این مفهوم، img0 تعداد دفعاتی که این مفهوم به صورت مبهم شناسایی شده و img0 فاصلة این مفهوم غیرمستقیم مبهم تا مفاهیم مستقیم اصلی است.

img0 

(5)

اگر مفهومی کاملا مبهم باشد یعنی img0، به آن مقدار حدّاقلی غیر از صفر نسبت داده می­شود. سپس این مفهوم نسبت به سایر مفاهیم مستقیم و غیرمستقیم غیرمبهم ارزیابی می­شود. رابطة 6 ارزیابی نسبت به مفاهیم مستقیم را نشان می­دهد که در آن منظور از img0 مفهوم مستقیم و img0 مفهوم غیرمستقیم مبهم است. تابع img0 فاصلة بین دو مفهوم در آنتولوژی را می­یابد و تابع img0 تعداد مسیرهای ممکن بین دو مفهوم را مشخص می­نماید. رابطة 6 برای تمامی مفاهیم مستقیم محاسبه می‌شود و نتایج با یکدیگر جمع می­شوند.

img0 

(6)

رابطة 7 ارزیابی مفاهیم مبهم نسبت به مفاهیم غیرمستقیم غیرمبهم را نشان می­دهد. که img0 مفهوم غیرمستقیم غیرمبهم و img0 مفهوم غیرمستقیم مبهم است. این رابطه برای تمامی مفاهیم غیرمستقیم غیرمبهم محاسبه می‌شود و نتایج با یکدیگر جمع می‌شوند.

نتایج حاصل از رابطة 6 و 7 با یکدیگر جمع می­شوند، اگر مقدار به دست آمده از یک آستانه بیش‌تر بود از این مفهوم رفع ابهام می­شود در غیر این صورت مفهوم مورد نظر حذف می‌شود. اگر نسبت مفاهیم رفع ابهام شده به کل مفاهیم مبهم پاراگراف از یک آستانه مشخص کم‌تر باشد مفاهیم غیرمبهم یک پاراگراف قبل و یک پاراگراف بعد نیز بررسی می­شوند و راجع به مفاهیم مبهم پاراگراف فعلی تصمیم گرفته می­شود. این امر سبب می­شود، اگر پاراگراف فعلی از لحاظ مفاهیم غیرمبهم ضعیف باشد مفاهیم بی­سبب حذف نشوند و با دقت بیش‌تری بررسی شوند.

 

img0 

(7)

4. استخراج ساختار سلسله مراتبی مفهومی اسناد

پس از انجام مراحل فوق در نهایت برای هر پاراگراف مجموعه­ای از مفاهیم مستقیم و غیرمستقیم و اطلاعاتی راجع به آن‌ها در دسترس است. مرحلة آخر وزن­دهی به مفاهیم و ترسیم شمای گرافی سند است. به دلیل اهمّیت مفاهیم مستقیم و مفاهیم غیرمستقیم-2 در مضمون سند این مفاهیم با ضرایب بیش‌تری نسبت به سایر مفاهیم در نظر گرفته می‎شوند. برای وزن‌دهی به مفاهیم سند، تعداد ارجاعات هر مفهوم به تعداد کل ارجاعات نوع مفهوم مورد نظر تقسیم می­شود و برای هر مفهوم با توجّه به نوع آن، وزن منحصر به فردی در نظر گرفته می‌شود. پس از آن مفاهیم مستقیم و نمونه­هایی که در سند بوده­اند انتخاب می‌شوند و به کمک ماتریس­های کلاس- کلاس و کلاس- نمونه، روابط بین آن‌ها استخراج می‌شود و ماتریس روابط نظیر هر سند ایجاد می‌شود. بنابراین نودهای گراف و اوزان مربوط به آن‌ها ایجاد می‌شود.

به منظور ترسیم یال­های گراف و محاسبة اوزان آن‌ها، کلیة مفاهیم غیرمستقیم-2 به صورت مفهوم مستقیم در نظر گرفته می‌شوند و مفاهیم غیرمستقیم-1 که همنام با مفاهیم مستقیم هستند، بررسی می‌شوند. اگر این مفاهیم غیرمستقیم همنام به عنوان فرزند انتخاب شده باشند بنابراین جهت یال­ها باید از مفاهیم مستقیم پدر این مفهوم به مفهوم مستقیم مورد نظر باشد. اگر مفاهیم غیرمستقیم به عنوان پدر انتخاب شده­اند، جهت یال­ها باید از فرزندان مستقیم این مفهوم به مفهوم مربوطه باشند. برای محاسبة اوزان نظیـر یال­های ترسیم شده در گراف، از ماتریس روابط

نظیر سند استفاده می­شود. اوزان مفاهیم غیرمستقیم همنام، در تعداد رابطة بین دو مفهوم مورد نظر ضرب می‌شود و بر تعداد ارتباط گره مورد نظر با پدرانش (یا فرزندانش) تقسیم­ می‌شود. همچنین متناسب با فاصلة مفاهیم همنام غیرمستقیم، ضریبی در نظر گرفته می­شود. در رابطة 8 هدف بررسی پدران با فاصلة یک است. اگرimg0 مفهوم مستقیمی باشد که همنام با آن، مفهوم پدر غیرمستقیم با فاصلة یک نیز وجود داشته باشد، برای تمامی فرزندان آن،img0، یال­هایimg0 به img0 به صورت زیر محاسبه می‌شود که img0 بیانگر تعداد فرزندان مفهومimg0با فاصلة یک است، img0 وزن مفهوم غیرمستقیم همنام با مفهوم اصلی است وimg0 بیانگر تعداد ارتباط بینimg0 وimg0 است. ضریبimg0 را نیز می‌توان با توجّه به فاصلة مفاهیم غیرمستقیم مقدار داد. رابطة 8 برای فرزندان نیز به طریق مشابه نوشته می­شود.

img0 

(8)

در نهایت پس از محاسبة حالات مختلف از فرزندان و پدران با فواصل‌ متفاوت، گراف جهت داری تولید می‌شود که نودهای آن مفاهیم مستقیم هستند. اوزان این مفاهیم و یال‌های مربوطه نیز از طریق توضیحات بیان شده و رابطة 8 محاسبه شده‌اند. گراف ایجاد شده برای هر سند به صورت ماتریس در پایگاه داده ذخیره می‌شود تا در مراحل محاسبة ماتریس شباهت بین اسناد و کاوش آن‌ها، به راحتی قابل بازیابی باشند.

به عنوان یک مثال، شکل 3 یک سند دلخواه در زمینة هتل است. از آنتولوژی دامنه مورد نظر جداول و ماتریس‌های مذکور ساخته شده‌اند و طبق روال توضیح داده شده، شکل 4 گراف آنتولوژیکال تولید شده را نمایش می‌دهد که شامل مفاهیم، اوزان و یال‌های آن‌ها است. با توجّه به اوزان مفاهیم، کلیت سند راجع به مفاهیم hotel و luxury hotel است. با توجّه به این اوزان می‌توان به سادگی مفاهیم کلی و پراهمّیت و مفاهیم جزئی را مشخص نمود. به عبارت دیگر این اوزان را می‌توان همانند درجة عضویت فازی تفسیر نمود که سند با چه درجه عضویتی به هر مفهوم متعلق است. در مورد اوزان و جهات یال‌ها نیز می‌توان چنین تفسیری ارائه داد. در واقع با توجّه به آنتولوژی موجود، شمای گرافی سند، زیر مجموعه‌ای از همان آنتولوژی است که اوزان یال‌ها و نودها در آنتولوژی اصلی 0.100 است اما در اسناد با توجّه به مضمون و مفهوم سند این اوزان مقادیر مختلفی می‌گیرند.

img0 

 

 

 

 

 

 

 

 

 

شکل 2- نمایش یک سند در زمینه هتل

 

·       معیار شباهت متناسب با نمایش آنتولوژیکال

مهم‌ترین گام­ها برای بهبود روال­های کاوش اسناد، نمایش مفهومی مناسب و معیار شباهت متناسب با این نمایش است. هرچه معیار شباهت توانایی بیش‌تری برای تقریب سطوح اختلاف و تشابه بین اسناد داشته باشد، مناسب­تر و کاربردی­تر است. روش آنتولوژیکال پیشنهادی، دارای چهار جزء با معنی است که برای تعیین شباهت و تفاوت بین اسناد کلیدی می­باشند: مفاهیم و اوزان هر مفهوم، یال­ها و اوزان منتسب به هر یال. معیار پیشنهاد شده برای مفاهیم و یال­ها به صورت مجزا محاسبه می­شود و خروجی آن ماتریس­های شباهت مجزا برای مفاهیم و یال­ها است. در مراحـل بعد مبتـنی بر ماتریس شبـاهت محاسبـه شده و با

 

 

img0 

 

[1] . Projection

[2]  .Tokenization

[3] . Adjacency Matrix

[4]  .Inverse Dictionary

شکل 3- گراف آنتولوژیکال سند در شکل (3)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

        

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

معیار پیشنهادی، درجة عضویت، اولویت و اهمّیت هر مفهوم را در نظر می­گیرد و براساس مفاهیم مشترک (یال‌های مشترک) هر دو سند میزان شباهت بین دو سند را تقریب می­زند. برای هر مفهوم مشترک در هر دو سند، دو وزن img0 و img0 محاسبه می­شود و در نهایت به کمک این اوزان میزان شباهت دو سند تقریب زده می­شود. رابطه­های 9 و 10 به ترتیب محاسبه اوزان img0 و img0 را بیان می‌نمایند که img0 وزن مربوط به تفاوت اولویت و اهمّیت مفاهیم و img0 مربوط به اختلاف اوزان مفاهیم مشترک دو سند است. در رابطة 9 img0 مفهوم مشترک img0 در سند img0 است، img0 اولویت مفهومimg0  را در سند img0  مشخص می­نماید،img0 وimg0 دو سند دلخواه هستند که هدف محاسبه شباهت بین آن دو است و img0 حدّاکثر اختلاف اهمّیت مفاهیم مشترک بین دو سند تعریف شده است. در رابطة 10img0 وزن مفهوم مشترکimg0 در سند img0 است.

 

img0 

(9)

img0 

(10)

رابطة 11 بیانگر معیار شباهت برای اندازه­گیری شباهت بین دو سند img0 وimg0 است. در این رابطه،img0 بیانگر تعداد مفاهیم مشترک دو سند است، نماد  بیانگر اندازة مجموعه (تعداد مفاهیم) بوده و img0  است.

 

img0 

(11)

·       سیستم استنتاج فازی

سيستم‌هاي فازي، سيستم‌هاي مبتني بر دانش يا قواعد هستند؛ قلب يك سيستم فازي يك پايگاه دانش است كه از قواعد اگر ـ آنگاه فازي تشكيل شده است. يك قاعده اگر ـ آنگاه فازي، يك عبارت اگر ـ آنگاه است كه بعضي كلمات آن به وسيلة توابع عضویت پيوسته مشخص شده‌اند. موتور استنتاج فازي، اين قواعد را با يك نگاشت از مجموعه‌هاي فازي در فضاي ورودي به مجموعه‌هاي فازي و در فضاي خروجي بر اساس اصول منطق فازي تركيب مي‌كند.  

سیستم استنتاج فازی متشکل از سه بخش فازی‌سازی، موتور استنتاج فازی و غیرفازی‌سازی است. در بخش فازی‌سازی یک متغیر crisp با استفاده از توابع عضویت تعریف شده به یک متغیر زبانی تبدیل می‌شود. در بخش دوم با استفاده از قوانین فازی (قوانین اگر-آنگاه) مقدار خروجی فازی تولید می‌شود. بخش غیرفازی‌سازی مقدار خروجی فازی از موتور استنتاج را با استفاده از توابع عضویت تعریف شده، به یک مقدار crisp تبدیل می‌نماید. این روند در شکل 5 نشان داده شده است. سیستم استنتاج طراحی شده در این بخش دارای سه ورودی است: میزان شباهت مفاهیم کلی، میزان شباهت مفاهیم جزئی و میزان شباهت یال‌های موجود در شمای گرافی اسناد. مفاهیم جزئی و کلی هر سند به صورت نسبی مشخص می‌شود.

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

برای هر یک از ورودی‌های سیستم استنتاج، سه تابع عضویتimg0، مطابق با شکل 6 مشابه با توابع عضویت در ]13[، تعریف شده است. محور افق بیان‌گر میزان شباهت بین اسناد و محور عمودی درجه عضویت را نشان می‌دهد. موتور استنتاج فازی ممدانی برای فازی‌سازی مقادیر ورودی استفاده شده است. مدل سیستم استنتاج فازی ممدانی از عملگر img0 استفاده می‌نماید.

img0 

(12)

 

شکل 4- ساختار سیستم استنتاج فازی ]23[

 

img0                        

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

        

 

 

شکل 5- توابع عضویت ورودی فازی

 

img0 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

        

موتور استنتاج طراحی شده به منظور خوشه‌بندی از بیست و هفت قانون فازی که در جدول 1 بیان شده است، استفاده می‌نماید. هر سطر از این جدول بدین گونه تفسیر می‌شود (قانون1):

 

img0اگر خوشه‌بندی اسناد فقط در یک دامنة مشخص باشد و هدف خوشه‌بندی دقیقی از اسناد یک دامنه باشد، ساختار مفهومی این اسناد در تعیین شباهت بین آن‌ها دارای اهمّیت است. اگر خوشه‌بندی در چند دامنه صورت گیرد و هدف یافتن یک خوشه‌بندی کلی بر اساس موضوعات دامنه باشد، ساختار مفهومی اسناد تأثیر چندانی در تعیین شباهت بین اسناد ندارند و در عوض مفاهیم کلی دارای اهمّیت بیش‌تری هستند. بنابراین اگر هدف خوشه‌بندی جزئی اسناد ‌باشد، جدول similaity1 و اگر هدف خوشه‌بندی کلی باشد similaity2، به کار گرفته می‌شوند. خروجی سیستم فازی دارای سه تابع عضویت با مقادیر شباهت img0 است. در نهایت با استفاده از روش

 

غیرفازی‌سازی مقدار شباهت نهایی بین دو سند تخمین زده می‌شود. بنابراین می‌توان مراحل زیر را برای محاسبة شباهت بین اسناد بیان نمود:

محاسبة شباهت بین مفاهیم جزئی، کلی و یال‌های اسناد استفاده از سیستم استنتاج فازی و تولید خروجی فازی غیرفازی‌سازی خروجی و محاسبة مقدار نهایی شباهت دو سند خوشه‌بندی سلسله مراتبی اسناد بر اساس ماتریس شباهت نهایی برای غیرفازی کردن مقادیر شباهت خروجی دو مرحله وجود دارد. مرحلة اول مشخص نمودن میزان شباهت بین اسناد (High,Low,Medium) است. دومین مرحله غیرفازی کردن مقدار این شباهت است. سیستم ممدانی برای مشخص نمودن میزان شباهت بین اسناد از روش Max گیری استفاده می‌نماید. در سیستم استنتاج فازی مطرح شده، پنج حالت ممکن است بین توابع عضویت متغیر خروجی رخ دهد که در رابطة 13 بیان شده‌اند. منظور از img0 میزان درجه عضویت به شباهت High، منظور از img0 میزان درجه عضویت به شباهت Low و منظور از img0 میزان درجه عضویت به شباهت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

 

 

 

 

 

 

(13)


شکل 6- روال محاسبة درجة عضویت به شباهت Low  با ورودی‌های ( 15%، 75%،25%)

img0        

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

به عنوان مثال، فرض می‌شود میزان شباهت دو سند، بین مفاهیم اصلی مقدار 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. خوشه‌بندی اسناد

پس از محاسبة ماتریس شباهت نهایی بین اسناد، با استفاده از الگوریتم خوشه‌بندی سلسله مراتبی پایین به بالا خوشه­بندی انجام می‌شود. الگوریتم خوشه‌بندی در گام‌های زیر صورت می‌پذیرد: هر سند به عنوان یک خوشه در نظر گرفته می‌شود. ترکیب دو خوشةimg0 بر اساس بیش‌ترین شباهت بین این اسناد محاسبة شباهت بین خوشة جدید و سایر خوشه‌ها بر اساس روش centroid-linkage و ترکیب نزدیک‌ترین خوشه‌ها در ادامه، مرحلة سوم تا زمانی که تنها یک خوشه باقی بماند، تکرار می‌شود.

 

 

img0 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

شکل 7- روال غیرفازی‌سازی برای ورودی‌های شکل 7

 

روش centroid-linkage از فاصلة بین مراکز خوشه‌ها استفاده می‌نماید. اگرimg0 یک شی در خوشهimg0 و img0 یک شی در خوشهimg0 وimg0 به ترتیب تعداد اشیاء در خوشه‌هایimg0 وimg0 باشند، آنگاه فاصلة بین دو خوشه از طریق رابطة 14 محاسبه می‌شود کهimg0،img0امین شی در خوشةimg0 است. شکل 9 این اندازه‌گیری را برای دو خوشه‌ی L,K نشان می‌دهد.

 

img0 

(14)

img0 

شکل 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 بیان شده‌اند. مقدار img0، تعداد جفت متونی است که در خوشه و دستة یکسانی ظاهر شده­اند. مقادimg0 به ترتیب false positive، false negative و true negative هستند.آزمايش‌های انجام شده براي ارزيابي الگوریتم پیشنهادی بر روي يک سيستم با ويندوز ویستا، با پردازندة دو هسته‌ای 2.53 گيگا هرتز اينتل همراه با 4 گيگا بايت حافظه، براي اسناد انگلیسی انجام گرفته است. مقدار آستانه برای رفع ابهام از یک مفهوم، به دست آوردن نمره‌ای بیش‌تر از 80 است. برای هر مفهوم مستقیم تعداد چهار سطح از فرزندان و چهار سطح از پدران اضافه می‌گردد.همچنین در مرحلة رفع ابهام در صورتی از مفاهیم پاراگراف‌های قبل و بعد استفاده می‌شود که نسبت مفاهیم رفع ابهام شده پاراگراف فعلی به کل مفاهیم مبهم    

 

 

img0                

 

[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- بخشی از آنتولوژی پیتزا

 

 

 

 

 

 

 

 

img0 

 

 

 

 

 

 

 

 

 

 

 

 

شکل 10- بخشی از آنتولوژی کامپیوتر

 

 

 

پاراگراف از 15% کم‌تر باشد. برای خوشه‌بندی تمامی اسناد از 1 تا 250 شماره‌گذاری می‌شوند و در یک مسیر مشخص قرار می‌گیرند. همانگونه که اشاره شد از پنج الگوریتم برای خوشه‌بندی دویست پنجاه سند در سه دامنة پیتزا، کامپیوتر و نوشیدنی‌ها استفاده شده است. برای خوشه‌بندی اسناد با روش CA-IBC، الگوریتم صد مرتبه با حالات برچسب‌گذاری اولیة مختلف اجرا می‌شود و نتیجة نهایی به صورت میانگین این نتایج اعلام می‌شود. برای این الگوریتم دو حالت در نظر گرفته شده است: 1- روش برچسب‌گذاری اولیه کاملاً تصادفی انجام شود (random). 2- فرض می‌شود که در صد مرتبه اجرا، اسناد مناسب به عنوان مرکز اولیة خوشه در نظر گرفته شوند (best). شکل‌های 12، 13، 14، 15، 16و17 نتایج ارزیابی پنج الگوریتم را نشان می‌دهند. شکل 20 به صورت میانگین شش معیار فوق را در پنج الگوریتم بررسی می‌کند.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

شکل 11- مقایسة پنج روش با معیار Precision

 

img0 

(15)

img0 

(16)

img0 

(17)

img0 

(18)

img0 

(19)

img0 

(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، در خوشه‌بندی جزئی با موفقیت بیش‌تری عمل کرده است. نمایش دقیق مفهومی اسناد، معیار شباهت متناسب با این نمایش و سیستم استنتاج فازی باعث برتری روش پیشنهادی شده است. البته به علّت تشابه بیش‌تر ساختار مفهومی اسناد، این خوشه‌بندی کمی مشکل‌تر از خوشه‌بندی کلی است.

 

نتیجه‌گیری

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

 

img0 

شکل 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

 

 

 

 


مقالات مرتبط

حقوق این وب‌سایت متعلق به سامانه مدیریت نشریات رایمگ است.
حق نشر © 1403-1396

صفحه اصلی| عضویت/ ورود| درباره رایمگ| تماس با ما|
[English] [العربية] [en] [ar]