روش های سلسله مراتبی به دو دسته کلی: روش های Bottom-up و روش های Top-down تقسیم می شوند. روش های سلسله مراتبی Bottom-up به این صورت عمل می کنند که در شروع، هر کدام از داده ها را در یک خوشه جداگانه قرار می دهد و در طول اجرا سعی می کند تا خوشه هایی نزدیک به یکدیگر را با هم ادغام نماید. این عمل ادغام تا زمانی که تنها یک خوشه داشته باشیم و یا این که شرط خاتمه برقرار گردد، ادامه می یابد. روش های Top-down دقیقاً به طریقه ی عکس عمل می نمایند، به این طریق که ابتدا تمام داده ها را در یک خوشه قرار می دهند و در هر تکرار از الگوریتم، هر خوشه به خوشه های کوچکتر شکسته می شود و این کار تا زمانی ادامه می یابد که یا هر کدام از خوشه ها تنها شامل یک داده باشند و یا شرط خاتمه الگوریتم برقرار گردد. شرط خاتمه معمولا تعداد کلاستر یا خوشه می باشد.
روش های مبتنی بر چگالی
اکثر روش های خوشه بندی که به روش تقسیم بندی عمل می کنند، معمولاً از تابع فاصله به عنوان تابع معیار خود بهره می برند. استفاده از چنین معیاری باعث می گردد که الگوریتم خوشه بندی تنها قادر به ایجاد خوشه هایی با اشکال منظم باشد. در صورتی که اگر خوشه های واقعی در داده ها دارای اشکال غیر منظمی باشند، این الگوریتم ها در خوشه بندی آن ها با مشکل مواجه می گردند. برای حل این گونه مشکلات، یک سری از روش های خوشه بندی پیشنهاد گردیده اند که عمل خوشه بندی را بر مبنای چگالی داده ها انجام می مدهند. ایده اصلی در این روش ها بر این اساس است که خوشه ها تا زمانی که داده های قرار گرفته درهمسایگی خوشه ها از حد معینی بیشتر باشد، رشد می کنند و بزرگ می شوند. چنین روش هایی قادرند خوشه هایی با شکل های نامنظم نیز ایجاد نمایند.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

البته دسته دیگری از روش های خوشه بندی مانند روش های مبتنی بر مشبک کردن فضا، روش های مبتنی بر مدل و … نیز وجود دارند که در این تحقیق مورد بررسی قرار نگرفته اند.
الگوریتم های وابستگی قواعد
الگوریتم های مختلفی برای تعیین وابستگی قواعد وجود دارد که برخی از مهم ترین آن ها در زیر آورده شده است:
الگوریتم NAÏVE
این الگوریتم پردازه ای برای کشف تمام قواعد وابستگی با حداقل Support=p% و Confidence=q% می باشد. در این الگوریتم لیستی از تمامی ترکیب های ممکن تهیه شده و سپس تعداد تکرار آن ها در مجموعه تراکنش های محاسبه می شود سپس با توجه به مقدار Support داده شده لیست ترکیب هایی که تعداد تکرار آن ها برابر یا بیشتر از تعداد مورد نظر است جدا شده و برای تمامی ترکیب های آن میزان Confidence محاسبه و با مقدار داده شده مقایسه می شود. سپس لیست قواعد با Confidence مورد نظر استخراج می گردد.(Gupta 2006)
در نسخه بهبود یافته این الگوریتم به جای شمارش تمامی ترکیب ها، تراکنش ها یموجود شمارش شده و ترکیب های با تعداد تکرار صفر منظور نمی شوند.
الگوریتم APRIORI
الگوریتم Apriori را می توان یکی از مهم ترین یافته ها در تاریخ استخراج وابستگی قواعد دانست که توسط چیونگ در سال ۱۹۹۶ ابداع گردید. یکی از کاربردی ترین مسائل مربوط به این تکنیک، تجزیه و تحلیل سبد بازار است. خرده فروشان با تجزیه و تحلیل سبد بازار می توانند رفتار خرید مشتریان را پیش بینی کنند. اینکار به آن ها کمک می کند تا بتوانند کالاهای خود را بهتر ساماندهی کرده و چیدمان بهتری از محصولات خود داشته باشند و از این طریق سودآوری خود را افزایش دهند.
در حالت معمولی برای یافتن مجموعه های پرتکرار باید تمام مجموعه های تک عضوی پر تکرار را پیدا کرد، سپس بر اساس آن مجموعه های دو عضوی پر تکرار را پیدا کرد و …
بنابراین در هر مرحله باید کل فضا جستجو شود. اما این الگوریتم از یک خصوصیت به نام خصوصیت Apriori استفاده می کند. به این صورت که اگر یک مجموعه از عناصر پرتکرار باشد، تمام زیر مجموعه های غیر تهی آن نیز پر تکرار خواهند بود. مثلا اگر مجموعه A به صورت A={C,D,E} پر تکرار باشد، آن گاه تمام مجموعه های زیر نیز پرتکرار هستند:
{C, D}, {C, E}, {D, E}, {C}, {D}, {E}
این خصوصیت را به این صورت نیز می توان توصیف کرد که اگر مجموعه I به یک تعداد مرتبه تکرار شده باشد، اگر A را نیز به آن اضافه کنیم تعداد تکرار مجموعه ی جدید از تعداد تکرار مجموعه قبلی بیشتر نخواهد بود. پس اگر اولی پرتکرار نباشد دومی هم پرتکرار نخواهد بود. ای الگوریتم نیز ای این خصوصیت استفاده می کند. الین الگوریتم در یافتن مجموعه های پرتکرار به این صورت عمل می کند:
فرض می کنیم Ck و Fk به ترتیب برابر با مجموعه اقلام کاندید و مجموعه اقلام پرتکرار با اندازه K باشند.

