مسبی
یادگیری سریع داده کاوی با مطالعه 10 الگوریتم برتر به همراه شبه کد

یادگیری سریع داده کاوی با مطالعه 10 الگوریتم برتر به همراه شبه کد

ویرایش: 1396/3/9
نویسنده: farideh11

مقدمه

داده کاوی شامل بهره ­گيري از ابزارهاي آناليز داده ­هاي پيچيده براي كشف الگوهاي موجود و روابط ناشناخته‌ي ميان داده­ ها در حجمي وسيع مي­ باشد. اين ابزارها شامل مدلهاي آماري، الگوريتمهاي رياضي و متد­هاي يادگيري ماشين و الگوريتم هايي كه بازدهي خود را بصورت خودكار از طريق تجربه افزايش مي دهند، مانند شبكه هاي عصبي و درخت هاي تصميم گيري، مي باشد. نتيجتاً داده کاوی علاوه بر جمع آوري و مديريت داده‌ها، در بر گيرنده ي آناليز و پيش بيني­هايي نيز مي­باشد. داده کاوی مي­تواند بر روي داده­هاي ارائه شده در فرمهاي عددي، متني و يا چند رسانه­اي اعمال شود و کشف پولشویی و فساد مالی و بدست آوردن نتایج راهبردی جهت تصمیم گیری­های آینده از مهمترین کاربردهای آن می­باشد. داده کاوی یکی از پیشرفتهای اخیر در حوزه کامپیوتر برای اکتشاف عمقی داده­هاست. داده کاوی، اطلاعات پنهانی که برای برنامه ریزی­های استراتژیک می­تواند حیاتی باشد را آشکار می­سازد.

با گسترش روز افزون استفاده از بانکهای اطلاعاتی رابطه­ای و انبارهای داده جهت نگهداری اطلاعات شرکتها و سازمانها، همچنین اهمیت انکارناپذیر استفاده از رخدادها و اطلاعات گذشته جهت تصمیم گیری­های آینده، نیاز به استفاده از روشهایی علمی جهت تحلیل اطلاعات موجود و دریافت نتایج مورد نظر بیش از گذشته مورد توجه قرار گرفته است. با توسعه­ی کاربردی علم آمار، مفاهیم بنیادی داده کاوی مطرح شده و تحقیقات در این زمینه آغاز شد. نتایج حاصله عبارتند از روشها و الگوریتم­های متفاوت مطرح شده در این زمینه. آنچه پیش روی شما قرار گرفته، مروری بر الگوریتمهای داده کاوی است.
در تلاش برای شناسایی برخی از الگوریتمهای تاثیر­گذاری که به صورت گسترده­ای در جامعه داده­کاوی استفاده شده­اند، کنفرانس بین المللی IEEE در داده­ کاوی، 10 الگوریتم را در هنگ کنگ شناسایی کرده ­اند. در اینجا به بررسی 10 الگوریتم برتر داده کاوی منتخب کنفرانس بین المللی داده کاوی می­ پردازیم. الگوریتم­های C4.5،k  میانگین، ماشین بردار پشتیبان، اپریوری، بیشینه­ سازی امیدواری، رتبه بندی صفحه، آدا بوست، k امین نزدیکترین همسایه، ناوی بیزو کارت، 10 الگوریتم برتر در زمره پرقدرت ترین الگوریتم هایی هستند که در تحقیقات مورد استفاده قرار می­گیرند. این الگوریتم­ها حوزه­های پیوند کاوی، آنالیز تجمعی، آموزش آمار، خوشه بندی و طبقه بندی را پوشش می­دهند که همگی از مباحث بسیار مهم در تحقیقات داده کاوی محسوب می­شوند. سعی بر آن است که این الگوریتم­ها توضیح داده شده، نقاط قوت و ضعف آنها نیز مورد بررسی قرار گیرد.

2-   الگوریتم C4.5

1-2  مقدمه

یکی از ابزارهای معمول مورد استفاده در داده کاوی، سیستم­های طبقه­ بندی می­ باشند. چنین سیستم­هایی به عنوان ورودی مجموعه­ای از نمونه­ ها را می ­گیرند که هر یک متعلق به یکی از تعداد دسته­های کوچک و توضیحاتی درباره مقادیرش برای یک مجموعه ثابت است. خروجی، یک طبقه ­بندی کننده میتواند با دقت پیش­ بینی کند که یک نمونه جدید به کدام کلاس متعلق است. C4.5 طبقه بندی­ها را بر اساس درخت­های تصمیم­گیری بیان می­کند. این الگوریتم هم قادر به ساختن درخت تصمیم و هم مجموعه ای از قوانین می­باشد. این مدل با شاخه کردن نمونه بر اساس فیلدی که بیشترین اطلاعات در هر مرحله بدست می­آورد، کار می­کند. فیلد نهایی باید به صورت طبقه­بندی باشد. همچنین امکان اینکه در هر مرحله هر یک از شاخه ها به بیش از دو زیر گروه تقسیم شوند نیز وجود دارد 

