بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
خوشه بندي مستندات متني به روش فازي عصبي HSOM
چکيده
امروزه ، استفاده از الگوريتمهاي خوشه بندي در گروهبندي مستندات متني از جايگاه بالايي ، خصوصا در سيستمهاي بازيابي اطلاعات برخوردار است . با استفاده از اين الگوريتمها مستندات بازيابي شده ، گروهبندي مي شوند تا مستندات مشابه ، در يک خوشه قرار گيرند. از ميان روشهاي مختلف خوشه بندي ، مدل عصبي SOM براي داده هاي با حجم بالا و مدل فازي KHM١ براي داده هاي خارج از محدوده عملکرد بهتري دارد.
در اين پژوهش ، با تلفيق دو روش KHM وSOM، الگوريتم نگاشت خودسازمانده هارمونيک HSOM پيشنهاد شده است . نتايج آزمايشات خوشه بندي مستندات بازيابي شده توسط سيستم SMART براي مجموعه OHSUMED ، براساس دو روش SOM و HSOM نشان مي دهند که HSOM برخلاف SOM، به مقداردهي اوليه حساسيت ندارد و همانند KHM داده هاي خارج از محدوده تاثيري بر نتيجه خوشه بندي نمي گذارند.
١. مقدمه
خوشه بندي يکي از ابزارهاي اساسي براي کشف ساختار زيرين مجموعه داده ها است . هدف اصلي خوشه بندي ، تقسيم يک مجموعه داده مشخص به تعدادي خوشه همگن است بطوريکه شباهت عناصر درون يک خوشه با هم ، بيش از شباهت آنها با عناصر ديگر خوشه ها باشد.
موتورهاي جستجو مستندات را بر اساس شباهتشان به سوال کاربر بازيابي و رتبه بندي مي کنند. با توجه به اينکه رتبه بندي فقط نزديکي مستندات به سوال کاربر را در نظر مي گيرد. لزوما مستندات مربوط در رتبه بندي ، کنار يکديگر قرار نمي گيرند .
ايده استفاده از خوشه بندي در بازيابي متون بر اين اساس است که اگر مستندات مشابه در يک خوشه و کنار يکديگر قرار گيرند در صورتيکه يکي از آنها به سوال کاربر مربوط باشد با احتمال زياد بقيه اعضاء خوشه نيز به سوال کاربر مربوط خواهند بود. بدين ترتيب مستندات مربوط ونامربوط راحتتر از يکديگر جدا مي شوند.
ابتدا محققين روش خوشه بندي کل مجموعه مستندات را بررسي کرده اند و اثرات آنرا در بهبود و بازيابي اطلاعات با روش هاي مرسوم بازيابي اطلاعات مقايسه نموده اند[١]. در حال حاضر محققين بيشتر علاقمند به بررسي اثرات خوشه بندي پس از بازيابي اطلاعات و پاسخ به سوال کاربر هستند. دو نوع از خوشه بندي که نتايج آنها در بازيابي اطلاعات قابل قبول بوده عبارتند از جستجوي خوشه ١ و پيمايش خوشه مراکز ثقل خوشه يا نماينده هاي خوشه محتواي يک خوشه را براي بازيابي نشان مي دهند. پرس و جو با نماينده هاي خوشه تطبيق داده مي شود و خوشه اي که بيشترين شباهت را به پرس و جو دارد بازيابي مي شود. در جستجوي خوشه ، مستندات داخل خوشه بازيابي شده در رابطه با پرس وجو مرتب نمي شود بلکه کل خوشه به عنوان يک موجوديت بازيابي مي شود[١]. سه نوع متفاوت از 5 جستجوي خوشه در بازيابي اطلاعات بررسي شده است : جستجوي بالا به پايين ٣ و جستجوي پايين به بالا٤ و جستجوي خوشه بهينه در اين پژوهش ما از جستجوي خوشه بهينه استفاده کرده ايم .
پيمايش خوشه براي دسترسي به اطلاعات با هدف غير مشخص به کار مي رود. در اين تکنيک مستندات به گروههايي خوشه بندي مي شود سپس با استفاده از خلاصه ها کاربر خوشه هايي را انتخاب مي کند. مجموعه مستندات اين خوشه ها زير مجموعه جديدي را تشکيل مي دهد. سيستم ، الگوريتم خوشه بندي را دوباره براي پراکندن زير مجموعه جديد بکار مي برد و دوباره خلاصه ها را به کاربر نشان مي دهد. با هر تکرار موفق خوشه ها کوچکتر مي شوند و بنابراين جزئيات بيشتري را بيان مي کند[٤][٢].
اخيرا روشهاي مختلفي بر اساس شبکه عصبي براي خوشه بندي مستندات پيشنهاد شده است [١٢] [ ٩] که هر کدام مزايا و معايب خود را دارا هستند. در اين مقاله ، مدل جديدي از شبکه هاي فازي عصبي خود سازمانده ارائه شده است که مي تواند داده هايي با ابعاد بالا را در دو بعد تصوير کند. اين مدل تلفيقي از دو روش KHM و SOM مي باشد.
روش خوشه بندي SOM براي کاربردهاي مختلفي قابل استفاده است . به همين دليل نسبت به ديگر روشهاي موجود توجه بيشتري را به خود جلب کرده است . با اين وجود، SOM به مقداردهي اوليه حساس مي باشد و داده هاي خارج از محدوده ، خوشه بندي را دچار مشکل مي سازد. در اين پژوهش ، براي حل اين مشکل از ايده K-Harmonic Means استفاده شده است KHM يک روش خوشه بندي فازي است . مشخصه مهم آن عدم حساسيت به داده هاي خارج از محدوده مي باشد. در اين روش ، براي نمايش خوشه ها، ماکزيمم مقدار عضويت داده ها نسبت به خوشه ها در نظر گرفته مي شود. هدف از اين پژوهش ، ارائه روش جديدي است که مزاياي روشهاي خوشه بندي SOM و KHM را همزمان در بر داشته باشد. در روش جديد HSOM، بجاي بکارگيري استراتژي رقابتي از روش ميانگين هارمونيک براي بروزآوري وزن نرونها استفاده شده است .
بخش بعدي به روش پيشنهادي HSOM اختصاص يافته است . بخش ٣ به روشهاي ارزيابي خوشه و بخش ٤ به آزمايش روش
HSOM و ارزيابي نتايج اختصاص يافته است و بخش پاياني نتيجه گيري مي باشد.
٢. روش پيشنهادي HSOM
در اين روش جديد فازي عصبي که ما آن را HSOM ناميديم ، توپولوژي شبکه مشابه SOM دوبعدي است با اين تفاوت که هنگام بروزآوري ، وزن تمام نرونها تغيير مي کند و اين عمل تنها مختص نرون برنده نمي باشد. بدين ترتيب ، امکان بکارگيري ايده فازي در شبکه عصبي فراهم مي گردد. براي بروزآوري وزنها در فاز يادگيري ، از تابع هزينه ميانگين هارمونيک استفاده شده است . در ادامه نحوه بروز آوري وزنها و نيز چگونگي نمايش خوشه ها شرح داده شده است .
٢. ١. بروزآوري وزن نرونها
تخصيص داده هاي ورودي به خوشه ها بر اساس تابع فاصله (d)x,m انجام مي گيرد. x نشان دهنده داده ورودي و m نمايانگر مجموعه اي از k مرکز خوشه مي باشد. (d)x,m در الگوريتم K-Harmonic Means بر اساس رابطه (٣) و در روش SOM به صورت رابطه (٤) بيان مي شود.
که (d)x,m مشخص مي کند يک نقطه داده اي خاص x تا چه حد به مرکز m جذب شده است . هر نقطه داده توسط مرکزي نمايش داده مي شود که به آن نزديکتر باشد. تابع هدف الگوريتم HSOM بر اساس جمع فواصل هارمونيکي (رابطه ٣) بصورت رابطه زير تعريف شده است . بروزآوري وزنها در الگوريتم HSOM با روش Steepest Descent انجام مي گيرد.
که K تعداد خوشه ها x نقطه داده و m مرکز خوشه مي باشد.مشکل اين رابطه از تساوي xi=mj حاصل مي شود. براي حل اين مشکل مخرج رابطه بالا بصورت اصلاح مي شود. ε يک مقدار بسيار کوچک مثبت مي باشد.
بر اساس مشتق تابع هدف ( ٥ ), وزن نرونها در طول يادگيري مرتبا به کمک رابطه زير تغيير مي کند. در حين فاز آموزش وروديها چندين بار ظاهر مي گردند تا وزنهاي اتصال را آموزش دهند و بدين ترتيب توزيع گره هاي خروجي نمايانگر توزيع نقاط ورودي است .
که تابعي از مراکز است . (α) نرخ آموزش و k تعداد نرونهاي خروجي است .
٢. ٢. تعيين خوشه ها
پس از فاز آموزش شبکه عصبي ، تخصيص داده هاي ورودي به خوشه ها بر اساس تابع عضويت انجام مي گيرد. در اين فرمول ، mj همان وزن نرون j ام است . هنگاميکه نقطه داده به يکي از مراکز نزديک است ، ميانگين هارمونيک امتياز خوبي (پائين ) به آن مي دهد. تابع عضويت به کمک رابطه زير بدست مي آيد که همان رابطه تعريف شده در KHM است :
براي تشخيص تعلق هر داده تنها به يکي از مراکز (خوشه بندي سخت )، در آزمايشهاي انجام گرفته تخصيص داده ها به خوشه ها بر اساس ماکزيمم ميزان عضويت انجام گرفته است .
٣. روشهاي ارزيابي خوشه بندي
به منظور محک زدن ايده بيان شده در اين مقاله ، مجموعه اي از معيارها مورد نياز است که روند خوشه بندي به راحتي قابل بررسي باشد. در ادامه ارزياب کيفيت خوشه بندي و خوشه بهينه شرح داده شده است .
٣. ١. کيفيت خوشه بندي
براي بررسي روند خوشه بندي از ارزياب کيفيت خوشه بندي استفاده کرده ايم [٧]. اين ارزياب بر اساس اطلاعات مرتبط بودن مستندات به پرس وجو قرار دارد. اگر D مجموعه کل مستندات و H مجموعه مستندات بازيابي شده با رتبه بالا از D را تشکيل دهند بطوريکه H به n خوشه Hn,..., ٢,H١Hتقسيم شده باشد، *P نسبت مستندات مرتبط از H است که برطبق ارزيابهاي انساني مرتبط تشخيص داده شده اند. براي هر خوشه نسبت Pi تعريف مي شود که نسبت تعداد مستندات مرتبط در هر خوشه است که صفر و يک ، مقادير ايده آل آن هستند. خوشه بندي که در آن *Pi=P باشد، نمي تواند به کاربر در دور کردن مستندات مرتبط کمکي نمايد.
کيفيت خوشه بندي بر اساس فرمول زير محاسبه مي شود. هر چه اين مقدار بيشتر باشد کيفيت خوشه بندي بهتر است .
٢.٣ . ارزيابي خوشه بهينه
ارزياب استاندارد بازيابي اطلاعات گراف دقت و فراخواني است که بر اساس ليست مستندات رتبه بندي شده توسط سيستم بازيابي اطلاعات محاسبه مي شود[١]. استراتژي بازيابي خوشه ، به عبارت ديگر خوشه ها را به جاي مستندات در پاسخ به هر سوال مرتب مي کند. ايجاد گرافهاي دقت و فراخواني در چنين سيستمهايي ممکن نيست . تابع ارزياب E براي سيستمهاي خوشه بندي توسط
Jardine و Rijsbergen در سال ١٩٧١ ارائه شده است .فرمول اين معيار:
که P وR تعازيف استاندارد دقت و فراخواني (تحت مجموعه مستندات يک خوشه ) مي باشند و پارامتري که اهميت دقت و فراخواني را مشخص مي کند. سه مقدار ٢و٠,٥و ١ معمولا براي اين پارامتر استفاده مي شود. اهميت يکسان براي دقت و فراخواني در نظر مي گيرد. اهميت دقت را دو برابر اهميت فراخواني و ٢ = اهميت فراخواني را دو برابر دقت لحاظ مي کند. ما در آزمايشات از هر سه مقدار استفاده کرده ايم .
خوشه بهينه براي هر پرس و جو خوشه اي است که کمترين مقدار E را براي آن پرس و جو داراست . Jardine و Rijsbergen اين اندازه را MK١ ناميدند. مزيت اصلي ارزيابي خوشه بهينه اين است که احتياجي به منابع خارجي براي ارزيابي ندارد. منابع خارجي شامل انتخاب يک استراتژي خاص است براي جستجوي خوشه اي که به پرس و جو نزديکتر است يا توانايي کاربر در بخش پيمايش ، کاربر بايد خوشه اي را پيدا کند که به نياز اطلاعاتيش مربوط باشد.
٤ . نتايج آزمايشات
اين آزمايشات در چهار چوب سيستم هاي بازيابي دو مرحله اي اطلاعات و در جهت بهبود مرحله دوم بازيابي صورت گرفته است .
شکل ١ سيستم دو مرحله اي بکار گرفته شده را نشان مي دهد.
شکل ١ : سيستم جستجوي خوشه
در اين آزمايشات از يک مجموعه تست استاندارد که براي آزمايشات ارزينه بازيابي اطلاعات بصورت وسيع بکار مي رود استفاده شده است . اين مجموعه OHSUMED نام دارد و حاوي ٣٤٨٥٦٦ سند از ٢٧٠ مجله پزشکي طي ٥ سال (١٩٩١-١٩٨٧) مي باشد در اين بررسي ها زير مجموعه اي از اين مجموعه که شامل مستندات ١٩٨٧ با ٥٤٧١٠ سند و ٦٣ سوال مي باشد استفاده شده است [٥].
سيتم بازيابي SMART براي بازيابي مستندات استفاده شده است . براي بازيابي ابتدائي مستندات از يک طرح وزندهي tfidf براي کلمات مستندات وپرس وجو استفاده شده است . ما کلمات پرس و جو و مستندات را بر اساس طرح atc.atc در سيستم
