خوشه طیفی

توسط علی رضا نقش نیلچی | سه شنبه هجدهم خرداد ۱۴۰۰ | 6:22

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

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

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

فهرست

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

با توجه به مجموعه ای از نقاط داده برشمرده شده ، ماتریس شباهت ممکن است به عنوان یک ماتریس متقارن تعریف شود $آ$ ، جایی که $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}$ . الگوریتم را می توان برای تقسیم بندی سلسله مراتبی با تقسیم مکرر زیرمجموعه ها به این روش ، استفاده کرد.

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

الگوریتم اساسی

لاپلاس را محاسبه کنید $ل$ (یا لاپلاسین نرمال شده)
اولین را محاسبه کنید $ک$ بردارهای ویژه (بردارهای ویژه مربوط به $ک$ کوچکترین مقادیر ویژه از $ل$ )
ماتریس تشکیل شده توسط اولین را در نظر بگیرید $ک$ بردارهای ویژه؛ $من$ ردیف هفتم ویژگی های گره نمودار را تعریف می کند $من$
گره های نمودار را براساس این ویژگی ها خوشه بندی کنید (مثلاً با استفاده از خوشه بندی k-means )

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

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

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

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

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

ایده های خوشه طیفی ممکن است بلافاصله آشکار نباشد. برجسته کردن روابط با روش های دیگر ممکن است مفید باشد. به طور خاص ، می توان آن را در زمینه روش های خوشه بندی هسته توصیف کرد ، که چندین شباهت را با رویکردهای دیگر نشان می دهد. [11]

رابطه با 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$ . از این رو ، برای برابری بین مشکلات ، پردازش پس از بردارهای ویژه مورد نیاز است. [12] تبدیل مسئله خوشه بندی طیفی به یک مسئله k- هسته معنی دار ، بار محاسباتی را تا حد زیادی کاهش می دهد. [13]

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

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

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

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

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

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

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

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

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

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

منابع

https://en.wikipedia.org/wiki/Spectral_clustering

مشخصات وب

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

ریاضیات

آموزش ریاضی