دانلود رایگان ترجمه مقاله روش سریع تشخیص پرت مبتنی بر kNN (ساینس دایرکت – الزویر 2015)

مبتدی (مناسب برای درک مفهوم کلی مطلب) 

در سال 2000 برای اداره کردن این وضعیت، Breunig et al بوسیله ی نشان دادن یک نشانگر برای هر واحد داده (فاکتور بخش مجزا (LOF) نامیده می شد) که نسبت بین تراکم محلی یک شیء و میانگین اشیاء نزدیک ترین k همسایه ام آنها می باشد، در تحقیق شناسایی بخش مجزای تراکم بنیان پیش گام شدند. روش LOF به این طریق کار می کند که در ابتدا LOF را برای هر شیء محاسبه می کند، سپس رتبه بندی نقاط داده بر اساس مقادیر LOF آنها مشخص می شود و در نهایت اشیاء با n مقدار بالای LOF به عنوان بخش مجزا بازگردانده می شوند

به دنبال ایده ی فاکتور بخش مجزای محلی، چندین بسط و اصلاحیه برای مدل پایه ی LOF ارائه شده است. در سال 2002، Tang et al یک فاکتور بخش مجزای اتصال بنیان (COF) را به منظور اداره کردن خصوصیت “جدا بودن” بخش های مجزا پیشنهاد کردند. “جدا بودن” به تراکم کم دلالت دارد اما تراکم کم همیشه به “جدا بودن” دلالت نمی کند. با توجه به نقطه ی داده ی o ، و نزدیک ترین k همسایه، اولین هزینه در تعریف هزینه فاصله از o تا نزدیک ترین همسایه ی آن است. به طور کلی، هزینه ی i ام (i≤k) برابر با کوچکترین فاصله از o و نزدیک ترین (i-1) شیء آن تا بهقی k-i شیء در همسایگی است. در نهایت، COF نسبت تعریف هزینه ی نقاط داده به میانگین هزینه ی نقاط داده ی نزدیک ترین k همسایه، می باشد. در سال 2003، Papadimitriou et al طرح شناسایی بخش مجزای محلی دیگری با نام انتگرال بخش مجزای محلی (LOCI) را بر مبنای مفهوم فاکتور انحراف چند دانه بودن (MDEF) پیشنهاد کرد. تفاوت اصلی میان LOF و LOCI این است که MDEF در LOCI از همسایگی های ε به جای نزدیک ترین k همسایه، استفاده می کنند. در سال 2004، Sun and Chawla یک معیار بخش مجزای محلی فضایی با نام SLOM مطرح کرد. در سال 2006، Jin et al روش INFLO که اجتماع داده ی نقاط نزدیکترین k همسایه و معکوس نزدیک ترین همسایه های آن را به منظور بدست آوردن میزان جدایی لحاظ میکرد را ارائه کرد. نزدیک ترین همسایگی معکوس برای نقطه ی داده ی p تعریف می شود تا شامل همسایگیِ نزدیکترین k همسایه ای شود که p برای آنها در میان نزدیکترین k همسایه است. به همین روش، INFLO تراکم p را با میانگین تراکم های اشیاء در اجتماع داده را به عنوان میزان جدایی مقایسه می کند. Zhang et al. با توجه به اینکه داده ی دنیای واقعی معمولا دارای توزیعی پراکنده است، یک تعریف بخش مجزای جدید با نام فاکتور بخش مجزای فاصله بنیان محلی (LDOF) در جهت شناسایی بخش های مجزا در مجموعه داده های پراکنده مطرح کرد. LDOF نسبت بینِ میانگین فواصل از یک نقطه ی داده تا نزدیک ترین k همسایه ی آن و میانگین فواصل دو به دو در میان این k+1 نقطه ی داده است، و به همین طریق، در جه ای که یک شیء از سیستم همسایگی اش منحرف شده را بدست می آورد. در سال 2013، Huang et al، رویکردی جدید برای شناسایی بخش مجزا با نام RBDA و بر مبنای یک معیار رتبه بندی که روی این سوال که آیا یک نقطه نسبت به نزدیک ترین همسایه های خود نزدیک نرین است یا نه متمرکز شده، مطرح کرد. RBDA با حذف مشکل محاسبه ی تراکم در همسایگی یک نقطه، بخش های مجزا را بر پایه ی محاسبه ی مرتبه ی نقطه ی در میان همه ی نزدیک ترین k همسایه ی آن مشخص می کند. اما متاسفانه چنین کاری دارای هزینه ی محاسباتی بالایی است.

