پیشرفت های اخیر در زمینه خوشه بندی داکیومنت Recent Developments in Document Clustering

1) مقدمه

خوشه بندی داکیومنت و یا متن زیر مجموعه ای از حوزه بزرگتر از خوشه بندی داده ها است که مفاهیم را از زمینه های بازیابی اطلاعات (IR)، پردازش زبان طبیعی (NLP)، و یادگیری ماشین (ML) قرض می گیرد. خوشه بندی اسناد از این پس به سادگی به عنوان خوشه بندی معرفی شده است.

فرایند خوشه بندی با هدف کشف گروه بندی های طبیعی است و بنابراین یک نمای کلی از رده ها(موضوعات) در مجموعه اسناد ارائه می دهد. در زمینه هوش مصنوعی،به عنوان یادگیری ماشین بدون سرپرست شناخته شده است. خوشه بندی را نباید با طبقه بندی اشتباه گرفت. در مسئله طبقه بندی شماره رده و ویژگی های آن بصورت قیاسی شناخته شده است و اسناد در این رده اختصاص داده است. در مقابل، در مسئله خوشه بندی همانطور که در شماره1 است ویژگی ها و یا عضویت (ترکیب) هر رده از پیش شناخته شده است. این تفاوت در شکل 1 نشان داده شده است. طبقه بندی مثالی از یادگیری ماشینی نظارت شده است.

شکل1: در تصویر (الف) سه رده شناخته شده است، و اسناد مرتبط با هر رده اختصاص داده شده است. در قسمت(ب) تعداد نامعلومی گروه بندی باید از داده های مبتنی بر شباهت معیار استنباط شود. (در این مورد، مسافت)

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

چالش اول درمسئله خوشه بندی مشخص کردن این است که کدام ویژگی ها اسناد تبعیض‌ امیز درنظر گرفته شده است. به عبارت دیگر، ما به دنبال یک مدل داکیومنت هستیم. اکثریت روش های خوشه بندی موجود نشان می دهد که هر داکیومنت به عنوان یک بردار انتخاب شده است. در نتیجه کاهش داکیومنت به منظور نشان دادن یک بازنمایی مناسب برای روش های خوشه بندی داده ها ملزم است. این مدل در فصل 3 بررسی می شود.

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

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

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

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

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

در نهایت، خواص الگوریتم های مورد بحث در این زمینه در بخش 9 مورد بحث و بررسی قرار گرفته است. که شامل قابلیت‌ اجراء‌ خوشه بندی query(جستجو) و خوشه بندی های بزرگتر و مجموعه های ایستا می شود.

2) خوشه بندی خوب، بد، زشت

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

دو مفهوم ذاتی جرا عملکرد(دقت) دقت و فراخوانی است. در زمینه بازیابى اطلاعات، فراخوانی به صورت نسبت داکیومنت مرتبط تعریف می شود که با نمام اسناد مرتبط موجود بازیابی می شود. در حالی که دقت نسبت بازیابی و سند مرتبط از تمام اسناد بازیابی است.زیرا فراخوان بوسیله بازیابی تمام اسناد در هر جستجو امری بدیهی است، f-measure هم هردو دقت و فراخوان را باهم توامان دارد. بجای فراخوان L و بجای دقتP استفاده می کنیم در نتیجه معادله کلیF-MEASURE بصورت زیر تعریف می شود:

1) (نیاز به دانلود ترجمه)

دقت و فراخوان عموما وزن برابر ( F1 ) دارند، اما متغیرهای موجود نشان می دهد وزنشان متفاوت است. برای مثال، دقت دوبرابر فراخوان است و یا برعکس( به ترتیب F0:5, F2است). برای بسط و توسعه این به خشه بندی، موجودیت مجموعه رده های مرجع را درنظر می گیریم و خوشه های مووجود بعنوان اسناد بازیابی شده از این رده ها عمل می کند.( خروجی الگوریتم خوشه بندی). تطبیق رده Iدر خوشهJ:

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

در این معادله n تعداد کل اسناد است . درواقع، تطابق یک به یک بین رده ها و خوشه ها بر اساس شباهت میان آنها انجام می شود.

