دانلود ترجمه مقاله یافتن خوشه هایی با اندازه ها، شکل ها و چگالی های مختلف در داده های نویزدار و با ابعاد بالا (سال 2003)

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

Finding Clusters of Different Sizes, Shapes, and Densities in Noisy, High Dimensional Data

چکیده
1- مقدمه
2- یک تعریف بهتر از شباهت
3- یک تعریف بهتر از چگالی
4- یک الگوریتم خوشه بندی نزدیک ترین همسایه مشترک
5- مطالعات تجربی
6- تحلیل پیچیدگی
7- نتیجه گیری و کار آینده
منابع

چکیده
مساله یافتن خوشه ها در داده ها هنگامیکه خوشه ها با اندازه، شکل و چگالی های مختلف وجود دارند و هنگامیکه داده ها شامل میزان زیادی از داده های آشفته و پرت هستند چالش برانگیز می باشد. بسیاری از این مشکلات مخصوصا هنگامیکه داده ها با ابعاد بسیار بالا، مانند داده های متنی و سری زمانی وجود دارند، حتی قابل توجه تر می شوند. در این مقاله، ما یک تکنیک خوشه بندی جدید را ارائه می کنیم که این مشکلات را حل می کند. الگوریتم ما درابتدا نزدیکترین همسایه های هر نقطه داده را پیدا می کند و سپس شباهت بین هر جفت از نقاط را برحسب تعداد نزدیکترین همسایه ای که در دو نقطه مشترک هستند مجددا تعریف می کند. با استفاده از این تعریف شباهت، ما داده های آشفته و پرت را حذف می کنیم، نقاط محوری را شناسایی می کنیم و سپس خوشه ها را حول نقاط محوری می سازیم. استفاده از یک تعریف نزدیکترین همسایه مشترک شباهت مشکل چگالی متغیر را حل می کند، درحالیکه استفاده از نقاط مرکزی مشکل مربوط به شکل و اندازه را برطرف می کند. به طور تجربی نشان می دهیم که الگوریتم ما بهتر از روش های سنتی (مانند K-میانگین) در انواع مجموعه داده ها، مانند داده های نفوذ شبکه KDD Cup ’99، داده سری های زمانی علوم زمینی NASA و مجموعه نقاط دوبعدی، عمل می کند. درحالیکه الگوریتم ما می تواند خوشه هایی با چگالی بالا را همانند الگوریتم های خوشه بندی دیگر پیدا کند، می-تواند خوشه هایی را که این روش ها نادیده می گیرند، یعنی خوشه هایی با چگالی پایین و متوسط را نیز پیدا کند، که این خوشه ها مهم هستند چونکه آن ها نواحی نسبتا یکنواخت احاطه شده توسط ناحیه های غیریکنواخت یا با چگالی بالاتر را ارائه می کنند. پیچیدگی زمان اجرای تکنیک ما است چونکه ماتریس شباهت باید ساخته شود. اما، تعدادی از بهینه سازی ها را بحث می کنیم که به الگوریتم کنترل مجموعه داده های بزرگ به طور موثر اجازه می دهند. برای مثال، 100000 سند از مجموعه TREC می توانند در یک ساعت در یک کامپیوتر رومیزی خوشه بندی شوند.

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

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

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