داده کاوی شامل بهره گيري از ابزارهاي آناليز داده هاي پيچيده براي كشف الگوهاي موجود و روابط ناشناختهي ميان داده ها در حجمي وسيع مي باشد. اين ابزارها شامل مدلهاي آماري، الگوريتمهاي رياضي و متدهاي يادگيري ماشين و الگوريتم هايي كه بازدهي خود را بصورت خودكار از طريق تجربه افزايش مي دهند، مانند شبكه هاي عصبي و درخت هاي تصميم گيري، مي باشد. نتيجتاً داده کاوی علاوه بر جمع آوري و مديريت دادهها، در بر گيرنده ي آناليز و پيش بينيهايي نيز ميباشد. داده کاوی ميتواند بر روي دادههاي ارائه شده در فرمهاي عددي، متني و يا چند رسانهاي اعمال شود و کشف پولشویی و فساد مالی و بدست آوردن نتایج راهبردی جهت تصمیم گیریهای آینده از مهمترین کاربردهای آن میباشد. داده کاوی یکی از پیشرفتهای اخیر در حوزه کامپیوتر برای اکتشاف عمقی دادههاست. داده کاوی، اطلاعات پنهانی که برای برنامه ریزیهای استراتژیک میتواند حیاتی باشد را آشکار میسازد.
با گسترش روز افزون استفاده از بانکهای اطلاعاتی رابطهای و انبارهای داده جهت نگهداری اطلاعات شرکتها و سازمانها، همچنین اهمیت انکارناپذیر استفاده از رخدادها و اطلاعات گذشته جهت تصمیم گیریهای آینده، نیاز به استفاده از روشهایی علمی جهت تحلیل اطلاعات موجود و دریافت نتایج مورد نظر بیش از گذشته مورد توجه قرار گرفته است. با توسعهی کاربردی علم آمار، مفاهیم بنیادی داده کاوی مطرح شده و تحقیقات در این زمینه آغاز شد. نتایج حاصله عبارتند از روشها و الگوریتمهای متفاوت مطرح شده در این زمینه. آنچه پیش روی شما قرار گرفته، مروری بر الگوریتمهای داده کاوی است.
در تلاش برای شناسایی برخی از الگوریتمهای تاثیرگذاری که به صورت گستردهای در جامعه دادهکاوی استفاده شدهاند، کنفرانس بین المللی IEEE در داده کاوی، 10 الگوریتم را در هنگ کنگ شناسایی کرده اند. در اینجا به بررسی 10 الگوریتم برتر داده کاوی منتخب کنفرانس بین المللی داده کاوی می پردازیم. الگوریتمهای C4.5،k میانگین، ماشین بردار پشتیبان، اپریوری، بیشینه سازی امیدواری، رتبه بندی صفحه، آدا بوست، k امین نزدیکترین همسایه، ناوی بیزو کارت، 10 الگوریتم برتر در زمره پرقدرت ترین الگوریتم هایی هستند که در تحقیقات مورد استفاده قرار میگیرند. این الگوریتمها حوزههای پیوند کاوی، آنالیز تجمعی، آموزش آمار، خوشه بندی و طبقه بندی را پوشش میدهند که همگی از مباحث بسیار مهم در تحقیقات داده کاوی محسوب میشوند. سعی بر آن است که این الگوریتمها توضیح داده شده، نقاط قوت و ضعف آنها نیز مورد بررسی قرار گیرد.
یکی از ابزارهای معمول مورد استفاده در داده کاوی، سیستمهای طبقه بندی می باشند. چنین سیستمهایی به عنوان ورودی مجموعهای از نمونه ها را می گیرند که هر یک متعلق به یکی از تعداد دستههای کوچک و توضیحاتی درباره مقادیرش برای یک مجموعه ثابت است. خروجی، یک طبقه بندی کننده میتواند با دقت پیش بینی کند که یک نمونه جدید به کدام کلاس متعلق است. C4.5 طبقه بندیها را بر اساس درختهای تصمیمگیری بیان میکند. این الگوریتم هم قادر به ساختن درخت تصمیم و هم مجموعه ای از قوانین میباشد. این مدل با شاخه کردن نمونه بر اساس فیلدی که بیشترین اطلاعات در هر مرحله بدست میآورد، کار میکند. فیلد نهایی باید به صورت طبقهبندی باشد. همچنین امکان اینکه در هر مرحله هر یک از شاخه ها به بیش از دو زیر گروه تقسیم شوند نیز وجود دارد
C4.5 يک معيار استاندارد در يادگيري ماشين است. انتخاب صفت در ID3 و C4.5 بر اساس حداقل کردن مقياس اطلاعات در يک گره است. هر مسير از ريشه به سمت يک گره، نمايانگر يک قانون دستهبندي ميباشد.
درک درختهای تصمیم گیری پیچیده ممکن است مشکل باشد، برای مثال اطلاعات یک کلاس معمولا در طول درخت پخش شده است. C4.5 یک جانشین فرمالیته متشکل از یک لیست از قوانین به شکل “if A and B and C and ... then class X” را تولید میکند که در آن قوانین هر کلاس باهم گروه بندی شدهاند. یک نمونه براساس اولین قانون پیدا شدهای که شرایط نمونه را ارضا میکند طبقهبندی میشود; اگر هیچ قانونی شرایط نمونه را ارضا نکند، مورد به کلاس پیشفرض اختصاص می یابد.
شکل (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 خلاصه
- ماتریس الگو را آماده میکنیم.
- تابع کرنلی را برای استفاده انتخاب میکنیم.
- پارامتر تابع کرنل و مقدار C را انتخاب می کنیم.
- برای محاسبهی مقادیرai ، الگوریتم آمورشی را با استفاده از حل کنندههای برنامه نویسی درجه دو اجرا میکنیم.
- دادههای جدید با استفاده از مقادیر 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 محاسبه نمیشود.
بر اساس مفهوم اعتبار در شبکه اجتماعی میتوان موارد زیر را مطرح کرد:
- وجود یک پیوند از یک صفحه به صفحه دیگر بطور ضمنی نشاندهنده نفوذ[5] صفحه مقصد است. بنابراین پیوند ورودی بیشتر برای صفحه i نشاندهنده نفوذ بیشتر این صفحه است.
2. صفحاتی که به i اشاره میکنند خود نیز دارای اعتبارهای متفاوتی هستند. پیوند رسیده از یک صفحه با اهمیت بالاتر ارزش بیشتری نسبت به پیوند رسیده از یک صفحه با ارزش کمتر دارد. میتوان نتیجه گرفت که صفحهای مهم است که از صفحات مهم دیگر پیوند گرفته باشد.
بر اساس مفاهیم مطرح شده درباره اعتبار در شبکههای اجتماعی، امتیاز رتبه بندی صفحه i برابر با مجموع امتیاز رتبه بندی صفحاتی است که به i پیوند دادهاند. از طرفی، چون ممکن است یک صفحه به تعداد زیادی صفحه پیوند داده باشد، پس باید امتیاز رتبهبندی آن بین تمام این صفحات تقسیم شود.
برای فرموله کردن این ایده، وب را به عنوان یک گراف جهتدار G=(V,E) فرض میکنیم که V مجموعه گرهها یعنی تمام صفحات موجود در وب و E نیز مجموعه یالها یعنی پیوند بین صفحات است. فرض میکنیم که تعداد صفحات در وب n است یعنی . حال رتبهبندی صفحه i یعنی P(i) به شکل زیر محاسبه میشود: که Oj تعداد پیوندهای خروجی صفحه j است. در این حالت در واقع ما دارای n معادله با n مجهول، یعنی رتبهبندی صفحات، هستیم. حال از یک ماتریس برای نمایش تمام معادلهها استفاده میکنیم. P را به عنوان یک بردار ستونی n بعدی از مقادیر رتبهبندی صفحه در نظر میگیریم:
(7-1)
همچنین A را به عنوان ماتریس همسایگی گراف وب در نظر میگیریم که:
Aij=
حال سیستم n معادله را میتوان به صورت زیر نوشت:
(7-2)