خوشه بندی با ثبات با استفاده از منظم سازی داده های پرت-پراکندگی / Robust Clustering Using Outlier-Sparsity Regularization

خوشه بندی با ثبات با استفاده از منظم سازی داده های پرت-پراکندگی Robust Clustering Using Outlier-Sparsity Regularization

  • نوع فایل : کتاب
  • زبان : فارسی
  • ناشر : آی تریپل ای IEEE
  • چاپ و سال / کشور: 2012

توضیحات

چاپ شده در مجله یافته ها در حوزه سیگنال – TRANSACTIONS ON SIGNAL
رشته های مرتبط مهندسی کامپیوتر و مهندسی الگوریتم ها و محاسبات
۱- مقدمه هدف خوشه بندی، تقسیم یک مجموعه داده ها به زیر مجموعه هایی به نام خوشه ها می باشد به طوری که داده های قرار گرفته در یک خوشه از برخی جهات با هم مشابه باشند. کار با داده های بدون برچسب و تحت مفروضات حداقل موجب شده است تا خوشه بندی به یک ابزار چالش بر انگیز و جهانی برای آشکار سازی ساختار های داده در طیف وسیعی از برنامه ها نظیر تحلیل ریزآرایه DNA و بیو انفورماتیک، تحلیل شبکه های اجتماعی، پردازش تصویر و داده کاوی(۱۸،۳۵) تبدیل شود. به علاوه، خوشه بندی می تواند یک مرحله پیش پردازش برای یادگیری نظارت شده در شرایطی باشد که در آن ها برچسب زدن داده ها به طور جداگانه پر هزینه است. تفسیر های مختلف از خوشه در رشته های مختلف منجر به فراوانی الگوریتم های خاص برنامه شده است(۳۵). در میان الگوریتم هایی که داده های برداری را خوشه بندی می کنند، خوشه بندی مبتنی بر مدل ترکیبی گوسی(GMM) و کامینز، دو طرح رایج می باشند(۲۶-۳۵). کامینز بستگی به فواصل اقلیدسی به عنوان یک شاخص تشابه دارد که به موجب آن ایجاد بخش ها یا پارتیشن هایی می کند که پراکندگی درون خوشه ای را به حداقل می رساند(۱۸). بر عکس، کامینز نرم( هم چنین موسوم به فازی) نیز برای هم پوشانی خوشه ها از طریق نسبت دادن هر نقطه مبنا به خوشه های چندگانه(۲) مناسب است. خوشه بندی مبتنی بر GMM داده های استخراج شده از تابع چگالی احتمالی(pdf) را در نظر می گیرد که در آن هر pdf کلاس مشروط متناظر با یک خوشه(۳۵) متناظر است. سپس خوشه بندی به عنوان یک محصول جانبی چارچوب براورد حداکثر درست نمایی(ML) برای پارامتر های GMM مطرح می شود که معمولا از طریق الگوریتم بیشینه سازی- امید ریاضی(EM) (11) بدست می آید. روش های هسته ای نیز برای خوشه بندی خوشه های قابل تفکیک غیر خطی طراحی شده اند(۲۹-۳۰). روش های خوشه بندی کامینز و مبتنی بر GMM، علی رغم محبوبیت خود به داده های متناقض موسوم به داده های پرت ناشی از وابستگی کارکردی آن ها به فاصله اقلیدسی(۲۰) حساس می باشند. داده های پرت به ندرت در داده ها به دلیل خطا های خواندن ظاهر می شوند یا دلیل دیگر این است که آن ها متعلق به پدیده های نادر یا بسیار مهم می باشند. با این حال، حتی تعداد کمی از داده های پرت میتوانند موجب شوند تا نتایج خوشه بندی غیر قابل اطمینان شود: براورد های مربوط به مراکز خوشه و پارامتر مدل می توانند به شدت اریبی داشته باشند و از این روی تخصیص داده به خوشه با مشکل مواجه می شود. به این ترتیب باید استوار سازی رویکرد های خوشه بندی در برابر داده های پرت با پیچیدگی محاسباتی کم به منظور آشکار سازی ساختار اصلی در داده ها استفاده شود. چندین رویکرد خوشه بندی قوی( با ثبات) مورد مطالعه قرار گرفته است(۱۶). آن دسته از رویکرد های مرتبط با چارچوب توسعه یافته در این جا شامل خوشه بندی احتمالی است که بر اساس کامینز فازی با اندازه گیری خصوصیت هر نقطه مبنا با توجه به هر خوشه برای تصمیم گیری در مورد این که آیا یک نقطه مبنا، داده پرت است یا نه(۲۴-۲۸) ایجاد می شود. با این حال، خوشه بندی احتمالی به مقدار دهی حساس است و می تواند یک خروجی را بیش از یک بار تولید کند. مشابه با(۱۹)، روش خوشه بندی نویز ارایه شده توسط(۱۰) یک خوشه اضافی را معرفی می کند که همه داده های پرت را پوشش می دهد و مرکز آن به طور اکتشافی فرض می شود که فاصله مساوی از همه داده های غیرپرت دارد. به منظور کاهش اریبی مرکزی، روش آلفا کات مراحل کامینز را اجرا می کند ولی مراکز خوشه با استفاده از تنها درصد آلفا از داده های تخصیص داده شده به هر خوشه براورد می شوند(۳۶). سایر جایگزین های قوی شامل رویکرد های خوشه بندی متوالی می باشند که یک تک خوشه را در یک زمان شناسایی کرده و نقاط آن را از مجموعه داده ها حذف می کنند(۲۲-۳۸). یک بیضی حداقل حجم حاوی یک کسر از پیش تعیین شده از داده ها در هر مرحله در(۲۲) شناسایی می شود، در حالی که(۳۸) مدل آلوده- هابر را با GMM ترکیب می کند. با این حال، حذف متوالی نقاط موجب تاخیر در ساختار داده اصلی می شود. روش های خوشه بندی مبتنی بر فاصله ( K-مدین) با الهام از آماره های باثبات، تابع دو وزنی توکی و میانگین پیراسته نیز پیشنهاد شده اند( ۴، ۱۵، ۲۳)، با این حال آن ها همگی محدود به خوشه های تفکیک پذیر خطی می باشند. یک رویکرد خوشه بندی برای شناسایی خوشه های با شکل دلخواه با استفاده از توابع هسته ای در (۱) توسعه یافت.اگرچه این روش در برابر داده های پرت مقاوم و انعطاف پذیر است، با این حال هدف این روش براورد تراکم است در حالی که تعداد خوشه های شناسایی شده به شدت بستگی به جست و جوی شبکه نسبت به یک پارامتر هسته ای دارند. رویکرد های مبتنی بر GMM با ثبات، Pdf های داده پرت-آگاه را معرفی کرده و مسئله ML معمولا از طریق الگوریتم های شبه-EM حل می شوند(۲۷-۳۱). اولین هدف این مطالعه، معرفی یک مدل داده برای خوشه بندی می باشد که صریحا داده های پرت را از طریق یک بردار داده پرت قطعی به ازای هر نقطه مبنا پوشش دهد( بخش دوم). یک نقطه مبنا در صورتی به عنوان داده پرت در نظر گرفته می شود که بردار داده پرت متناظر آن، غیر صفر باشد. بررسی این موضوع که داده های پرت پراکندگی کم تری در دامنه بردار داده های پرت دارد، منجر به ایجاد یک ارتباط مبرهن بین خوشه بندی و پارادایم سنجش فشرده(CS)(7) می شود. بر اساس این مدل، یک روش خوشه بندی داده پرت-آگاه برای خوشه بندی هر دو از دیدگاه های قطعی( کامینز) و احتمالی(GMM) توسعه می یابد. دومین هدف این مطالعه بررسی الگوریتم های خوشه بندی تکراری مختلف توسعه یافته برای خوشه بندی کامینز سخت، کامینز نرم و خوشه بندی مبتنی بر GMM( بخش سوم) می باشد. الگوریتم ها بر مبنای تکرار نزول مختصات بلوک(BCD) بوده و تولید آپدیت های شکل بسته برای هر مجموعه از متغیر های بهینه سازی می کند. به ویژه، براورد داده های پرت برای حل مسئله گروه- لاسو استفاده می شود(۳۷) که راه حل آن در شکل بسته محاسبه می شود. الگوریتم های خوشه بندی با ثبات جدید با پیچیدگی محاسباتی کم هزینه با رتبه مشابه با الگوریتم های خوشه بندی غیر با ثبات عمل می کنند. چندین کاربرد معاصر در زمینه بیو انفورماتیک، تحلیل شبکه های اجتماعی، پردازش تصویر و یادگیری ماشینی مستلزم خوشه بندی داده پرت-آگاه داده های با بعد بالا یا مستلزم خوشه های تفکیک پذیر غیر خطی می باشند. برای رفع این نیاز های خوشه بندی، الگوریتم های خوشه بندی با ثبات جدید در بخش چهارم بررسی شده و این سومین هدف این مطالعه است. مدل مفروض نه تنها امکان این هسته سازی را برای هر دو خوشه بندی کامینز و و احتمالی را می دهد، بلکه منجر به الگوریتم های تکراری با آپدیت های شکل بسته می شود. در بخش ۵، الگوریتم های توسعه یافته با استفاده از مجموعه داده های مصنوعی و نیز واقعی از سیستم های تشخیص رقم دست نوشته و شبکه های اجتماعی تست می شوند. نتایج موید کارایی و اثر بخشی روش ها است. در بخش شش نتیجه گیری ارایه می شود.