2.2. الگوریتم هایی بر مبنای خوشه بندی MST
امتیازات بخش مجزای فاصل بنیان و نیز تراکم بنیان نسبت به تنظیمات پارامترهایشان حساس هستند. این موضوع بوسیله ی مجموعه داده ی دو بعدی نشان داده شده در شکل 2 می تواند نمایش داده شود. برای روش های شناسایی بخش های مجزای فاصله بنیان، اگر نزدیک ترین k=6 همسایه در نظر گرفته شود، همه ی نقاط داده در خوشه ی c3 به عنوان بخش مجزا شناسایی نخواهند شد در حالیکه اگر k=7 باشد، همه ی نقاط داده در خوشه ی c3 به عنوان بخش مجزا لحاظ می شوند. مشکلاتی مشابه برای روش های شناسایی بخش مجزای تراکم بنیان وجود دارد. وضعیت برای شناسایی بخش های مجزا در فضای ویژگی با ابعاد بالا می تواند بدتر باشد چون نقاط داده در آنجا به سادگی پدیدار نمی شوند.
اینجا محلی است که الگوریتم های خوشه بندی بنیان، می توانند معنای بیشتری داشته باشند. نگرانی اصلی الگوریتم های خوشه بندی به عنوان یک ابزار بسیار مهم داده کاوی، یافتن خوشه ها از طریق بهینه سازی برخی معیارها مانند کمینه کردن فاصله ی خوشه ی درونی و بیشینه کردن فاصله ی خوشه ی داخلی است. واحد های داده در گروه های کوچک، به عنوان یک محصول فرعی معمولا می توانند به عنوان بخش های مجزا (دماغه) ای ذکر شوند که باید برای افزایش اطمینان خوشه حذف گردند. الگوریتم های کلاسیک خوشه بندی مانند الگوریتم میانگین های k و PAM، به گروه بندی نقاط داده در پیرامون برخی “مراکز” وابسته هستند و در زمانی که مرز های خوشه ها غیر عادی باشند به خوبی کار نمی کنند. به عنوان یک جایگزین، روش هایی با بنیان تئوری گراف که از طریق الگوریتم های خوشه بندی بر مبنای MST به عنوان نمونه داده شده اند، می توانند خوشه هایی با مرزهای غیر عادی را بیابند.

یک درخت پوشای کمینه دارای حداقل وزن کل است در حالیکه یک گراف وزن دار متصل روی مجموعه ای از نقاط داده اما بدون مسیر بسته شده است. اگر یک وزن که دلالت بر فاصله ی بین دو نقطه ی پایانی دارد، به هر لبه تخصیصی داده شود، هر لبه در یک MST کوتاه ترین فاصله بین دو زیر شاخه ای خواهد بود که بوسیله ی آن لبه متصل می شوند. این نکته به عنوان دارایی برشِ MST استناد می شود. بنابراین، حذف بلندترین لبه ها متناسب با انتخاب انفصال ها در جهت شکل دهی خوشه ها است. درخت پوشای کمینه (MST) خوشه بندی بنیان، برای اولین بار به وسیله ی Zahn در سال 1971 ارائه شد و تا کنون به طور گسترده ای مورد مطالعه قرار گرفته است. با توجه به این موضوع، نقاط داده در کوچکترین خوشه هایی که بوسیله ی بریدن بلندترین لبه ها در یک MST شکل گرفته اند به احتمال زیاد می توانند بخش مجزا باشند. چندین روش شناسایی بخش مجزای MST بنیان پیشنهاد شده است. اما برای مجموعه های داده ی بزرگ و با ابعاد بالای مدرن که در آنها تنها یک مجموعه از N نقطه ی داده ارائه می شود، این الگوریتم های شناسایی بخش مجزای MST بنیان از زمان اجرای درجه دوی ملزوم برای ساخت یک MST رنج می برند.
برای دقت بیشتر محاسباتی، Wang و دیگران یک روش شناسایی بخش مجزای سه مرحله ای کارآمد پیشنهاد دادند (در ادامه به صورت MST+LOF ذکر می شود). در ابتدا، یک ساختار کارآمد از یک درخت پوشای بسیار نزدیک به دخت پوشای کمینه ی مجموعه داده ساخته می شود. دوم، بلندترین لبه ها در درخت پوشای بدست آمده حذف می شوند تا خوشه ها را شکل دهند. براساس این یافته که نقاط داده در خوشه های کوچک به احتمال زیاد همگی می توانند بخش مجزا باشند، این خوشه های کوچک انتخاب می شوند و به عنوان کاندیداهای بالقوه ی بخش مجزا در نظر گرفته می شوند. در نهایت، عوامل مجزا بودن تراکم بنیان، LOF، برای کاندیداهای بالقوه ی بخش مجزا محاسبه و به منظور مشخص کردن بخش مجزای محلی ارزش گذاری می شوند. مزیت اصلی این الگوریتم، بازده محاسباتی آن است.

