از ویکیپدیا، دانشنامه آزاد

 

مثالی از دو نمودار بهم پیوسته

در آمار چند متغیره و خوشه بندی داده ها ، تکنیک های خوشه بندی طیفی از طیف ( مقادیر ویژه ) ماتریس شباهت داده ها برای کاهش ابعاد قبل از خوشه بندی در ابعاد کمتر استفاده می کنند. ماتریس شباهت به عنوان ورودی ارائه می شود و شامل ارزیابی کمی شباهت نسبی هر جفت نقطه از مجموعه داده است.

در کاربرد تقسیم بندی تصویر ، خوشه بندی طیفی به عنوان دسته بندی اشیا-مبتنی بر تقسیم بندی شناخته می شود .

 

فهرست

تعاریف [ ویرایش ]

با توجه به مجموعه ای از نقاط داده ای برشمرده شده ، ماتریس شباهت ممکن است به عنوان یک ماتریس متقارن تعریف شودآ، جایی که A_ {ij} \ geq 0 اندازه گیری شباهت بین نقاط داده با شاخص ها را نشان می دهد من و ج. رویکرد کلی به خوشه بندی طیفی است به استفاده از یک استاندارد خوشه روش (بسیاری از روش های مانند وجود دارد، K -means مورد بحث زیر ) در مربوطه بردارهای ویژه یک ماتریس لاپلاس ازآ. روشهای مختلفی برای تعریف لاپلاس وجود دارد که تفسیرهای مختلف ریاضی دارند ، بنابراین خوشه بندی نیز تفسیرهای مختلفی خواهد داشت. بردارهای اختصاصی مربوط به مواردی هستند که با کوچکترین مقادیر ویژه لاپلاس مطابقت دارند بجز کوچکترین مقدار ویژه که دارای مقدار 0 خواهد بود. برای کارایی محاسباتی ، این بردارهای ویژه اغلب به عنوان بردارهای ویژه مربوط به بزرگترین چندین مقادیر ویژه یک محاسبه می شوند عملکرد لاپلاسین.

خوشه طیفی به خوبی در رابطه با تقسیم بندی یک سیستم چشمه جرمی شناخته شده است ، جایی که هر جرم با یک نقطه داده مرتبط است و هر سختی فنر مربوط به وزن یک لبه است که تشابه دو نقطه داده مربوط را توصیف می کند. به طور خاص ، مرجع کلاسیک [1] توضیح می دهد که مسئله مقدار ویژه که حالتهای ارتعاش عرضی یک سیستم چشمه جرمی را توصیف می کند دقیقاً همان مسئله مقدار ویژه نمودار ماتریس لاپلاکی است که به صورت تعریف شده است

L: = DA،

جایی که د ماتریس قطری است

D_ {ii} = \ sum_j A_ {ij}.

توده هایی که به سختی توسط فنرها در سیستم چشمه جرمی متصل می شوند ، به وضوح از حالت تعادل در حالت های لرزش با فرکانس پایین با هم حرکت می کنند ، بنابراین اجزای بردارهای ویژه مربوط به کوچکترین مقادیر ویژه نمودار Laplacian می توانند برای معنی دار بودن استفاده شوند خوشه بندی توده ها.

یک روش خوشه ای طیفی مرتبط با محبوبیت الگوریتم برش های نرمال یا الگوریتم Shi-Malik است که توسط Jianbo Shi و Jitendra Malik معرفی شده است [2] که معمولاً برای تقسیم تصویر استفاده می شود . نقاط را به دو مجموعه تقسیم می کند(B_1 ، B_2)بر اساس بردار ویژه vمربوط به دومین کمترین مقدار ویژه از متقارن نرمال لاپلاس تعریف شده به عنوان

{\ displaystyle L ^ {\ text {norm}}: = ID ^ {- 1/2} AD ^ {- 1/2}.}

یک الگوریتم ریاضی معادل [3] طول می کشد بردار ویژه مربوط به بزرگترین مقدار ویژه از راه رفتن تصادفی نرمال مجاورت ماتریسP = D ^ {- 1} الف.

