کاوش سریع برون هشته - Artificial Intelligence

**Astaraki** · ۰۲-۳۱-۱۳۹۰, ۱۰:۰۵ قبل از ظهر

کاوش سریع برون هشته

کاوش سریع برون هشته های مبتنی بر فاصله در پایگاه داده هایی با ابعاد زیاد مسئله رایج در داده کاوی پیدا کردن برون هشته ها وغیر عادی ها در پایگاه داده است. برون هشته ها نقاطی هستند که رویداد آنها در یک مدل داده کم است.از آنجائیکه برون هشته ها نادر هستند می توانند در اثر داده بد ،مضمون های بد خواهانه یا جمع آوری ناقص باشند.اخیرا محققان شناسایی برون هشته ها را درکارهایی مثل، پاک کردن داده، شناسایی نقص و شناسایی نفوذ به کار برده اند.راه های زیادی برای شناسایی برون هشته ها وجود دارد.یک راه شناسایی بر اساس مدل است که فرض می شود داده ینرم افزار Wekaالگوريتمهاي يادگيري ماشين در جاواتمام الگوريتمهاي تعريف شده در اين كتاب، پيادهسازي شدهاند و بصورت آزاد در سايت Weka 3 - Data Mining with Open Source Machine Learning Software in Java جهت استفاده شما قرار داده شده است. اينكار به شما اجازه ميدهد كه شما ياد بگيريد كه آنها چگونه كار ميكنند و چه چيزي هستند؟ پيادهسازيها در سيستم weak انجام شده است و در دانشگاه waikato در نيوزيلند توسعه داده شده است. كلمه weak خلاصهاي از عبارت محيط ويكاتو براي تحليل دانش است.(همچنين وكا بر وزن mecca نام پرندهاي بدون پرواز و با طبيعت كنجكاو است كه فقط در نيوزيلند يافت ميشود.) سيستم به زبان جاوا نوشته شده است و يك زبان برنامهنويسي شيگرايي است كه براي تمام سطوح رايانه بهصورت گسترده قابل دسترس خواهد بود. وكا در سيستم عاملهاي لينوكس، ويندوز و سيستم عامل مكينتاش آزمايش شده است. جاوا اجازه فراهم ساختن واسط توسعهاي بسياري از الگوريتمهاي يادگيري مختلف را به ما ميدهد. اين كارها شامل پيشپردازش، پسپردازش و محاسبه نتايج شماي يادگيري روي هر مجموعه داده موجود ميشود. واسط در اين فصل توضيح داده شده است. وكا شامل چندين سطح مختلف است. ابتدا براي تمام آنها پيادهسازيهايي از الگوريتمهاي يادگيري كه شما ميتوانيد براي مجموعه دادهاي از خط توضيحات بهكار ببريد، فراهم ميكند. همچنين ابزارهاي گوناگوني براي ارسال مجموعه داده را شبيه الگوريتم گسستهسازي كه در فصل 7 تعريف شده را شامل ميشود. شما ميتوانيد مجموعه داده را پيشپردازش كنيد، آنرا در شماي يادگيري بهكار ببريد و يا ردهبند نتيجهگيري و اجراي آنرا تحليل كنيد. بهعنوان مثالي براي شروع كار، ما نحوه ارسال صفحه گسترده به مجموعه داده با يك شكل درست جهت پردازش و ساختن درخت تصميم از آن را توضيح ميدهيم. نحوه يادگيري براي ساختن درختهاي تصميم فقط يك شروع است. الگوريتمهاي فراوان ديگري براي كاوش وجود دارند. مهمترين اهميت نرمافزار از بين ويژگيهاي آن اين است كه بهصورت خودكار از كد اصلي توليد ميشود و بهصورت مختصر ساختار آن را منعكس ميكند. ک توزیع پارامتریک دارد.چنین روش هایی در فضاهایی با ابعاد زیاد خوب کار نمی کنند و پیدا کردن مدل حقیقی کار مشکلی است.برای غلبه بر این محدودیت ها، محققان به روش های غیر پارامتریک که از فاصله یک نقطه با نزدیک ترین همسایه اش به عنوان معیاری از غیر عادی بودن، استفاده می کنند،روی آوردند. تعریف رایج برون هشته ها بر اساس فاصله به صورت زیر است بالاترین نقاط داده هستند که فاصله آنها با K امین همسایه نزدیک شان بزرگ است.هنگامی که کارا بودن شناسایی برون هشته بر اساس فاصله اثبات شد ،این روال ادامه پیدا کرد تا از لحاظ زمانی به صرفه تر شود. در این مقاله الگوریتم RBRP ارائه شده است. RBRP یک الگوریتم دو فازه،برای کاوش برون هشته های مبتنی بر فاصله در پایگاه داده هایی با ابعاد زیاد است.RBRP ، n برون هشته بالا در پایگاه داده را که فاصله شان با k امین همسایه نزدیک زیاد است پیدا می کند.

