بخشی از مقاله
خلاصه
با توجه به حجم روز افزون اطلاعات متنی، نیاز به تسریع و افزایش دقت بازیابی اطلاعات متنی امری ضروری به نظر می رسد. خوشه بندی اسناد یکی از تکنیک هایی است که می توان از آن به منظور بهبود فرایند بازیابی اطلاعات استفاده کرد. به همین منظور در این مقاله ضمن معرفی و بررسی چند نمونه از روش های خوشه بندی و طبقه بندی از جمله K-Means و KNN و ... برای طبقه بندی اسناد با استفاده از خوشه بندی روش جدیدی پیشنهاد می شود که در آن با بهره گیری از الگوریتم تکاملی داده ها را خوشه بندی می کنیم که در مقایسه با روش K-Means با دقت بیشتری صورت می گیرد و در نهایت داده ها با روش KNN طبقه بندی می شوند. استفاده از الگوریتم پیشنهادی برای به کارگیری خوشه بندی متون قبل از طبقه بندی منجر به افزایش سرعت محاسبات می گردد.
.1 مقدمه
با پیشرفت تکنولوژی و تئوری اطلاعات، نیاز بشر به دسته بندی و مدیریت اطلاعات روز به روز افزایش میابد. در هنگام مواجهه با حجم داده های بزرگ، برای جلوگیری از پراکندگی، در هم ریختگی و همچنین مدیریت بهینه و پردازش مناسب آن ها، طبقه بندی و شناسایی الگوها می تواند نقش موثر و مهمی در تجزیه تحلیل داده ها داشته باشد.
خوشه بندی و طبقه بندی به عنوان دو رکن اصلی در استخراج اطلاعات می باشند. ما می توانیم از خوشه بندی برای کمک به طبقه بندی اطلاعات یا به عنوان یک روش جایگزین برای کاهش ابعاد استفاده نماییم. تاکنون روش های متعددی برای طبقه بندی و خوشه بندی در زمینه های مختلف پیشنهاد شده است، که در اینجا به اختصار تعدادی از آن ها را بررسی می کنیم.
خوشه بندی اسناد به معنی گروه بندی اسناد است به نحوی که اسناد درون یک گروه دارای بیشترین شباهت و اسناد گروه های مختلف نسبت به هم دارای کمترین شباهت باشند. خوشه بندی اسناد دارای کاربرد های زیادی در پردازش متن مانند بازیابی سریع اطلاعات، سازماندهی بدون ناظر اسناد و غیره می باشد. همچنین برای افزایش کارایی در موتورهای جستجو، نتایج حاصل از جستجو را با استفاده از خوشه بندی اسناد ارائه می کنند.
داده ها می توانند در اشکال مختلف باشند همانند : متن، تصویر، فرم فضایی و غیره .در این میان رایج ترین شکل داده ها که ما در حال بررسی فوق العاده آنها هستیم داده های متنی، شناسایی اثر انگشت، تشخیص چهره و غیره یکی از ساده ترین و متداول ترین روش ها درمیان روش های خوشه بندی با الگوریتم تکراری، روشی به نام K-means است که در آن داده ها به k گروه متمایز تقسیم می شوند.
در این روش، فاصله ی هر نمونه ی آزمایشی جدید ابتدا با تمام مراکز خوشه ها اندازه گیری می شود و سپس نمونه ی جدید نزدیک ترین خوشه نسبت به خود را انتخاب کرده و با آن خوشه بندی می گردد. KNN روش دیگری است که اولین بار توسط E.Fix و J.Hodges ارائه گردید و الگوریتم آن شامل محاسبه ی فاصله اقلیدسی درمیان نقاط نمونه های آزمایشی و تشکیل ماتریس فواصل بین تمام جفت نقاط موجود - x,y - است. هریک از نقاط داده در این مجموعه به کلاسی تعلق دارند که با برچسب های'…'F11c={c} تعیین می گردند.
سپس به تعداد K نمونه آموزشی دارای کمترین فاصله از نمونه آزمایشی انتخاب شده و با توجه به برچسب کلاس آنها، در مورد برچسب کلاس داده آزمایشی موردنظر تصمیم گیری می شود Isomap .روش دیگری است برای یادگیری Manifold است، که در آن سعی می شود ویژگی ها را از فضایی با ابعاد زیاد به فضایی با ابعاد کم تبدیل کند به گونه ای که ساختار اصلی ویژگی ها حفظ شود. به عنوان مثال کاهش ابعاد تبدیل مجموعه داده X با ابعاد D به یک مجموعه داده جدید Y با ابعاد d - d<<D - در حالی که ساختار اصلی آن حفظ شود.
در خوشه بندی انتخاب معیار شباهت مناسب یک گام مهم در استخراج اطلاعات است. در معیار شباهت، شباهت یک تابع حقیقی با ارزش است که شباهت بین دو داده را اندازه گیری می کند. طبقه بندی اطلاعات بر اساس خوشه های استخراج شده صورت می گیرد. بر فرض مثال مقدار زیادی داده بدون برچسب در اختیار داریم که بر چسب زدن آنها توسط انسان بسیار زمان بر بوده و فرایند پر هزینه ای است استفاده از روش ذکر شده - طبقه بندی بر اساس خوشه بندی - مزایای خاص خود را دارد. به طور عمده دارای 4 ماژول می باشد که عبارت اند از : -1 پردازش -2 خوشه بندی -3 محاسبه تشابه -4 طبقه بندی.
.2 پردازش
پیش پردازش : هر مجموعه داده - بر فرض مثال : متن - را در مدل فضای برداری به صورت بسته ای از کلمات نمایش می دهیم. در سیستم پردازش اطلاعات - متن - از فعالیت هایی نظیر استخراج استفاده می شود که شامل: ریشه یابی، حذف کلمه متوقف، تشکیل بردار با توجه به شکل شماره . - 1 - استخراج از طریق Tokenization از فایل انجام می شود .Tokenization روند شکستن یک جریان از متن به کلمات، عبارات، علامت و یا دیگر عناصر معنی دار به نام نشانه است مقالات کامل توسط داوران کنفرانس مورد ارزیابی قرار میگیرند. به این منظور لازم است.[1]
2-1حذف کلمه متوقف
کلمات متوقف بعضی از حروف، کلمات و اعداد هستند که معمولا در هر متنی به تعداد نسبتا زیادی بافت می شوند و مانع از اجزای الگوریتم با دقت و درصد موفقیت بالا می شود . کلماتی مانند: از، و، به، رو، غیره.
2-2 پیدا کردن ریشه یا ساقه یک کلمه
هدف از این پردازش حذف پسوند های مختلف به منظور کاهش است که این کار را می توان با استفاده از الگوریتم های مختلف همانند پورتر ریشه یابی، الگوریتم لوینز و غیره انجام داد. که ما در این جا از الگوریتم پورتر ریشه یابی استفاده کرده ایم.
2-3تشکیل بردار
به منظور انجام هر گونه فعالیت استخراج متن ابتدا باید محتویات پنهان متن به فرمت ها عددی برای پردازش بیشتر تبدیل گردند.
.3 خوشه بندی
الگوریتم خوشه بندی نیمه تحت نظارت به این معنی است که ما از هر دو داده برچسبدار و بدون برچسب برای انجام خوشه بندی استفاده می کنیم. متون برچسبدار از محیط مرئی خوشه انتخاب می شوند و متون بدون برچسب بر اساس گرفتن مراکز اجزای متن انتخاب می شوند. روند دقیق خوشه بندی شامل سه مرحله است:
-1 مقدار دهی اولیه
-2 خوشه بندی
-3 تشکیل خروجی روند خوشه نیمه تحت نظارت از هر دو متن برچسبدار و بدون برچسب به عنوان ورودی استفاده می کند. در گام مقدار دهی اولیه هر متنی که با یک برچسب در ارتباط می باشد همان برچسب به آن داده می شود. اگر یک متن دارای برچسب نباشد آن را به عنوان '' `` unlabeled مشخص می کند. بنابراین ما در گام مقدار دهی اولیه در حال تشکیل کاندید هایی برای مرحله خوشه بندی متن می باشیم .
در گام خوشه بندی کاندیدهایی که برچسب مشابه دارند با هم به عنوان یک خوشه گروه بندی می شوند و آنها در حال حاضر توسط مرکزخوشه و برچسب های مرتبط با آنها شناخته می شوند. اسناد بدون برچسب به یک لیست اضافه می شوند. سپس ما را یک سند بدون برچسب را از لیست می گیریم و فاصله آن را از سایر اسناد بدون برچسب موجود در لیست و همچنین مرکز خوشه برچسبدار محاسبه می کنیم.
در صورتی که سند بدون برچسب حداقل فاصله را از خوشه برچسبدار گرفت سپس به آن خوشه اضافه شده و برچسب آن خوشه به آن اختصاص داده می شود. مرکز خوشه به روز می شود و سند بدون برچسب از لیست حذف می گردد. اگر سند بدون برچسب دارای حداقل فاصله با سایر سند بدون برچسب باشد بعد از آن که دو سند بدون برچسب با هم ادغام شدند به لیست اسناد بدون برچسب به عنوان یک سند اضافه می شوند.
این فرایند تا زمانی ادامه پیدا می کند که همه سند بدون برچسب مشخص شده باشند. این روند ادامه می یابد تا تمام اسناد و مدارک بدون برچسب یک برچسب به آنها داده شود. در نهایت پس از تشکیل خوشه، اگر هر خوشه کمتر از 3 سند به عنوان عضو داشته باشد پس از آن که خوشه به عنوان خوشه بی ربط مشخص شده از مدل حذف می گردد. این بدان معناست که خوشه زیاد به فرآیند طبقه بندی ما کمک نمی کند .
پس از فرآیند خوشه نیمه تحت نظارت مجموعه ای از خوشه های متن با برچسب به عنوان خروجی تولید می شود. و این خوشه متن برچسبدار به عنوان یک مدل طبقه بندی برای گام طبقه بندی متن عمل می کند. روش های اساسی که در اینجا مورد استفاده قرار گرفته است برچسب یک متن بدون برچسب با برچسب خوشه متن که نزدیک ترین به متن بدون برچسب می باشد را مشخص می کند.