با دانستن بردارهای اختصاصی ، تقسیم بندی ممکن است به روش های مختلفی انجام شود ، مانند محاسبه میانگین متر از اجزای دومین کوچکترین بردار ویژه است v، و قرار دادن تمام نقاطی که م componentلفه آنها در آن استv بزرگتر است از متر که در B_ {1}، و بقیه در B_ {2}. الگوریتم می تواند برای تقسیم بندی سلسله مراتبی با تقسیم مکرر زیرمجموعه ها به این روش استفاده شود.

الگوریتم ها [ ویرایش ]

اگر ماتریس شباهت آقبلاً به طور واضح ساخته نشده است ، اگر راه حل مسئله ارزش ویژه مربوطه به روشی بدون ماتریس (بدون دستکاری صریح یا حتی محاسبه ماتریس شباهت) ، مانند الگوریتم Lanczos ، انجام شود ، بازده خوشه بندی طیفی ممکن است بهبود یابد .

برای نمودارهای با اندازه بزرگ ، ارزش ویژه دوم ماتریس لاپلاکی نمودار (نرمال) اغلب بد شرطی است و منجر به همگرایی حل کننده های ارزش ویژه تکراری می شود. پیش شرط یک فناوری کلیدی است که سرعت همگرایی را تسریع می کند ، به عنوان مثال ، در روش LOBPCG بدون ماتریس . خوشه بندی طیفی با شناسایی ساختار جامعه و سپس خوشه بندی جوامع ، با موفقیت بر روی نمودارهای بزرگ اعمال شده است. [4]

خوشه بندی طیفی با کاهش ابعاد غیر خطی ارتباط نزدیک دارد و می توان از تکنیک های کاهش ابعاد مانند تعبیه محلی-خطی برای کاهش خطاهای ناشی از سر و صدا یا پرتگاه ها استفاده کرد. [5]

نرم افزار رایگان برای پیاده سازی خوشه طیفی در پروژه های بزرگ منبع باز موجود است مانند Scikit یادگیری [6] با استفاده از LOBPCG با multigrid پیش شرط ، [7] و یا ARPACK ، MLlib برای شبه بردار ویژه خوشه با استفاده از تکرار قدرت روش، [8] و R . [9]

رابطه با k- معنی [ ویرایش ]

مشکل k -means kernel پسوند k -means است که در آن نقاط داده ورودی به صورت غیر خطی و از طریق یک تابع هسته به فضای ویژگی ابعاد بالاتر ترسیم می شوند.{\ displaystyle k (x_ {i}، x_ {j}) = \ varphi ^ {T} (x_ {i}) \ varphi (x_ {j})}. مسئله k- kernel وزن دار با تعریف وزن این مشکل را بیشتر گسترش می دهدw_r برای هر خوشه به عنوان عکس متقابل تعداد عناصر در خوشه ،

\ max _ {{\ {C_ {s} \}}} \ sum _ {{r = 1}} ^ {k} w_ {r} \ sum _ {{x_ {i}، x_ {j} \ in C_ {r}}} k (x_ {i} ، x_ {j}).

فرض کنید F ماتریسی از ضرایب نرمال سازی برای هر نقطه برای هر خوشه است F_ {ij} = w_r اگر من ، j \ در C_rو در غیر این صورت صفر است. فرض کنیدکماتریس هسته برای تمام نقاط است. k- kernel وزن دار به معنای مسئله با n و k خوشه است به این صورت ،

{\ displaystyle \ max _ {F} \ operatorname {trace} (KF)}

به طوری که

{\ displaystyle F = G_ {n \ times k} G_ {k \ times n} ^ {T}}

G ^ TG = من

به طوری که {\ displaystyle \ operatorname {rank} (G) = k}. علاوه بر این ، محدودیت های هویتی نیز وجود داردF داده شده توسط ،

F \ cdot \ mathbb {I} = \ mathbb {I}

