چکیده
پایگاه های داده ی دنیای واقعی امروزی معمولا شامل میلیون ها مورد با هزاران حوزه می شوند. به عنوان یک نتیجه، روش های شناسایی بخش جدای سنتی توزیع بنیان دارای توانایی های محدود شده ی بسیاری هستند و رویکردهای جدید همسایه های نزدیکترین K بنیان، محبوب تر شده اند. اما، مشکل با این روش های همسایه های نزدیکترین K بنیان این است که آنها بسیار به مقدار K حساس هستند(می توانند رتبه بندی متفاوتی برای بخش های مجزای برتر n داشته باشند)، از نظر محاسباتی برای مجموعه های داده بسیار پر هزینه هستند و در کل در اینکه آیا آنها برای مجموعه های ابعاد زیاد به خوبی کار می کنند یا نه شک وجو دارد. در این مقاله برای تا حدی دور زدن این مشکلات،یک فاکتور جدید بخش مجزای سراسری و یک فاکتور جدیدی بخش مجزای محلی و یک الگوریتم شناسایی بخش مجزای کارآمد بر مبنای این دو فاکتور مطرح کردیم که به راحتی پیاده سازی می شود و با راه حل های موجود می تواند عملکردهای رقابتی را بهبود ببخشد.آزمایشات انجام شده روی هر دو مجموعه های داده ی ترکیبی و واقعی، کارآمدی روش ما را نشان می دهند.
1. مقدمه
شناسایی بخش مجزا با هدف گذاری برای کشف مشاهدات بسیار دور شده از سایر مشاهدات (به میزانی که شک هایی به وجود آید مبنی بر این که این مشاهات بوسیله ی مکانیزم متفادتی ایجاد می شوند) تبدیل به یک کار داده کاوی مهم شده است. شناسایی بخش مجزا با مورد استفاده قرار گرفتن در حوزه های متعدد مختلفی مانند شناسایی نفوذ برای امنیت سایبری، شناسایی تقلب برای کارت های اعتباری، بیمه و مالیات، شناسایی سریع شیوع بیماری در حوزه ی پزشکی، شناسایی خطا در شبکه ی سنسور برای نظارت سلامت، ترافیک، وضعیت ماشین، هوا، آلودگی و مراقبت و غیره ، منافع بسیار زیادی را تولید کرده و در سال های اخیر روش های بسیاری برای این هدف ایجاد شده است، که از میان آنها می توان رویکردهای توزیع بنیان، عمق بنیان، فاصله بنیان، تراکم بنیان و خوشه بندی بنیان را نام برد.
آخرین الگوریتم شناسایی بخش مجزا بر پایه ی نزدیک ترین k همسایه(مانند تعدادی از روش های فاصله بنیان و تراکم بنیان) راه های مختلفی برای فیلتر کردن داده ی عادی و موقعیت یابی تعداد کم بخش های مجزا نشان داده اند. در حالیکه این روش ها برای پیاده سازی ساده هستند اما سایر جنبه های مربوط به الگوریتم ها نیز ارزش تحقیقات بیشتر را دارند. اولا، این روش ها معمولا تنها n بخش مجزای برتر را با دو مقدار نشان می دهند. یکی از این مقادیر فاکتور بخش مجزا (به عنوان امتیاز نیز در این مقاله به آن اشاره شده) و دیگری رتبه بندی نقاط براساس امتیازات. بنابراین، روش های مختلف می توانند برای n بخش مجزای برتر، رتبه بندی های مختلفی داشته باشند. دوما، مشاهده شده که روش های شناسایی بخش مجزا بر مبنای نزدیک ترین k همسایه به پارامتر k حساس هستند و تغییری کوچک در k می تواند منجر به تغییرات در امتیازات و متقابلا رتبه بندی شود. به عنوان یک نتیجه، به جز برای بخش های مجزای خیلی قوی که امتیازات در آنها متمایز هستند، رتبه بندی نیز به k حساس است. سوما، برای مجموعه داده های بزرگ مدرن با N واحد داده، زمان اجرای ، که برای جستجوی دقیق همسایه های k بوده، باید به طور معناداری بهبود داده شود. در نهایت، در فضا با بعد بالا، نقاط داده به طور برابر به یکدیگر نزدیک می شوند و مشکلی که "نفرین ابعاد" نامیده می شود را به وجود می آورند و این مسئله وجود دارد، چه ایده ی این تعاریف بخش مجزا برای داده ی بعد زیاد هنوز معنادار باشند و چه نباشد.
این مقاله در نشریه الزویر منتشر شده و ترجمه آن با عنوان روش سریع تشخیص پرت در سایت ای ترجمه به صورت رایگان قابل دانلود می باشد. جهت دانلود رایگان مقاله فارسی و انگلیسی روی عنوان فارسی (آبی رنگ) کلیک نمایید.
منبع:
