پرس‌وجو‌های کلیدی برای خوشه‌بندی و برچسب‌گذاری

| | ارسال نظر | بازتاب (0)

پرس‌وجو‌های کلیدی برای خوشه‌بندی و برچسب‌گذاری

تیم گالوب، ماتیاس باس، بنو استاین و ماتیاس هیگن

 

چکیده

در این مقاله به بازبینی مسئله‌ی خوشه‌بندی از چشم‌اندازی مبتنی بر بازیابی اطلاعات پرداخته خواهد شد. ایده‌ی مورد نظر، استفاده از پرس‌وجوها به عنوان ویژگی‌هایی در فرایند خوشه‌بندی است که در انتها نقش برچسب‌های خوشه توصیفی را نیز "به‌طور آزاد" ایفا کنند. این چشم‌انداز جدید ما از محدودیت‌های پرس‌وجو برای خوشه‌بندی و برچسب‌گذاری یا علامت‌گذاری خوشه، برخوردار است که موجب حصول اطمینان از وجود ثبات با یک موتور جست‌وجوی مرجع بر پایه‌ی کلید واژه‌ها خواهد گردید.

رویکرد ما از ترکیب روش‌های مختلف در یک خط لوله‌ی سه مرحله‌ای به‌وجود آمده است. به‌طور کلی، گونه‌ای متفاوت از کی-میانگین[1] محدود به پرس‌وجو با استفاده از پرس‌وجو‌های عبارت اسمی در برابر یک موتور جست‌وجوی ESA محور، از بهترین عملکرد برخوردار است. در بخش ارزشیابی، نوعی مقیاس خوشه‌بندی نرم[2] را معرفی نموده‌ایم که مجموعه داده‌هایی از نسخه‌ی گسترش یافته و قابل دسترس Ambient را نیز به همراه دارد. رویکرد خود را با دو مورد از خط پایه‌های معمول و مورد استفاده، کی-میانگین‌های توصیفی و کی-میانگین‌های به علاوه‌ی χ2  را مقایسه خواهیم نمود. با توجه به این‌که خوشه‌های دریافت شده از کیفیت بالا و قابل مقایسه‌ای برخوردار بودند، ارزشیابی برچسب خوشه‌های متناظر، نمایانگر تنوع وسیعی در توان توضیحی هستند. در یک تحقیق کاربری متشکل از 49 شرکت کننده، عناوین ایجاد شده طی رویکرد ما به‌طور قابل توجهی از قدرت بالای متمایز کننده برخوردار بود که به افزایش جدایی میان انسان و خوشه‌های رایانشی منتهی می‌گردد.

1.    مقدمه

خوشه‌بندی اسناد یکی از روش‌های پرطرفدار جهت جست‌وجوی مجموعه‌های عظیمی مانند کتابخانه‌های دیجیتال، دانش‌نامه‌ها و یا نتایج جست‌وجوهای اینترنتی به شمار می‌رود. هدف از خوشه‌بندی، سازمان‌بندی خودکار مجموعه‌ای از اسناد به تعداد کمی از دسته‌های منسجم یا خوشه است، به نحوی که اسناد موجود در یک خوشه با یک‌دیگر نسبت به موارد موجود در خوشه‌های دیگر شباهت بیش‌تری داشته باشند. با استفاده از برچسب‌های کوتاه و پرمعنی برای خوشه‌ها (خلاصه‌سازی محتوای خوشه)، کاربر می‌تواند یک دید کلی نسبت به آن مجموعه کسب نموده، به جست‌وجوی نظام‌مند پرداخته یا تمرکز خود را بر یک زیرمجموعه‌ی خاصی از اسناد معطوف نماید که با اطلاعات مورد نیاز وی هم‌خوانی داشته باشد.

عمل خوشه‌بندی اسناد از دو گام کلی برخوردار است: 1) آشکارسازی ساختار موضوعی در یک مجموعه اسناد و 2) ارائه‌ی توصیفات معنادار که این ساختار را به کاربر منتقل کند. برای اولین گام که به آن خوشه‌بندی گفته می‌شود، الگوریتم‌های موثر بسیاری ارائه شده‌اند. با این حال، الگوریتم‌های خوشه‌بندی پرطرفدار مانند روش کی-میانگین معمولا نمی‌توانند برچسب‌های معناداری برای خوشهها تولید کنند. به این امر معمولا در گام دوم پرداخته می‌شود که عبارت است از برچسب‌گذاری خوشه‌ها. یکی از اشکال‌های اصلی روش‌های برچسب‌گذاری معمول و کلید واژه محور این است که تنها به گزینش ویژگی‌های "آماری" از اسناد محدود هستند؛ به عنوان مثال، پیوند زدن برجسته‌ترین کلید واژه‌هایی که در یک خوشه وجود دارند. با این وجود، فهرستی از کلید واژه‌ها می‌تواند جنبه‌های مختلف و نامرتبط از اسناد را به نمایش گذاشته و معمولا نمی‌تواند یک برچسب خوانا تولید کند.

جهت در نظر گرفتن جنبه‌ی اصلی برچسب‌های معنادار برای خوشه‌بندی اسناد، از چشم‌اندازی مبتنی بر بازیابی اطلاعات استفاده می‌کنیم. لازم به ذکر است که فهم کاربر نسبت به مناسب بودن یک برچسب برای مجموعه‌ای از اسناد می‌تواند مشابه با تصمیم یک موتور جست‌وجو نسبت به تطابق سند با پرس‌وجو در نظر گرفته شود. در نتیجه، پرس‌وجوها را به عنوان نامزدهایی مطلوب برای برچسب خوشه‌ها و هم‌چنین به عنوان ویژگی‌های مناسبی برای خوشه‌بندی به خودی خود در نظر می‌گیریم. از این طریق، رابطه‌ی مستقیمی میان خوشه‌بندی و فناوری جست‌وجو برقرار کرده‌ایم. به علاوه، تعامل میان سیستم‌های بازیابی اطلاعات و تحلیل خوشه، به ایجاد رویکردی بصری نسبت به خوشه‌بندی نتیجه جست‌وجوی سلسله مراتبی منتهی می‌گردد: زمانی که ابعاد مرتبط در یک مجموعه اسناد به شکل پرس‌وجوهای جست‌وجو نمایان گردیدند، هر کدام از مجموعه نتایج متناظر می‌تواند نقش یک ورودی برای تکراری دیگر از فرایند خوشه‌بندی را ایفا نموده که به نوبه‌ی خود، به مجموعه‌ی جدیدی منجر می‌شود که اکنون از ابعادی با جزئیات بیش‌تر برخوردار است و این همان پرس‌وجوهای جست‌وجو به شمار می‌رود.

آنچه که در این حوزه انجام داده‌ایم در سه بخش خلاصه می‌گردد: (1) یک خط لوله‌ی پردازش سه مرحله‌ای و انعطاف‌پذیر برای خوشه‌بندی با استفاده از پرس‌وجوهای جست‌وجو تحت عنوان ویژگی‌ها و برچسب‌ها، (2) نسخه‌ای گسترش یافته، رایگان و در دسترس از مجموعه داده‌های Ambient با تعداد 4680 سند همراه با حاشیه‌نویسی دستی، و (3) یک مطالعه‌ی کاربری با 49 شرکت کننده که در آن، به مقایسه میان توان توضیحی برچسب‌های خوشه ایجاد شده طی رویکرد ما با خط پایه‌هایی که به طور معمول مورد استفاده قرار می‌گیرند.

 

2.    تحقیقات مرتبط

یکی از کاربردهای اولیه خوشه‌بندی اسناد، ارتقای بازیابی بر پایه‌ی یک فرضیه در رابطه با خوشه‌بندی بود؛ طبق این فرضیه، "اسنادی که با یک‌دیگر ارتباط نزدیکی دارند، معمولا به درخواست‌های مشابهی مرتبط هستند" [16]. بعدا، از خوشه‌ها به عنوان رابط کاربری مرورگر جهت جست‌وجو و مرتب‌سازی مجموعه اسناد مانند الگوریتم مشهور پراکنده‌سازی/جمع‌آوری[3] استفاده شد [4]. الگوریتم‌های متعدد خوشه‌بندی اسناد را می‌توان به سه دسته تقسیم نمود [3]: الگوریتم‌های داده محور، آگاه به شرح، و شرح محور.