1. 1. در ابتدا K=1 قرار می دهد.

1. 1. در ابتدا تمامی اقلام پرتکرار تک عضوی با عنوان F₁ را پیدا می کند.

1. 1. مراحل زیر را زمانی که هیچ مجموعه پرتکرار جدیدی یافت نشود تکرار می کند.

۳-۱ مجموعه اقلام کاندید (K+1) عضوی که همان C_k+1 است را از مجموعه اقلام پرتکرار K عضوی (F_k) می یابد.
۳-۲ مجموعه اقلام پرتکرار F_K+1 را با در نظر گرفتن شرط حداقل پشتیبان و حذف اقلام غیر پرتکرار، پیدا می کند.
لازم به ذکر است که گام (۳-۱) در دو مرحله صورت می گیرد. یکی تولید اقلام کاندید^[۴۱] و یکی هرس کردن^[۴۲] اقلامی که پرتکرار نیستند. از مرحله اول تحت عنوان مرحله پیوست^[۴۳] نیز یاد می شود(آخوندزاده نوقانی،۱۳۸۸).

• • مرحله تولید اقلام کاندید و یا پیوست

در این مرحله به دلیل جلوگیری از مجموعه های تکراری از قانون لگزیکوگرافی استفاده می شود و عناصر براساس قاعده الفبایی با یکدیگر ترکیب می شوند. بنابراین در ابتدا باید عناصر بر مبنای ترتیب حروف الفبا مرتب شده باشند. در ضمن دو مجموعه در صورتی با یکدیگر قابل پیوست هستند که عناصر آن ها غیر از عنصر آخر با یکدیگر برابر باشند(آخوندزاده نوقانی،۱۳۸۸).

• • مرحله هرس