2.3. بخش مجزا کاوی با ابعاد بالا بر مبنای طرح
الگوریتم های شناسایی بخش مجزایی که تا کنون ارائه شدند، فرضیه هایی ضمنی از داده ی نسبتا با ابعاد کم ایجاد می کنند و فواصل در فضای ابعاد کامل را در جهت یافتن بخش مجزا استفاده می کنند اما، در فضای با بعد بالا، داده نامتراکم است و ایده ی یافتن بخش های مجزای معنادار به طور اساسی پیچیده تر و غیرواضح می شود. جدا از در نظر گرفتن رفتار داده در ابعاد کامل، انحرافات غیر عادی می توانند در برخی زیر فضاها با ابعاد کمتر قرار گیرند. طراحی روش هایی هدفمندتر برای یافتن بخش های مجزایی که مختص به زیرفضای خاص در سوال با بررسی رفتار داده در زیرفضا، ممکن می شود. در حقیقت، در 11 گزارش شده است که بخش های مجزای جذاب تر در پایگاه داده ی آماری بسکتبال NBA98 با استفاده از ویژگی های کمتری بدست آمدند. براساس این مشاهدات، Aggarwal and Yu روش های جدیدی برای شناسایی بخش مجزا ارائه کردند (در ادامه به صورت شناسایی بخش مجزا بر مبنای طرح (PBOD) ذکر می شود) که اگر در یک طرح با ابعاد کمتر، یک نقطه ی داده در یک منطقه ی محلیِ تراکمِ کمِ غیرعادی حضور داشته باشد،آن را بخش مجزا تعریف می کند. برای مشخص کردن و یافتن چنین طرح هایی، در ابتدا یک گسسته سازی شبکه ی داده اجرا می شود. هر یک از ویژگی های d داده به محدوده های φ تقسیم شده اند و از این رو هر محدوده شامل یک کسر f=1/ φ از سوابق می شود. برای یک مکعب K بعدی که بوسیله ی برداشتن محدوده های شبکه از ابعاد مختلف k<=d ایجاد می شود، ضریب پراکندگی S(c) برای مکعب C به صورت زیر محاسبه می شود: که N در آن تعداد نقاط داده است و n(C) به تعداد نقاط در مکعب k بعدی دلالت دارد. مکعب هایی را که حضور نقطه ها در آن به طور معناداری کمتر از میزان مورد انتظار است، تنها از طریق ضرایب پراکندگی منفی نشان داده می شوند. وقتی چنین الگوهایی مشخص شد، بخش های مجزا به عنوان آن سوابقی که چنین الگوهایی در آنها وجود دارد، تعریف می شوند. یک مشاهده ی جالب این است که چنین طرح هایی با ابعاد کمتر می توانند حتی در مجموعه های داده ای که مقادیر ویژگی از دست رفته دارند نیز کاویده شوند. افزایش نمایی فضای جستجوی طرح های ممکن با ابعاد، مشکل PBOD است. این الگوریتم برای چند صد بعد عملی نیست.