الگوریتم‌های داده‌ محور معمولا به حوزه‌ی متن محدود نیستند. داده‌هایی که قرار است خوشه‌بندی شوند در مدل‌هایی به نمایش گذاشته می‌شوند که شرایط برای محاسبه‌ی شباهت‌ها میان موضوع داده‌ها را فراهم می‌سازد. الگوریتم کی-میانگین یکی از پرطرفدارترین موارد از این دست به شمار می‌رود (بخش 3.3). یکی از روش‌های پرطرفدار نمایش داده در حوزه متن، مدل فضای برداری[4] با اوزان tf. idf  و تشابه کسینوسی است [18]. با این وجود،  تولید برچسبی که بتوان آن را به کاربر ارائه نمود، بخشی از الگوریتم‌های داده محور نبوده و به عنوان گامی مستقل پس از آن تلقی می‌شود. برچسب‌های به‌وجود آمده توسط کلید واژه‌های متداول در اسناد موجود در یک خوشه [21] یا اعمال تست χ2  پیرسون با در نظر گرفتن خوشه‌های دیگری که خط پایه‌ی اولیه‌ی ما را تشکیل می‌دهد [12]، نمونه‌هایی از این دست به شمار می‌روند. به هرحال، چنین برچسب‌هایی معمولا دنباله‌ای از کلید واژه‌های بی‌ربط هستند که موجب می‌شود حتی بهترین نوع از خوشه‌بندی، برای کاربرانی که به برچسب‌ها به مثابه شرح خوانا نگاه می‌کنند، فایده‌ی کم‌تری داشته باشد؛ اشکالی که موجب الهام بخشی جهت ایجاد دسته‌ی دومی از الگوریتم‌های خوشه‌ای گردید.

در الگوریتم‌های آگاه به شرح تلاش گردیده تا اشکالات برچسب‌گذاری در رویکردهای داده محور طی حصول اطمینان از جامع بودن و معناداری نتایج ایجاد شده توسط برچسب‌های خوشه‌ای مرتفع شود. یکی از راه‌های دستیابی به این هدف، استفاده از الگوریتم‌هایی است که اسناد را بر پایه‌ی تنها یک ویژگی به خوشه ارتباط می‌دهند و سپس از آن ویژگی به عنوان برچسب استفاده می‌کنند که به اصطلاح، به آن خوشه‌بندی تک تک[5] گفته می‌شود. خوشه‌بندی درخت پسوندی[6] [25]، یکی از نمونه‌هایی است که از عبارات مورد استفاده‌ی متداول به عنوان ویژگی‌های شباهت بهره می‌گیرد. ابتدا، با استفاده از تک عبارات متداول و مشترک که از درخت‌های پسوندی بهره می‌برند، خوشه‌های پایه شناسایی می‌گردند. سپس، خوشه‌های پایه با توجه به تشابهات در عبارت‌های خود با یک‌دیگر ادغام می‌گردند. با این حال، از آن‌جا که گام مرتبط با ادغام خوشه‌ها بر اساس یک معیار تک ارتباطی است، عبارات ترکیب شده از خوشه‌های ادغامی که همان برچسب خوشه‌ها را تشکیل می‌دهد، معمولا نامرتبط بوده و در نتیجه می‌تواند موجب گمراهی کاربر شود. در سیستم SnakeT [5] تلاش شده است که با استفاده از عبارات برگرفته از نوعی هستان شناسی از پیش تعریف شده، برچسب‌های به دست آمده مشابه، غنی شوند؛ اما با این وجود، تحلیل خوشه جلوتر از مرحله‌ی برچسب‌گذاری بوده و بر آن غالب است، و این همان مسئله‌ای می‌باشد که در دسته‌ی بعدی از الگوریتم‌ها برای رفع آن تلاش‌هایی صورت گرفت.

در الگوریتم‌های شرح محور، برچسب خوشه‌ها به عنوان عناصر اساسی خوشه‌بندی در نظر گرفته می‌شود. در این حالت، فرض بر این است که اگر یک برچسب معنادار قادر به توصیف یا تشریح خوشه نباشد، احتمالا ارزشی برای کاربر ندارد. این یعنی توصیف و شرح بر تخصیص یک سند به خوشه مقدم‌تر است. الگوریتم‌های شرح محور معمولا با مورد استفاده‌ی مرتبط با خوشه‌بندی نتایج جست‌وجوی اینترنتی سروکار دارد که یکی از نمونه‌های پیش قدم در این زمینه، Lingo نام دارد [14]؛ یک چارچوب متن باز برای خوشه‌بندی نتایج جست‌وجو که اکنون بخشی از Carrot2 است. تجزیه مقدار تکی از ماتریس قطعه‌ای یک نتیجه‌ی متداول جست‌وجو برای استخراج بردارهای متعامدی استفاده می‌گردد که طبق فرض، موضوعات متنوعی را در قطعه‌ها به نمایش می‌گذارند. سپس با استفاده از مدل فضای برداری، اسناد به خوشه‌های موضوعی استخراج شده تخصیص می‌یابند.

وایس[7] با هدفی مشابه، به بازبینی الگوریتم کی-میانگین داده محور پرداخته و آن را با نسخه‌ای شرح محور اصلاح نموده است: کی-میانگین‌های توصیفی [24]، که دومین خط پایه‌ی ما به شمار می‌رود. ابتدا، کی-میانگین‌ها با ویژگی‌های tf. idf  اجرا می‌شود. سپس، عبارات متداول به عنوان برچسب‌های بالقوه برای خوشه‌ها از مرکزوار[8] (گرانیگاه) خوشه استخراج می‌شوند. برای تخصیص به اسناد، الگوریتم به دنبال اسناد خوشه‌ای می‌گردد که با عبارت تسهیل کننده‌ی مدل فضای برداری مرتبط باشد.

تمرکز الگوریتم‌های شرح محور بر کیفیت برچسب معطوف است، اما هنوز هم از پتانسیل کامل این امر بهره نمی‌برد. اسنادی که از برچسب موضوعی برخوردار نبوده اما از چشم‌انداز بازیابی اطلاعات، مرتبط محسوب می‌شوند، متعلق به خوشه‌ی آن موضوع شناخته نمی‌شوند. ما معتقدیم پرس‌وجوهایی در برابر موتورهای جست‌وجوی مناسب، با بهره برداری از تحقیقات گسترده‌ی مرتبط با بازیابی اطلاعات در دهه‌های اخیر، قادر به رفع این اشکال هستند. در بخش بعد، چند مورد از تفکرات مرتبط که الهام بخش رویکرد ما نیز بوده‌اند، مورد بحث و بررسی قرار گرفته است.

 

3.    رویکرد ما

در رویکرد ما، از پرس‌وجوها به عنوان اهرم‌هایی مفید در فرایند خوشه‌بندی و به عنوان برچسب استفاده شده است. از این طریق، از مفهومی آشنا برای کاربران در تجربه‌ی خود از جست‌وجوی روزانه در اینترنت بهره گرفته‌ایم که مبتنی بر پیوند کلید واژه‌ها به مجموعه‌های اسناد توسط پرس‌وجوها است. با تفسیر Lingo [14] و کی-میانگین‌های توصیفی [24]  می‌توان از پرس‌وجوهای جست‌وجو در الگوریتم‌های آن‌ها استفاده نمود. با این حال، پرس‌وجوها تنها برای تایید اعتبار خوشه‌بندی به کار می‌روند. در عوض، پرس‌وجوهای موجود در روش ما به عنوان نیروی محرک در هنگام دریافت خوشه‌بندی در نظر گرفته می‌شوند؛ این مطلب، از چارچوب خوشه‌بندی بهینه نظری (OCF)[9] توسط فوهر و همکارانش الهام گرفته شده که طبق آن، امتیازات مرتبط بودن جست‌وجو یا رده‌های بازیابی به عنوان ویژگی‌های خوشه‌بندی به شمار می‌روند [6]. با این وجود،  OCF به مسئله برچسب‌گذاری خوشه‌های حاصله نمی‌پردازد.

در رویکرد جدید ما، تفکری کلی از OCF با مفهوم گالوب و همکارانش مبتنی بر مفهوم پرس‌وجوهای کلیدی به عنوان توصیف کنندگان سند [8,9] ترکیب شده که اخیرا جهت پیشنهاد اسناد مرتبط مورد استفاده قرار گرفته است [10]. ما از پرس‌وجوهای کلیدی به عنوان ویژگی‌های خوشه‌بندی به سبک OCF استفاده خواهیم نمود، اما آنگاه پرس‌وجوهای کلیدی مناسبی را به عنوان برچسب پیشنهاد خواهیم داد. بر اساس یافته‌های استاین و مایر زو آیبن [21]، برچسب‌های معنادار خوشه باید جامع (ترکیب نحوی مناسب)، توصیفی (انعکاس هر سند در خوشه)، و متمایز کننده (هم‌پوشانی معنایی حداقل میان دو برچسب خوشه‌ای) باشند. اکثر تکنیک‌های برچسب‌گذاری خوشه‌ها به اندازه‌ی کافی به جنبه‌ی توصیفی این مطلب نمی‌پردازند، اما همان‌طور که نشان خواهیم داد، پرس‌وجوها از این قابلیت برخوردارند.

