بخشی از مقاله
چکیده:
هدف اصلی این پژوهش، تبیین مفهوم خوشهبندی و تکنیکهای وابسته به آن در حوزه دادهکاوی است. از این رو، تعاریف و فرآیند خوشه-بندی، انواع روشهای خوشهبندی سلسله مراتبی و افرازی و رویکردهای وابسته به آنها مورد بررسی قرار میگیرند، وگامها و مراحل انجام آن تشریح میگردند. در ادامه این مقاله مروری که به روش مطالعات کتابخانهای انجام میشود، روشهای ارزیابی نتابج خوشهبندی و کاربردهای الگوریتمهای خوشهبندی در بازیابی مدارک و اسناد ایکس.ام.ال. توضیح داده میشوند.
کلمات کلیدی: خوشهبندی، دادهکاوی، بازیابی مدارک، اسناد ایکس.ا.م.ال.
مقدمه
اولین بار ایده خوشهبندی در دهه 1935 ارائه شد و امروزه باپیشرفتها و جهشهای عظیمی که در آن پدید آمده، خوشهبندی مورد توجه بسیاری از محققان قرار گرفته است - طاهریان فرد . - 1389 به طور کلی خوشهبندی، گروهبندی نمونههای مشابه با هم در یک حجم داده میباشد. هدف خوشهبندی یافتن خوشههای مشابه از اشیاء در بین نمونههای ورودی است. کار اساسی توزیع دادهها به K گروه مختلف است که دادههای هر گروه با یکدیگر مشابه بوده و دادههای گروههای مختلف با یکدیگر نامتشابه باشند. این تشابه یا عدم تشابه بر اساس معیارهای اندازهگیری فاصله تعریف میشود. به عبارتی دیگر، خوشهبندی نوعی عملیات دادهکاوی غیرمستقیم است که برای انجام آن هیچ دستهای از قبل وجود ندارد و درواقع متغیرها به دو طبقه مستقل و وابسته تقسیم نمیشوند. در اینجا تمرکز روی گروههایی از اشیاء است که به هم شبیه هستند تا با کشف این شباهتها بتوان رفتارها را بهتر شناسایی کرد و بر مبنای این شناخت بهتر تصمیمگیری نمود - غضنفری، علیزاده، و تیمورپور . - 1387 یکی از مسائل مهم در خوشهبندی انتخاب تعداد خوشه هاست.
در بعضی از الگوریتمها، تعداد خوشهها از قبل مشخص شده است و در بعضی دیگر خود الگوریتم تصمیم میگیرد که دادهها به چند خوشه تقسیم شوند - قاسمی . - 1388 به طور کلی سه روش عمده سلسله مراتبی، روش تقسیمی، و روش همپوشانی برای اجرای فرآیند خوشهبندی وجود دارد - ابوالقاسم مسلمان، مومنی و زین العابدینی . - 1395 از کاربردهای خوشهبندی میتوان به شناسایی متن، تجزیه و تحلیلی دادههای فضایی، پردازش تصویر، علوم اقتصادی، بازاریابی، خاکبرداری، مطالعات زمینلرزه و برنامهریزی شهری اشاره کرد - غضنفری، علیزاده، و تیمورپور 1387، فلدمن، سنگر. - 2007 3هدف اصلی این پژوهش، تبیین مفهوم خوشهبندی و تکنیکهای وابسته به آن در حوزه دادهکاوی است. از این رو، انواع روشهای خوشهبندی مورد بررسی قرار میگیرد، وگامها و مراحل انجام آن تشریح میگردند.
پیشینه پژوهش
حسینی - 1390 - در پژوهشی عناصر و مؤلفههای رابط کاربر در نظامهای بازیابی اطلاعات مبتنی بر خوشهبندی را مورد بررسی قرار داده است. وی کاربرد خوشهبندی را در خوشهبندی مجموعه، مدلسازی زبان و بازیابی مبتنی بر خوشهبندی میداند.نتایج پژوهش بر این تأکید میکند که خوشهبندی به ارائه اطلاعات مؤثر برای مرورهای کاوشی، افزایش دقت یا بازیافت، کارآمدی بالا و جستجوی سریع منجر میشود.ابوالقاسم مسلمان و دیگران - 1395 - در مطالعهای در یک پژوهش کاربردی میزان دقت در بازیابی منابع شنیداری با استفاده از الگوریتم کی-مینز را مورد بررسی قرار دادهاند. نتایج پژوهش آنها نشان داد که استفاده از روش خوشه-بندی میتواند در افزایش میزان دقت مؤثر باشد.حسنپور، کنور و داس - 2014 - 1 در مقالهای رویکردی را پیشنهاد کردهاند که قوانین خوشهبندی را با استفاده از شاخصهای شباهت مبتنی بر هستیشناسی را بهبود میبخشد. نتایج پژوهش آنها نشان داد که این قانون خوشهبندی معنایی در دنیای وب معنایی کاربردی است و به کاربران نهایی در بازیابی کمک میکند.
روش پژوهش: این روش از مطالعات کتابخانهای - سندی - بهره گرفته است. با جستجو و مطالعه در پایگاههای اطلاعاتی فارسی و انگلیسی، کتب و مقالات مرتبط استخراج و مطالعه شدند. تعریف خوشهبندی: خوشهبندی روشی است که برای گروهبندی موجودیتها - مدارک - مشابه مورد استفاده قرار میگیرد. در این روش، مدارک در گروههایی از پیش تعیین نشده به نام خوشه قرار میگیرند؛ به طوری که مدارک مشابه درکنار یکدیگر و مدارک نامشابه دور از یکدیگر قرار میگیرند - تن،اشتینباخ و کومار. - 2006 2عوامل گوناگونی درخوشهبندی مؤثر است یکی از آنها نوع خصیصهای است که به واسطه آن یک مدرک مورد بازنمایی قرار میگیرد. نوع خصیصه انتخابی به همراه الگوریتم مناسب در خوشهبندی اهمیت زیادی دارد - دیلن، کگان و نیکلاس - 2003 3 به همین دلیل، انتخاب درست خصیصه برای مدارک در نتایج خوشهبندی تأثیرگذار خواهد بود.
به عبارت دیگر، خوشهبندی عبارتست از گروهبندی عناصر اطلاعاتی درون دستهها و ردههایی که دارای شباهت ساختاری هستند. در خوشهبندی سعی میشود تا اطلاعات به خوشههایی تقسیم شوند که شباهت بین اطلاعات درون هر خوشه حداکثر و شباهت بین اطلاعات در بین خوشههای متفاوت حداقل شود - عامری، ولدان زوج، و مختارزاده . - 1386خوشهبندی از جمله روشهایی است که در آن هیچگونه برچسبی برای رکوردها در نظر گرفته نمیشود و رکوردها فقط براساس معیار شباهتی که معرفی شده است، به مجموعهای از خوشهها گروهبندی خواهند شد. عدم وجود برچسب سبب میشود که هر الگوریتم خوشهبندی یک الگوریتم بدون ناظر به حساب آید. در روشهای بدون ناظر، الگوریتم مراحلی را تحت نامهای آموزش و ارزیابی نداشته و در پایان عملیات خوشهبندی مدل ساخته شده - که عملا همان خوشههای ایجادشده میباشد -
به همراه کارایی آن به عنوان خروجی ارائه میشود - صنیعی آباده، محمودی و طاهرپرور . - 1393در انتخاب روش خوشهبندی باید توجه کرد که شیوه منحصر بهفردی که برای انواع گوناگون ساختار دادهای کاربرد و عمومیت داشته باشد، وجود ندارد. از سویی، تکنیکهای گوناگونی برای نمایش داده، اندازهگیری شباهت و دستهبندی وجود دارد که منجر به تولید انواع متنوعی از روشهای خوشهبندی میشود. اندازه و توزیع دادهها در انتخاب تکنیک مربوطه نقش بسزایی دارد. رویکردهای اساسی در خوشه بندی: کاهش بعد دادهها1 و پیشبینی2 از رویکردهای اساسی در این حوزه هستند. در کاهش بعد،خوشهبندی، دادههای با حجم زیاد را به چند بخش تقسیم میکند.یعنی به جای پردازش کل مجموعه داده، مجموعه داده اولیه را به صورت فشرده در میآورد و درپیشبینی تحلیل خوشهای انجام میشود. خوشهها بر اساس مشخصهای خاص تعیین میشوند. در مرحله بعد، دادههای جدید و ناشناخته میتوانند براساس شباهت در خوشهای خاص قرار گیرند - سهیلی و دیگران . - 1394
فرآیند خوشهبندی وروش و ارزیابی صحت آن:
روش اندازهگیری شباهت، معیار خوشهبندی نوع الگوریتم خوشهبندی را تعیین میکند. فاصله یا شباهت معیاری است که به صورت جفت جفت برای دادهها در نظر گرفته میشود. هدف از کاربرد این معیار این است که نشان دهد دو شی یا بردارهای مشخصه آنها چقدر به هم شباهت دارند. معیار خوشهبندی بر اساس شکل و نوع خوشهها انتخاب میشوند. خوشهبندی به روشهای گوناگونی انجام میشود. علاوه بر انتخاب معیار شباهت یا فاصله که نوع الگوریتم را برای افراز دادهها تعیین میکند، تصمیمات دیگر نیز باید لحاظ شوند. یکی از آنها، تعیین عضویت شی است. در برخی شرایط، خوشهها به سختی انتخاب میشوند به این معنا که افرازهای داده به صورتی است که هر داده تنها در یک خوشه قرار میگیرد. در برخی شرایط دیگر، حالات خوشهها راحت تعیین میشوند، به این معنا که در این افرازها یک داده ممکن است به چندین دسته تعلق داشته باشد.
همچنین در افراز فازی هر داده با یک درجه عضویت به یک خوشه تعلق دارد. تمامی فرآیندهای خوشهبندی، در نهایت تضمینکننده دستیابی سریع و مطمئن به اطلاعات همبسته و شناسایی ارتباط منطقی بین آنهاست - محمدعلیپور، درودی . - 1386روشهای صحت خوشهبندی معمولا بر اساس معیاری بهینه یا روشهای آماری برای جواب این سوال که آیا نتیجه خوشهبندی معنادار است یا نه انجام میشود. به طور کلی سه روش تعیین صحت آزمون بیرونی و درونی و نسبی وجود دارد. آزمون بیرونی برمقایسه ساختار خوشهبندی و ساختار قبلی داده می-پردازد.آزمون درونی، به بررسی ساختار درونی خوشهها میپردازد. وآزمون نسبی به مقایسه دو ساختار میپردازد و شایستگی نسبی هریک را بررسی میکند - سهیلی و دیگران . - 1394 روش خوشهبندی: از دیدگاه سنتی روشهای خوشهبندی به طور کلی به دو دسته سلسله مراتبی و افرازی تقسیم میشوند که در سالهای اخیر نیز روشهای نوینی به آنها افزوده شدهاند - سهیلی و دیگران . - 1394
روشهای سنتی:ویژگی اصلی روشهای سنتی در این است که هر شی تنها در یک خوشه قرار میگیرد و به طور کلی آنها را در دو گروه سلسله مراتبی و غیر سلسله مراتبی قرار میدهند. روش سلسله مراتبی:این روش مانند یک درخت عمل میکند. هر شاخه کوچکتر جزئی از یک شاخه بزرگتر است و در نهایت همه به صورت سلسله مراتبی به تنه درخت وصل میشوند. یعنی در نهایت، اشیاء به صورت یک نمودار درختی و به صورت بازگشتی در خوشههای کوچک و کوچکتر قرار میگیرند که اصطلاحا به آن دندوگرام3 میگویند. مزیت این روش این است که
