منبع تحقیق با موضوع خوشه‌بندی، درخت تصمیم، قوانین انجمنی، تحلیل داده

)

شکل (3-4) سیستم رده‌بندی متن و مدیریت دانش مبتنی MKTPKS
3-7-2-1-2- تشکیل پایگاه داده رابطه‌ای
خروجی کاربرد خوشه‌بندی K-Means باید به صورت فرمت‌های قابل استفاده در جداول رابطه‌ای مختلف ذخیره‌سازی گردد. این جداول شامل ستون‌هایی به همراه شناسه خوشه‌بندی هستند، خوشه‌بندی و برچسب‌گذاری خوشه‌ها بیشتر در پردازش‌های هرس اطلاعات کلیدی یا کشف دانش مورد استفاده قرار می‌گیرد، این عملکرد به ذخیره‌سازی و مدیریت اطلاعات برای بیشتر تحلیل‌ها کمک می‌نماید.
3-7-2-2- سطح دوم: واحد پالایش دانش
ورودی این واحد در قالب جداول رابطه‌ای که در آن اسناد به عنوان معاملات یا تراکنش‌های انجام شده شرایط به عنوان اقلام در نظر گرفته می‌شوند. فرایند با پالایش اطلاعات و دانش کلیدی به همراه تولید NKTPKS و از طریق کاربرد قوانین انجمنی APRIORI جهت کاوش انجام گردیده است. در ساخت MKTPKS یک بخش اساسی و ضروری استفاده از تحلیل داده‌ها برای رده‌بندی مستندات متنی است. ساخت MKTPKS بر یافتن قوانین انجمنی ارجحیت دارد به دلیل آن که شناسایی بیش از حد قوانین موجب ازدیاد جمعیت در پایگاه دانش می‌گردد. علاوه بر این MKTPKS می‌تواند به کشف روابط باارزش‌تر در شرایط تعریف شده در متن کمک نماید. این اعمال به یافتن ارتباطات در میان مفاهیم مختلف تعریف شده در مستندات متنی کمک می‌نماید. نگاشت MKTPKS های کشف شده به مجموعه‌های ویژه از مستندات به شناسایی مجموعه مستندات حاوی اطلاعات خوب و بد کمک می‌نماید.152
3-7-2-3- سطح سوم: واحد رده‌بندی متن و کاربرد دانش
داده‌ها اصولاً به صورت پایگاه داده نیمه ساختار یافته و نه به طور کاملاً ساختار یافته و نه بدون ساختار در طبیعت ذخیره می‌شوند. برای رده‌بندی داده‌های متنی به کلاس‌ها از پیش تعریف شده لازم و ضروری است. مجموعه مورد نظر به صورت دستی به کلاس‌های متفاوت جهت آزمون و صحت رده‌بندی افراز گردد. این افراز به کمک کارشناسان دامنه صورت می‌پذیرد. خصیصه‌های طبقه‌بندی مجموعه‌ای از ویژگی‌های کلاس یا متغیر هدف است. در این پژوهش این کار با کمک کارشناسان حوزه که درک درستی از زمینه‌های داده‌های متنی و معنای شرایط تعریف شده در اسناد متنی دارند صورت پذیرفته است. در واحد سطح سوم رده‌بندی‌های متفاوت استفاده می‌شوند که جهت مطالعه تأثیرات شرایط رده‌بندی داده‌های متنی به دو کلاس مختلف که می‌تواند ساخت رده‌بندی مستندات را با دقت بیشتری بهبود دهد. رده‌بندی‌های خاص مطرح شده در پژوهش جاری عبارت‌اند از اول درخت تصمیم‌گیری (C 4.5)، دوم نزدیک‌ترین همسایه (K-NN)، سوم بیز ساده (NaiveBayes) و چهارم ماشین‌های پشتیبان بردار (SVMs). نتیجه این آزمون رده‌بندی‌های متفاوت به وسیله تغییرپذیری مبتنی بر انتخاب متغیرهای اطلاعاتی بر روی محدوده معیارهای فاصل‌هایی متفاوت، از معیار فاصله اقلیدسی ساده تا متدهای مبتنی بر هسته روش ارائه شده در پژوهش مذکور است. هدف از رده‌بندی، اعتبارسنجی فرضیه مبتنی بر متد ارائه‌شده بر روی MKTPKS جهت بهبود صحت رده‌بندی بر روی الگوریتم‌های رده‌بندی است.153
3-7-3- تحلیل و طراحی
الگوریتم تحلیل درخت تصمیم اکثراً برای مشکلات رده‌بندی و فرایند ساخت شروع درخت تصمیم به وسیله انتخاب گره تصمیم و جداسازی آن به زیر گره و برگ مورد استفاده قرار می‌گیرد. الگوریتم درخت تصمیم C4.5 توسعه‌یافته الگوریتم ID3 است. این الگوریتم مبتنی بر ساخت درخت تصمیم و جداسازی به وسیله گره‌های تصمیم به وسیله انتخاب جداسازهای بهینه و ادامه جستجو در حد امکان می‌باشد. برای استفاده از مفاهیم بهره‌اطلاعاتی و کاهش آنتروپی جهت کسب تقسیم مطلوب از رابطه‌های ذیل استفاده می‌نماییم. فرض نمایید متغیر X ارزش K احتمال ممکن p1,p2,…,pk را داشته باشد آنگاه آنتروپی X از رابطه زیر محاسبه می‌گردد. فرمول 3-2:
H(X)= -∑pjlog2(pj)
برای محاسبه میانگین مورد نیاز اطلاعات می‌توان از مجموع وزن‌دار آنتروپی برای زیرمجموعه‌های فردی (مجزا) استفاده نمود. فرمول 3-3:
Hs (X)=∑i=1k Pi Hs(Ti)
لازم به ذکر است Pi نشان‌دهنده نسبت رکوردها در زیرمجموعه‌های i است. برای محاسبه بهره اطلاعاتی از رابطه زیر استفاده نمود.
فرمول 3-4:
information gain IG(S)=H(T)-Hs(T)
3-7-3-1- الگوریتم نزدیک‌ترین همسایه (K-NN)
الگوریتم نزدیک‌ترین همسایه تکنیکی است که می‌توانید جهت رده‌بندی داده‌ها به وسیله استفاده از معیار فاصله استفاده نمایید. [64] الگوریتم نزدیک‌ترین همسایه از طریق نمونه‌های آموزشی کار می‌نماید که در این روش مجموعه نه تنها شامل داده‌ها می‌گردد بلکه طبقه‌بندی مورد نظر برای هریک از آیتم‌ها صورت می‌پذیرد. در واقع داده‌های آموزش مدل می‌شوند. الگوریتم K-NN در اصل به وسیله پیدا کردن حداقل فاصله از نمونه‌های ورودی جدید از نمونه‌های آموزشی کار می‌نماید. بر اساس معیار فوق هر نمونه ورودی جدید در کلاس مربوط به خود قرار می‌گیرد. معمول‌ترین تابع محاسبه فاصله، فاصله اقلیدسی است که در فرمول 1 به آن اشاره گردیده است.
3-7-3-2- الگوریتم بیز ساده (Naïve Bayes)
الگوریتم بیز ساده یک روش سهل و خوب شناخته شده رده‌بندی است که برای حل مشکلات حوزه عملی مورد استفاده قرار می‌گیرد. [64] رده‌بندی بیز ساده برای یافتن احتمالات مشترک از کلمات و کلاس‌ها از مجموعه رکوردها استفاده می‌گردد. این رویکرد مبتنی بر تئوری بیز ساده است. احتمال کلاس c در مستند dj از رابطه زیر به دست می‌آید.. در این الگوریتم فرض براین است که طبقات مستقل از یکدیگر هستند که با عنوان استقلال مشروط کلاس مطرح می‌گردد. فرمول 3-5:
P(c /dj)=(P(dj / c)P(c))/(P(dj)) j=1,2,3,…,m
3-7-3-3- الگوریتم ماشین‌های پشتیبان بردار (SVMs)
الگوریتم SVM اولین بار در سال 1960 در روسیه توسعه داده شد. این الگوریتم رده‌بندی غیرخطی است که از متدهای غیرخطی استفاده می‌کند و داده‌ها را از فضای ورودی یا فضای پارامتری به فضای ویژگی‌هایی با ابعاد زیاد نگاشت می‌نماید. [64] هدف این الگوریتم انتخاب ابرصفحه جداساز بهینه جهت حداکثرسازی حاشیه بین دو کلاس است. برای حل مشکل طبقه‌بندی دودویی که در آن W1 و W2 نشان‌دهنده دو کلاس در یک مجموعه داده‌های آموزشی هستند، مجموعه X={x1,x2,…,xn} به همراه برچسب کلاس ارائه شده است. ابرصفحه‌ایی که داده‌های مجزا را به دو کلاس طبقه‌بندی می‌نماید به شرح زیر است.
فرمول 3-6:
f(x)=sgn( + b)
در رابطه بالا w بردار ضریب و b میزان تمایل به یک‌طرف (چولگی) ابرصفحه و sgn مخفف تابع دوقطبی است. مشکل بهینه‌سازی که منجر به تولید ابرصفحه می‌گردد به صورت زیر نوشته می‌گردد.
فرمول 3-7:
Minimizew,x 1/2||w||2
فرمول 3-8:
Yi(+b)=1, for i= 1,2,…,N
بزرگ‌تر شدن حاشیه باعث بهترشدن توانائی تعمیم انتظار می‌گردد. درخت تصمیم (C 4.5)، نزدیک‌ترین همسایه، بیز ساده و ماشین‌های پشتیبان بردار که در مراحل قبل در مورد آن‌ها توضیحاتی ارائه شد جهت رده‌بندی داده‌های متنی در این پژوهش مورد استفاده قرار گرفته‌اند. الگوریتم روی مجموعه داده‌های منتقل شده از مجموعه ویژگی‌های کاندید و خصیصه‌ها اعمال می‌گردد و یک کاربرد ترکیبی (Hybrid) از سطح 1 (واحد ذخیره‌سازی و پردازش دانش) و سطح 2 (واحد پالایش دانش) صورت می‌پذیرد. نتایج کاربرد این رویکرد ترکیبی ساخت مجموعه MKTPKS است. این عمل با استفاده از رویکرد خوشه‌بندی صورت می‌پذیرد. در نتیجه یک فضای وجود یا عدم وجود برای عبارات کلیدی در اسناد ساخته می‌شود. هر نماینده بردار از اسناد با استفاده از مجموعه MKTPKS 3TermSets انجام می‌پذیرد. رابطه لیستی از عبارات کلیدی تشکیل شده و وجود آن‌ها را در اسناد و نماینده مربوط به کلاس‌ها در شکل 3-5 نشان داده شده است.154 (اگر نامزد مجموعه باشد مقدار 1 و در غیراینصورت مقدار 0 به خود اختصاص داده است)
Ci: برچسب کلاس با توجه به داده‌های آموزشی
Fm: نماینده مجموعه MKTPKS 3TermSets
Fm