1.3. پرس‌وجو‌ها: نامزدهایی برای برچسب‌ها

برای مدل‌سازی میزان توصیفی برچسب‌های خوشه، درک کاربر از یک برچسب را بدین صورت در نظر می‌گیریم: نمایش برچسب یک خوشه، موجب فعال‌سازی یک مفهوم در ذهن کاربر می‌گردد و هر سندی که با این مفهوم مرتبط باشد، بایستی در دسته‌ی آن برچسب قرار بگیرد. از لحاظ مفهومی، این فرایند با عمل استاندارد بازیابی اطلاعات یا جست‌وجوی پرس‌وجو محور ارتباط بسیار نزدیکی دارد. این همانندی ما را بر آن داشت تا استفاده از پرس‌وجوهای جست‌وجو را به عنوان برچسب‌های خوشه که باید اسناد خوشه‌ی مربوط را بازیابی کنند، پیشنهاد دهیم. عمل خوشه‌بندی سند که بتوان آن را به عنوان جست‌وجوی پرس‌وجو محور معکوس تنظیم نمود، بدین صورت است: با توجه به یک مجموعه از اسناد، تعدادی از پرس‌وجوهای متنوع جست‌وجو را به دست آورد که در زمان ثبت در یک موتور جست‌وجوی مرجع، بتواند سند را بازیابی کند. علاوه بر اسناد بازیابی شده‌ی آن‌ها تحت عنوان محتوای خوشه، پرس‌وجوها یک خوشه‌بندی برچسب‌گذاری شده را تشکیل خواهند داد. این مطلب نشان می‌دهد که خوشه‌های بالقوه‌ی یک سند طی پرس‌وجوهایی به دست می‌آیند که برای آن‌ها بازیابی شده و به اولین محدودیت جدید درون مجموعه اصطلاحات خوشه‌بندی محدود، منتهی می‌شود [2]: محدودیت پرس‌وجوی مشترک CQ[10] که طبق آن، دو سند در صورتی که با یک پرس‌وجوی مشترک قابل بازیابی نباشند، نمی‌توانند در یک خوشه قرار بگیرند.

برای یافتن پرس‌وجوهای برچسب‌گذاری، لغات احتمالی بایستی تعریف شوند. تولید لغات یکی از گام‌های مهم در خط لوله‌ی ما است، چرا که انتخاب عبارات لغوی تعیین کننده‌ی توان جامع برچسب‌های خوشه به شمار می‌رود. در صورتی که عبارات مبهم، دو پهلو و خیلی جزئی بوده و جامع نباشد، برچسب‌های خوشه نیز به ناچار این ایرادات را نشان خواهد داد و قادر به انعکاس محتوای یک خوشه نخواهد بود. هم‌چنین، اندازه‌ی لغات نیز بر عملکرد کلی تاثیر گذار است. در رابطه با ساختار نحوی برچسب‌های خوشه‌ای، اسامی دسته‌ها در سیستم‌های دسته‌بندی یا ویکی‌پدیا ایده‌آل هستند [21, 22, 24]. اسامی دسته‌ها معمولا عبارات اسمی یا حرف ربط آن‌ها می‌باشند؛ بر این اساس، عبارات اسمی جهت ایفای نقش برچسب‌های خوشه‌ای را مناسب می‌دانیم. به دلایل مرتبط با خوانایی، محدود نمودن تعداد حروف ربط را به یک عدد پیشنهاد می‌کنیم. به عنوان مثال، "کتابخانه‌ها و آرشیوهای دیجیتال". این مطلب دومین محدودیت ما را تشکیل می‌دهد که محدودیت نحوی پرس‌وجو QS[11]  نام داشته و بر اساس آن، یک برچسب خوشه‌ای از عبارات اسمی یا حروف ربط آن‌ها تشکیل شده است.

با این وجود، تمامی عبارات اسمی انتخاب‌های مناسبی برای برچسب‌های خوشه‌ای را تشکیل نمی‌دهند. حتی با وجود این‌که تعیین کننده‌ها معمولا به‌عنوان بخشی از عبارت اسمی در نظر گرفته می‌شوند، در سناریوی ما ضروری نیستند. همین امر برای پسا-اصلاح کننده‌ها[12] و غیره نیز صدق می‌کند. ما عبارات اسمی را به عنوان پیوندی از پیش-اصلاح کننده‌ها و یک اسم اصلی در نظر می‌گیریم. با این حال، پیش-اصلاح کننده‌ها هنوز به نحوی که بتوان برچسب‌های خوشه‌ای طولانی به صورت دلخواه را تولید نمود، دستخوش محدودیت نشده‌اند. بر اساس توزیع موجود در ویکی‌پدیا که در آن، نام دسته به‌طور متوسط شامل 87/3 عبارت است، سومین محدودیت ما مشخص شده که عبارت است از محدودیت طولی پرس‌وجو QL[13] و طبق آن، یک برچسب خوشه‌ای در دو عبارت اسمی، حداکثر چهار اصطلاح را شامل می‌شوند (یعنی طول حداکثر برابر است با هشت، به علاوه‌ی حرف ربط). برای پیدا کردن عبارات مناسب، از استخراج‌کننده اسم اصلی بارکر و کورناچیا[14] [1] استفاده می‌کنیم که ارائه دهنده‌ی نوعی رده‌بندی عبارات است که از آن و به ازای هر سند، 6 مورد برتر را انتخاب می‌کنیم (طبق آنچه که در مطالعات آزمایشی تعیین شده است)؛ سپس این عبارات منتخب بر اساس انواع مختلف آن با استفاده از کتابخانه‌ی Apache OpenNLP مرتب می‌شود تا از انحرافات مختلف اجتناب گردد. البته استخراج کننده‌های عبارات کلیدی دیگر را نیز می‌توان در این مجموعه ادغام نمود:

برای اجتناب از عبارات بی‌معنی مانند "اشکال بزرگ" یا "نمونه متداول"، صورت دیگری از تولید واژگان را در نظر می‌گیریم که تنها عبارات اسمی از واژگان از پیش تعریف شده را می‌پذیرد. بر اساس پیشنهادات میالچیا و سومای [13]، تیترهای مقالات موجود در ویکی‌پدیا را به عنوان منبعی از واژگان کنترل شده و از پیش تعریف شده انتخاب می‌کنیم که شامل عبارات مناسب و سازگار است. با اعمال سه محدودیتی که قبلا به آن‌ها اشاره شد، تنها تیترهایی را انتخاب می‌کنیم که از حداکثر طول چهار اصطلاح برخوردار باشند. به علاوه، آن دسته از تیترهایی را که در ویکی‌پدیا منحصرا شامل کلمات توقف (پرتکرار)، تاریخ و حروف لاتین یا خاص می‌شوند را حذف می‌کنیم، زیرا معمولا نمی‌توانند نقش برچسب‌های خوشه‌ای معنادار را ایفا کنند. دامنه‌ی واژگانی که حاصل می‌شود از 2869974 تیتر برخوردار است که هم‌چنین بر اساس انواع مختلف خود مرتب می‌شوند. جهت رده‌بندی عبارات انتخابی ممکن در ویکی‌پدیا، از امتیاز عبارت کلیدی[15] [13] به عنوان نسبت تعداد مقالاتی که حاوی عبارت به عنوان یک لینک هستند و تعداد کل مقالاتی که از عبارت برخوردارند، استفاده می‌کنیم.

2.3. موتورهای جست‌وجو و مدل‌های بازیابی مورد بررسی