نکته ای که در مورد مجموعه به دست آمده از مرحله قبل وجود دارد این است که ممکن است برخی از عناصر آن پرتکرار نباشند، البته تمام عناصر پرتکرار در آن قرار دارند. بنابراین لازم است تا مرحله هرس کردن انجام شود.
به این منظور باید تمامی اعضای این مجموعه بررسی شوند تا مشخص شود که آیا پرتکرار هستند یا خیر؟ اما چون ممکن است تعداد آن ها زیاد باشد لذا برای کاهش حجم محاسبات از اصل APriori استفاده می شود. به این صورت که اگر یکی از زیر مجموعه ها پرتکرار نباشد، آن مجموعه نیز پرتکرار نخواهد بود. بنابراین برای پیدا کردن مجموعه های پرتکرار کافی است مجموعه های غیر پرتکرار را از آن ها جدا کرد. به عنوان نمونه مجموعه F₃ که مجموعه اقلام پرتکرار ۳ عضوی است را در نظر بگیرید.
F₃ = {{A, B, C}, {A, B, D}, {A,B, E}, {A,C,E}, {A,D,E}, {B,D,E}}
با ترکیب اقلام پرتکرار فوق ۳ مجموعه جدید به دست می آید که عبارتند از:
C₄ = {{A, B, C, D}, {A, B, C, E}, {A, B, E, D}}
تنها عضوی از مجموعه فوق که به عنوان اقلام کاندید ۴ تایی پیشنهاد می شود، {A, B, D, E} است. به علت این که سایر موارد غیر پرتکرار هستند. به عنوان نمونه {A, B, C, D} در مرحله هرس حذف می شود. زیرا برخی از زیر مجموعه های آن عبارتند از {A, C, D} و {B, C, D} متعلق به F₃ نیستند.
پس از آن که مجموعه های پرتکرار استخراج شدند، نوبت به استخراج قوانین قوی با اطمینان بالا می رسد. در این مرحله تمام زیر مجموعه های غیر تهی یک مجموعه پرتکرار نوشته شده و تمامی قواعد ممکن بر اساس آن استخراج می شود. سپس اطمینان را برای هر یک از قوانین محاسبه نموده و اگر بیشتر از حد قابل قبول بود به عنوان یک قانون پذیرفته می شود(آخوندزاده نوقانی،۱۳۸۸).
الگوریتم های طبقه بندی
الگوریتم ها و روش های مختلفی تا کنون برای طبقه بندی پیشنهاد شده اند که برای مثال می توان از روش های طبقه بندی با بهره گرفتن از درخت تصمیم C4.5، درخت طبقه بندی و رگرسیونCART، شبکه های بیزین، SVM، طبقه بندی مبتنی بر قواعد، طبقه بندی با بهره گرفتن از شبکه های عصبی و …. نام برد که در زیر برخی از آن ها تشریح شده اند:
الگوریتم درخت طبقه بندی و رگرسیون (CART)
روش درخت طبقه بندی و رگرسیون (CART) توسط Breiman و همکارانش در سال ۱۹۸۴ پیشنهاد شد(Larsed 2003).
درخت های تصمیم تولید شده توسط CART دودویی بوده و دقیقا دو شاخه برای هر گره تصمیم دارد. CART به صورت بازگشتی داده های آموزشی را بر اساس مقادیر مشابه مشخصه هدف به زیر مجموعه هایی تقسیم می کند. الگوریتم CART با انجام یک جستجوی گسترده در همه متغیرهای موجود و تمامی تقسیم های ممکن، نقطه تقسیم بهینه را برمبنای معیار زیر انتخاب نموده درخت تصمیم را توسعه می دهد.
فرض کنیم Ф(s|t) یک مقیاس برای تعیین میزان مناسب بودن یک کاندید تقسیم S در گره t باشد:
# classes
Ф(s|t) = 2PL PR Σ|P ( j |tL ) – P ( j |tR)
j=1
t_L= فرزند چپ نود t
t_R= فرزند راست نود t
P_L= تعداد رکوردها در t_L تقسیم بر تعداد رکوردها در مجموعه ی آموزشی
P_R= تعداد رکوردها در t_R تقسیم بر تعداد رکوردها در مجموعه ی آموزشی
P (J|t_L) = تعداد رکوردهای کلاس j در t_L تقسیم بر تعداد رکوردها در t
P (j|t_R) = تعداد رکوردهای کلاس j در t_R تقسیم بر تعداد رکوردها در t