مدل مخلوط فرآیند دیریکله

• ژوئن 23، 2014
• واسیلیس ورینیوتس
• . 2 نظر

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

به روز رسانی: چارچوب یادگیری ماشین Datumbox اکنون منبع باز و رایگان است دانلود. برای مشاهده اجرای مدل‌های مخلوط فرآیند دیریکله در جاوا، بسته com.datumbox.framework.machinelearning.clustering را بررسی کنید.

1. تعریف مدل مخلوط فرآیند دیریکله

استفاده از فرآیندهای دیریکله به ما اجازه می دهد که یک مدل مخلوط با اجزای نامتناهی داشته باشیم که می توان حد مدل محدود را برای k تا بی نهایت در نظر گرفت. بیایید فرض کنیم که مدل زیر را داریم:

معادله 1: مدل مخلوط فرآیند دیریکله

جایی که G به صورت تعریف شده است و به عنوان نماد کوتاه برای که یک تابع دلتا است که 1 اگر را می گیرد و 0 در جای دیگر. θ_i پارامترهای خوشه ای هستند که از G نمونه برداری شده اند. توزیع مولد F توسط پارامترهای خوشه ای θ پیکربندی می شود._i و برای تولید x استفاده می شود_i مشاهدات در نهایت می توانیم توزیع چگالی را تعریف کنیم که توزیع مخلوط ما (مخلوط بی نهایت قابل شمارش) با نسبت های اختلاط است و اختلاط اجزاء .

شکل 1: مدل گرافیکی مدل مخلوط فرآیند دیریکله

در بالا می توانیم مدل گرافیکی معادل DPMM را مشاهده کنیم. جی₀ توزیع پایه DP است و معمولاً به‌منظور آسان‌تر کردن محاسبات و استفاده از ویژگی‌های ریاضی جذاب، قبل از توزیع مولد F ما مزدوج انتخاب می‌شود. α فراپارامتر اسکالر فرآیند دیریکله است و بر تعداد خوشه هایی که به دست خواهیم آورد تأثیر می گذارد. هر چه مقدار α بزرگتر باشد، خوشه ها بیشتر می شوند. هرچه α کوچکتر باشد خوشه های کمتری خواهند داشت. باید توجه داشته باشیم که مقدار α بیان می کند قدرت ایمان در جی₀. مقدار بزرگ نشان می دهد که بیشتر نمونه ها متمایز بوده و دارای مقادیر متمرکز بر G هستند₀. G توزیع تصادفی بر روی فضای پارامتر Θ است که از DP نمونه برداری شده و احتمالاتی را به پارامترها اختصاص می دهد. θ_i بردار پارامتری است که از توزیع G ترسیم می شود و شامل پارامترهای خوشه است، توزیع F با θ پارامتر می شود._i و x_i نقطه داده تولید شده توسط Generative Distribution F است.

توجه به این نکته ضروری است که θ_i عناصر فضای پارامتر Θ هستند و خوشه های ما را "پیکربندی" می کنند. آنها همچنین می توانند به عنوان متغیرهای پنهان در x دیده شوند_i که به ما می گوید x از کدام جزء/خوشه است_i از و پارامترهای این مولفه چیست. بنابراین برای هر x_i که مشاهده می کنیم، یک θ رسم می کنیم_i از توزیع G با هر قرعه کشی توزیع بسته به انتخاب های قبلی تغییر می کند. همانطور که در طرح urn Blackwell-MacQueen دیدیم، توزیع G را می توان با انتخاب های آینده ما از θ ادغام کرد._i فقط به G بستگی دارد₀: . تخمین پارامترهای θi از فرمول قبلی همیشه امکان پذیر نیست زیرا بسیاری از پیاده سازی ها (مانند فرآیند رستوران چینی) شامل شمارش از طریق افزایش نمایی k مولفه. بنابراین از روش های محاسباتی تقریبی مانند نمونه گیری گیبس استفاده می شود. در نهایت باید توجه داشته باشیم که با وجود اینکه k خوشه ها بی نهایت هستند، تعداد خوشه های فعال . بنابراین θ_i تکرار می شود و یک اثر خوشه بندی را نشان می دهد.

2. استفاده از فرآیند رستوران چینی برای تعریف مدل مخلوط بی نهایت

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

یک رویکرد جایگزین، استفاده از فرآیند رستوران چینی برای مدل‌سازی متغیرهای پنهان z است_i از تکالیف خوشه ای به این ترتیب به جای استفاده از θ_i برای نشان دادن پارامترهای خوشه و انتساب خوشه، از متغیر پنهان z استفاده می کنیم._i برای نشان دادن شناسه خوشه و سپس از این مقدار برای تخصیص پارامترهای خوشه استفاده کنید. در نتیجه، دیگر نیازی نیست هر بار که مشاهده جدیدی دریافت می‌کنیم، یک θ را نمونه‌برداری کنیم، بلکه در عوض با نمونه‌گیری z، تخصیص خوشه را دریافت می‌کنیم._i از CRP با این طرح، یک θ جدید فقط زمانی نمونه برداری می شود که ما نیاز به ایجاد یک خوشه جدید داشته باشیم. در زیر مدل این رویکرد را ارائه می کنیم:

معادله 2: مدل مخلوط با CRP

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

3. استنتاج مدل مخلوط و نمونه برداری گیبس

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

نمونه برداری گیبس فرو ریخته یک الگوریتم ساده زنجیره مارکوف مونت کارلو (MCMC) است. سریع است و ما را قادر می سازد تا در حین نمونه برداری از متغیر دیگری، برخی از متغیرها را ادغام کنیم. با این وجود، این الگوریتم از ما می خواهد که یک G را انتخاب کنیم₀ که قبل از توزیع مولد F مزدوج است تا بتواند معادلات را به صورت تحلیلی حل کند و بتواند مستقیماً از آن نمونه برداری کند. .

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

• z را مقداردهی اولیه کنید_i تکالیف خوشه ای به صورت تصادفی
• تا همگرایی تکرار کنید
• به طور تصادفی تبر را انتخاب کنید_i
  
• z دیگر را نگه دارید_j برای هر j≠i ثابت شد:
• مقدار جدیدی را به z اختصاص دهید_i با محاسبه "احتمال CRP" که به z بستگی دارد_j و x_j از همه j≠i:

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