در گام فهرست‌سازی سند در خط لوله خوشه‌بندی ما، با استفاده از پرس‌وجوها به عنوان واسطه‌هایی مناسب برای کسب خوشه‌ها و برچسب‌ها، از تلاش‌های تحقیقاتی صورت گرفته‌ی دهه‌ی اخیر در زمینه‌ی مدل‌های بازیابی بهره می‌گیریم. البته مدل‌های بازیابی مختلف ممکن است خوشه‌بندی‌ها و برچسب‌های متفاوتی را ارائه کنند. مدل‌هایی که در خط لوله‌ی ما مورد آزمایش قرار می‌گیرند عبارت است از: مدل کلاسیک بولی[16] (پرس‌وجوهایی بر پایه‌ی منطق بولی اما بدون امکان رده‌بندی)، مدل فضای برداری با توزین tf . idf [18] (مدل‌سازی اسناد و پرس‌وجوها به عنوان بردار)، BM25 [17] ("tf . idf + طول سند";)، و ESA [7] با مقالات ویکی‌پدیا به عنوان مجموعه پیش زمینه (رویکرد مدل‌سازی موضوعی با در نظر گرفتن شباهت‌های معناشناسانه). بر اساس ارزشیابی ما، مدل بازیابی ESA مناسب‌ترین مدل برای کار ما شناخته شده است.

برای آن دسته از مدل‌های بازیابی که نتایج را رده‌بندی می‌کنند، دو محدودیت ارتباطی دیگر قرار می‌دهیم تا اسناد با رده‌های پایین‌تر به عنوان بخشی از مجموعه نتایج مورد نظر برای خوشه‌بندی در نظر گرفته نشوند. این محدودیت‌های ارتباطی منعکس کننده‌ی تفکر پرس‌وجوی کلیدی گالوب و همکارانش [8] است: یک پرس‌وجوی کلیدی برای یک سند، پرس‌وجویی است که سندی در بالاترین رده‌ها را ارائه کند. طبق محدودیت بالاترین مقدار k، تنها بالاترین نتایج k از یک پرس‌وجو می‌تواند به عنوان مجموعه نتیجه محسوب شود؛ بر اساس تفکر اصلی پرس‌وجوی کلیدی، ما مقدار k را برابر با 10 فرض می‌کنیم. از آن‌جایی که یک سند در رده‌ی k+1 می‌تواند به میزان سند موجود در رده‌ی k مرتبط باشد، این نوع قطع جریان ساکن می‌تواند مشکل‌زا بوده و موجب محدود شدن اندازه‌ی خوشه‌های ممکن در سناریوی ما شود؛ عدم اطلاع از اندازه خوشه‌ها پیش از عمل، فرایند را دشوار می‌سازد. در نتیجه، ما محدودیت امتیاز را پیشنهاد می‌کنیم که بر اساس آن، سند باید از امتیاز بازیابی بالاتری نسبت به مرز ارتباطی t برخوردار باشد تا به عنوان بخشی از مجموعه‌ی نتیجه به شمار آید. طبق تجارب آزمایشی ما با تکنیک‌های مختلف از "گرفتن میانگین" امتیازات بازیابی، t=si2/si ، که در آن si  به معنای امتیاز بازیابی یک سند می‌باشد و به نظر انتخاب خوبی بوده است. در قیاس با میانگین استاندارد t=si/N ، در این فرمول بر بالاترین امتیازات تاکید شده و تاثیر امتیازات پایین‌تر کاهش یافته است.

3.3. الگوریتم‌های خوشه‌بندی محدود به پرس‌وجو

به ازای هر سند در مجموعه‌ای که قرار است خوشه‌بندی شود، تمامی پرس‌وجوهایی که سند بر اساس آن بازیابی شده را طبق محدودیت ارتباطی فوق‌الذکر در یک شاخص بازگشتی ذخیره می‌کنیم [15]. فهرست‌های متعاقب اسناد در شاخص بازگشتی حاوی پرس‌وجوهای کلیدی بوده و نقش ویژگی‌های سند را برای خوشه‌بندی ایفا می‌کند. در ادامه، سه الگوریتم خوشه‌بندی مختلف را معرفی خواهیم نمود که محدودیت پرس‌وجوی مشترک را رفع می‌کنند.

خوشه‌بندی پوشش مجموعه. این الگوریتم طی فرض خوشه‌بندی به عنوان یک مسئله‌ی پوشش مجموعه (SCP)[17] در فهرست‌های نتیجه واژگان پرس‌وجو به آن می‌پردازد. در سناریوی ما، یکی از انواع متفاوت الگوریتم پوشش مجموعه حریصانه[18] را به کار خواهیم برد [23]. به ازای k تعداد تکرار، پرس‌وجوی q بر اساس این موارد انتخاب می‌شود: وجود اندازه مجموعه نتیجه‌ی آن در یک محدوده‌ی خاص، پوشش حداکثر تعداد اسنادی را که طی پرس‌وجوهای قبلی پوشش داده نشده‌اند، و نرخ مثبت بالای پرس‌وجو در اسناد پوشش داده نشده در مجموعه نتیجه و در نموداری که اسناد را طی مرز مبتنی بر اشتراک به یک‌دیگر متصل می‌کند (یعنی وجود چندین مرز میان دو سند امکان‌پذیر است). نرخ مثبت یک مجموعه نتیجه‌ی جدید، همان نسبت مرزهای حقیقی میان اسناد پوشش داده نشده در مجموعه نتیجه و حداقل تعداد مرزها است، در صورتی که هر کدام از این اسناد تنها توسط یک پرس‌وجو قابل بازیابی باشد. توجه داشته باشید که از این طریق، اسناد در خوشه‌بندی می‌توانند بخشی از چندین مجموعه نتیجه باشند.

خوشه‌‌بندی تجمعی[19]. دومین نوع از الگوریتم‌های ما بر پایه‌ی رویکردی تجمعی از خوشه‌بندی سلسله مراتبی قرار دارد. با هر کدام از اسناد در خوشه‌ی خود آغاز نموده و سپس جفت‌هایی از خوشه‌ها را در یک رویکرد "پایین به بالا" با یک‌دیگر ترکیب می‌نماید. برای این ترکیب، به مقیاس‌هایی برای فاصله میان جفت‌های تشکیل شده از اسناد به‌علاوه‌ی یک معیار پیوندی در رابطه با فاصله‌ی خوشه‌ها نیاز است. ما برای هر دو فاصله، تعداد پرس‌وجوهای کلیدی مشترک را انتخاب نموده‌ایم. در رابطه با شباهت خوشه نیز رویکرد خوشه‌بندی پیوند کامل را دنبال می‌کنیم (با در نظر گرفتن تمامی شباهت‌های جفت سند میان دو خوشه)؛ زیرا این امر از پدیده‌ی زنجیری خوشه‌بندی تک پیوندی جلوگیری نموده که در آن ممکن است خوشه‌ها به دلیل نزدیکی یک جفت از اسناد به یک‌دیگر، علیرغم عدم شباهت بسیار میان تمامی اسناد دیگر، با هم ترکیب گردند. الگوریتم ما دو خوشه‌ای را با هم ترکیب می‌کند که جفت‌های سند موجود در آن‌ها از بیش‌ترین میزان اشتراک پرس‌وجو برخوردار باشند. در صورتی که این تعداد حداکثری میان بیش از دو خوشه مشترک باشند، الگوریتم نسبت به ضریب پرس‌وجوهای مشترک تا غیر مشترک جفت‌های سندی تصمیم‌گیری می‌کند. به دلیل این‌که اسناد دو خوشه‌ی ترکیب شده لزوما تنها خوشه‌هایی نیستند که توسط پرس‌وجوهای کلیدی مشترک بازیابی شده‌اند، ما تمامی خوشه‌های باقی مانده‌ای که طی پرس‌وجوهای کلیدی بازیابی شده‌اند را نیز در نظر می‌گیریم.  

زمانی که عمل ترکیب در نهایت به تعداد مطلوبی از خوشه‌ها منتهی شد، الگوریتم متوقف می‌گردد. اما تنها پیوند زدن مجموعه پرس‌وجوها به عنوان برچسب خوشه متناظر در بسیاری از موارد محدودیت طول پرس‌وجوی ما را خدشه‌دار می‌کند (به عنوان مثال، زمانی که بیش از دو پرس‌وجو در یک گره باقی مانده است). بر همین اساس، تلاش می‌کنیم پرس‌وجو یا جفتی از آن را پیدا کنیم که "بهترین" پوشش برای اسناد خوشه‌ای باشند. از آن‌جا که تمامی پرس‌وجوها حداقل اسناد خوشه‌ای را پیدا می‌کنند، ما پرس‌وجویی (یا جفتی از آن) را انتخاب می‌کنیم که کم‌ترین تعداد از اسناد اضافی خوشه‌های دیگر را بازیابی کنند.

