بخشی از مقاله
چکیده
بازیابی متون به فنآوری جستجو و استخراج اطلاعات از مجموعه اسناد متنی گفته میشود. طبقهبندی دادههای متنی بهعنوان یکی از روشها در این راستا میباشد که همراه با چالشهایی از قبیل پیچیدگی دادهها، بزرگی چه از نظر تعداد چه از نظر ابعاد و همچنین وجود ساختار سلسله مراتبی برای اکثر دادههای متنی میباشد. بدین منظور برای غلبه بر این مشکلات نیاز به روشهایی است که ضمن برطرف نمودن مشکلات مذکور دقت طبقهبندی را نیز افزایش دهد در این تحقیق ضمن پیش پردازش دادههای متنی و تبدیل آن به ماتریسهای عددی از یک روش دو مرحلهای مبتنی بر افرازبندی برای غلبه بر مشکلات مذکور در دادههای متنی استفاده شده است. نتایج بدست آمده از اجرای این روش بر روی مجموعه داده متنی در مقایسه با روشهای افرازبندی و سلسله مراتبی اجرا شده بر روی دادههای متنی، حاکی از آن است که دقت طبقهبندی متون نسبت به الگوریتمهای مورد مقایسه، افزایش یافته است. همچنین سرعت روش مذکور بر روی دادههای متنی به مراتب بالاتر از روش عمومی K-means برای دادههای متنی است.
-1 مقدمه
امروزه خوشهبندی نقش حیاتی در روشهای بازیابی اطلاعات برای سازماندهی مجموعههای بزرگ مستندات متنی مانند وب دارد. خوشهبندی اسناد یکی از روشهای متداول برای تفکیک موضوعی متن از بین متون الکترونیکی، صفحات وب و اسناد دیجتال موجود در خبرگزاریها و کتابخانه دیجیتال است.[1] خوشهبندی اسناد در حوزههای متنکاوی و بازیابی اطلاعات، خلاصهسازی متون، استخراج کلمات کلیدی، سازمان دادن به اسناد نقش بهسزایی دارد.[2] همچنین از خوشهبندی برای طبقهبندی اسناد وب استفاده میگردد.
خوشهبندی یک تکنیک دستهبندی بدون نظارت است که در آن مجموعه دادهها که معمولاً بردارهایی در فضای چند بعدی میباشند، براساس یک معیار شباهت یا عدم شباهت به تعداد مشخصی خوشه تقسیم میشوند. روش سلسله مراتبی و روش افرازبندی دو روش متداول در خوشهبندی دادههای متنی میباشد. در روش سلسله مراتبی، خوشهبندی ساختاری شبیه درخت داشته که تمامی دادهها به اولین گره درخت متعلق بوده و هرچه در شاخههای درخت پیش میرویم خوشهبندی دقیقتر میشود.
[3] در روش افرازبندی، دادهها بر پایه مراکز خوشه تقسیم شده و بر اساس شباهت، تعلق داده به یکی از خوشهها تعیین میشود. برای ارزیابی کیفیت خوشه های ایجاد شده در طبقهبندی نظارتنشده از معیار ارزیابی خارجی جهت بررسی نتایج براساس برچسب کلاس استفاده میشود. ازجمله این متغیرها F-measure است که بهصورت نسبت متغیرهای دقت1و فراخوانی2به دست میآید. متغیر دقت بهصورت نسبت کلمات وابسته و بازیابی شده به کلمات بازیابی شده تعریف میشود. در واقع این متغیر درجه دقت نتایج تولید شده توسط الگوریتم طبقهبندی را معین میکند.
همچنین متغیر فراخوانی بهصورت نسبت کلمات وابسته و بازیابی شده به کلمات وابسته مشخص میشود که توانایی روش طبقهبندی برای تولید همه کلماتی که در یک گروه هستند را نشان میدهد. هر چقدر ناحیه مشترک بین دو متغیر دقت و فراخوانی بیشتر باشد مقدار متغیر F-measure بیشتر و درنتیجه دقت و سرعت روش طبقهبندی بیشتر خواهد بود. بهدلیل حجم بالای دادههای متنی، شکل استاندارد الگوریتمهای خوشهبندی سلسله مراتبی کارایی مناسبی ندارند زیرا پیچیدگی زمانی آن حداقل O - n2 - میباشد n - تعداد نمونهها - ، بنابراین این روش با افزایش n کارا نمیباشد. در طبقهبندی متون با دو چالش مواجه هستیم یکی نوع داده پیچیده با ابعاد بالای دادهها و دیگری اینکه در طبقهبندی متون معمولا دادههای متنی بهصورت سلسله مراتبی هستند و روشهای افرازبندی دادهها را بهصورت سلسله مراتبی سازماندهی نمیکنند.
ما در این تحقیق میخواهیم از روشی استفاده کنیم که هم بر مسئله داده با ابعاد بالا غلبه کند و هم نتیجهی طبقهبندی، نتیجه سلسله مراتبی داشته باشد اگرچه از روش افرازبندی استفاده شده است. تاکنون روش ها و الگوریتم های مختلفی برای طبقه بندی کردن اسناد متنی پیشنهاد و مورد استفاده قرار گرفته است. کلیه این الگوریتم ها را می توان به سه دسته کلی تقسیم نمود: الگوریتم هایی که طبقه بندی اسناد را بر اساس ساختار اسناد یا براساس محتوا و یا ترکیب ساختار و محتوای اسناد انجام می دهند که هر کدام مزایا و معایب خود را دارند.
آنچه که در همه روش های طبقه بندی اسناد مشترک است مرحله پیش پردازش اسناد است که در طی آن باید خصوصیات متن که از اهمیت بالاتری نسبت به بقیه برخوردارند استخراج شده تا مستندات متنی در قالب بردار نگهداری شوند، و بتوان به راحتی و با استفاده از معیاری مانند فاصله کسینوسی، بردارهای مشابه را پیدا نمود. برای نمایش برداری این نوع داده ها، معمولا از مدل فضای برداری استفاده میشود [3]و سپس عملیات طبقه بندی روی آنها انجام می شود. در بخش بعدی کارهای مرتبط با طبقه بندی اسناد بصورت نظارت نشده مورد بررسی قرار گرفته است. در بخش3 مقدمات روش مورد استفاده بیان شده است. در بخش 4 به شرح روش مورد استفاده پرداخته شده است. در بخش 5و 6 شرح پیاده سازی و بررسی نتایج و ارزیابی روشهای مطرح بیان شده است.
-2 کارهای مرتبط
بهطورکلی خوشهبندی متون به دو نوع خوشهبندی بر اساس افرازبندی و روش سلسله مراتبی 3تقسیم میشود. روشهای افرازبندی مجموعهای از متون را به تعدادی از خوشههای از پیش تعیین شده تقسیم میکنند مانند الگوریتم k-means اما الگوریتمهای سلسله مراتبی به صورت یک مجموعه تودرتو از خوشهها که معمولا به صورت ساختار درختی است نشان داده میشوند مانند.UPGMA الگوریتم K-Means یکی از متداولترین روشهای خوشهبندی مبتنی بر تکرار میباشد.
این الگوریتم در مواردی دارای کاربرد میباشد که در آن هر داده تنها به یک کلاس تعلق گیرد. این الگوریتم، یک الگوریتم نظارت نشده و دارای تکرار میباشد که در آن مجموعه داده به K خوشه تقسیمبندی شده و نقاط داده به طور تصادفی به این خوشهها تعلق میگیرند. سپس برای هر نقطه، فاصله آن نقطه تا مرکز خوشه محاسبه میشود. و نقطه مورد نظر به نزدیکترین خوشه تعلق میگیرد. این کار آنقدر تکرار میشود تا تابع خطا حداقل شود، و یا اعضای خوشهها تغییر نیابد.
الگوریتم Bisecting K-means بیشتر برای کار بر روی متون مورد استفاده قرار میگیرد و ترکیبی از خوشهبندی سلسله مراتبی و افرازبندی میباشد. بهدلیل تعداد ابعاد بالای بردار مستندات متنی، شکل استاندارد الگوریتمهای خوشه بندی تقسیمی یا تجمیعی کارایی مناسبی ندارند. الگوریتم خوشه بندیBisecting K-mean براساس الگوریتم k-means است این الگوریتم میتوانند برای حجم بالای دادههای ورودی که ابعاد زیادی دارند اجرا گردد. پس Bisecting K-means برای خوشهبندی مستندات متنی مناسب است.
این الگوریتم K - به اندازه تعداد خوشهها - تکرار میشود و در هر بار تکرار، یک خوشه بدست میآید. در ابتدا تمام مستندات متنی در یک خوشه فرض میشوند و در یک حلقه هر بار یک خوشه که بیشترین تعداد متن را دارد انتخاب میشود. سپس دو نقطه تصادفی در آن خوشه به عنوان مراکز جدید دو خوشه نتیجه، در نظر گرفته میشوند و مشابه الگوریتم k-means عملیات خوشهبندی انجام میشود. به این ترتیب خوشه انتخاب شده به دو خوشه شکسته میشود. این عملیات با k-1 بار تکرار درون حلقه، K خوشه بدست می آید.
الگوریتمهای افرازبندی مانند خانواده k-means عملکرد خوبی بر روی خوشهبندی اسناد دارد. یکی از ویژگیهای مهم الگوریتمهای افرازبندی این است که از تابع معیار سراسری استفاده میکند هدف این تابع معیار بهینه نمودن جنبههای مختلف از شباهت درون خوشهای، عدم شباهت برون خوشهای و ترکیب آنهاست. از آنجاییکه تابع کسینوس، شباهت دو سند را اندازهگیری میکند، تنها شباهت دوبهدو هنگام تعیین اینکه آیا یک سند به یک خوشه اختصاص دارد یا خیر در نظر گرفته میشود. هنگامیکه خوشهها خوب از هم جدا نیستند تقسیمبندی آنها تنها براساس شباهت دوبهدو به اندازه کافی خوب نیست زیرا برخی از اسناد در خوشههای مختلف ممکن است مشابه یکدیگر باشند برای حل این مشکل [4] از مفهوم همسایهها4و پیوند5برای خوشهبندی مستندات استفاده میکنند.
اگر دو سند به اندازه کافی مشابه باشند آنها همسایهی یکدیگرند و تابع پیوند بین دو سند نشان دهنده تعداد همسایگان مشترک آنهاست. [4] در الگوریتم k-means Bisecting روش پیشنهادی، خوشهای که مرکز ثقل آن کوچکترین تعداد همسایگان محلی را دارد برای تقسیم شدن انتخاب میشود. نتایج نشان داده است که مرکز ثقل اولیه انتخاب شده توسط [4] به خوبی توزیع شده و هر یک نزدیک به تعداد کافی از اسناد موضوعی مرتبط است بهطوریکه دقت خوشهبندی را بهبود میبخشند.
خوشهبندی ترکیبی یکی از روشهای رایج داده کاوی است که از ترکیب روشهای اولیه خوشهبندی حاصل میشود و باعث افزایش دقت خوشهبندی نسبت به روشهای اولیه میگردد. [5]برای حل مشکل مقداردهی الگوریتم k-means بر روی مستندات از خوشهبندی ترکیبی الگوریتمهای k-means وPSO با استفاده از نمونه برداری جهت بهبود نتایج خوشهبندی استفاده
نمودهاند. الگوریتم بهینه سازی اجتماع ذرات 6 یک روش - PSO - بهینه سازی ابتکاری مبتنی بر قوانین احتمال است. مشکل خوشهبندی اسناد چند بعدی بودن آنهاست و با روش ترکیبی میتوان بر آن غلبه کرد.
استفاده از PSO + k-Means برای خوشهبندی نیاز به حافظه بزرگ و زمان اجرا بالا دارد. الگوریتم افرازبندی دارای محدودیتهایی ازجمله تعداد خوشهها به عنوان ورودی باید داده شوند، براساس مقداردهی اولیه آنها همگرا به مینیمم محلی مختلف هستند و آنها با خوشههای خالی نمیتوانند کار کنند، کار با الگوریتم افرازبندی با استفاده از فاصله کسینوسی برای مجموعه دادههای متنی یک محدودیت دیگری ایجاد میشود که اگر سند دارای مقداری صفر در مدل فضای برداری باشد، خوشهبندی نمیشود و الگوریتم افرازبندی متوقف میشود.
برای حل این مشکلات [6] یک الگوریتم جدید برای تولید تعدادی از خوشهها بهطور خودکار پیشنهاد دادهاند. الگوریتم پیشنهادی به طور خودکار مجموعه متنی ناشناخته را در خوشههای بهینه، خوشهبندی میکند و نیازی به تعیین k خوشه به عنوان ورودی ندارد. الگوریتم k-means برای تعداد زیادی اسناد به دلیل خطای صفر - مقدار فضای برداری صفر و کسینوس شباهت - نمیتواند کار کند. الگوریتم پیشنهاد شده این مشکل را حل نموده است. اغلب الگوریتمهای خوشهبندی افرازبندی مورد استفاده با مشکل در تله افتادن راهحل بهینه محلی دچار صدمه میشوند.
[7] یک الگوریتم از نوع افرازبندی برای خوشهبندی اسناد با استفاده از یک گراف مبتنی بر تابع هدف که معمولا منجر به راهحل بهینه سراسری میشود و کارایی آن با افزایش تعداد خوشهها افزایش مییابد، پیشنهاد دادهاند. برخلاف الگوریتمهای خوشهبندی مانند k-means الگوریتم پیشنهادی از یک روش حریصانه استفاده میکند. الگوریتم شامل دو مرحله میباشد، در مرحله اول هدف بدست آوردن انتخاب k دانه به عنوان نماینده تنها یک خوشه است و مرحله دوم - مرحله پالایش - شامل تکرار تغییرات در ساختار خوشه است.
در مرحله اول، در ابتدای الگوریتم k سند انتخاب میشود از این پس به این اسناد بهعنوان دانه مراجعه شده است از این دانهها بهعنوان اولین مراکز از k خوشههای مورد نیاز استفاده میشود. در ابتدا یک سند بهطور تصادفی انتخاب نموده و در Seed -Vector که در ابتدا خالی است، قرار میدهیم. Seed-Vector مجموعهای برای نگهداری دانهها است. دانهها اسنادی هستند که نماینده هر خوشه میباشند. هدف این مرحله انتخاب نمودن k دانه که هر یک نماینده فقط یک خوشه است.
