خوشه بندی مبتنی بر چگالی یا غلظت

مقاله‌ای در این زمینه یافتم که در اینجا قرار می‌دهم.

خوشه بندی مبتنی بر چگالی:

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

مقدمه:

خوشه بندی مسئله یافتن مجموعه‌ای از اشیای مشابه درون یک دیتاست است به گونه‌ای که اشیای نامشابه در گروه‌های مجزا باشند یا به عنوان گروه نویز یا داده‌های پرت ملاحظه گردند. در کل خوشه‌بندی به عنوان یک کار یادگیری غیرنظارت دیده می‌شود. با تعیین داده به عنوان مجموعه‌ای از اشیای از یک فضای داده D ⊂ S و تابع عدم شباهت dis : S × S → R ، این کار برای یادگیری یک گروه‌بندی معنادار از داده است که اغلب، دیتاست مجموعه‌ای از نقاط با ارزش واقعی d بعد است، برای مثال D ⊂ S = R می‌باشد، که می‌تواند به عنوان نمونه‌ای آمده از بعضی از غلظت‌ p(x) احتمالی ناشناخته شده، با دی ترسیتد شده به عنوان فاصله اقلیدسی یا دیگر فاصله‌ها باشد. معنای شباهت درون گروهی و عدم شباهت میان گروهی برای خانواده‌های مختلف خوشه‌بندی متفاوت است.

از نقطه نظر رویه‌ای، روش‌های مختلف خوشه‌بندی به دنبال افراز دیتاست به مجموعه‌ای از کا گروه است که مجموع (مربع شده) عدم شباهت جفت‌های همه اشیای خوشه یا مجموع (مربع شده) عدم شباهات همه اشیای خوشه با ملاحظه (w.r.t.) بعضی از خوشه‌های ارائه شده ….

where the sum of (squared) pairwise dissimilarities between all cluster objects or the sum of (squared) dissimilarities of all cluster objects with respect to (w.r.t.) some cluster representative (e.g., the mean value) are minimized and the respective values between different clusters are maximized, given some dissimilarity function dis

این فرضیه‌ها معمولا نتیجه در خوشه‌های کوژ یا شکلی دارند.