خوشه‌بندی کی-میانگین محدود شده. الگوریتم خوشه‌بندی محدود به پرس‌وجو در این بخش از الگوریتم پرطرفدار کی-میانگین داده محور همراه با ویژگی‌های پرس‌وجوی کلیدی بهره می‌برد. با توجه به مجموعه‌ای از نقطه‌های داده، کی-میانگین‌ها در سه گام عمل می‌کنند: (1) در مقداردهی اولیه، مقادیر تصادفی k درون دامنه‌ی داده‌ها به عنوان نمایندگان اولیه‌ی خوشه انتخاب می‌شوند (مرکزوار). در سناریوی ما، اگر سند به وسیله پرس‌وجوی موجود در شاخص بازگشتی بازیابی شده باشد، هر سند توسط یک بردار با 1 در موقعیت i و در غیر این صورت با 0 نشان داده می‌شود. جهت مقداردهی اولیه، ما تعداد k از این بردارها را به صورت تصادفی تولید می‌کنیم. (2) در مرحله‌ی واگذاری، هر نقطه داده به نزدیک‌ترین مرکزوار خود تخصیص یافته و در نتیجه‌ی آن خوشه‌هایی از نقاط داده‌ها تشکیل می‌شوند. (3) در مرحله‌ی به‌روزرسانی، مرکزوارهای k از خوشه‌های جدید محاسبه گردیده و وارد مرحله‌ی تخصیص می‌شوند تا زمانی که به هم‌گرایی دست یافته یا به آستانه‌ی تکرار برسد. در سناریوی ما، به ازای هر خوشه، پرس‌وجویی انتخاب می‌شود که مجموعه نتایج آن از لحاظ مقیاس F بهترین پوشش بر اسناد تخصیص یافته را داشته باشد. مرکزوار جدید به عنوان بردار میانگین نتیجه‌ی اسناد از بهترین پرس‌وجو محاسبه می‌گردد.

4.    ارزشیابی

ما در نسخه‌ای گسترش یافته از داده‌های Ambient به مقایسه‌ی انواع مختلفی از خط لوله‌ی خوشه‌بندی پرس‌وجو محور سه مرحله‌ای خود با دو مورد از رویکردهای معمول و مورد استفاده می‌پردازیم. در این میان، یک تحقیق کاربری با 49 شرکت کننده در رابطه با توان توضیحی برچسب خوشه‌ها انجام می‌دهیم.

1.4. مجموعه داده‌های AMBIENT++

مجموعه داده‌های اصلی Ambient در سال 2008 توسط کارپینتو و رومانو منتشر شد و در زمینه‌ی خوشه‌بندی اسناد و ارزشیابی برچسب‌ها به محبوبیت زیادی دست یافته است [19, 20]. این مجموعه شامل 44 موضوع مبهم و دو پهلو است که هر کدام، 18 موضوع فرعی دارد که برگرفته از صفحات ابهام‌زدایی ویکی‌پدیا می‌باشند. برخی از موضوعات فرعی به مجموعه‌ای از اسناد (URL، تیتر، قطعه) تخصیص داده شده‌اند که طی ثبت هر موضوع به عنوان یک پرس‌وجو در یک موتور جست‌وجوی اینترنتی یا تخصیص دستی هر URL در 100 نتیجه‌ی برتر به یک موضوع فرعی جمع‌آوری شده‌اند. با این حال، اسناد ذخیره نشده و موضوعات فرعی از لحاظ اندازه بسیار نابرابر هستند. در نتیجه، ما مجموعه داده‌های Ambient را به عنوان پیکره‌ی گسترش یافته‌ی خود تحت عنوان AMBIENT++ طبق آنچه که در ادامه آمده است، بازسازی می‌کنیم.

اسناد موجود در URLهای اصلی Ambient، پایه و اساس گسترش پیکره‌ای ما را تشکیل داده و در گام اول گنجانده می‌شوند. مولفه‌های مجموعه داده‌های اصلی تعداد 2257 URL را به یک موضوع فرعی تخصیص دادند؛ در واقع، هیچ سندی به اکثر موضوعات فرعی تخصیص داده نشده است، در حالی که موارد دیگر از تعداد 76 URL برخوردار بوده‌اند. در اوایل سال 2016، تنها 1697 سند از مجموعه داده‌های اصلی قابل گنجاندن بود. پس از یک بازرسی دستی، 611 سند باید حذف می‌شدند چرا که موضوع فرعی تخصیص داده شده‌ی اصلی دیگر مورد بحث قرار نگرفته بود و در این حالت 1086 سند باقی ماند. بر این اساس، ما داده‌ها را غنی می‌کنیم تا حداقل 10 سند در هر کدام از موضوعات فرعی قرار داده شوند. بدین منظور، توضیحات برگرفته از صفحات ابهام‌زدایی ویکی‌پدیا در یک موتور جست‌وجوی اینترنتی ثبت گردید و فهرست‌های به‌دست آمده به صورت دستی و تا زمانی که برای هر موضوع فرعی 10 سند در دسترس قرار گرفت، ارزیابی شدند (بدون در نظر گرفتن صفحاتی که تنها حاوی عکس، ویدیو، جدول و غیره بودند). در برخی از موارد، توضیحات موضوع فرعی پرس‌وجوهای موفقی نیستند (به عنوان مثال، طول یا جزئیات بیش از حد). در این موارد، مفسران ما به‌طور دستی به تشکیل یک پرس‌وجوی مناسب‌تر پرداختند. اما با وجود این‌که 4506 سند اضافی را به موضوعات فرعی تخصیص دادیم، چند موضوع اندک هنوز هم از 10 سند "معتبر" برخوردار نبودند. تعداد کل اسناد 5592 عدد بود.

به دلیل عدم امکان غنی‌سازی تمامی موضوعات فرعی به شکل بهینه و این‌که برخی از موضوعات فرعی حاوی تعداد بسیار بیش‌تری از 10 سند هستند، ما مجموعه داده‌ها را با موضوعات فرعی که دقیقا 10 سند را شامل می‌شوند، متعادل می‌کنیم. موضوعات فرعی با کم‌تر از 10 سند را حذف نموده و از میان مواردی که حاوی تعداد زیادی سند هستند، تنها 10 نتیجه پرس‌وجوی برتر را حفظ می‌کنیم که در قیاس با 25 موضوع فرعی در مجموعه داده‌های اصلی  Ambient،  به تعداد 481 موضوع فرعی با 10 سند منتهی می‌شود. در طول پالایش (فیلتر) دستی، چند موضوع فرعی با معانی همسان را نیز پیدا نمودیم (به عنوان مثال، موضوع فرعی 12.11 (globe، یک گروه موسیقی ژاپنی با سبک ترنس/پاپ-راک) و موضوع فرعی 12.17 (globe (گروه موسیقی، گروه موسیقی پاپ))) که جداسازی آن‌ها در خوشه‌بندی به نحوی که یکی از آن‌ها را حفظ کنیم، بیش از حد دشوار است؛ در نتیجه، 13 موضوع فرعی حذف شدند. در مجموعه داده‌های غنی شده ما، هر کدام از 44 موضوع حداقل از سه موضوع فرعی برخوردار است (تعداد کل 468) که هریک حاوی 10 سند می‌باشد. برای استخراج محتوای اصلی 4680 سند موجود در پیکره، ما از استخراج کننده‌ی پیش‌فرض[20] از کتابخانه‌ی بویلرپایپ[21] [11] استفاده می‌کنیم که در آزمایش‌های اولیه از بهترین عملکرد برخوردار بوده است. 

4.2. مقیاس F نرم به عنوان یک مقیاس جدید ارزشیابی