3. یک الگوریتم شناسایی بخش مجزا ی الگو گرفته از MST
از مطالعه ی ما در مورد شناسایی بخش مجزای فاصله بنیان، تراکم بنیان و خوشه بندی بنیان، چندین مشاهده بدست آورده ایم:
اولا، روش های فاصله بنیان، به صورت تئوری بوسیله ی محاسبه ی KNN برای هر نقطه ی داده، محاسبه ی امتیازات بخش مجزای فاصله بنیان برای آنها، رتبه بندی همه ی اشیاء برمبنای امتیازاتشان و در نهایت برگرداندن نقاط داده با n امتیاز بزرگتر به عنوان بخش های مجزا، کار می کند اما هیچ دلیلی وجود ندارد تا فرض کنیم که موضوع همین است. برای مثال، در شکل 3، اگرچه امتیازات بخش مجزای فاصله بنیان می تواند از منظر یک MST، برای این مجموعه داده محاسبه شوداما هیچ بخش مجزای برجسته ای وجود ندارد. متاسفانه، معیار خوشه بندی بر پایه ی MST تمایل به بریدن مجموعه های کوچکِ گره های جدا شده در یک گراف دارد و می تواند در زمانی که هیچ بخش مجزایی وجود ندارد، قسمت بندی بدی را ارائه دهد. این حقیقت می تواند به سادگی از مجموعه داده های نشان داده شده در شکل 3 نشان داده شود. بنابراین، باید راهی برای قضاوت در مورد اینکه آیا بخش های مجزا وجود دارد یا نه وجود داشته باشد. برای انجام دادن چنین کاری، به عنوان تخمین درجه اول، وزن های لبه (برای مثال فواصل لبه) در خوشه ی یک MST می تواند فرض شود که یک توزیع متحدالشکل میانگین متناظر را دنبال می کند و از این رو انحراف استاندارد می تواند محاسبه شود. تناسب انحراف استاندارد روی میانگین می تواند استعمال شود تا در سطحی قضاوت کند که آیا بخش های مجزا وجود دارند یا نه.
دوما، الگوریتم های شناسایی بخش مجزای تراکم بنیان، نمی تواند در شناسایی بخش مجزای سراسری، به خوبی کار کند. برای مثال، مجموعه داده در شکل 4 را در نظر بگیرید. ظاهرا، نقطه ی داده ی A دورترین نقطه از نزدیکترین شش همسایه ی خود است و از این رو باید به عنوان یک بخش مجزای سراسری مشخص شود اما برای k=6، الگوریتم LOF ، بالاترین امتیاز بخش مجزا را به جای نقطه ی A به نقطه ی داده ی B تخصیص می دهد. این مسئله به این علت است که LOF به عنوان یک تناسب محاسبه می شود و نقطه ی داده ی B بالاترین تناسب را برای این k می گیرد. به عنوان یک نتیجه، الگوریتم های LOF بنیان، در شناسایی A به عنوان چشمگیرترین بخش مجزا شکست می خورند. از منظر یک MST، همان طور که در سمت راست شکل 4 نشان داده شده، اگر وزن لبه ی درخت (برای مثال فاصله) به عنوان یک عامل استفاده شود، این موضوع اتفاق نمی افتد و امتیاز داده ی A برای k های مختلف، ثابت می ماند.
سوما، براساس دارایی برش، الگوریتم های خوشه بندیِ MST بنیان می توانند برای شناسایی خوشه های کوچکی که از طریق لبه های بلند به نقاط داده ی معمولی متصل می شوند، مفید باشند و همان طور که در شکل 4 نشان داده شده، می توانند به عنوان بخش مجزا انتخاب و لحاظ شوند. اگرچه، الگوریتم های شناسایی بخش مجزا بر مبنای خوشه بندیِ MST استاندارد معمولا زمان اجرای درجه دویی را برای تضمین ارضا ی ویژگی های MST دارند اما از دیدگاه ما، این موضوع نه کارآمد است و نه لازم.
براساس این مشاهدات، ایده های کارکردن در پشت الگوریتم کتارآمد شناسایی بخش مجزای الگو گرفته از MST مادر زیرگروه پیش رو رسمیت پیدا می کند.