در حالیکه f-measure کیفیت کلی خوشه بندی را در حالت بازیابی مدنظر قرار دارد، ترکیبی از خوشه خود نمی داند. دو اقدام اضافی یعنی اندازه گیری درصد خلوص خوشه و آنتروپی انجام می شود. اندازه گیری درصد خلوص درصد دامنه اعضا رده در خوشه داده شده را بررسی می کند.(هرچه بزرگتر بهتر است)، در حالی که آنتروپی به نظر می رسد در توزیع اسناد از هر رده مرجع در درون خوشه (هرچه کوچکترباشد بهتر است). این معادل بصورت زیر نوشته می شود:

3) (نیاز به دانلود ترجمه)

4) (نیاز به دانلود ترجمه)

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

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

5) (نیاز به دانلود ترجمه)

محدوده NMI [0، 1] است، که در آن ارزش هرموردی هماهنگی کامل بین خوشه و رده مرجع دارد و با آن مشخص می شود. دوباره تحریک NMI دقت خوشه بندی اندازه گیری می شود تا عدم تطابق میان تعداد خوشه و تعداد رده مرجع مشخص شود. تعداد کارآمد و بهینه اگر بصورت اکثریت نباشد در حوزه خوشه بندی فرض کنید داده های دریافتی خوشه k را و بنابراین در این مورد اندازه گیری مرسوم استفاده می شود و کاربرد دارد. نگرشی متفاوت در زمینه کیفیت الگوریتم خوشه بندی وجود دارد که بررسی ثبات پارتیشن های تولیدی در طول اجراست. روش بصری اندازه گیری ثبات بررسی میانگین عملکرد است. در زمینه اطلاعات مشترک نتایج زیر برای برسی میانگین اطلاعت مشترک ثبت شده استفاده می شود. مجموعه خوشه rاست و خوشه بندی مجزا است در نتیجه ANMI بصورت زیر تعریف می شود:

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

در حالی که ماتریس سردرگمی بطور مکرر در زمینه خوشه بندی اتفاق نمی افتد. همانطور که در بالا گفته شد در یک توزیع مختصر روی می دهد. ماتریس سردرگمی 4 ابزار تجسم است که خلاصه طبقه بندی های اشتباه (خطا) ساخته شده توسط سیستم فراهم می کند.

جدول 1: ماتریس سردرگمی برای رده A(4عنصر)،B(4عنصر)،C(8عنصر)

C B A

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

0 2 2 B

8 0 0 C

در شکل 1، سه رده از اشیاء را میبینیم(برای مثال داکیومنت). این تفسیر به شرح زیر است:

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

از سوی دیگر، نیمی از رده A در رده Bاشتباه طبقه بندی شده اند و برعکس. معیارهای توصیف شده برای خوشه های از هم متلاشی شده توضیح داده می شود. روش معمول برای ارزیابی خروجی الگوریتم خوشه بندی فازی تولید خوشه ی سخت از خروجی فازی است. ( خوشه های سخت نامیده می شود) که بواسطه اعضاء داکیومنت آستانه سازی شده و به اجرا می رسد. و این داکیومنت با ارزش آستانه داخل خوشه در نظر گرفته می شود و تاجاییکه داکیومنت برای دو خوشه باشد در هر دو ظاهر می شود.

3) مدل فضای برداری

مدل برداری [40] در اصل برای نمایه سازی های بطور خودکار طراحی شده است. بر اساس مدل فضای برداری، مجموعه داکیومنت n با m بصورت ماتریس داکیومنت m*n نشان داده می شود(که هر داکیومنت یک بردار از ابعاد m است). اگر چه این مدل به خودی خود ثابت شده است، اساس بحث های بعدی هم هست و درحال حاضر علاقه به بررسی در این حوزه وجود دارد. بنابراین، شرح مختصری از این مدل به شرح زیر است:

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

3.1 پیش پردازش

پیش پردازش شامل مراحلی است که بعنوان ورودی یک داکیومنت متنی و خروجی یک مجموعه نشانه ها در نظر گرفته می شود ودر مدل برداری گنجانده شده است. این مراحل عمدتا شامل موارد زیر است:

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

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

جستجو ریشه کلمه : فرآیند کاهش واژه به پایه و بنیان آن یا ریشه اصلی کلمه. برای مثال لغت مرتبط، ارتباط، ارتباطات همه از ریشه ارتباط داشتن هستند. الگوریتم پورتر [37] عملا استاندارد الگوریتم ریشه یابی است.

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

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

3.2مثال

برای نشان دادن این فرایند، در نظر گرفتن چند جمله ابتداعی بصورت انتزاعی لازم است [ 6 ] :

خوشه بندی داکیومنت به عنوان یک ابزار بازیابی اطلاعات نیست. به دو دسته کلی تقسیم می شود: اول، خوشه بندی که برای موارد بزرگ و بسیار آهسته است( اغلب با اجرا درجه دوم در تعدادی اسناد). و دوم، خوشه بندی هایی که بطور موثر بازیابی ندارند. ما این مشکلات را بررسی کردیم و زمانی با این مسائل مواجه شدیم که از خوشه بندی در زمینه بهبود روش جستجو معمولی استفاده نمودیم.

بعد اجرا مراحلی که در بالا ذکر شد به نتایج زیر رسیدیم:

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

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

4 توسعه k-means

از لحاظ تاریخی، الگوریتم های سلسله مراتبی اغلب روش خوشه بندی غالب است. همانطور که بسیاری از تحولات اخیر در این زمینه صورت گرفته است. بعدا بطور خلاصه بیان می شود.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

از سوی دیگر ، الگوریتم سلسله مراتبی مقیاسی ندارد. (در هر مرحله ادغام، شباهت ها باید مقایسه شود ) ، و بنابراین کابردهای همزمان و یا مجموعه های بزرگ مناسب نیست. علاوه بر این، به طور کلی الگوریتم پارتیشن بندیمورد قبول است و از الگوریتم سلسله مراتبی بهتر عمل می کند. [43]. در مواردی که یک سلسله مراتب مورد نظر است، نتایج فوق العاده با استفاده از روش بارتیشنال در هر سطح سلسله مراتب بدست آمد. [56].

روش پارتیشنال نمونه ای کللاسیک از روش k-means است که با انتخاب k داکیومنت اولیه از خوشه شروع می شود و داکیومنت برای خوشه بندی تخصیص داده می شود. در حالی که به روز رسانی مراکز جرم این خوشه (خوشه بندی بالا به پایین ). داده های متنی جهت دار است و به منظور به روز رسانی مرکز ثقل این خوشه ها تخصیص یافته است. وبرای بردار داکیومنت معمول است. و برای کسینوس شباهت های اندازه گیری به جای مسافت استفاده می شود. نتایج الگوریتم k-meansکروی نامیده می شود.

اگر چه محبوب است، در بخشی به دلیل سهولت انجام کار k-means دارای مشکلاتی هم هست: مستعد و مناسب برای نقاط دورافتاده و سر و صدا است. ، که n در آن تعداد اسناد در مجموعه استk تعداد خوشه های مورد نظر و l تعداد تکرار است.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

به نام (oskmns) خلاصه می شود در واقع k-meansکروی(skmns) توسعه یافته است که ازتکنیک های یادگیری رقابتی برای سرعت بخشیدن به خوشه بندی حالی که به دقت مشابه و یا بهتر دست یابی پیدا کند استفاده می نماید. این الگوریتم خوشه هایی دقیق تولید می کند. (0:05 NMI) بعنوان CLUTO یک الگوریتم خوشه بندی مبتنی بر گراف(به بخش 6 مراجعه کنید).

در یک طرح یادگیری رقابتی آنلاین، اسناد به طور مداوم جریان دارند. در مقابل با این الگوریتم دسته ای که در تمام مجموعه داده ها در دسته مجزا اجرا می شود. در حالیکه داکی.منت به خوشه بندی اضافه می شود سلولها یا همان خوشه ها با هم مقایسه می شوند. این میزان یادگیری بصورت زیر توصیف می شود.برای مثال یک بردار سند در مجموعه D را تصور کنید. سپس دو الگوریتم oskmns و skmns را به منظور به حداقل رساندن اهداف زیر خلاصه می کنیم:

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

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