در چارچوب آزمایشی ما، هر موضوع از مجموعه داده‌های AMBIENT++ را به عنوان یک مجموعه برای خوشه‌بندی در نظر می‌گیریم که در آن خوشه‌بندی "بهینه"، خوشه‌هایی را تشکیل می‌دهد که با موضوعات فرعی مرتبط همسان هستند. با این حال، خوشه‌بندی‌های پرس‌وجو محور ما می‌توانند به خوشه‌هایی منتهی شوند که ارزشیابی آن‌ها با مقیاس F سنتی در برابر اطلاعات میدانی دشوارند. به عنوان مثال پرس‌وجوی "حیوان" برای موضوع "شتر" می‌تواند اسنادی درباره‌ی جانور کوهان‌دار را بازیابی کند، اما این اسناد می‌تواند درباره‌ی نوعی عنکبوت (عنکبوت شتری، هر دو موضوع فرعی مرتبط با موضوع شتر) نیز باشد و در این حالت، خوشه‌ی به دست آمده در برابر یکی از دو حقیقت عینی موضوعات فرعی/خوشه‌ها قابل ارزشیابی نیست. جهت مقایسه‌ی کیفیت خوشه‌بندی‌ها با چنین خوشه‌های دو پهلو یا دارای همپوشانی، مقیاس F  نرم (این نام از الگوریتم‌های خوشه‌بندی نرم الهام گرفته شده که در آن‌ها، یک سند ممکن است در چندین خوشه وجود داشته باشد) را پیشنهاد می‌کنیم. این مقیاس در سطح جفت‌های سندی به محاسبه‌ی درست/غلط و مثبت/منفی می‌پردازد؛ برخلاف مقیاس F سنتی که جفت‌های سند-خوشه را بررسی می‌کند. به ازای هر جفت سند در خوشه‌بندی، توان ارتباطیs  را با استفاده از نسبت خوشه‌های مشترک به تمامی خوشه‌هایی که به آن‌ها تخصیص داده شده‌اند، محاسبه می‌کنیم (حداکثر توان ارتباطی برابر است با 1). اگر دو سند در اطلاعات میدانی در موضوع فرعی/خوشه‌ی یکسانی باشند، s به امتیاز مثبت صحیح و 1-s به امتیاز منفی کاذب اضافه می‌شود؛ در غیر این صورت، در نهایت، s به امتیاز مثبت کاذب و 1-s به امتیاز منفی صحیح اضافه می‌شود. از امتیازات در فرمول "سنتی" مقیاسF  استفاده می‌شود. لازم به ذکر است که مقیاس F نرم، "متقارن" نیست (به عنوان مثال، تنها بازیابی شش مورد از ده سند در یک خوشه بدتر از بازیابی تمام ده سند به همراه چهار مورد مثبت کاذب است).

4.3. راه‌اندازی خط‌لوله‌ی ما

برای هر کدام از مراحل خط لوله (تولید واژگان، فهرست‌بندی اسناد، خوشه‌بندی محدود)، عملکرد گونه‌های مختلف بر یک مجموعه‌ی تمرینی از ده موضوع را با "بهترین" خوشه‌بندی ممکن و یک خوشه‌بندی فهرستی مقایسه می‌نماییم. بهترین خوشه‌بندی طی تحلیل جامعی به دست می‌آید که پرس‌وجوها را از فهرستی پیدا می‌کند که به بهترین شکل موضوعات فرعی را در رابطه با مقیاس F نسبت به اطلاعات میدانی شناسایی می‌نماید. خوشه‌بندی فهرست از تمامی لیست‌های متعاقب در فهرست به عنوان خوشه استفاده می‌کند. منطق این رویکرد بر پایه‌ی فرضی است که طبق آن، ورودی‌های فهرست معکوس به عنوان پشتیبانی برای خوشه‌بندی پرس‌وجو محور دیده می‌شود: به هر میزان که پرس‌وجوها مجموعه نتیجه‌های مشابهی را بازیابی کنند، احتمال گروه‌بندی این اسناد با هم بالا می‌رود.

در آزمایش‌های مقدماتی ما، واژگان عبارت اسمی نسبت به واژگان ویکی‌پدیا از عملکرد خوشه‌بندی نسبتا بهتری برخوردار است (مقیاس F 26/0 در برابر 91/0) و هم‌چنین مقیاس F نرم کمی بالاتر برای خوشه‌بندی فهرست (26/0 در برابر 25/0) به نحوی که عبارات اسمی را به عنوان واژگان انتخاب می‌کنیم. جهت تصمیم‌گیری تعداد عبارات برای استخراج به ازای هر سند، 1 الی 20 عبارت استخراج شده را برای هر سند آزمایش می‌کنیم. به طرزی جالب توجه، مقیاس F بهترین خوشه‌بندی در شش عبارت اسمی استخراج شده به اشباع می‌رسد. در نتیجه، تصمیم می‌گیریم که شش عبارت از هر سند را استخراج کنیم.

جهت غلبه بر تاثیر عبارات احتمالا ناکافی برای مقایسه‌ی مدل‌های بازیابی مختلف (بولی، tf . idf، BM25، ESA) و تنظیمات پارامتر محدودیت ارتباطی (رده یا امتیاز)، به صورت دستی به تولید پرس‌وجوهای مناسب برای هر یک از موضوعات فرعی در مجموعه‌ی تمرینی خود پرداخته و مقیاس F فهرست‌های نتیجه را با توجه به موضع فرعی که پرس‌وجو متعلق به آن است، مقایسه می‌کنیم. همان‌طور که در سناریوی AMBIENT++ ما انتظار می‌رفت، یک محدودیت ثابت قطع کننده در رده‌ی 10، عملکرد بسیار بهتری نسبت به یک محدودیت امتیاز دارد که خوشه‌هایی با بیش از 70 سند را ارائه می‌کند (به یاد داشته باشید که هر موضوع فرعی 10 سند دارد). به جز چند مورد استثنا، هر سه مدل بازیابی رده‌بندی محور نسبت به مدل بولی عملکرد بهتری دارند، در حالی که مدل ESA از مدل‌های دیگر در 8 مورد از 10 موضوع عملکرد مناسب‌تری دارد. در رابطه با ESA در مجموعه تمرینی ما، مقالات کامل ویکی‌پدیا به عنوان مجموعه مفاهیم پیش زمینه، عملکرد بهتری در بیش از چند پاراگراف اولیه‌ی هر مقاله دارند.

از سه روش خوشه‌بندی در خط لوله‌ی ما (پوشش مجموعه، تجمعی، کی-میانگین‌های محدود)، روش کی-میانگین‌های محدود بالاترین امتیازات مقیاس F نرم را با ESA در مجموعه تمرینی ما به دست می‌آورد (0/83 در برابر 0/77 برای دو مورد دیگر) اما هنوز هم فاصله‌ی زیادی تا بهترین خوشه‌بندی با مقیاس F نرم متوسط 94/0 دارد.

بهترین حالت راه‌اندازی خط لوله ما (خوشه‌بندی کی-میانگین‌های محدود با شش عبارت اسمی استخراج شده و ده نتیجه برتر ESA با مقالات ویکی‌پدیا به عنوان مجموعه‌ی پیش زمینه) اکنون با دو مورد از رویکردهای معمول خوشه‌بندی + برچسب‌گذاری مقایسه می‌شود: کی-میانگین‌ها به‌علاوه‌ی خط پایه χ2  [12] که نماینده‌ی الگوریتم‌های داده محور و کی-میانگین‌های توصیفی [24] نشان دهنده‌ی الگوریتم‌های شرح محور است.

 

شکل 1. مقایسه‌ی خوشه‌بندی کی-میانگین‌های محدود شده‌ی ما با خط پایه

 

4.4. کیفیت خوشه‌بندی

ارزشیابی کیفیت خوشه‌بندی در تمامی موضوعات موجود در مجموعه داده‌های جدید AMBIENT++ ما با به کارگیری مقیاس F نرم برای خوشه‌هایی برگرفته توسط الگوریتم برای یک موضوع صورت می‌پذیرد. با مقیاس F نرم میانگین 83/0، کی-میانگین‌های محدود جدید ما و میانگین‌ها به علاوه‌ی χ2  تقریبا بهتر از کی-میانگین‌های توصیفی با مقدار 82/0 هستند (کی یا k همیشه به عنوان عدد حقیقی موضوعات فرعی برای هر الگوریتم تنظیم می‌شود)؛ بر این اساس، ادغام پرس‌وجو به کیفیت خوشه‌بندی خدشه وارد نمی‌کند. شکل 1 نحوه‌ی توزیع در سطح موضوعی را نشان می‌دهد که طبق آن، عملکرد متفاوتی برای برخی از موضوعات به نمایش گذاشته شده اما گرایش‌های کلی (موضوعاتی که طی عملکرد الگوریتم ما مرتب شده‌اند) و برخی از موضوعات تقریبا دشوار برای خوشه‌بندی (پوشش مجموعه و روش‌های خوشه‌بندی تجمعی ما نیز در این موارد با مشکلات مشابهی روبرو هستند) با یک‌دیگر مشابه می‌باشند.  

4.5. کیفیت برچسب خوشه