از نقطه نظر آمار چنین روش‌هایی همگام با رهیافت پارامتریکی است که که غلظت ناشناخته p(x) از داده به مخلوطی از کا غلظت p(x فرض می‌شود که هر یک با یک گروه از کا گروه در این داده همگام است. …

The pi(x) are assumed to belong to some parametric family (e.g., Gaussian distributions) with unknown parameters.

این پارامترها سپس بر نمونه معین (دیتاست) تخمین زده می‌شوند.

در مقابل خوشه‌بندی مبتنی بر غلظت رهیافت غیر پارامتریک است که خوشه‌ها در آن به عنوان نواحی پر غلظت از p(x در نظر گرفته می‌شوند.

روش‌های مبتنی بر غلظت نیاز به تعداد خوشه‌ها به عنوان پارامترهای ورودی ندارد. خوشه‌بندی مبتنی بر غلظت نیازی به تعداد خوشه‌ها به عنوان پارامترهای وردی ندارد، و همین‌طور فرض‌های مرتبط با غلظت p(x) یا واریانسی که ممکن است در این خوش‌ها در دیتاست  وجود داشته باشد انجام نمی‌دهد.

As a consequence, density-based clus-
ters are not necessarily groups of points with a low
pairwise within-cluster dissimilarity as measured by a
dissimilarity function
dis
and, thus, do not necessar-
ily have a convex shape but can be arbitrarily shaped
in the data space.

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

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

انتخاب نواحی بالای یک گرایش مطمئن مرتبط با خوشه‌بندی مبتنی بر غلظت یک سطح غلظت بر طبق انتخاب شده فراهم می‌آورد. شکل ۲ ب

دیگر انگیزه طبیعی از آن اغلب در وحش‌شناسی یافت می‌شود، چون کار من زیاد روی این قسمت نیست، این‌ها را با زبان اصلی می‌ذارم:

Species diverge, as is commonly assumed, from some common ancestor in different directions as
adaptations to different forces of selection. Hence, zoologists define families of different species, where the members probably exhibit not an extraordinary high pairwise similarity to all other members but exhibit a certain similarity to at least some other member of the family.

همچنین

Also, geometrically, evolutionary development can be seen as a tree of paths through the space spanned by the variables describing the pheno- types of organisms.

Clusters of such geometry بسیار مرتبط با شبیه سازی مشکل توصیف شده به وسیله رهیافت خوشه‌بندی مبتنی بر غلظت هستند.

مثالی از هندسه تغییرات

An example for the geometry of variations can be given based on Fisher’s Iris data set 7 (well known as an example data set in the domain of classification). It comprises four descriptors of the Iris flower, namely length and width of petals and sepals, respectively. These descriptors are collected for individual flowers of three different species. While the original purpose of these data was to study linear separability, it can serve here to illustrate the typical properties of natural (biological) clusters.  The scatter plot given in Figure 3 shows that the occurring natural clusters are typically not spherical in shape because the extreme individuals within each species are not as similar to each other as they are perhaps to some instance of another species, yet there can be found a chain of similar individuals more or less connecting the individuals within each species. (For another well known example with discussion, see Figure 4 in Ref 8.)

انگیزه‌های آماری خوشه‌بندی مبتنی بر غلظت

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

ادامه در مقاله اصلی

حاشیه: خوب صبر کن، آری من با این الگوریتم را کامل یاد بگیرم پس ادامه می‌دم

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

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

۱: انتخاب آستانه فاصله، آستانه فرکانس، آر و کا

۲: محاسبه شباهت مثلی همه نقاط

۳: ارزیابی فرکانس کای آی، این فرکانس تعداد نقاط قرار گرفته شده در فاصله آر از نقطه ایکس آی را نشان می‌دهد، از این رو این یک سنجه غلظت است.

۴:‌ حذف همه نویزها یعنی نقاط بدون غلظت جایی که کای آی کوچتر از کا است.

۵:‌ خوشه‌بندی نقاط باقی مانده به وسیله رهیافت تک لینکه

۶: سرانجام، نقاط نویز بر اساس معیارهایی می‌توانند به یک خوشه‌ مناسب اختصاص داده شوند.

 «بعضی از معیارها» به عنوان یک ابهام بین‌المللی باقی ماندند. ویچارت مثالی برای شامل کردن نقاط نویز در نزدیکترین خوشه به آنها را ارائه داد. این مطمینا یک راه حل الهامی است، دیگر راه حل‌ها نیز ممکن است محتمل باشند برای مثال تعین نکردن خوشه برای داده‌های نویز. بعدها می‌توان قابل پذیرش باشد که این خوشه‌ها داری غلظت معینی هستند.

یک خوشه‌بندی مبتنی بر غلظت رسمی‌تری توسط هاریتگان نشان داده شد. تعیین غلظت پی در نقطه ایکس یعنی پی ایکس، آستانه غلظت گاما، و لینک‌های اختصاص داده شده برای بعضی از جفت‌های اشیا، یک density-contour cluster در سطح گاما به عنوان maximally connected set of points xi همچنان که پی ایکس آی بزرگتر از گاما باشد. لینک‌های بین نقاط می‌تواند به طور اختصاصی برای تابع فاصله دیس استفاده شود. برای مثال دو نقطه متصل به یکدیگر هستند اگر فاصله میان آنها بیشتر مقدار آستا آر نباشد.

هر دو روش الهام گرفته از شباهت میان آنچه خوشه‌ها را تشکیل می دهد است. فرضیه پایه این الهام این است که دیتاست دی زیر مجموعه آر  (مجموعه آر با دی بعد) یک نمونه از غلظت احتمالی ناشناخته شده پی ایکس است، و خوشه‌ها نواحی پر غلظت، غلظت پی ایکس هستند. یافتن نواحی غلیظ در پی ایکس معمولا به دو ماده اولیه نیاز دارد. اولین ماده تخمین غلظت محل در هر نقطه است (که معمولا از میزان نزدیکی یا دوری به هسته استفاده می‌شود، و دیگری نشانه‌ای از روابط میان اشیا است (معمولا نقاط مرتبط با یکدیگر هستند، اگر در فاصله اکسپلون از هم قرار داشته باشند). خوشه‌ها به عنوان مجموعه ماکسیمال از اشیا ساخته می‌شوند که مستقیما یا متعددا مرتبط با اشیایی هستند که غلظت آنها بیشتر از مقدار آستانه گاما است. مجموعه {x|p(x)>λ} از همه اشیای با غلظت بالا سطح غلظت مجموعه پی در سطح گاما صدا زده می‌شود. اشیایی که در این خوشه‌ها جای ندارند، نویز صدا زده می‌شوند.

انواع متفاوتی از نمونه‌های مبتنی بر غلظت موجود است که از جنبه‌های زیر با هم متفاوت هستند:

  • چطور باید غلظت پی ایکس تعیین شود؟
  • چطور نشانه مرتبط تعریف شده است؟
  • چطور الگوریتمی برای یافتن مولفه‌های مرتبظ شده از گراف تحریکی پیاده‌سازی شده است، و چطور این الگوریتم به وسیله ساختارهای داده مناسب برای به دست آوردن مقیاس حتی برای دیتابیس‌های بزرگ پشتیبانی شده است؟

نکته:

In addition, for some methods a cluster consists only of objects whose density exceeds the threshold λ, whereas other methods also include objects with lower density into a cluster if they are connected to at least one object with density above the threshold λ.

 کارایی الگوریتم مبتنی بر غلظت:

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

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

….

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

کشف خوشه‌ها:

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

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

خوب فکر می‌کنم الان کافی باشه

 

دیدگاه‌تان را بنویسید: