مقاله خوشه بندی به وسیله تبدیل تدریجی داده

بخشی از مقاله

-1 مقدمه

خوشهبندی مجموع مجذورهای اقلیدسی، مسئلهی NP سختی است [1] که N نقطه داده و k خوشه را نشان میدهد. هدف به حداقل رساندن خطای مجذور میانگین فاصله نقاط داده از نزدیکترین مرکز ثقل - MSE - است. در شرایطی که k یعنی تعداد خوشهها ثابت است، خوشهبندی مجذورهای اقلیدسی می-تواند بهصورت چندجملهای O - nkd+1 - انجام شود >2] که در آن d تعداد ابعاد را نشان میدهد. این عمل بسیار کند است زیرا kd+1 توان بالایی است، بنابراین الگوریتمهای بهینه زیر مطرح می-شوند. الگوریتم k-means سریع و ساده است [3] و بدترین زمان اجرای آن O - nkd - است .[4] در k-means، مجموعهای از نقاط داده    سعی در تعیین نقاط داده در k مجموعه الگوریتمهای k-means در شرایطی که واگذاریها دچار تغییر نشوند، همگرا میشوند. در عمل الگوریتمهای k-means زمانی که ضابطه جبری بهطور فراوانی تغییر نکند متوقف میشوند: در خوشههای متقارن اجتناب از عدم همگرایی و در سایر پیکربندیها، اجتناب از طولانی شدن بیشازحد زمان همگرایی مفید است. عیب اصلی روش k-means این است که نمیتواند کلیه مسائل و مشکلات خوشهبندی را حل کند. - شکل - 1 در این شکل k-means