از آن‌جایی که رویکرد جدید ما در چشم‌اندازی مبتنی بر کیفیت خوشه با دو مورد از رویکردهای مورد استفاده معمول قابل مقایسه است، به مقایسه‌ی کیفیت برچسب نیز می‌پردازیم. به این دلیل دشواری ارزشیابی میزان مناسب بودن برچسب یک خوشه، یک تحقیق کاربری با 49 شرکت کننده (23 زن، 26 مرد، با میانگین سنی 3/18 و SD=6.8) بر روی مجموعه داده‌های AMBIENT++ انجام می‌دهیم که از دو آزمایش برای ارزشیابی این موارد برخوردار است: (1) توان متمایز کننده، و (2) توان توضیحی برچسب‌های خوشه.

 

شکل 2. (چپ) تصویری از اولین آزمایش مطالعاتی کاربر، (راست) توزیع قضاوت (CKM=کی-میانگین‌های محدود، DKM=کی-میانگین‌های توصیفی، χ2 = کی-میانگین‌ها + χ2 ) که نشان می‌دهد برچسب‌های رویکرد ما به‌طور قابل توجهی نسبت به برچسب‌های خط پایه از توان متمایز کننده‌ی بیش‌تری برخوردارند.

 

آزمایش شماره 1: توان متمایز کننده. در اولین آزمایش، به بررسی میزان اعمال تمایز میان اسناد در یک خوشه نسبت به خوشه‌های دیگر، توسط برچسب آن‌ها می‌پردازیم. تحقیق ما به صورت تجربی و بر پایه‌ی مرورگر می‌باشد که از طراحی درون-سوژه‌ای برخوردار است، یعنی از هر کدام از شرکت کنندگان درباره‌ی برچسب‌های هر رویکرد سوال می‌شود. برای یک موضوع فرعی مورد نظر، یک توصیف کوتاه متشکل از حداکثر پنج کلمه که به صورت دستی آماده شده است، یک تصویر شناسایی کننده، انتخاب گشته (در عوض متن ابهام زدایی اصلی و طولانی) و برچسب‌های خوشه‌ای یک الگوریتم که برای موضوع یک موضوع فرعی دریافت شده است، به شرکت کننده داده می‌شود. سپس، شرکت کننده بایستی برچسبی که مناسب‌ترین مورد برای یک موضوع فرعی بوده را انتخاب کند (انتخاب اجباری). در مورد محدودیت‌های زمانی، تنها زیرمجموعه‌ای از 22 موضوع تصادفی را در نظر می‌گیریم که از هر کدام، حداکثر چهار موضوع فرعی با بالاترین میانگین خوشه‌بندی از مقیاس F نرم در هر سه رویکرد را انتخاب می‌کنیم (همیشه بالاتر از 8/0 اما برخی از موضوعات تنها از سه موضوع فرعی برخوردارند (میانگین 77/3)). حداکثر هشت برچسب به کاربر نشان داده می‌شود (برخی از موضوعات، از موضوعات فرعی کم‌تری برخوردارند که از موارد دیگر، هفت مورد تصادفی اضافی انتخاب می‌شود). هر کدام از ترکیبات موضوع فرعی-الگوریتم در تحقیق ما توسط سه شرکت کننده مورد قضاوت قرار گرفت که به 747 نتیجه منتهی شد (.3(22.3.77.3))؛ به‌طور متوسط، حدود 15 قضاوت به ازای هر شرکت کننده که موجب می‌شود هیچ شرکت کننده‌ای، یک موضوع فرعی یکسان را دو مرتبه مورد قضاوت قرار ندهد (این امر برای الگوریتم دیگری نیز صورت نمی‌گیرد).

شکل 2، یک تصویر و نتیجه‌ی اولین آزمایش را نشان می‌دهد. در این تصویر، نام موضوع (جگوار) در بالا نشان داده شده است، موضوع فرعی برای قضاوت نیز توسط یک تصویر و شرح مختصر در سمت راست به نمایش گذاشته شده و فهرست به هم ریخته‌ی تصادفی از برچسب‌های خوشه‌ای برای خوشه‌ها در موضوع در سمت چپ تصویر آمده است. اگر هیچ یک از برچسب‌ها راضی کننده نباشد، شرکت کننده باید پایین‌ترین دکمه در تصویر را فشار دهد.

در جدول نتایج، اولین ردیف، نشان دهنده‌ی تعداد قضاوت‌ها است که در آن برچسب انتخاب شده همان برچسبی است که طی رویکرد تولید شده است (یعنی مثبت صحیح)، دومین ردیف حاوی تعداد قضاوت‌هایی است که در آن‌ها، شرکت کنندگان برچسب متفاوتی نسبت به آنچه که طی رویکرد تولید شده را انتخاب نموده (یعنی مثبت کاذب)، و سومین ردیف قضاوت‌هایی را نشان می‌دهد که در آن‌ها شرکت کنندگان هیچ یک از برچسب‌های ارائه شده را انتخاب نکرده‌اند (منفی کاذب). امتیاز  F1 گزارش شده، یک تک مقیاس مشترک است و برای برآورد آماری تاثیرگذاری به ازای هر فرد، نسبت تخصیص‌های صحیح برچسب (مثبت‌های صحیح) را در میان تمامی تخصیص‌های ارائه شده برای یک موضوع فرعی (مثبت‌های صحیح، مثبت‌های کاذب، منفی‌های کاذب) را مقایسه می‌کنیم. هر موضوع فرعی توسط سه شرکت کننده مورد قضاوت قرار می‌گیرد و برچسب‌های تخصیص داده شده به دو گروه صحیح (مثبت‌های صحیح) و کاذب (مثبت‌های کاذب و منفی‌های کاذب) تقسیم می‌شود. در صورتی که هر سه شرکت کننده برچسب صحیح را انتخاب کرده باشند، نسبت برابر با 1=33  خواهد بود. اگر تنها یک شرکت کننده برچسب صحیح را انتخاب کند، نسبت برابر با 13  خواهد بود. بر اساس تست شاپیرو-ویلک[22]، نسبت‌های فردی شرکت کنندگان برای هیچ یک از رویکردها از توزیع نرمال برخوردار نبوده است، به نحوی که تست رده‌ی علامت‌دار ویلکاکسن[23] غیر پارامتری را به عنوان آزمایش مناسب معناداری در طرح تحقیقاتی خود با داده‌های نسبت و سه رویکرد جهت مقایسه انتخاب می‌نماییم. به ازای نسبت‌های 49 شرکت کننده، هنگام مقایسهی توزیع رویکرد ما با کی-میانگین‌های توصیفی، مقدار p 005/0 را به دست می‌آوریم و در قیاس با کی-میانگین‌ها به علاوه‌ی χ2 ، مقدارp کمتر از 001/0 به‌دست می‌آید که نشان می‌دهد رویکرد ما به‌طور قابل توجهی موجب افزایش توان متمایز کننده‌ی برچسب‌های خوشه نسبت به خطوط پایه می‌شود.

آزمایش شماره 2: توان توضیحی. در دومین آزمایش، به بررسی توان توضیحی برچسب‌های خوشه می‌پردازیم. برچسب‌های خوشه‌ای مختلف که طی رویکردهایی برای یک موضوع فرعی تولید شده‌اند، به شرکت کننده نشان داده می‌شود و او بایستی برچسبی را انتخاب کند که ارائه دهنده‌ی بهترین توضیح برای آن موضوع فرعی است. طی محاسبه‌ی مقیاس F نسبت به موضوع فرعی، ما از پوشش موضوع فرعی یکسان توسط خوشه‌های رویکردها اطمینان حاصل می‌کنیم. تنها در صورتی که خوشه‌ی هر رویکرد در رابطه با اسناد موضوع فرعی از آستانه‌ی 8/0 فراتر رود، موضوع فرعی را درون مجموعه داده‌های این آزمایش قرار می‌دهیم که موجب می‌شود هر سه رویکرد، خوشه‌بندی‌های مناسبی را به‌دست آورند. همانند روند موجود در آزمایش 1، سه شرکت کننده به قضاوت در مورد 226 عدد از 468 موضوع فرعی می‌پردازند و این بار نیز موضوع فرعی یکسان به یک کاربر بیش از یک مرتبه نشان داده نمی‌شود.

چهار ردیف اول در جدول موجود در شکل 3 نشان دهنده‌ی تعداد قضاوت‌هایی است که در آن‌ها هر کدام از سه، دو، یک یا هیچکدام از شرکت کننده‌ها رویکرد متناظر را انتخاب نموده‌اند. برای هر سه رویکرد، مجموع 226 موضوع فرعی مورد قضاوت قرار گرفتند. رویکرد ما عملکرد بهتری نسبت به کی-میانگین‌ها داشته (اما در توزیع رای به ازای هر موضوع اختلاف چشمگیری نداشتند) و این دو روش نسبت به کی-میانگین‌ها به علاوه‌ی χ2  مناسب‌تر بوده‌اند.

 