……………………

F5
F4
F3
F2
F1

Ci
1
……………………
0
1
0
1
Doc.ID
شکل (3-5) نمایش نامزدهای مجموعه termset

بنابراین کل فضای مستندات به فرم MKTPKS 3TermSets انتقال داده شده‌اند و اطلاعات کلیدی به دقت به فرم داده‌های متنی تعریف شده‌اند. ماتریس جدید کارایی در فعالیت‌های رده‌بندی جهت تقسیم مستندات به دو کلاس متفاوت دارد. در این بخش جهت تحلیل داده‌ها نیاز به مطالعه برای به کار بردن الگوریتم‌های داده‌کاوی متفاوت خواهیم داشت. داده‌ها باید به فرمت مناسب تبدیل گردند. داده‌ها برای پردازش بیشتر در فایل متنی تثبیت می‌گردند. کلمات توقف نیز از داده‌های متن حذف شدند و یک متد ریشه‌یابی ساده نیز اعمال گردیده است. این متد داده‌کاوی متنی به کاهش ابعاد داده با حفظ فضای اطلاعات مفید و بدون از دست دادن اطلاعات کلیدی کمک می‌نماید. واحد سطح اول: فایل متنی ذخیره شده را در نرم‌افزار Weka یا RapidMiner بارگذاری می‌نماییم که از طریق آن با به‌کارگیری تکنیک‌های خوشه‌بندی متفاوت می‌توان به درک اولیه و کشف و تسخیر و عبارات کلمه کلیدی دانش دست یافت. الگوریتم خوشه‌بندی k-means جهت جداسازی فضای اطلاعاتی ورودی به اعداد و زیر فضاها اعمال می‌گردد. تعداد زیادی از آزمایش‌ها برای پیدا کردن یک تعداد مناسب خوشه‌ها به منظور کاهش اثر از دست دادن اطلاعات صورت می‌پذیرد. کاربرد تکنیک خوشه‌بندی تسخیر اطلاعات کلیدی با اولین سطح از دانش در عبارات کلمه کلیدی کمک می‌نماید. اطلاعات کلیدی تسخیر شده در خوشه‌های مختلف به مجموعه‌های مختلف از اطلاعات موجود در هر سند155 اشاره دارد، بنابراین تفسیر این اطلاعات کلیدی و این که دقیقاً اسناد حاوی اطلاعات خوب یا بد هستند دشوار است. در گام دوم یعنی واحد پالایش دانش از قوانین انجمنی الگوریتم APRIORI جهت کاوش MKTPKS استفاده می‌شود. ورودی در قالب جداول رابطه‌ای که در آن اسناد به عنوان معاملات و تراکنش‌ها به عنوان اقلام است در نظر گرفته می‌شود. خروجی به شکل MKTPKS 3-Termsets خواهد بود. همکاری این عبارات جهت تولید 3-TermSets MKTPKS به عنوان یک نهاد واحد برای نمایش موضوعات کلیدی مورد بحث در اسناد پایگاه داده متنی داده شده است. با توجه به مثال قبل در این سطح برای پیدا نمودن موضوعات کلیدی مورد بحث در پایگاه داده متنی دچار مشکل می‌شویم و رده‌بندی اسناد به اطلاعات خوب و بد به درستی و با صحت و دقت صورت نمی‌پذیرد. به منظور غلبه بر این مشکل روند استخراج اطلاعات مفید در اسناد مدون مذکور به تصفیه بیشتر نیاز دارد، این پالایش از اطلاعات کلیدی و یا کشف دانش در سطح 1، از طریق کاوش قوانین انجمنی APRIORI صورت می‌پذیرد. لازم به ذکر است قبل از کاربرد این کاوش، اطلاعات کلیدی تسخیر شده از عبارات کلیدی نیاز به ذخیره‌سازی خواهند داشت. این فعالیت یک پایگاه داده رابطه‌ای با استفاده از جداول حاوی برچسب‌های خوشه‌ای، اصطلاحات کلیدی شناسایی‌شده و کد شناسایی اسناد (شناسه) ایجاد می‌نماید. این جداول رابطه‌ای به فرم MKTPKS مورد استفاده قرار می‌گیرند که اولاً باعث کاهش تعداد ابعاد در فضای ویژگی و ثانیاً جهت اعتبارسنجی فرضیه برای دستیابی به دقت بالاتر در رده‌بندی می‌شوند. بخش رده‌بندی و بهره‌برداری از دانش نشان می‌دهد که روش‌های مورد استفاده برای رده‌بندی داده‌های متنی به دو کلاس مختلف تقسیم می‌گردد. نتایج به دست آمده از کاربرد سطح 2 (واحد پالایش دانش) به فرم مدل ماتریس جدید مبتنی بر MKTPKS 3-termSets که در بخش‌های قبل مورد بررسی قرار گرفت در دسترس خواهند بود. ماتریس جدید در نرم‌افزار Weka و یا RapidMiner بارگذاری شده و چهار الگوریتم رده‌بندی مختلف در رده‌بندی کلاس‌های مربوطه به کار برده می‌شوند. مجموعه متغیر هدف برای این منظور به کار برده شده تا متغیر کلاس تعداد اسناد حاوی اطلاعات خوب یا بد را مشخص نماید. هدف از آموزش سیستم و تعیین نرخ رده‌بندی صحیح و نادرست بود. نتایج به دست آمده از طریق رده‌بندی‌های مختلف در MKTPKS 3-termsets بر اساس مدل ماتریس بوده