Description

I. INTRODUCTION CLUSTERING aims to partition a set of data into subsets, called clusters, such that data assigned to the same cluster are similar in some sense. Working with unlabeled data and under minimal assumptions makes clustering a challenging, yet universal tool for revealing data structures in a gamut of applications such as DNA microarray analysis and bioinformatics, (social) network analysis, image processing, and data mining [18], [35]. Moreover, clustering can serve as a pre-processing step for supervised learning in applications where labeling data one-at-a-time is costly. Multiple interpretations across disciplines of what a cluster is, have led to an abundance of application-specific algorithms [35]. Among the algorithms which cluster data represented by vectors, K-means and Gaussian mixture model (GMM-)based clustering are two popular schemes [26], [35]. K-means relies on the Euclidean distance as a similarity measure, thereby yielding partitions that minimize the within-cluster scatter [18]. Contrastingly, soft (a.k.a. fuzzy) K-means is well-suited for overlapping clusters by allowing each datum to belong to multiple clusters [2]. GMM-based clustering considers data drawn from a probability density function (pdf), where each class-conditional pdf corresponds to a cluster [35]. Clustering then arises as a by-product of a maximum likelihood (ML) estimation framework for the GMM parameters, which are typically obtained through the expectation-maximization (EM) algorithm [11]. Kernel methods have been devised to enable clustering of nonlinearly separable clusters [29], [30]. Notwithstanding their popularity, K-means and GMM-based clustering are sensitive to inconsistent data, termed outliers, due to their functional dependency on the Euclidean distance [20]. Outliers appear infrequently in the data, emerging either due to reading errors or because they belong to rarely-seen and hence, markedly informative phenomena. However, even a few outliers can render clustering unreliable: cluster centers and model parameter estimates can be severely biased, and thus the data-tocluster assignment is deteriorated. This motivates robustifying clustering approaches against outliers at affordable computational complexity in order to unravel the underlying structure in the data. Several robust clustering approaches have been investigated [16]. Those more relevant to the framework developed here include possibilistic clustering, which builds on fuzzy K-means by measuring the so-called typicality of each datum with respect to each cluster to decide whether a datum is an outlier [24], [28]. However, possibilistic clustering is sensitive to initialization, and can output the same cluster more than once. Similar to [19], the noise clustering method of [10] introduces an additional cluster intended to capture all outliers, and its centroid is heuristically assumed to be equidistant from all non-outlying data. To mitigate centroid bias, the -cut method performs K-means steps, but cluster centroids are estimated using only the -percentage of the data assigned to each cluster [36]. Other robust alternatives include sequential clustering approaches which identify a single cluster at a time, and remove its points from the dataset [22], [38]. A minimum-volume ellipsoid containing a predetermined fraction of the data is identified per step in [22]; while [38] combines Huber’s -contaminated model with a GMM [20]. However, sequentially removing points can hinder the underlying data structure.Inspired by robust statistics, clustering methods based on the -distance (K-medians), Tukey’s biweighted function, and trimmed means have been also proposed [4], [15], [23]; but they are all limited to linearly separable clusters. A clustering approach identifying clusters of arbitrary shape using kernel functions was developed in [1]. Even though resilient to outliers, this method targets density estimation, while the number of clusters identified depends critically on a grid search over a kernel parameter. Robust GMM-based clustering approaches introduce outlier-aware pdfs, and the ML problem arising is typically solved via EM-like algorithms [27], [31]. The first contribution of the present work is to introduce a data model for clustering that explicitly accounts for outliers via a deterministic outlier vector per datum (Section II). A datum is deemed an outlier if its corresponding outlier vector is nonzero. Translating the fact that outliers are rare to sparsity in the outlier vector domain leads to a neat connection between clustering and the compressed sensing (CS) paradigm [7]. Building on this model, an outlier-aware clustering methodology is developed for clustering both from the deterministic (K-means), and the probabilistic (GMMs) perspectives. The second contribution of this work comprises various iterative clustering algorithms developed for robust hard K-means, soft K-means, and GMM-based clustering (Section III). The algorithms are based on a block coordinate descent (BCD) iteration and yield closed-form updates for each set of optimization variables. In particular, estimating the outliers boils down to solving a group-Lasso problem [37], whose solution is computed in closed form. The novel robust clustering algorithms operate at an affordable computational complexity of the same order as that of their non-robust counterparts. Several contemporary applications in bioinformatics, (social) network analysis, image processing, and machine learning call for outlier-aware clustering of high-dimensional data, or involve nonlinearly separable clusters. To accommodate these clustering needs, the novel robust clustering algorithms are kernelized in Section IV; and this is the third contribution of our work. The assumed model not only enables such a kernelization for both K-means and the probabilistic setups, but it also yields iterative algorithms with closed-form updates. In Section V, the algorithms developed are tested using synthetic as well as real datasets from handwritten digit recognition systems and social networks. The results corroborate the effectiveness of the methods. Conclusions are drawn in Section VI.
اگر شما نسبت به این اثر یا عنوان محق هستید، لطفا از طریق "بخش تماس با ما" با ما تماس بگیرید و برای اطلاعات بیشتر، صفحه قوانین و مقررات را مطالعه نمایید.

دیدگاه کاربران


لطفا در این قسمت فقط نظر شخصی در مورد این عنوان را وارد نمایید و در صورتیکه مشکلی با دانلود یا استفاده از این فایل دارید در صفحه کاربری تیکت ثبت کنید.

بارگزاری