جایی که \ mathbb {I}  بردارهایی را نشان می دهد.

F ^ T \ mathbb {I} = \ mathbb {I}

این مشکل می تواند دوباره تکرار شود ،

{\ displaystyle \ max _ {G} \ operatorname {trace} (G ^ {T} G).}

این مشکل با محدودیت هویت معادل مسئله خوشه خوشه ای طیفی است Fآرام هستند به طور خاص ، مسئله k- kernel وزن می تواند به عنوان یک مسئله خوشه بندی طیفی (تقسیم نمودار) و بالعکس تنظیم شود. خروجی الگوریتم ها بردارهای ویژه ای هستند که نیازهای هویتی متغیرهای شاخص تعریف شده را برآورده نمی کنند.F. از این رو ، برای برابری بین مشکلات ، پردازش بردارهای ویژه مورد نیاز است. [10] تبدیل مسئله خوشه بندی طیفی به یک مسئله وزن هسته k- به معنای کاهش بار محاسباتی است. [11]

رابطه با DBSCAN [ ویرایش ]

خوشه طیفی همچنین مربوط به خوشه بندی DBSCAN است که اجزای متصل به چگالی را پیدا می کند. اجزای متصل با خوشه طیفی مطلوب مطابقت دارند (بدون برش لبه ها). و DBSCAN از یک نمودار همسایگی نامتقارن با لبه هایی که نقاط متراکم نیستند استفاده می کند. [12] بنابراین ، DBSCAN یک مورد خاص از خوشه بندی طیفی است ، اما یکی از آنها الگوریتم های کارآمدتر را امکان پذیر می کند (بدترین حالتO (n ^ {2})، در بسیاری از موارد عملی بسیار سریعتر با شاخص ها).

اقدامات مقایسه خوشه بندی ها [ ویرایش ]

راوی کانان ، سانتوش ومپالا و آدریان وتا [13] اندازه گیری دو معیار را برای تعریف کیفیت خوشه بندی داده شده ارائه دادند. آنها گفتند که خوشه بندی یک خوشه بندی (α، ε) است اگر رسانایی هر خوشه (در خوشه بندی) حداقل α باشد و وزن لبه های بین خوشه حداکثر ε کسر وزن کل کل لبه ها در نمودار. آنها همچنین به دو الگوریتم تقریب در همان مقاله نگاه می کنند.

راه حل های تقریبی [ ویرایش ]

خوشه بندی طیفی از نظر محاسباتی گران است مگر اینکه نمودار پراکنده باشد و ماتریس شباهت بتواند به طور کارآمد ساخته شود. اگر ماتریس تشابه ماتریس هسته RBF باشد ، خوشه بندی طیفی گران است. الگوریتم های تقریبی برای کارآمدتر شدن خوشه بندی طیفی وجود دارد: روش قدرت ، [14] روش Nystrom ، [15] و غیره. با این حال ، تحقیقات اخیر [16] به مشکلات خوشه طیفی با روش Nystrom اشاره کرده است. به طور خاص ، ماتریس شباهت با تقریب Nystrom از نظر عنصر مثبت نیست ، که می تواند مشکل ساز باشد.

تاریخ و ادبیات مرتبط [ ویرایش ]

خوشه بندی طیفی سابقه ای طولانی دارد. [17] [18] [19] [20] [21] [2] [22] خوشه طیفی به عنوان یک روش یادگیری ماشین توسط شی و مالک [2] و نگ ، اردن و ویس رواج یافت. [22]

ایده ها و اقدامات شبکه مربوط به خوشه بندی طیفی نیز نقش مهمی در تعدادی از برنامه ها دارد که ظاهراً از مشکلات خوشه بندی متفاوت است. به عنوان مثال ، همگرا شدن شبکه هایی با پارتیشن طیفی قوی تر در مدل های به روزرسانی نظر که در جامعه شناسی و اقتصاد استفاده می شود ، زمان بیشتری می برد. [23] [24]

همچنین به [ ویرایش ] مراجعه کنید

منابع