8) (نیاز به دانلود ترجمه)

میزان یادگیری و چگونگی کنترل خوشه ها و تنظیم برای ورودی بعدی بهترین عملکردش بر اساس معادله زیر است

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

که در این معادله N تعداد اسناد، M تعداد تکرارها دسته ای و nfمیزان یادگیری نهایی مطلوب است. و برابر 0.01 است.

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

شکل 2: (الف) به شکل غیر محدب را نشان می دهد که kmeans سنتی خوشه بندی مشکل دارد. در شکل(ب)، kmeans هسته یا کرنال با موفقیت دو خوشه را در نتیجه طرح ریزی بردار سند به فضای بالاتر بعدی جدا می کند.

4.2 k-meansهسته ای یا کرنال

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

10) (نیاز به دانلود ترجمه)

ساختار کرنل k بصورتn*n است که kij برابر است با k(di,dj). تعمیم این فرمول برای هر سند وزن درنظر گرفته می شود. (w(d در این مورد، ماتریس وابسته k بعنوان وزن لبه گراف درنظر گرفته می شود که روش طیفی برای دریافت برش استفاده می شود.(برای مثال الگوریتم برش چندجانبه)

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

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

مشکل دیگر با روش k-meansکرنل این است که تسلط قطری دارد. بطور خلاصه، این مشکل زمانی رخ می دهد که اشیاء(برای مثال اسناد) بسیار مشابه درنظر گرفته شوند و باتوجه به خودشان با شباهتشان با دیگر اشیاء مقایسه شود. درنتیجه شباهت ماتریس ارزش بسیار زیادی مقایسه مورب با دیگر ارزشها دارد. مشاهده شده است که این مورد فشای راه حل را تا یافتن حالت اولیه فراتر از آن محدود می سازد. که گفته می شود مطالعات تجربی حاکی از این است که k-meansکرنل حتی الگوریتم چندمرحله ای را هم به اجرا در می آورد. برای مثال بخش 7.3.

روش کرنل بدون نظارت به منظور تولید خوشه هایی متداخل بکار برده می شود. برای مثال k-meansفازی با توسعه روش کار k-meansکرنل ایجاد شده است.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

5) الگوریتم های زایشی

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

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

5.1 مدل گاوسین

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

در شکل 5.1 نشان داده شده است.

تطبیق یک نسخه اصلاح شده از نماد و مدل شامل تعداد مشخص خوشه ها با خوشه های علامت دار (نیاز به دانلود ترجمه) است. فرض کنید m*n مدل برداری از مجموعه D مشتق می شود. هر خوشه توزیع گاسین در بعد M است با مرکزیت و ماتریس . بنابراین هر خوشه (نیاز به دانلود ترجمه) با بردار سند بر اساس معادله زیر برابر است:

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

بر اساس این مذل احتمال کلی به صورت زیر نشان داده می شود.

12 )

5.2 حداکثر انتظار

الگوریتم این مورد فرایند تکرار کافی برای محاسبه حداکثر احتمال (ML) راه حل برای یک مدل است. شامل دو مرحله است: مرحله انتظار و یا e-step که ، داده های از دست رفته. با توجه به داده های مشاهده شده ( جمع آوری اسناد ) و برآورد فعلی از مدل ( خوشه ) تخمین زده می شود. مرحله دیگر m-stepیا مرحله به حداکثر رساندن ساختار احتمالی در فرضه به حداکثر رسانده می شود تا داده های از دست رفته شناسایی شوند. برای بحث بیشتر به [ 4 ] مراجعه کنید.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

13) (نیاز به دانلود ترجمه)

14) (نیاز به دانلود ترجمه)

و مرحله m که پارامترهای مدل (نیاز به دانلود ترجمه) را آپدیت می کند به منظور به حداکثر رساندن احتمالات داده شده در احتمالات محاسبه شده در مرحله e

15) (نیاز به دانلود ترجمه)

16) (نیاز به دانلود ترجمه)

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

