توضیحات
عنوان فارسی: یادگیری K در مفهوم K
عنوان انگلیسی مقاله ترجمه شده:
Learning the k in k-means
یادگیری K در مفهومK
چکیده
هنگامی که در خوشه بندی یک مجموعه داده، تعداد کافی از خوشه های مورد استفاده در اغلب موارد واضح نیست، مسئله ی انتخاب عدد k به طور خودکار الگوریتمی سخت است. در این مقاله یک الگوریتم بهبود یافته برای یادگیری K ارائه می شود.الگوریتم G-means بر پایه یک آزمون آماری برای فرضیه ها که زیر مجموعه ای از داده ها یک توزیع گاوسی را دنبال می کنند بنا گردیده است.الگوریتم G-means ، الگوریتم k-means را با افزایش k به صورت سلسله مراتبی اجرا می کند تا تست فرضیه ی داده های اختصاص داده شده به هر مرکز k-means یک توزیع گاوسی هست را بپذیرد . دو مزیت کلیدی این است که آزمون فرضیه کوواریانس داده ها را محدود نمی کند و ماتریس کامل کوواریانس را محاسبه نمی کند. علاوه بر این، G-means تنها نیاز به یک پارامتر بصری، استاندارد که همان سطح آماری آلفا می باشد، دارد.نتایج حاصل از آزمایشات نشان می دهد که الگوریتم به خوبی کار می کند و بهتر از روش اخیر براساس مجاز BIC برای پیچیدگی مدل است. در این آزمایش ها، ما نشان می دهیم که BICرا به عنوان یک عملکرد به ثمر رسانده بی اثر است، زیرا پیچیدگی مدل به اندازه کافی قابل جبران نیست.
1 معرفی و کارهای انجام شده مرتبط
الگوریتم خوشه بندی ابزار مفید برای داده کاوی، فشرده سازی، تخمین چگالی احتمال و بسیاری از وظایف مهم دیگر است. با این حال، بیشتر الگوریتم های خوشه ای نیاز به کاربر برای مشخص کردن تعداد خوشه ها (به نام k) و همیشه مشخص نیست که بهترین مقدار برای k چیست. شکل 1 نمونه هایی را نشان می دهد که k نامناسب انتخاب شده است. انتخاب k اغلب یک تصمیم ad hoc بر اساس دانش قبلی، فرضیه ها و تجربه عملی است. هنگامیکه داده ها دارای ابعاد بسیاری هستند، انتخاب k بسیار دشوارتر می شود، حتی وقتی لوستر ها به خوبی جدا شده اند.
الگوریتم های خوشه بندی مبتنی بر مرکز (به ویژه k-means و maximization انتظارات گاوس) معمولا فرض می کنند که هر خوشه به یک توزیع غیرمستقیم مانند گاوسی پیوسته است. با استفاده از این روش، تنها یک مرکز باید برای مدل سازی هر زیر مجموعه داده ها که یک توزیع غیرمجاز را دنبال کند. اگر چندین مرکز برای توصیف داده های کشیده شده از یک حالت استفاده شوند، مراکز توضیح نیازی به پیچیدگی داده ها نیستند و در واقع مراکز متعدد حقیقت را در مورد زیرمجموعه کمتر از یک مرکز ضبط می کنند.
در این مقاله یک الگوریتم ساده به نام G-mean ارائه می کنیم که مناسب را پیدا می کند k با استفاده از یک آزمون آماری برای تصمیم گیری در مورد اینکه آیا یک مرکز KS را به دو مرکز تقسیم می کند.
نمونه هایی را توصیف می کنیم و نتایج تجربی را نشان می دهند که الگوریتم جدید موفق است.
شکل 1: دو خوشه بندی که در آن k انتخاب نامناسب بود. تیرهای تاریک k-means هستند، مراکز در سمت چپ، مراکز بیشماری وجود دارد. پنج مورد باید استفاده شود. در سمت راست، بسیاری از مراکز استفاده می شود؛ یک مرکز برای نشان دادن داده ها کافی است به طور کلی، یک مرکز باید برای نشان دادن یک خوشه گاوسی استفاده شود.
این تکنیک برای بسیاری از الگوریتم های خوشه ای غیر از k-means قابل استفاده و قابل استفاده است، اما در اینجا تنها الگوریتم k-means برای سادگی را در نظر می گیریم.
الگوریتم های متعددی پیشنهادی برای تعیین k به طور خودکار پیشنهاد شده است. مثل روش ما، اغلب روش های قبلی، پیچ و مهره های اطراف k-means یا برخی خوشه های دیگر است که الگوریتم برای ثابت k روش های بسته بندی استفاده از قوانین تقسیم و / یا ادغام برای مراکز به افزایش یا کاهش k به عنوان پیشرفت پیشنهاد می شود .
Pelleg و Moore یک چارچوب قانونی برای یادگیری k را پیشنهاد می کنند که آنها آنها را فرا می گیرند means الگوریتم به بررسی بسیاری از مقادیر k و نمرات هر مدل خوشه بندی می پردازد با استفاده از معيار اطلاعات به اصطلاح Bayesian: BIC (C | X) = L (X | C) – p 2 log n که در آن L (X | C) احتمال ورود به مجموعه داده X بر اساس مدل C p = k (d + 1) تعداد پارامترهای مدل C با ابعاد d و k مراکز خوشه ای و n تعداد نقاط در مجموعه داده است. X بدین معنی را انتخاب می کند که مدل با بهترین نمره BIC در داده ها. به غیر از BIC، دیگر توابع امتیاز نیز در دسترس هستند.
Bischof و همکاران از یک چارچوب حداقل طول توصیف (MDL) استفاده کنید، جایی که طول توصیف اندازه گیری این است که چگونه داده ها با مدل مناسب می شوند. الگوریتم آنها با مقدار بزرگ برای k شروع می شود و مراکز را حذف می کند (هرگاه که انتخاب طول توصیف را کاهش دهد، k را کاهش می دهد). بین مراحل کاهش k، آنها از الگوریتم k-means برای بهینه سازی مدل مناسب با داده استفاده می کنند.
با الگوریتم خوشه بندی سلسله مراتبی، دیگر روش ها می توانند برای تعیین بهترین تعداد خوشه ها. یکی از اینها ساخت یک درخت ادغام (“dendrogram”) از داده ها است بر روی متریک فاصله خوشه ای و جستجو برای مناطق درخت است که با احترام پایدار هستند به فاصله های بین و خوشه ای [9، بخش 5.1]. این روش تخمین k بهتر است با دانش دانش خاص و شهود بشری اعمال می شود.
2 الگوریتم گاوسی (G-means)
الگوریتم G-means با تعداد کمی از مراکز K شروع می شود و رشد می کند تعداد مراکز هر تکرار الگوریتم به دو مرکز تقسیم می شود که داده ها از یک توزیع گاوسی به دست نمی آیند. بین هر دور تقسیم، ما در کل مجموعه داده ها و تمام مراکز برای ارزیابی راه حل فعلی، k-means را اجرا می کنیم. ما می توانیم فقط با k = 1 راه اندازی کنیم یا اگر می توانیم برخی از مقادیر قبلی k را بدست آوریم، می توانیم مقدار بزرگتری از k را انتخاب کنیم.
G-means به طور مرتب تصمیمات را بر اساس یک آزمون آماری برای داده های اختصاص داده شده به هر مرکز می گیرد. اگر داده هایی که در حال حاضر به یک مرکز k-means معروف هستند، به عنوان Gaussian نمایش داده می شوند، ما می خواهیم این داده ها را تنها با یک مرکز نشان دهیم. با این حال، اگر داده های مشابه گاوسی را نداشته باشند، ما می خواهیم از چندین مرکز برای مدل سازی داده ها استفاده کنیم. الگوریتم چندین بار k-means را اجرا می کند (زمانیکه k مراکز را پیدا می کند)، بنابراین پیچیدگی زمانی بیشتر از O (k) برابر k-means است.
توجه:
- برای دانلود فایل word کامل ترجمه از گزینه افزودن به سبد خرید بالا استفاده فرمایید.
- لینک دانلود فایل بلافاصله پس از خرید بصورت اتوماتیک برای شما ایمیل می گردد.
به منظور سفارش ترجمه تخصصی مقالات خود بر روی کلید زیر کلیک نمایید.
سفارش ترجمه مقاله
دیدگاهها
هیچ دیدگاهی برای این محصول نوشته نشده است.