با سه آغازگر تصادفی شروع بکار کرده است. دایرههای آبیرنگ نشاندهنده خوشههایی است که بیش از یک مرکز ثقل دارند و پیکانهای آبی نشاندهنده خوشههایی هستند که به بیش از یک مرکز ثقل نیاز دارند. از طریق ساختار خوشه-بندی کلی و رفع مشکلاتش میتوان به مرکز ثقل ابتدایی با موقعیتهای بهینه توسط k-means دستیافت. این مسئله باعث کندتر شدن الگوریتم خوشهبندی یا ایجاد انواع پیچیدهتر k- means میشود [7] k-means++ .[7- 14] شبیه به k-means است اما فرمت پیچیدهتری برای مرکز ثقل ارائه میدهد. مدل پیچیده گاوس 15]و[16 و روشهای [17] cut-based نیز راه-حلهای قابل قبولی ارائه میدهند. در 18]، [20 مطالبی راجع به خوشهبندی تحلیلی، بهینهسازی اجتماع ذرات و درخت پوشای کمینه مبتنی بر الگوریتم تقسیم و ادغام مطرحشدهاند. در این مقاله به روشی کاملا متفاوت با روشهای سنتی به بررسی   نشان داده خواهد شد که تعداد کمی از مراحل تبدیل نیاز مشکل خوشهبندی میپردازیم.    هستند تا به خوشهبندی باکیفیت خوب دست یابند.

-2 الگوریتم k-means*

بهجای اینکه تلاش در جهت حل مسئله تخصیص درست خوشهها از طریق تطبیق مدل خوشهبندی به داده x صورت گیرد، کاری متفاوت صورت میگیرد و داده با ساختار خوشهبندیشدهی بهینه مطابقت مییابد. در ابتدا داده مصنوعی x* را که سایز مشابه n و d بعد دارد بهعنوان داده ورودی ایجاد میکنیم، ازاینرو بردارهای داده به k قسمت تقسیم میشوند که خوشهها را بدون هیچ تغییری جدا میکند. سپس نگاشتی از تناظر یکبهیک که مربوط به داده ورودی است را به داده مصنوعی، نمایش میدهیم .نکته کلیدی این است که در حال حاضر خوشهبندی در اختیارداریم که برای داده مصنوعی مطلوب و بهینه است، اما نه برای داده واقعی. در مرحله بعد تبدیلی معکوس از داده مصنوعی به داده ابتدایی صورت میگیرد که این کار بهوسیله برخی تغییرات تدریجی صورت میگیرد. اگر تغییرات کوچک باشند، بردارهای داده تدریجی به موقعیت ابتداییشان حرکت میکنند که این حرکت بدون شکست ساختار خوشهبندی صورت میگیرد. جزییات الگوریتم شامل شبه دستورالعملهایی است که در بخش 2 ارائهشده است.

مشکلات اصلی این روش، یافتن ساختار مناسبی برای داده مصنوعی است که چطور باید نگاشت را نمایش داد و چطور تبدیلی معکوس را کنترل کرد. در ادامه نشان داده میشود که طرح پیشنهادی بهسادگی کارکرده و بر مشکلات مکانی مربوط به k-means فایق میآید؛ اما نمیتوان اثبات کرد که در هر بار نتیجه مطلوب فراهم شود، بااینوجود با استفاده از آزمایش ها نشان داده میشود که این روش بهطور قابلتوجهی بهتر از k-means++ وk-means تکرارشونده است. درنهایت باید گفت که روش پیشنهادی نوعی k-means است که بهندرت به راهحلی بد منجر میشود، همچنین در آزمایشها الگوریتم پیشنهادی به علت استفاده مکرر از k-means به نام k-means* نامگذاری شده است و در بخشهای زیر، فازهای آن موردبررسی قرار خواهند گرفت، شبه کد 1 را ببینید. البته بهجای استفاده از k-means برای نقاط داده اصلی، مجموعه دادهی مصنوعی دیگری یعنی k خوشهی با واریانس صفر مستقل از هم ایجاد میکنیم

-1-2     

الگوریتم بهوسیله انتخاب ساختار خوشهبندی مصنوعی شروع میشود و سپس نقاط داده را بین آنها بهطور یکسان تقسیم میکند. این کار از طریق تعیین هر نقطه داده در مجموعه داده اصلی x1 به یک نقطه داده متناظر در مجموعه داده جدید x2 انجام میشود - شکل . - 2 هفت ساختار متفاوت برای ارزشدهی آغازی در نظر گرفته می-شود:

·    خط: در این ساختار، خوشهها در طول یک خط مرتبشدهاند. مکانهای k بهعنوان مقدار وسط محدوده در هر بعد تنظیم میشوند بهجز اندازه آخرین بعد که خوشه k بهطور یکنواخت در طول خط توزیع میشود - شکل . - 3 حدود 10 درصد از نقاط نزدیک به مرزها بدون خوشه باقی میمانند.

·    قطر: در این ساختار، k مکان بهطور یکنواخت با قطر محدود پایگاه داده تنظیم میشوند.

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

·    اعداد تصادفی با پارتیشنبندی بهینه: در این ساختار موقعیتها تصادفیاند، اما در این ساختار از پارتیشنهای بهینه جهت نگاشت استفاده میشود، یعنی نقاط داده به نزدیکترین خوشه تخصیص داده میشوند.

·    ارزشدهی آغازی بکار گرفتهشده در :k-means++ در این ساختار مراحل کار صورت زیر است. فرض کنید - D - ، کوتاهترین فاصله نقطه داده به نزدیکترین مرکز ثقلش که قبلا انتخاب کردهایم، است. اولین مرکز ثقل را بهطور تصادفی برای x انتخاب کنید. مرکز ثقل بعدی را بهعنوان نقطه انتخاب کنید، توزیع احتمال وزندار را جاییکه نقطهای با احتمالی متناسب با انتخابشده است بکار ببرید. تا زمانی که کل مراکز ثقل k انتخاب کنیم. درنتیجه، مراکز جدید بهاحتمالزیاد به نواحی که کمبود مراکز ثقل دارند، اضافه میشوند.

·    خط با خوشههای ناهموار: در این ساختار، نقاط بیش از دو برابر بهطور عمدی در نیمی از موقعیت خوشهها قرار می-گیرند.

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

همه نقاط ایجادشده در این مجموعه داده تصادفی هستند اما بهطور یکنواخت در این ساختار قرارگرفتهاند. الگوریتم با تعداد دفعات معینی که بزرگتر از یک بوده و توسط کاربر با مقدار اولیه 20 تنظیم میشود اجرا میشود . - step>1 - در هر مرحله، همه نقاط داده بهطرف موقعیت اصلیشان حرکت میکنند - شکل . - 4 موقعیت نقطه داده iام در داده اصلی و موقعیت آن نقطه در ساختار مصنوعی هست. بعد از هر تبدیل k-means اجراشده و کدهای قبلی را همراه با مجموعه داده توصیفشده بهعنوان ورودی ارائه میکند. بعدازاینکه همه مراحل تکمیل شدند، خروجی c تولید خواهد شد. این احتمال وجود دارد که دونقطه که به خوشه یکسانی در پایگاه داده اصلی تعلق دارند، در خوشههای متفاوتی در مجموعه دادهای که ساختهشده قرار بگیرند. سپس به آهستگی به موقعیتهای نهایی در طول تبدیل معکوس حرکت میکنند.