شکل4 الگوریتم EM بعد از n بار تکرار را نشان می دهد. مشاهدات دقیق الگوریتم در شرایط تخمین پایین: در هر تکرار، یک گروه پایین تر محاسبه می شود و خوشه میزان صعود و نزدیک به (ناشناخته) توزیع درست را تخمین می زند.

همانطور که در هر طرح احتمالی بیشینه، داشتن پارامترهای آزاد بیش از حد با داده های ناکافی منجر به تداخل می شود. در [27]، این مشکل با استفاده از تجزیه مقدار منحصر به فرد بردار فضای لغات و اسناد کاهش می یابد. آنها سپس بیست تا از ابعادی که بیشترین مفدار را دارد انتخاب کرده بر می دارند تا فضای کاهشی برای انجام خوشه بندی محیا شود.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

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

این اصلاحات که می تواند به عنوان شواهدی بر فرضیات توزیع داده ها در نظر گرفته می شود(گاسین) کاملا غلط است.و مدل هلی دیگر مورد نیاز است. برای مثال، بجای الگوریتم em از مدل میزس فیشر استفاده می شود که در فصل 5.3 شرح داده می شود.

مشکل الگوریتم em این است که پیچیدگی در زمان اجرا در تعداد خوشه k و یا O(k2n) بصورت درجه دو است.( احتمال برای هر خوشه دوباره محاسبه می شود). مشکل عملی دیگر بی ثباتی و همچنین مقدار دهی اولیه تصادفی(k-meansهم همسن مشکل را داشت).است. بررسی مفصل تر در زمینه em از جمله تجزیه و تحلیل زمان اجرا بصورت کامل است که در مثال ذکر می شود.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

(vMF) توزیع آنالوگ همان توزیع گاسین برای داده های جهت دار است. الگوریتم kmeans کروی (بخش 4) بطور موثر در توزیع Vmf مشان داده می شود. شواهد تجربی نشان می دهد که این مدل توزیع داده های متنی را بهتر از سایر مدل ها از جمله مدل های چندگانه و یا مدل برنویلی تخمین می زند.

سند مجموعه است ، خوشه، و درنتیجه احتمال اینکه d متعلق به (نیاز به دانلود ترجمه) بصورت زیر تعریف می شود:

17) (نیاز به دانلود ترجمه)

در اینجا Z نشان دهنده تابع بسل (یک عامل عادی) Bessel. است. این ساختار و تابع تخمین میزند مشکل پارامتر در ماتریس توزیع vMFاست و بنابراین به جای یک طرح بازپخت قطعی می تواند مورد استفاده قرار گیرد. به عبارت ساده، این مقدار برای شروع با مقدار کم (نیاز به دانلود ترجمه) شروع می کند و کم کم آن را افزایش می دهد.

متناوبا، اشتقاق‌ em مدل vMF را به عنوان توزیع زمینه ای استفاده می کند. که در آن (نیاز به دانلود ترجمه) در مرحله m براورد می شود. براساس این مدل، الگوریتم em نشان داده شده است است که به طور کارآمدی kmeans کروی درحال اجراست. در ادامه واقیاتی در مورد مقدار kmeans کروی حالت خاصی از الگوریتمem استفاده شده در مدل vMF بیان می شود. که در آن بجای براورد (نیاز به دانلود ترجمه) خوشه ها ثابت فرض می شود.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

نمونه محدودتر الگوریتم em این مدل است. این الگوریتم بین مدل مرحله دوباره برآورد نمونه مرحله دوباره تعیین قرار دارد. در نتیجه O(kn) پیچیدگی زمان اجرا دارد. (em هم این مشکل را دارد).

با وجود این خواص سودمند، الگوریتم اشتباهات زیادتری نسبت به الگوریتم em ندارد. .تمایز مهم بین الگوریتم های زایشی و نرم این است که مدل بطور جزئی هر سند را به هر خوشه تعمیم نم دهد و مبتنی بر احتمال بعدی نیست.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