2-2   طبقه­ بندی کننده­­های مجموعه قوانین

C4.5 يک معيار استاندارد در يادگيري ماشين است. انتخاب صفت در ID3 و C4.5 بر اساس حداقل کردن مقياس اطلاعات در يک گره است. هر مسير از ريشه به سمت يک گره، نمايان­گر يک قانون دسته­بندي مي­باشد.

درک درخت­های تصمیم­ گیری پیچیده ممکن است مشکل باشد، برای مثال اطلاعات یک کلاس معمولا در طول درخت پخش شده است. C4.5 یک جانشین فرمالیته متشکل از یک لیست از قوانین به شکل “if A and B and C and ... then class X” را تولید می­کند که در آن قوانین هر کلاس باهم گروه بندی شده­اند. یک نمونه براساس اولین قانون پیدا شده­ای که شرایط نمونه را ارضا می­کند طبقه­بندی می­شود; اگر هیچ قانونی شرایط نمونه را ارضا نکند، مورد به کلاس پیش­فرض اختصاص می­ یابد.

مجموعه قوانین C4.5 از درخت تصمیم اولیه (هرس نشده) ساخته می­شوند. انتخاب صفت در C4.5 بر اساس حداقل کردن مقياس اطلاعاتدر يک گره است. هر مسير از ريشه به سمت يک گره، نمايان­گر يک قانوندسته­بندي مي­باشد. تئوري بر اين اساس است که تعداد آزمون­هايي که باعثمي­شود يک نمونه جديد در داخل پايگاه داده، دسته­بندي شود، حداقل گردد. پيچيدگي درخت تصميم به شدت وابسته به مقدار اطلاعاتي است که با آن صفت درارتباطند. با انتخاب آن صفت، اطلاعات بيشتری از صفات ديگر،جدا و تقسيممي­شود. الگوريتم اصولا صفتي که حداکثر توان جداسازي بين دسته­ها را دارد،انتخاب مي­کند و درخت تصميم را بر اساس آن مي­سازد. توليد درخت تصميماوليه از روي مجموعه داده­اي، مهم­ترين بخش الگوريتم C4.5مي­باشد. الگوريتم در نهايت يک دسته­بندی را در قالب يک درخت تصميم توليد مي­کند کهداراي دو نوع گره است: يک گره به صورت برگ که يک دسته را مشخص مي­کند و يکگره تصميم که آزمون­هايي روي يک صفت انجام مي­دهد تا يک شاخه يا زير درختبه عنوان خروجي آزمون توليد شود. همچنین درخت­های مشابه­، به صورت بازگشتيبه هر زير مجموعه از نمونه­ها اعمال مي­شود. اين رويه ادامه مي­يابد تا زيرمجموعه­ها شامل نمونه­هايي باشند که همگی به يک دسته تعلق داشته باشند. فرآيند ساخت درخت، يک فرآيند واحد نمي­باشد. متاسفانه، مشکل پيدا کردنکوچکترين درخت تصميم از روي يک نمونه داده­اي مساله­اي NP-Complete است. بنابراين، بايد روش­هاي ساخت درخت غير عقب­گرد باشند و به صورت حريصانه عمل نمايند.