شکل 3. (چپ) تصویری از دومین آزمایش مطالعاتی کاربر، (راست) توزیع قضاوت (CKM=کی-میانگین‌های محدود، DKM=کی-میانگین‌های توصیفی، χ2 = کی-میانگین‌ها + χ2 ) که نشان می‌دهد برچسب‌های رویکرد ما نسبت به برچسب‌های خط پایه از توان توضیحی بیش‌تری برخوردارند.

5.    نتیجه‌گیری و دورنمای تحقیق

ما در این تحقیق به ارائه‌ی یک خط‌لوله‌ی خوشه‌بندی پرس‌وجو محور جدید با استفاده از پرس‌وجوهای کلیدی به عنوان ویژگی‌هایی برای فرایند خوشه‌بندی و هم‌چنین به عنوان برچسب‌هایی برای خوشه‌های به‌دست آمده پرداخته‌ایم. مقایسه میان دو مورد از خط پایه‌های معمول مورد استفاده نشان می‌دهد که رویکرد کی-میانگین‌های محدود ما با مدل بازیابی ESA از چشم‌انداز کیفی خوشه‌بندی، رقیب یک‌دیگر بوده و کیفیت برچسب را به میزان قابل توجهی افزایش می‌دهد. در نتیجه، تفکر ما مبنی بر بازبینی مسئله‌ی خوشه‌بندی از چشم‌انداز مبتنی بر بازیابی اطلاعات با ترکیب تفکراتی از چارچوب بهینه‌ی خوشه‌بندی و تحقیقات مرتبط با پرس‌وجوهای کلیدی، مسیری امیدوار کننده در جهت حمایت از کاربرانی است که با فعالیت‌های تحقیقاتی جست‌وجوگرانه سروکار داشته و نیازمند راهنمایی به شکل خوشه‌بندی‌های اسناد با برچسب‌های مناسب هستند. به عنوان بخشی از ارزشیابی ما، مجموعه داده‌های غنی شده ABMIENT++ را نیز معرفی نمودیم که متشکل از 4680 سند حاشیه‌نویسی شده به صورت دستی است که در دسترس عموم قرار خواهد گرفت و هم‌چنین از یک مقیاس ارزشیابی کیفیت خوشه تحت عنوان مقیاس F نرم نیز برخوردار است.

قراردهی اصطلاحات از طبقه‌بندی‌های از پیش تعریف شده، می‌تواند مسیرهای جالب توجهی برای تحقیقات آینده را تبیین نماید. در این تحقیق، ما تنها به ارزشیابی تیترهای ویکی‌پدیا به عنوان گام اول پرداخته‌ایم. اما هنوز هم پتانسیل زیادی را برای جست‌وجو در این مسیر و هم‌چنین در زمینه‌ی ارزشیابی مجموعه داده‌های دیگر با مدل‌های بازیابی مختلف بیش‌تر را پیش‌بینی می‌کنیم، زیرا عملکرد تمامی مدل‌ها هنوز هم بسیار پایین‌تر از بهترین خوشه‌بندی پرس‌وجوی پیشگو قرار دارد.

 

 

منابع

1. Barker, K., Cornacchia, N.: Using noun phrase heads to extract document keyphrases. In: AI, pp. 40–52 (2000)

2. Basu, S., Davidson, I., Wagstaff, K.: Constrained Clustering: Advances in Algorithms, Theory, and Applications. Chapman & Hall/CRC, Boca Raton (2008)

3. Carpineto, C., Osi´nski, S., Romano, G., Weiss, D.: A survey of web clustering engines. ACM Comput. Surv. 41(3), 17:1–17:38 (2009)

 

4. Cutting, D.R., Karger, D.R., Pedersen, J.O., Tukey, J.W., Scatter, G.: A clusterbased approach to browsing large document collections. In: SIGIR, pp. 318–329 (1992)

5. Ferragina, P., Gull`ı, A.: The anatomy of SnakeT: a hierarchical clustering engine for web-page snippets. In: Boulicaut, J.-F., Esposito, F., Giannotti, F., Pedreschi, D. (eds.) PKDD 2004. LNCS (LNAI), vol. 3202, pp. 506–508. Springer, Heidelberg (2004)

6. Fuhr, N., Lechtenfeld, M., Stein, B., Gollub, T.: The optimum clustering framework: implementing the cluster hypothesis. Inf. Retr. 15(2), 93–115 (2012)

7. Gabrilovich, E., Markovitch, S.: Computing semantic relatedness using Wikipediabased explicit semantic analysis. In: IJCAI, pp. 1606–1611 (2007) Keyqueries for Clustering and Labeling 55

8. Gollub, T., Hagen, M., Michel, M., Stein, B.: From keywords to keyqueries: content descriptors for the web. In: SIGIR, pp. 981–984 (2013)

9. Gollub, T., V¨olske, M., Hagen, M., Stein, B.: Dynamic taxonomy composition via keyqueries. In: JCDL, pp. 39–48 (2014)

10. Hagen, M., Beyer, A., Gollub, T., Komlossy, K., Stein, B.: Supporting scholarly search with keyqueries. In: Ferro, N., et al. (eds.) ECIR 2016. LNCS, vol. 9626, pp. 507–520. Springer, Heidelberg (2016). doi:10.1007/978-3-319 30671-1 37

11. Kohlsch¨utter, C., Fankhauser, P., Nejdl, W.: Boilerplate detection using shallow text features. In: WSDM, pp. 441–450. ACM (2010)

12. Manning, C.D., Raghavan, P., Sch¨utze, H.: Introduction to Information Retrieval. Cambridge University Press, Cambridge (2008)

13. Mihalcea, R., Csomai, A. Wikify!: Linking documents to encyclopedic knowledge. In: CIKM, pp. 233–242 (2007)

14. Osi´nski, S., Stefanowski, J., Weiss, D.: Lingo: search results clustering algorithm based on singular value decomposition. In: IIPWM, pp. 359–368 (2004)

15. Pickens, J., Cooper, M., Golovchinsky, G.: Reverted indexing for feedback and expansion. In: CIKM, pp. 1049–1058 (2010)

16. van Rijsbergen, C.J.: Information Retrieval. Butterworth-Heinemann, London (1979)

17. Robertson, S., Zaragoza, H.: The probabilistic relevance framework: BM25 and beyond. FnTIR 3(4), 333–389 (2009)

18. Salton, G., Wong, A., Yang, C.-S.: A vector space model for automatic indexing. CACM 18(11), 613–620 (1975)

19. Scaiella, U., Ferragina, P., Marino, A., Ciaramita, M.: Topical clustering of search results. In: WSDM, pp. 223–232 (2012)

20. Stein, B., Gollub, T., Hoppe, D.: Beyond precision@10: clustering the long tail of web search results. In: CIKM, pp. 2141–2144 (2011)

21. Stein, B., Meyer zu Eißen, S.: Topic identification: framework and application. In: I-KNOW, pp. 522–531 (2004)

22. Treeratpituk, P., Callan, J.: An experimental study on automatically labeling hierarchical clusters using statistical features. In: SIGIR, pp. 707–708 (2006)

23. Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)

24. Weiss, D.: Descriptive clustering as a method for exploring text collections. PhD thesis, University of Poznan (2006)

25. Zamir, O., Etzioni, O.: Web document clustering: a feasibility demonstration. In: SIGIR, pp. 46–54 (1998)

 



[1] k-means

[2] soft clustering measure

[3] Scatter/Gather algorithm

[4] Vector Space Model

[5] Monothetic Clustering

[6] Suffix Tree Clustering

[7] Weiss

[8] Centroid

[9] Optimum Clustering Framework

[10] Common-query Constraint

[11] Query-syntax Constraint

[12] Post-modifiers

[13] Query-length Constraint

[14] Barker and Cornacchia’s head noun extractor

[15] Keyphraseness score

[16] classic Boolean model

[17] Set Cover Clustering

[18] Greedy Set Cover Algorithm

[19] Agglomerative Clustering

[20] Default Extractor

[21] Boilerpipe library

[22] Shapiro-Wilk test

[23] Wilcoxon signed rank test

خوش آمدید!

| | | بازتاب (0)
خواندن این مطلب به این معنی است که مراحل ثبت نام با موفقیت به پایان رسیده و شما می توانید شروع به کار با وبلاگ نمائید

موضوعات