فاز اول
هدف از فاز اول RBRP تقسیم پایگاه داده به بخش هایی است، طوریکه نقاطی که در فضا به هم نزدیک هستند به یک بخش نسبت داده شوند.این شیوه برای تقسیم پایگاه داده به بخش ها در الگوریتم زیر نشان داده شده است. این الگوریتم یک فرایند بازگشتی برای تقسیم خوشه بندی هرمی است. در هر مرحله به طور متناوب داده به k قسمت تقسیم می شود.این تقسیم بندی تکراری شبیه مرحله تقسیم بندی به کار رفته در K-means است. با k(در پیاده سازی 6 در نظر گرفته شده است) مرکز تصادفی شروع می شود(مرحله 1)و هر نقطه به نزدیک ترین مر کز نسبت داده می شودو k بخش ایجاد می شود (مرحله 5 -8) . بعد k مرکز برای این kبخش پیدا می شود (مرحله 10). فرایند تا حد مشخصی ادامه داده می شود. برای هر کدام از این بخشها اگر سایز آن بخش بزرگتر از حد آستا نه ای(binsize) تعریف شده توسط کاربرباشد ، فرایند به صورت بازگشتی تکرار میشود .(مرحله 13-14)این استراتژی ما را مطمئن می سازد که نقاطی که در فضا به هم نزدیک هستند در یک بخش قرارمی گیرند.فاز اول RBRP در تابع bin پیاده سازی شده است.

كد:

 Algorithm  RBRP phase 1

Procedure: Bin

Require: Binsize, the maximum size of a bin; k, the number of partitions; it , no. of iterations; D, data

points to be binned.

Ensure: B, the set of bins.

1: c = {c1, c2, . . . , ck} (the set of k random centers)

2: p = {p1, p2, . . . , pk} (the set of k partitions of D)

3: for it iterations do

4: Empty all k partitions in p

5: for each d in D do

6      : j = Closest(c, d)

 7     : Insert(d, j)

8: end for

9: c = {}

10: RecomputeCenters(c, p)

11: end for

12: for each pi in p do

 13   : if size of pi > Binsize then

 14        : Bin(Binsize, k, it,pi )

 15   : else

 16        : Reorganize data points in pi , ordered as per their projection along the principal component of pi

 17       : Add pi to B

 18    : end if

19: end for

Note:

Closest(c, d) returns the index of the nearest elements in c to d

Insert(d, j) inserts point d in j th partition in p

RecomputeCenters(c, p) inserts k centers of partitions in p into

فاز دوم

در فاز دوم RBRP به ترتیب هر بخش برای پیدا کردن تقریبا نزدیک تر ین همسایه ها یک نقطه داده پویش می شود برای پیدا کردن سریع نزدیک ترین همسایه ها در طی پویش ترتیبی، نقاط داده در هر بخش به ترتیب تصویرشان درجزء اصلی نقاط در بخش مرتب می شوند.که این کار در فایل asli.m در خطوط 71-91 پیاده سازی شده است. در فاز دوم RBRP در ابتدا برای هر نقطه شروع به جستجو برای پیدا کردن تقریبا نزدیک ترین همسایه های آن که در آن بخش قرار دارند می کنیم. (مرحله 7-14).اگر تمام بخش جستجو شود و K تقریبا نزدیک ترین همسایه ها پیدا نشوند به نزدیک ترین بخش بعدی می رویم.(مرحله 6)و جستجو را برای تقریبا نزدیک ترین همسایه ها ادامه می دهیم. جستجو به طور تکراری ادامه پیدا می کند تا زمانیکه k نزدیک ترین همسایه پیدا شوند.

كد:

Algorithm  RBRP phase 2

Procedure: Find outliers

Require: k, the number of nearest neighbors; n, the number of outliers to be returned; D, the set of data points.

Ensure: O, the set of outliers.

1: c = 0 (c is the cutoff threshold)

2: O = {}

3: for each bin b in B do

 4    : for each d in b do

   5       : Neighbors(d) = {}

 6         : for each t in B, ordered by increasing distance to b do

 7              : for each p in t such that p _= d do

 8                    : if |Neighbors(d)| < k or Distance(d, p) < Maxdist(d, Neighbors(d)) then

 9                         : Neighbors(d)=Closest(d, Neighbors(d) ∪ p, k)

10:                   end if

11:                    if |Neighbors(d)| ≥ k and c > Distance(p, d)) then

12:                         break

13:                    end if

14:              end for

15:        end for

16:     end for

17: O = TopOutliers(O ∪ b, n)

18: c = MaxThreshold(O)

19: end for

Note:

Maxdist(d, S) returns the maximum distance between d and an element in set S

Closest(d, S, k) returns the k nearest elements in S to d

TopOutlier(S, n) returns the top n outliers in S based on the distance to their kth nearest neighbor

فاصله بین دو نقطه در تابع distance محاسبه می شود.تابع closest ،K (که در اینجا 6 فرض شده است )نزدیک ترین همسایه های نقطه را پیدا می کند.تابع Topoutlier ،n (که در اینجا 30 فرض شده است) outlier که فاصله آنها با نزدیک ترین همسایه شان بزرگ تر است را برمی گرداند.خروجی دیگر Topoutlier حدآستانه برش است که فاصله ضعیف ترین outlier را از k امین همسایه اش را نشان می دهد.فاز دوم در تابع asli.m پیاده سازی شده است.خروجی برنامه آرایه Topout است که شامل 30 برون هشته است.