C4.5درخت اولیه را با استفاده از الگوریتم­های تقسیم و غلبه (بازگشتی) و با یک مجموعه از نمونه­های داده شده­ی S، به شرح زیر تولید می کند:

  • اگر تمام نمونه­ها در S متعلق به یک کلاس باشند، درخت، یک برگ با برچسب کلاس پرتکرار[1] در S خواهد بود.
  • در غیر این صورت، یک تست بر اساس یک صفت واحد با دو یا چند نتیجه انتخاب کنید. برای هر نتیجه از تست، یک شاخه به ریشه درخت اضافه کنید و بر اساس نتیجه برای هر نمونه، S را به زیر مجموعه­های s1, s2, … پارتیشن­بندی کنید و همان روش بازگشتی را برای هر زیر مجموعه اعمال کنید و گره­های حاصله را فرزندان گره قبلی قرار دهید. شکل 2-1 شبه کد الگوریتم C4.5  ]2[ را نشان می­دهد:

Algorithm C4.5(D)

Input: an attribute-valued dataset D

1: Tree={}

2: if D is “pure” OR other stopping criteria met then

3:   terminate

4: end if

5: for all attribute aÎD do

6:   compute information-theoretic criteria if we split on a

7: end for

8: atest = Best attribute according to above computed criteria

9: Tree = create a decision node that tests atest in the root

10: Dp = induced sub-dataset from D based on atest

11: For all Dp do

12:      Treep = C4.5(Dv)

13:      Attach treep to the corresponding branch of  Tree

14: end for

15: return Tree    

شکل (2-1) شبه کد الگوریتم C4.5.

الگوريتم C4.5 دامنه دسته ­بندي را علاوه بر صفات قياسي در انواع صفات عددي نيز توسعه مي­دهد. برای جلوگیری از اتصالات بیشتر ، درخت تصمیم اولیه باید هرسشود. برای هرس کردن درخت  C4.5 پس از ساختن درخت، یک بار به عقب برمی­گردیم و انشعاب­های بی­فایده را با جایگزین کردن گره برگ بجای آنها، حذف می­کنیم. الگوریتم هرس بر اساس یک برآورد بدبینانه از میزان خطا(E)  در ارتباط با مجموعه­ای با N نمونه است که در آن E متعلق به یک کلاس پرتکرار نمی­باشد، است. C4.5 بجای E/N ، که E واقعه در N آزمایش مشاهده شده­اند، حد بالایی از احتمال دو جمله­ای را با استفاده از اطمینان که توسط کاربر مشخص شده است و مقدار پیش­فرض آن 0.25 است، تعیین می ­کند.

هرس کردن از برگ به ریشه انجام می­شود. خطای برآورد شده در یک برگ با N نمونه و E خطا، همانگونه که در بالا مشاهده شد، N برابر نسبت خطای بدبینانه است. C4.5 برای یک زیر درخت، خطاهای تخمینی شاخه ­ها را جمع می­کند و آنرا با خطای تخمینی مقایسه می­کند در صورتی زیر درخت با یک برگ جایگزین می­شود که: اگر دومی بیشتر از اولی نباشد آنگاه زیر درخت هرس می­شود. بطور مشابه C4.5 خطاهای تخمینی را بررسی می­کند و در صورتی یک زیر درخت با یکی از شاخه­هایش جایگزین می­شود که آن به نفع درخت باشد. الگوریتم هرس کردن در یک گذر از درخت کامل می­شود.

3    الگوریتم k میانگین

1-3   مقدمه

این الگوریتم یک متد ساده تکرار شونده است، برای خوشه­ بندی مجموعه­ای از داده­های در اختیار در تعداد مشخصی خوشه (k) که کابر تعیین می­کند. این الگوریتم توسط محققین مختلف و به صورت­های مختلفی ارائه شده است . در این الگوریتم داده­ها در گروه­های مجزا خوشه­بندی می­شوند. این الگوریتم تعداد مشخصی خوشه را تعریف می­کند و به طور مکرر داده­ها را درون این خوشه­ها قرار می­دهد و مرکز خوشه را هر بار تعیین می­کند تا جایی که دیگر امکان بهبود بیشتری وجود نداشته باشد. به جای پیش­بینی کردن مقدار خروجی، الگوریتم  kمیانگین از پروسه­ای استفاده می­کند که به دنبال یافتن الگوهایی در بین داده ­های ورودی است.

در اجرای الگوریتم  kمیانگین  اولین کار مشخص کردن  k یا همان تعداد خوشه ­ها در الگوریتم k میانگین است. براي اين الگوريتم شکلهاي مختلفي بيان شده است. ولي همة آنها داراي روالي تکراري هستند که براي تعدادي ثابت از خوشه‌ها سعي در تخمين موارد زير دارند:

  • بدست آوردن نقاطي به عنوان مراکز خوشه‌ها; اين نقاط در واقع همان ميانگين نقاط متعلق به هر خوشه هستند.
  • نسبت دادن هر نمونه داده به يک خوشه; که آن داده کمترين فاصله تا مرکز آن خوشه را دارا باشد.

در نوع ساده‌اي از اين روش ابتدا به تعداد خوشه‌‌هاي مورد نياز نقاطي به صورت تصادفي انتخاب مي‌شود. سپس داده‌ها، با توجه به ميزان نزديکي (شباهت) به يکي از اين خوشه‌ها نسبت داده‌ مي‌شوند و بدين ترتيب خوشه‌هاي جديدي حاصل مي‌شود. با تکرار همين روال مي‌توان در هر تکرار با ميانگين‌گيري از داده‌ها مراکز جديدي براي آنها محاسبه کرد و مجددا داده‌ها را به خوشه‌هاي جديد نسبت داد. اين روند تا زماني ادامه پيدا مي‌کند که ديگر تغييري در داده‌ها حاصل نشود. تابع زير به عنوان تابع هدف مطرح است.

-2   توصیف الگوریتم

الگوريتم زير الگوريتم پايه براي اين روش محسوب مي‌شود:

  • در ابتدا k نقطه به عنوان به نقاط مراکز خوشه‌ها انتخاب مي‌شوند.
  • هر نمونه داده به خوشه‌اي که مرکز آن خوشه کمترين فاصله تا آن داده را داراست، نسبت داده‌ مي‌شود.
  • پس از تعلق تمام داده‌ها به يکي از خوشه‌ها، براي هر خوشه يک نقطه جديد به عنوان مرکز محاسبه مي‌شود (ميانگين نقاط متعلق به هر خوشه).

مراحل 2 و 3 تکرار مي‌شوند تا زماني که ديگر هيچ تغييري در مراکز خوشه‌ها حاصل نشود. در این صورت الگوریتم تمام می­شود.

اجرای الگوریتم به صورت نمایشی در شکل (3-1) آمده است. توجه کنید که هر تکرار الگوریتم به N*K مقایسه احتیاج دارد که پیچیدگی زمانی هر تکرار را تعیین می­کند. تعداد تکرارها برای همگرایی، متفاوت است و به مقدار N بستگی دارد ولی در اولین بار این الگوریتم به صورت خطی عمل می­کند.

هر موقع که تغییری در مرحله انتساب داده یا مرحله جابجایی میانه وجود دارد، نزدیکی کاهش خواهد یافت و از این رو همگرایی در یک تعداد متناهی از تکرار تضمین شده است. در واقع این الگوریتم به مکان هسته مرکزی اولیه بسیار حساس است.

شکل (3-1) جواب­های نا­مطلوب برای هر سه انتخاب مختلف میانه را نشان می­دهد. مساله نزدیکی محلی می­تواند با اجرای چند­باره الگوریتم با نقاط مختلف و یا با اعمال محدودیت جستجو در مورد همگرایی، جواب داده شود (شکل 3)-2)(.
الگوریتم k میانگین، بیشترین استفاده را در عمل تقسیم­بندی خوشه­ها دارد. این الگوریتم ساده، قابل فهم و بطور منطقی مقیاس­پذیر است و می­توان آنرا به سادگی اصلاح کرد تا با سناریوهای مختلف مانند شبه مشاوره و داده­های جاری سروکار داشته باشد. پیشرفت­ها و کلیت­های مداوم الگوریتم پایه، ارتباط مداوم آنرا تضمین می­کند و بتدریج بر تاثیر گذاری آن افزوده است

 4-  الگوریتم ماشین بردار پشتیبان

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

در ماشین بردار پشتیبان یک داده به صورت یک بردار P بعدی (یا یک لیست از P عدد) دیده می­شود و ما می­خواهیم بدانیم که آیا می­توان چنین نقاطی را با یک ابرصفحه P-1 بعدی جدا کرد. این عمل، جداسازی خطی نامیده می­شود. ابرصفحه­ های بسیاری وجود دارند که می­توانند داده ­ها را جدا کنند. سوال اینجاست که چه ابرصفحه ای را انتخاب کنیم.

مفهوم آموزشی که اشیا بتوانند به عنوان نقاط در یک فضای با ابعاد بالا دسته­بندی شوند و پیدا کردن خطی که آنها را جدا کند منحصر به فرد نیست. آنچه ماشین بردار پشتیبان را از سایر جداکننده­ها متمایز می­کند چگونگی انتخاب ابرصفحه است. در ماشین بردار پشتیبان، ماکزیمم کردن حاشیه بین دو کلاس مدنظر است. بنابراین ابرصفحه­ای را انتخاب می­کند که فاصله­ی آن از نزدیکترین داده­ها در هر دو طرف جداکننده­ی خطی، ماکزیمم باشد. اگر چنین ابرصفحه­ای وجود داشته باشد، به عنوان ابرصفحه ماکزیمم حاشیه شناخته می­شود. شکل (4-1) این مفهوم را به صورت بصری نشان می­دهد.  برای ساخت ماکزیمم حاشیه، دو صفحه مرزی موازی با صفحه جداکننده رسم کرده آن دو را آنقدر از هم دور می­کنیم که به داده­ها برخورد کنند. صفحه جداکننده­ای که بیشترین فاصله را از صفحات مرزی داشته باشد، بهترین جداکننده خواهد بود.تابع تصمیم­ گیری برای جداکردن داده­ها با یک زیرمجموعه­ای از مثال­های آموزشی، که بردارهای پشتیبان (نزدیک­ترین داده­های آموزشی به ابرصفحه جداکننده) نامیده می­شوند، تعیین می­شود. در واقع ابرصفحه بهینه در ماشین بردار پشتیبان که در شکل (4-2) نشان داده شده است، جداکننده­ای بین بردارهای پشتیبان است.

در صورت استفاده مناسب از ماشین بردار پشتیبان این الگوریتم قدرت تعمیم خوبی خواهد داشت. علی رغم ابعاد زیاد، از سرریز شدن پرهیز می­کند. همچنین به دلیل استفاده از بردارهای پشتیبان به جای کل داده­ها، این الگوریتم فشرده سازی اطلاعات را نیز انجام می­دهد. هدف این دسته از الگوریتم­ها تشخیص و متمایز کردن الگوهای پیچیده در داده­ها (از طریق کلاسترینگ، دسته بندی، رنکینگ، پاکسازی و غیره) و پيدا کردن تمام صفحات در فضاي p بعدي است که نمونه‌هاي مثبت و منفي را با بيشترين حاشيه از هم جدا می­كنند.

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

یک ابرصفحه، یک زیرفضای k بعدی در یک فضای n بعدی تعریف می­کند که k<n. مثلا خط یک ابرصفحه یک بعدی در یک فضا با هر تعداد بعد است. در سه بعد، صفحه یک ابرصفحه دوبعدی است و به همین ترتیب برای فضاهای با ابعاد بالاتر ابرصفحه تعریف می­شود. بطور هندسی مرز با کمترین فاصله بین نزدیکترین داده و نقطه­ای روی ابرصفحه مطابقت می­کند. همین ترتیب هندسی به ما اجازه می­دهد تا کشف کنیم که چگونه مرزها را بیشینه کنیم.

4-4     ماشین بردار پشتیبان غیر خطی

مجموعه داده­هایی که به طور خطی قابل جداسازی هستند با مقداری نویز خوب کار می­کنند. اما اگر مجموعه داده ما خیلی پیچیده بود چه؟

این مجموعه داده را نمی­توان به سادگی با یک خط دسته­بندی کرد. در این موارد از نگاشت به فضایی با ابعاد بالاتر (شکل (4-6)) استفاده می­شود.

ایده­ی اصلی نگاشت به فضای بالاتر( فضای ویژگی) انتقال x به فضای بالاتر برای راحتی جداسازی است:

  • فضای ورودی: فضای x
  • فضای ویژگی : فضای   j(xi)

چرا انتقال می دهیم؟

  • عملگرهای خطی در فضای ویژگی معادل عملگرهای غیرخطی در فضای ورودی هستند در نتیجه با نگاشت تغییری در مساله ایجاد نمی­کنیم.
  • جداسازی با انتقال مناسب راحت­تر است.

برای انتقال ابتدا تابع  j(x)را برای نگاشت به فضای دیگر، پیدا می­کنیم. سپس فرمول ماشین بردار پشتیبانی به صورت زیر تغییر می­یابد:

فضای نگاشت اصلی همواره می­تواند به فضای ویژگی با ابعاد بالاتر دیگری که در آن، مجموعه آموزشی قابل جداسازی باشد، نگاشت یابد. انجام محاسبات در فضای ویژگی چون ابعاد بیشتری دارد می­تواند پرهزینه باشد. در حالت کلی این فضا بی­نهایت است. برای غلبه بر این مشکل از حقه کرنل[1] استفاده می­شود.

 4-5             تابع کرنل

تابع کرنل، یک جداکننده خطی متکی بر ضرب داخلی بردارهاست که به صورت :

می­باشد. اگر نقاط با استفاده از انتقال   به فضای ویژگی (فضای با ابعاد بالاتر) انتقال یابند، ضرب داخلی آنها به صورت :

 تبدیل خواهد شد.

یک تابع کرنل تابعی است که مطابق یک ضرب داخلی در فضای ویژگی است. بنابراین ما از محاسبه­ی (x)φخود­داری کرده و به جای آن از تابع کرنل استفاده می­کنیم.

انتخاب کرنل­های غیرخطی به ما اجازه­ی ساخت جداکننده­های خطی در فضای ویژگی را می­دهد در صورتی که آنها در فضای اصلی غیرخطی هستند. با استفاده از توابع کرنل مساله به فرم زیر تبدیل خواهد شد:

4-6    ماشین بردار پشتیبان چند کلاسی[1]

یکی از مشکلات ماشین بردار پشتیبان، پیچیدگی محاسباتی آن است. با این حال این مشکل بطور قابل قبولی حل شده است. ماشین بردار پشتیبان اساسا یک جداکننده دودویی است. برای مسائل چند کلاسی، رهیافت کلی، کاهش مساله­ی چند کلاسی به چندین مساله دودویی است. هریک از مسائل با یک جداکننده دودویی حل می­شود. سپس خروجی جداکننده­های دودویی ماشین بردار پشتیبان با هم ترکیب شده و به این ترتیب مساله چند کلاس حل می­شود.

 4-7    کاربردهای ماشین بردار پشتیبان

  • در اقتصاد
  • پیش­بینی رکود
  • تشخیص صورت
  • دسته­بندی و کاهش ویژگی برای تشخیص سریع صورت
  • انتخاب ژن در دسته­بندی سرطان
  • شناسایی گفتار
  • شناسایی الگو
  • ...

4-8   خلاصه

  1.  ماتریس الگو را آماده می­کنیم.
  2.  تابع کرنلی را برای استفاده انتخاب می­کنیم.
  3.  پارامتر تابع کرنل و مقدار C را انتخاب می کنیم.
  4.  برای محاسبه­ی مقادیرai ، الگوریتم آمورشی را با استفاده از حل کننده­های برنامه نویسی درجه دو اجرا می­کنیم.
  5.  داده­های جدید با استفاده از مقادیر ai   و بردارهای پشتیبان می­توانند دسته­بندی شوند.

 4-9   مزایا و معایب ماشین بردار پشتیبان

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


 5    الگوریتم اپریوری

5-1  مقدمه

بسیاری از الگوریتم­های الگویاب، از قبیل الگوریتم­هایی که برای ساختن درخت تصمیم­گیری، استنتاج قوانین دسته­بندی و جمع­بندی داده­ها که زیاد در استخراج اطلاعات استفاده می­شوند، در جامعه تحقیق یادگیری ماشین گسترش یافته­اند. الگوی مکرر و استخراج قوانین مرتبط، یکی از معدود استثنائات این شیوه است ]2[. این الگوریتم در سال 1996 توسط چنگ  ابداع شد و یکی از مهمترین یافته­ها در تاریخ استخراج قوانین وابستگی می­باشد. یکی از محبوب­ترین دیدگاه­های استخراج اطلاعات، یافتن یک الگوی مکرر از یک مجموعه داده اجرایی و استخراج قوانین مرتبط است. یافتن الگوی مکرر (الگویی با فراوانی برابر یا بیشتر از حداقل پشتیبانی) ساده نیست و این بدلیل پیچیدگی محاسبات حاصل از انفجارهای ترکیبی است. وقتی یکبار الگوی مکرر بدست آید، ایجاد قوانین مرتبط با اطمینانی برابر یا بیشتر از حداقل اطمینان آسان خواهد بود.

5-2  الگوریتم

فرض کنید ابتدا باید تمام مجموعه­های تک عضوی مکرر را پیدا کنید، سپس براساس آن مجموعه­های دو عضوی مکرر را پیدا کنید و ... .

بنابراین در هر مرحله باید کل فضا جستجو شود اما این الگوریتم از یک خصوصیت به نام خصوصیت اپریوری استفاده می­کند، به این صورت ­که اگر یک مجموعه­ای از عناصر مکرر باشد، تمام زیر مجموعه­های غیر تهی آن نیز مکرر خواهند بود. مثلا" اگر مجموعه A نامبرده شده در زیر مکرر باشد، آن­گاه مجموعه­های زیر نیز مکرر هستند.

A= {Milk, Bread, Cigarettes}, {Milk, Bread}, {Milk, Cigarettes}, {Bread, Cigarettes} {Milk},{Bread},{Cigarettes}

این خصوصیت را این­گونه نیز می­توان توصیف کرد که اگر مجموعه­ی I به یک تعداد مرتبه تکرار شده باشد، اگر A را نیز به آن اضافه کنیم تعداد تکرار مجموعه­ی جدید از تعداد تکرار مجموعه­ی قبلی بیشتر نخواهد بود. پس اگر اولی مکرر نباشد دومی هم مکرر نخواهد بود. اما این الگوریتم چگونه از این خصوصیت استفاده می­کند؟ در اینجا عملکرد آن­را شرح می­دهیم:

می­دانیم که از LK-1یعنی یک زیرمجموعه K-1 عضوی برای بدست آوردن LK، یعنی مجموعه­های K عضوی استفاده می­شود. این کار در دو مرحله صورت می­گیرد، ابتدا باید مجموعه­ای از اعضا پیدا شود، که با LK-1  برای به دست آوردن LK  ترکیب شود. این مجموعه از عناصر را CK  نامیده و مرحله به دست آوردن آن را مرحله پیوست می­نامیم. مرحله بعد اضافه کردن این عناصر به مجموعه­های قبلی است که آن را مرحله هرس می­نامیم ]1[.

  • ·مرحله پیوست

ابتدا باید مطمئن شویم که عناصر بر مبنای ترتیب حروف الفبا مرتب شده باشند. LK-1 ها را با li و اعضای آنها را به صورت li[j] نشان می­دهیم. اگر K-2 عنصر اول آنها با یکدیگر برابر باشند، آنگاه دو مجموعه­ی LK-1 با یکدیگر قابل پیوست هستند، یعنی داشته باشیم:

)l1[1] = l2[1] ) ^ (l1[2] = l2[2]) ^ … (l1[k-2] = l2[k-2]) ^ (l1[k-1] < l2[k-1])