یک ماتریس یک نمایش طبیعی برای اطلاعات مجاورت بین راس است، و در نتیجه بردار ادل به عنوان یک گراف تفسیر شده است. خوشه بندی طیفی شامل یافتن برش ار این گراف است که منجر به تولید خوشه های خوب می شود. برای موارد خاص که یک گراف دو قسمتی است در شکل 5 نشان داده شده است.

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

یک گراف معمول مبتنی بر خوشه بندی اسناد CLUTO8 است. که در حالت منبع باز و آزاد برای شارژ قرار دارد و از طرح خشن و غیر خشن استفاده می کند.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

یک مورد خاص از خوشه بندی مبتنی بر گراف، در پژوهش های اخیر بیشتر مورد توجه واقع شده است گراف دو قسمتی از ستون و ردیف داده های ورودی ایجاد می کند. فرض اساسی در فرای این خوشه بندی همزمان این است که لغات که باهم رخ می دهند مفاهیم مشابه دارند. و و گروهی از اسناد مشابه که مهم باشند را در برنمی گیرد اما همچنین گروه لغات مشابه دارد. این مطالب در تصویر 5 نشان داده شده است.

برش در کاهش در این گراف دو قسمتیخوشه بندی کوکلاستر تولید می کند یعنی لغات در ردیف و اسناد در ستون. نشان داده شده است که بهینه سازی این برش مشکل معادل برای محاسبه مقدار منفرد تجزیه ماتریس اولیه است. میزان منفرد تجزیه اغلب بعنوان تحلیل محتوا اصلی ارجاع داده می شود و تکنیک کاهشی جبر خطی است. در بخش 7 توضی داده می شود.

6.1 خوشه بندی تقسیم /ادغام

مفهوم هدایت اندازه گیری می کند که آیا سختی وجود دارد یا نه و این به عنوان پدیده ای برای دریافت برش بهینه در گراف پیشنهاد می شود. بهینه سازی مانن برش NP پیشنهاد می شود.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

مرحله دوم یافتن خوشه بندی درختی از خروجی فاز تقسیم شروع می شود.انواع مختلف توابع و ساختارها برای مثال k-means در این فاز استفاده می شود. با این حال، خوشه های وابسته مزایایی دارد مثل اینکه به شناخت قبلی تعداد خوشه ها بستگی ندارد.این یک مزیت کارامد در مورد برنامه های کاربردی پس از بازیابی است مشل زمانی که در صفحات وب موتور جستجو در حال گردش است. که تعداد صحیحی از خوشه ها شناخته شده نیست.

شکل 6 : تقسیم و ادغام : یک سلسله مراتب است که با برش تکرار محاسبه می شود و درخت فرعی با استفاده از خوشه بندی وابسته گروه بندی می شود.

6.2 خوشه بندی فازی

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

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

مانند الگوریتم k-means فازی کوکلاسترینگ ساختار فازی را بهینه می بخشد. تفاوت اصلی این است که ماهیت تراکم در این است که الگوریتم برای ک.پوکلاستر واژه و اسناد بیشتر از خوشه بندی اسناد بتنهایی بهینه شده است.

معادله آن بصورت زیر نوشته می شود:

18) (نیاز به دانلود ترجمه)

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

19) (نیاز به دانلود ترجمه)

20) (نیاز به دانلود ترجمه)

ارزیابی تجربی نشان داده است که الگوریتم های کوکلاسترینگ فازی k-means فازی متفاوت مدرنتری است [29] (که با استفاده از شباهت کسینوسی به جای فاصله ی اقلیدسی عمل می کند) در مجموعه داده ها خاص [46]. در حالی که اجرا این روش بهتر از دیگر روش هاست. مزیت دیگر این روش اعضا واژه به طور طبیعی از خوشه بندی منتج می شود. درحالیکه وازه بطور همزمان در داکیومنت خوشه بندی می شود.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

تفاوت میان الگوریتم کودوک فازی در بخش 7.3 اشاره شد.هر دو اعضا اسناد و واژه در مدل فازی تولید می شود. با این حال درحالیکه کودوک فازی تراکم را در فضای ویژگی اصلی به اجرا می گذارد بعدا روش PCAاجرا می شود. این روش بعدا توضیح داده می شود. و در فضای کاهشی تجزیه ماتریس کار می کند.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.