توجه کنید که دو عنصر آخر به ترتیب مرتب شده­اند و از وجود عناصر تکراری جلوگیری می­کنند. اجتماع دو مجموعه­ی قابل پیوست، ترکیب را به وجود می­آورد (البته مرتب از نظر الفبایی).

با این روش ترکیب، مجموعه حاصل K عضو خواهد داشت، که البته عنصر آخر از نظر ترتیبی از مجموعه دوم خواهد بود.



6  الگوریتم بیشینه­سازی امیدواری 

6-1    مقدمه

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

ترکیب توابع تعمیم یافته­ی متناهی، یک روش انعطاف­پذیر ریاضی را برای مدلسازی و دسته­بندی داده­هایی که به عنوان پدیده تصادفی مشاهده شده­اند، ارائه می­دهد. در اینجا به استفاده­ی بیشینه سازی امیدواریجهت پردازش ترکیب توابع تعمیم یافته­ی متناهی از طریق روش حداکثر احتمال متمرکز می­شود ]2 .[

6-2   توصیف الگوریتم بیشینه سازی امیدواری

 مجموعه داده­های مشاهده شده را به صورت  که مستقل از هم هستند و مجموعه داده­های نامرئی را به صورت  و کل داده­ها را به صورت در نظر می­گیریم. الگوریتم بیشینه سازی امیدواری با فرض بیشینه نزدیکی (ML)  می­گردد که  را بیشینه کند. این امید ریاضی روی توزیع احتمال X که توسط پارامترهای معلوم  اندازه گیری می­شود. الگوریتم بیشینه سازی امیدواری برای تخمین توزیع احتمالی روی X به جای پارامترهای واقعی  از فرض فعلی  استفاده می­کند. تابع  را به گونه­ای تعریف می­کنیم که  را به صورت تابعی از  تعریف کند. با فرض  و اینکه داده­های Y از کل داده­های X مشاهده شده­اند، داریم :

(6-1)

الگوریتم بیشینه سازی امیدواری یک الگوریتم تکراری است که هر تکرار آن دو مرحله دارد: مرحله تخمین[1] و مرحله بیشینه سازی[2][1] .

مرحله 1 : مرحله تخمین: با استفاده از مقدار فرض فعلی  و داده­های مشاهده شده Y مقدار  را محاسبه می­کند تا توزیع احتمالی روی X را تخمین زند .

مرحله 2 : مرحله بیشینه سازی: فرض  را با فرض  ای جایگزین می­کند که تابع Q را بیشینه کند.

                                     (6-2)

در چارچوب داده­های ناقص الگوریتم بیشینه سازی امیدواری، نشان دهنده بردار داده­های مشاهده شده و z نشان دهنده بردار داده­های ناقص است، بردار­های کامل به این صورت بیان می­شود که در آن توان T ، نشان دهنده بردار ترانهاده است:

(6-3)                           

الگوریتم بیشینه سازی امیدواری به مشکل حل عملیات اطلاعات ناقص معادله ممکن نزدیک می­شود. این کار را غیر مستقیم و با پیشرفت تکراری، با توجه به عملیات ممکن "داده های کامل" یا عملیات  انجام می­دهد. از آنجائیکه این کار به وضوح به داده­های غیر قابل مشاهده z بستگی دارد، مرحله تخمین طوری صورت می­گیرد که در آن لگاریتم  توسط عملیات Q جایگزین می­شود و از اندازه اخیر استفاده می­کند. بطور ویژه در (k+1) امین تکرار الگوریتم بیشینه سازی امیدواری، مرحله تخمین به این صورت عمل می کند:

(6-4)

که در آن  امید ریاضی را با استفاد از بردار واحد نشان می­دهد. مرحله بیشینه سازی، تخمین Ψ را بوسیله­ی ارزش (k+1)Ψ  بروز می­کند. مراحل تخمین و بیشینه سازی بطور متوالی جابجا می­شوند تا تغییرات ارزش­های الگوریتم محتمل کمتر از برخی آستانه­های مشخص شده باشند.

همانطور که اشاره شد، الگوریتم بیشینه سازی امیدواری، برای افزایش تکرار هر یک از بیشینه سازی­های امید ریاضی، ثابت و به صورت زیر است:

(6-5)         

می­توان نشان داد که مراحل تخمین و بیشینه سازی شکل­های ساده­ای دارند در حالیکه عملیات چگالی محتمل داده­های کامل از یک خانواده نمایی است. معمولا در عمل، راه­حل مرحله بیشینه سازی به شکل محدود وجود دارد. در آن نمونه­ها که این راه­حل وجود ندارد ممکن است نتوان برای یافتن ارزش Ψ که در کل، عملیات  را حداکثر می­کند تلاش کرد. برای چنین شرایطی ممکن است یک الگوریتم بیشینه سازی امیدواری کلی[3] انتخاب شود که در آن مرحله­ی تخمین نیازمند این باشد که  (k+1) Ψ طوری انتخاب شود که (k+1) Ψ عملیات Q،  را بر ارزش موجود در (k)Ψ =Ψ  افزایش دهد یعنی

 برخی ازموانع الگوریتم بیشینه سازی امیدواری عبارتند از:

  • این الگوریتم خود بخود اندازه ماتریس واریانس اندازه­های واحد را تولید نمی­کند. با این حال این مشکل را می­توان به سادگی از روش درست مربوط به الگوریتم بیشینه سازی امیدواری از بین برد.
  • گاهی اوقات همگرایی بسیار آهسته صورت می­گیرد.
  • در برخی مسائل، مراحل تخمین و بیشینه سازی می­توانند از هم جدا شوند.

تاکنون نمونه­های زیادی از الگوریتم بیشینه سازی امیدواری دیده­ایم، که هرکدام شامل محاسبة مقادیر موردانتظار متغیرهای پنهان برای هر مثال و سپس محاسبة دوباره مقدار پارامترها بوده است. برای انجام این کار از مقادیر موردانتظاری استفاده کردیم که گویی مشاهده شده بودند.

7 الگوریتم رتبه­ بندی صفحه

رتبه­بندی صفحه یک رتبه­دهی استاتیک به صفحات وب است که مقدار مربوط به هر صفحه به صورت آفلاین محاسبه می­شود و همچنین این الگوریتم مستقل از پرس­و­جو است. محاسبه­ی رتبه­بندی یک صفحه بر اساس ایده­ی محاسبه اعتبار[1] یک عامل در شبکه اجتماعی[2] است.

پیوند ورودی[3] صفحه i، پیوندهایی است که از صفحات دیگر به صفحه i اشاره می­کند. معمولا پیوندهایی که از صفحات درون سایت صفحه i می­رسند، محاسبه نمی­شود.

پیوند خروجی[4] صفحه i، پیوندهایی است که از صفحه i به سایر صفحات اشاره می­کند. معمولا پیوندهای به صفحات درون سایت صفحه i محاسبه نمی­شود.

بر اساس مفهوم اعتبار در شبکه اجتماعی می­توان موارد زیر را مطرح کرد:

  1. وجود یک پیوند از یک صفحه به صفحه دیگر بطور ضمنی نشان­دهنده نفوذ[5] صفحه مقصد است. بنابراین پیوند ورودی بیشتر برای صفحه i نشان­دهنده نفوذ بیشتر این صفحه است.

2. صفحاتی که به i اشاره می­کنند خود نیز دارای اعتبارهای متفاوتی هستند. پیوند رسیده از یک      صفحه با اهمیت بالاتر ارزش بیشتری نسبت به پیوند رسیده از یک صفحه با ارزش کمتر دارد. می­توان نتیجه گرفت که صفحه­ای مهم است که از صفحات مهم دیگر پیوند گرفته باشد.

بر اساس مفاهیم مطرح شده درباره اعتبار در شبکه­های اجتماعی، امتیاز رتبه بندی صفحه i  برابر با مجموع امتیاز رتبه بندی صفحاتی است که به i پیوند داده­اند. از طرفی، چون ممکن است یک صفحه به تعداد زیادی صفحه پیوند داده باشد، پس باید امتیاز رتبه­بندی آن بین تمام این صفحات تقسیم شود.

برای فرموله کردن این ایده، وب را به عنوان یک گراف جهتدار G=(V,E) فرض می­کنیم که V مجموعه گره­ها یعنی تمام صفحات موجود در وب و E نیز مجموعه یال­ها یعنی پیوند بین صفحات است. فرض می­کنیم که تعداد صفحات در وب n است یعنی . حال رتبه­بندی صفحه i یعنی P(i) به شکل زیر محاسبه می­شود: که Oj تعداد پیوندهای خروجی صفحه j است. در این حالت در واقع ما دارای n معادله با n مجهول، یعنی رتبه­بندی صفحات، هستیم. حال از یک ماتریس برای نمایش تمام معادله­ها استفاده می­کنیم. P را به عنوان یک بردار ستونی n بعدی از مقادیر رتبه­بندی صفحه در نظر می­گیریم:

                        (7-1)                                                                                                                 

1/Oi if (i,j) E

 

همچنین A را به عنوان ماتریس همسایگی گراف وب در نظر می­گیریم که:

0   otherwise

 

Aij=

حال سیستم n معادله را می­توان به صورت زیر نوشت:

(7-2)                                                                                                                                                             



منبع: http://www.cs.umd.edu/~samir/498/10Algorithms-08.pdf
امتیاز دهی به مقاله




نظرات   (0 نظر)
مرتب سازی بر اساس:

 

ثبت نظر:

شما می توانید درباره یادگیری سریع داده کاوی با مطالعه 10 الگوریتم برتر به همراه شبه کد نظر دهید یا سوال بپرسید:

نام و نام خانوادگی:

 

کلمات کلیدی: داده کاوی ، K میانگین ، ماشین بردار پشتیبان ، بیشینه سازی امیدواری ، اپریوری ، آدابوست ، ناوی بیز ، الگوریتمهای داده کاوی