دانلود پایان نامه ارشد درمورد دودویی، تفکیک‏پذیر، داده‏های

دانلود پایان نامه ارشد

است.
3-1-1. جداکننده‏های خطی
می‏توان رده‏بندهای دودویی را به عنوان جداکننده خطی نیز در نظر گرفت که داده‏های فضای دوبعدی را با یک خط از یکدیگر افراز می‏کند. معمولاً فرض می‏شود که رده‏بندها خطی هستند، به این معنا که ابر صفحه197های متمایل‏شده هستند (در مواقعی که داده‏ها به صورت خطی تفکیک‏پذیر نباشند، از هسته‏ها استفاده می‏شود که داده‏ها را به فضایی با ابعاد بیشتر می‏نگارند تا داده‏های خطی تفکیک‏پذیر شوند).

شکل 3-1: شمایی از داده‏ها‏ی خطی و غیر خطی جدایی پذیر
بنابراین، تابع رده‏بند دودویی با بردار وزن w∈R^D و مقدار عددی b∈R فرموله می‏شود. فرمول رده‏بند دودویی در رابطه‏ی 3-1 نشان داده شده است.
رابطه (3-1) f(x,w,b)=w^t φ(x)+b=∑_d▒w_d φ〖(x)〗_d+b
تصمیمات رده‏بندی بر مبنای علامت f انجام می‏گیرد : اگر f(x)0 باشد ، آنگاه کلاس +1 در نظر گرفته می‏شود و هرگاه f(x)<0 باشد، کلاس -1انتخاب می‏شود. هنگامی که خود را به فرض خطی بودن مقید می‏کنیم، مسئله یادگیری به پیدا کردن مقادیر مناسب برای w و b تبدیل می‏شود. این مقادیر بر اساس داده‏های آموزشی 〖(x_n,y_n)〗_(1:N)یادگرفته می‏شود.
3-1-1-1. پرسپترون
الگوریتم پرسپترون[86،36] که الهام گرفته از ساختار عصبی بدن انسان است، بردار وزن w و مقدار b را به روشی بر‏خط می‏آموزد؛ بدین معنا که در هر زمان یکی از نمونه‏های مجموعه آموزشی یاد گرفته می‏شود. در هر مرحله، پرسپترون اطمینان حاصل می‏کند که پارامترهای جاری به گونه‏ای تنظیم شده‏اند که نمونه مورد بررسی را درست رده‏بندی کنند و اگر این چنین بود یادگیری با نمونه بعدی ادامه می‏یابد. در غیر این صورت، بردار وزن و مقدار گرایش〖(b)〗^2 بگونه‎‏ای اصلاح می‏شوند که به نمونه مورد بررسی نزدیک‏تر باشند. الگوریتم آن قدر در کل مجموعه آموزشی تکرار می‏شود که یا اصلاح جدیدی صورت نگیرد و یا تعداد تکرارها به حداکثر رسیده باشد. اگر داده‏ها تفکیک‏پذیر باشند، قابل اثبات است که پرسپترون در نهایت به مجموعه‏ای از پارامترها همگرا می‏شود که کل داده آموزشی را به درستی رده‏بندی می‏کنند. البته شایان ذکر است که این روش به قابلیت تعمیم بسیار ضعیفی منجر می‏شود. به همین منظور برای بهبود قابلیت تعمیم، از میانگین‏گیریِ وزنی استفاده می‏شود. میانگین‏گیریِ وزنی با تغییر الگوریتم پرسپترون استاندارد و به این صورت انجام می‏گیرد که بردار وزنی نهایی برگردانده شده، میانگین تمام بردارهای وزنی است که در طول آموزش بدست آمده‏اند. می‏توان نشان داد که میانگین وزنی به راه حل‏های پایدارتر و با قابلیت تعمیم بهتری منجر می‏شود. [7،112]
یک راه حل ساده پیاده‏سازی میانگین وزنی به این صورت است که دو مجموعه از پارامترها در هر مرحله حفظ شوند: پارامترهای جاری و پارامترهای میانگین.
در هر مرحله از الگوریتم (پس از پردازش یک نمونه)، پارامتر جاری و پارامترهای میانگین در هرمرحله از الگوریتم (پس از پردازش یک نمونه)، پارامترهای جاری و پارامترهای میانگین افزوده می‏شود و پس از خاتمه الگوریتم، پارامترهای میانگین بر تعداد مراحل تقسیم می‏شوند و پارامتر‏های حاصل با عنوان پارامترهای نهایی در نظرگرفته‏می‏شود. یکی از ویژگی‏های مثبت این الگوریتم علاوه بر سادگی آن، این است که بردار φ(x) معمولا یک بردار پراکنده است که موجب می‏شود بروز بردار ویژگی اصلی به صورت کارایی صورت پذیرد، البته باید توجه داشت که جمع کردن و میانگین گرفتن از بردار‏ها‏ی ویژگی در این روش تا حدودی ناکارآمد می‏باشد.
شکل 3-2، یک پیاده‏سازی مناسب از الگوریتم پرسپترون میانگین‏دار را نمایش می‏دهد. در مرحله اول، بردار وزن و مقدار گرایش جاری با صفر مقدار دهی اولیه می‏شوند. در مرحله دوم، بردار وزن و گرایش میانگین با صفر مقدار دهی اولیه می‏شوند. در مرحله سوم، شمارنده میانگین با 1 مقدار دهی می‏شود . الگوریتم در حلقه ی(I) تکرار می‏شود در هر تکرار الگوریتم یکی از نمونه‏ها را پردازش می‏کنند. در مرحله ششم بررسی می‏شود که آیا الگوریتم نمونه (x_n,y_n) را درست رده‏بندی کرده است یا خیر. در صورتی نمونه(x_n,y_n) درست رده‏بندی نشده است که y_n و پیش بینی جاری، w_0^T φ(x_n )+b_0، علامت جبری یکسانی نداشته باشند، که در آن صورت ضرب آنها منفی می‏شود. در صورتی که نمونه (x_n,y_n) با پارامترهای (w_0:b_0) درست رده‏بندی نشده باشد، الگوریتم در مرحله هفتم،w_0 را به y_n φ(x_n) و b_0 را به y_n نزدیکتر می‏نماید. در مرحله هشتم برداروزنی میانگین به طریقی مشابه بروز می‏شود با این تفاوت که شمارنده میانگین به عنوان عامل افزاینده به کار می‏رود در نهایت در مرحله دهم صرف نظر از اینکه تصحیح بردار وزنی و یا مقدار گرایش صورت گرفته است یا خیر ، شمارندهC افزایش می‏یابد.
پس از خاتمه الگوریتم، پارامترهای نهایی به عنوان خروجی بازگردانده می‏شوند در مورد الگوریتمی که از میانگین وزنی استفاده نمی‏کند، مقادیر〖 w〗_0 و b_(0 ) به عنوان خروجی بازگردانده می‏شوند؛ ولی در مورد الگوریتم میانگین‏دار، مقادیر ⟨〖 w〗_0-〖 w〗_a│c⟩ و ⟨〖 b〗_0-〖 b〗_a│c⟩ به عنوان خروجی بازگردانده می‏شوند و بدین صورت میانگین وزن دار حاصل می‏شود.
الگوریتم پرسپترون میانگین‏‏دار (x_(1:N),y_(1:N),I)
w_0←(0,0,…,0),b_0←0
w_a←(0,0,…,0),b_a←0
c←1
به ازای i=I تا i=1 انجام بده
به ازای n=N تا n=1 انجام بده
اگر y_n [w_0^T φ(x_n)+b_0 ]≪0 آنگاه
w_0←w_0+y_n φ(x_n ),b_0←b_0+y_n
w_a←w_a+〖cy〗_n φ(x_n ),b_a←b_a+〖cy〗_n
شرط پایان
c←c+1
پایان حلقه دوم
پایان حلقه اول
بازگرداندن مقدار (w_0-w_a│c ,├ b_0-b_a ┤|c ) به عنوان مقدار خروجی
شکل 3-2: الگوریتم پرسپترون میانگین‏دار
3-1-1-2. ماشين بردار پشتيبان
ماشین بردار پشتیبان شیوه دیگری برای حل یک مسئله یادگیری است که در آن مسئله در قالب یک مسئله بهینه‏سازی حل می‏شود. ماشین بردار پشتیبان198 بر اساس جداسازهای با بیشترین حاشیه هستند. ایده اصلی در جداسازهای با بیشترین حاشیه، یافتن ابر صفحه است که رده‏ها را با بیشترین حاشیه از یکدیگر افراز نمایند. حاشیه به فاصله‏ای گفته می‏شود که دو خط موازی جداساز به صورت مساوی از دو طرف طی می‏کنند تا یکی از آنها به یکی از داده‏ها برخورد نماید. از لحاظ تئوری می‏توان ثابت کرد که جداسازی که بیشترین حاشیه را داشته باشد قابلیت تعمیم بیشتری نیز خواهد داشت [115،116] و با تغییرات کوچک در داده‏ها صحت رده‏بندی حفظ می‏شود. علاوه برآن می‏توان نشان داد که تنها پارامترهایی به جداسازی بیشترین حاشیه منجر می شوند که اگر آنها را مستقل از b در نظر بگیریم، ‖w‖ در آن‏ها کوچک باشد.
حالتی را درنظر بگیرید که داده‏ها قابل تفکیک هستند و اندازه حاشیه برابر با 1 است. بدین معنا که مجموعه‏ای از پارامتر‏ها وجود دارد که داده‏های آموزشی را با حاشیه برگی رده‏بندی می‏نماید. در این صورت مسئله SVM به صورت رابطه‏ی3-2 در می‏آید.
رابطه(3-2)
〖Mininmize〗_(w,b ) 1/2 ‖w^2 ‖

subject to y_n [w^T φ(x_n )+b]≥1 ∀n
مسئله بهینه‏سازی SVM به دنبال یافتن بردار وزن w و گرایش b است به گونه‏ای که نرم کمینه شود. در بسیاری از موارد این مسئله بهینه‏سازی غیر عملی است زیرا ممکن است چنین پارامترهایی وجود نداشته باشد که از محدودیت مسئله بهینه‏سازی تبعیت نمایند. بعلاوه در مواقعی هم که داده‏ها تفکیک‏پذیر هستند عموما ترجیح نمی‏دهیم که الگوریتم به بهترین کارایی رده‏بندی بر روی داده‏های آموزشی برسد؛ به عبارتی دیگر مقداری خطا قابل تحمل است، در نتیجه SVM‏های «نرم‏حاشیه»199 مطرح شدند. مفهوم SVM نرم‏حاشیه این است که لزومی ندارد که تمام نمونه‏ها با حاشیه 1 رده‏بندی شوند. علاوه بر آن، به ازای هر نمونه‏ای که از محدودیت رده‏بند SVM تبعیت نمی‏کند، محاسبه می‏شود که آن نمونه چقدر با موقعیتی فاصله دارد که در آن محدودیت SVM «سخت‏حاشیه»200 ارضا می‏شود؛ این اندازه به عنوان انعطاف آن نمونه شناخته می‏شود. مسئله SVMهای نرم‏حاشیه به فرم رابطه‏ی 3-3 می‏باشد.
رابطه (3-3)
〖Mininmize〗_(w,b ) 1/2 ‖w^2 ‖ +C∑_(n=1)^N▒ξ_n

subject to y_n [w^T φ(x_n )+b]≥1-ξ_n ∀n ξ_n≥0
در معادله SVMهای نرم‏حاشیه تابع هدف از دو مولفه تشکیل شده است؛ اولین مولفه را ملزم به یافتن پاسخی می‏کند که قابلیت تعمیم خوبی داشته باشد. مولفه دوم (مجموع مقادیر متغیر‏های انعطاف) SVM را ملزم می‏نماید که بیشتر داده‏های آموزشی را به درستی رده‏بندی نماید. پارامتر C ≥ 0موازنه‏ای میان تطبیق رده‏بند با داده‏های آموزشی و یافتن یک بردار وزنی کوچک می‏باشد. در صورتی کهC به بی‏نهایت میل نماید شیوه SVM نرم‏حاشیه به SVM سخت‏حاشیه نزدیک می‏شود که در آن تمام داده‏های آموزشی باید به درستی رده‏بندی شوند. در صورتی که C به صفر میل کند SVM کمتر به درست رده‏بندی کردن داده‏های آموزشی اهمیت می‏دهد و به سادگی یک بردار وزن کوچک را جستجو می‏کند.
همان‏طور که گفته شد،در محدودیت مربوط به SVM نرم‏حاشیه، دیگر نیازی نیست که نمونه با حاشیه 1 رده‏بندی شود و به جای آن هر نمونه با حاشیه1-ξ_n رده‏بندی می‏شود. اگر پارامتر‏ها به گونه‏ای یافت شوند که در آن تمام نمونه‏های آموزشی با حاشیه 1 رده‏بندی شوند آنگاه تمام ξ_n ها می‏توانند برابر با صفر قرار داده شوند. اما به عنوان نمونه در مورد داده‏های تفکیک‏ناپذیر این متغیر‏های انعطاف‏ می‏توانند نماینگر خطا باشند. هرچند که تعداد محدودیت‏ها به تعداد داده‏هاست ولی می‏توان توسط شرایط Karush-Kuhn-Tucker [21] نشان داد که در یک بردار وزن بهینه تنها تعداد بسیار کمی از آن‏ها مقدار غیر صفر دارند بدین معنا که هنگامی که wوb مقدار بهینه داشته باشند y_n [x^T φ(x_n )+b]مطلقا بزرگتر از یک بوده و به ازای بسیاری ازn ها برابر با صفر است. نمونه‏هایی که وزن متناظر با آن‏ها غیر صفر است بردار پشتیبان خوانده می‏شوند زیرا تنها این نمونه‏ها هستند که در تصمیم‏گیری رده‏بند تاثیر خواهند داشت.
الگوریتم‏های بسیاری برای حل کردن SVM وجود دارند ساده‏ترین آن‏ها تبدیل آن به یک مسئله برنامه ریزی غیرخطی[21] و اعمال یک بسته بهینه‏سازی عمومی بر روی آن است. پس از تبدیل مسئله SVM به یک مسئله برنامه ریزی غیرخطی مسئله به فرم زیر در می آید:
رابطه(3-4)
Max W(α)=∑_(i=1)^n▒α_i -1/2 ∑_(i=1)^n▒∑_(i=1)^n▒α_i α_j y_i y_j 〈x_i,x_j 〉

subject to α_i≥0,∑_(i=1)^n▒α_i y_i=0

در این صورت w از طریق رابطه‏ی 3-5 وb از طریق معادله 3-6 بدست خواهند آمد.
رابطه (3-5) w=∑_(i=1)^n▒α_i y_i x_i
رابطه (3-6 ) b=1/y_i -w^T x_i

توابع هسته ماشین بردار پشتیبان
ضرب داخلی در فضای ویژگی‏ها 〈x_i,x_j 〉 در رابطه‏ی3-2 هسته معادلی در فضای ورودی دارد.
رابطه(3-7)
K(x,x^’)=〈φ(x)،φ(x^’)〉
این تساوی هنگامی برقرار است که شرایط ویژه‏ای بر قرار باشد؛ هنگامی که K یک تابع تعریف شده مثبت متقارن باشد که شرایط مرسر را ارضا کند شرایط مرسر در رابطه‏های 3-8 و 3-9 آورده شده است.
رابطه(3-8)
K(x,x^’ )=∑_m^∞▒a_m φ_m (x) φ_m (x^’ ), a_m≥0
رابطه(3-9)
∫▒〖∫▒K(x,x^’ ) g(x)g(x^’ )dxdx^’>0 , gϵL_2 〗
در صورتی که تابع هسته این شرایط را داشته باشد آنگاه نمایان‏گر این ضرب داخلی در فضای ویژگی‏ها قابل قبول است. برخی از توابع متداول و معتبری که شرایط مرسر را ارضا می‏کنند در ادامه معرفی شده‏اند.
تابع چند جمله‏ای
هسته چند جمله‏ای201 یک روش مشهور در مدل کردن‏های غیر خطی است.
رابطه(3-10)
K(x,x^’ )=〖(〈x,x^’ 〉+1)〗^d
تابع RBF
رابطه(3-11)
K(x,x^’ )=exp(-‖x-x^’ ‖^2/〖2σ〗^2 )
تابع حلقوی202
رابطه(3-12)
K(x,x^’ ) tan⁡〖h(k〈x,x^’ 〉+θ)〗
3-1-1-3. درخت تصميم
در پرسپترون هنگامی دو بردار ویژگی مشابه هستند که به خروجی یکسانی منجر شوند ولی می‏توان با به کارگیری دنباله‏ای از پرسش‏ها رده‏بندی را انجام داد که درآن پاسخ هر پرسش به پاسخ پرسش ماقبل خود بستگی دارد. این شیوه‏های بیست سوالی خصوصا برای رده‏بندی داده‏هایی که معیاری جهت سنجش شباهت ندارند مناسب است چرا که تمام پرسش‏ها می‏توانند در قالب پرسشهای «بله/خیر»،«درست/نادرست» و یا «آیا مقدار مورد پردازش عضوی از مجموعه‏ای از مقادیر هست یا خیر» در بیایند و دیگر نیازی به وجود معیار مشابهت نیست.
چنین دنباله‏ای از پرسش‏ها در قالب یک درخت تصمیم جهت‏دار و یا در حالت ساده‏تر در قالب یک درخت نمایش داده می‏شوند که مطابق عرف نخستین گره و یا به عبارتی گره ریشه در بالاترین سطح درخت نمایش داده می‏شود و توسط پیوند‏ها و یا شاخه‏هایی به سایر گره‏ها متصل می‏شود . گره‏های سطوح بعدی نیز به همین ترتیب به گره‏های سطوح پایین تر متصل می‏شوند تا به گره‏های انتهایی یا به عبارتی به گره‏های برگ برسیم نمونه از درخت تصمیم را در شکل 3-3 مشاهده می‏کنید. به منظور رده‏بندی یک داده فرآیند از گره ریشه آغاز می‏شود که محتوی سوالی در مورد مقدار یکی از ویژگی‏های داده است پیوند‏های متفاوتی که از گره ریشه آغاز شده‏اند نمایانگر مقادیر متفاوت ممکن برای آن ویژگی هستند. براساس مقدار ویژگی پرسش شده یکی از پیوندها دنبال شده تا به یک گره سطح پایین‏تر برسیم. تمام پیوند‏های یک گره باید دو به دو مجزا و جامع باشند بدین معنا که در هنگام تصمیم‏گیری تنها یک پیوند باید از یک گره دنبال شود مرحله بعدی تصمیم‏گیری در گره جدید است تصمیم‏گیری را طبق منوال قبلی در این گره و گره های بعدی ادامه می‏دهیم تا به به گره‏های برگ برسیم که درآن پرسش دیگری وجود ندارد هر گره برگ با یک رده برچسب خورده است که پس از رسیدن به هر برگ رده داده مورد برسی برابر با رده مشخص شده توسط آن برگ قرار داده می‏شود.
از مزیت‏های درخت‏ تصمیم نسبت به بسیار دیگری از رده‏بندها همانند شبکه‏های عصبی قابلیت تفسیر آن است به راحتی می‏توان اطلاعات موجود در درخت را بصورت عبارات منطقی نمایش داد. مزیت دیگر درخت تصمیم رده‏بندی سریع است معمولا با چندین پرسش ساده رده‏بندی صورت می‏گیرد.

تصویر 3-3: نمونه‏ای از یک درخت تصمیم

الگوریتم C5 [53] یکی از الگوریتم‏هایی است که با استفاده از داده‏های آموزشی درخت تصمیم را می‏سازد درختی که توسط الگوریتم C5 تولید می‏شود می‏تواند برای رده‏بندی به کار برود. الگوریتم C5 به طریقی مشابه یا الگوریتم ID3 و با استفاده از مفهوم آنتروپی اطلاعات درخت تصمیم را از روی داده‏های آموزشی می‏سازد. داده‏های آموزشی یک مجموعه به صورت S=s_1,s_2,… , از نمونه‏های رده‏بندی شده است. هر نمونه S_i=x_1,x_2,… یک بردار است که در آن x_i ها نمایانگر ویژگی‏های آن نمونه هستند. داده‏های آموزشی با بردار C=c_1,c_2,… نشانه‏گذاری شده‏اند که درآن‏ها c_i ها رده متناظر با هر نمونه را نشان می دهد.
الگوریتم C5 از این حقیقت استفاده می‏کند که هر ویژگی داده می‏تواند برای تولید یک تصمیم به کار رود که بر اساس آن داده‏ها به زیر بخش‏های کوچک‏تری تقسیم می‏شوند این الگوریتم بهره اطلاعاتی نرمال شده ویژگی را محاسبه می‏کند و ویژگی برای ایجاد تصمیم انتخاب می‏شود که بهره اطلاعاتی نرمال شده بیشتری داشته باشد. تصمیم فهرست داده‏ها را براساس مقادیر مختلف آن ویژگی به چند زیر فهرست تقسیم می‏نماید پس از آن الگوریتم بر روی زیر فهرست‏ها دنبال می‏شود.
الگوریتم C5 موارد پایه کمی دارد. متداولترین مورد پایه هنگامی است که تمام نمونه‏های موجود در فهرست به یک رده یکسان تعلق داشته باشند. در چنین مواقعی، یک گره برگ حاوی برچسب آن رده تولید می‏شود. مورد پایه دیگر هنگامی است که هیچ ویژگی نتواند داده‏های مورد بررسی را افراز کند. در چنین مواردی مابین داده‏های باقیمانده رای اکثریت گرفته می‏شود و گره برگی با برچسب رده‏ای که اکثریت را داشته باشد ایجاد می‏شود علاوه بر این موارد ممکن است در یک زیر شاخه از یک گره هیچ نمونه‏ای وجود نداشته باشد (هیچ یک از نمونه‏ها در میان نمونه‏های مورد برسی مقدار خاص مورد نظر از ویژگی‏ای را که برای ساخت گره تصمیم به کار رفته بود نداشته‏اند) در این مورد گره برگی با برچسب رده اکثریت نمونه‏های مورد بررسی ساخته می‏شود. روال الگوریتم C5 را در شکل 3-4 مشاهده می‏نمایید.

تست کردن موارد پایه
به ازای هر ویژگی a مرحله 3 را انجام بده
بدست آوردن بهره اطلاعاتی نرمال شده هنگامی که داده‏ها براساس ویژگی a تفکیک شوند.
انتخاب ویژگی ای که بالاترین بهره اطلاعاتی نرمال شده را دارد.
تولید یک گره تصمیم که داده‏ها را بر اساس ویژگی انتخاب شده در مرحله قبل افراز می‏کند.
تکرار عملیات فوق به ازای زیر لیست‏های بوجود آمده توسط افراز مرحله قبل
شکل3-4: الگوریتم C5
3-2. خوشه‏بندی
هدف از خوشه‏بندی که یکی از مهمترین روش‏های یادگیری بدونِ‏ناظارت محسوب می‏شود، کشف یک ساختارp در میان مجموعه داده‏ی D می‏باشد که تابع هدف F:P→R بهینه شود. به عبارت دیگر، با توجه به انتظاراتی که با شنیدن نام خوشه‏بندی ایجاد می‏شود، پیش بینی می‏شود که یک الگوریتم مناسب قادر باشد تا از طریق بررسی شباهت‏ها یا تفاوت‏هایی (مانند فاصله‏ها) موجود میان نقاط داده‏ای در مجموعه داده مفروض به کشف ساختار بپردازد. به این ترتیب خوشه‏هایی ایجاد می‏شود که آیتم‏های موجود در هر خوشه بسیار شبیه به یکدیگر باشند و با آیتم‏های خوشه‏های دیگر نیز تا حد ممکن متفاوت باشند. از جنبه محاسباتی باید در نظر داشت که تقسیم N نمونه به C خوشه، ایجاد تعداد زیادی از افرازها را فراهم می‏سازد.[2] استفاده از عدد استرلینگ را برای نشان دادن داده‏های ممکن برای این افرازها را معرفی کرده‏است.
رابطه (3-13) =1/c! ∑_(i=1)^c▒〖(-1)〗^((c-i)) (_i^c)i^n Sn(c)
به طور کلی یک الگوریتم افراز یک مجموعه داده‏ی D را می‏گیرد و مجموعه‏ای از خوشه‏ها P={Ci,…,CC} را که یک شِما از افراز نمونه‏ها از D است را برمی‏گرداند. این بدین معنا است که خوشه‏های Ci با هم اشتراک ندارند(c_i∪c_j=∅,i≠j) و اجتماع همه آنها مجموعه داده را کامل می‏کند(∪c_i=D).
[56] الگوریتم افرازبندی را به دو دسته‏ی اصلی تقسیم بندی می‏کند؛ (1) بسته‏ای، (2) افزایشی. الگوریتم‏های خوشه‏بندی بسته‏ای، کل مجموعه داده‏ها را بررسی می‏کنند تا مناسب‏ترین راه را برای سازماندهی آنها پیدا کنند. الگوریتم‏های افزایشی، در هر بار، یک مرحله از افراز داده‏ها را انجام می‏دهد. به طوریکه هر مرحله شامل یک آیتم داده‏ای واحد باشد. الگوریتم‏های بسته‏ای در ابتدای کار به تمام داده‏های مجموعه داده نیاز دارند. در حالیکه الگوریتم‏های افزایشی برای برنامه‏های کاربردی برخطی که داده‏ها در جریان مشاهدات افزایش پیدا می کنند مناسب هستند.
3-2-1. الگوريتم‏های افراز بسته‏ای
این الگوریتم‏ها شامل چهار دسته‏ی کلی برای خوشه‏بندی می‏باشند 1) خوشه‏بندی مبتنی بر بخش‏بندی (تابع هدف)، 2) خوشه‏بندی سلسله مراتبی، 3) خوشه‏بندی مبتنی بر مدل، و 4) خوشه‏بندی مبتنی بر گراف.
در خوشه‏بندی مبتنی بر بخش بندی، اساس کار یک تابع هدف است. که کمینه سازی آن ما را به کشف ساختار موجود در مجموعه رهنمون می‏سازد و (در بسیاری موارد مسئله ی بهینه‏سازی را می‏توان به خوبی فرموله کرد) به طور معمول در این گروه از الگوریتم‏ها، تعداد خوشه‏ها از قبل مشخص است و کار با بهینه‏سازی تابع هدف ادامه پیدا می‏کند. با اعمال برخی تغییرات روی الگوریتم‏ها می‏توان تعداد خوشه‏ها را به طور پویا تنظیم کرد. مسئله‏ی اصلی در خوشه‏بندی سلسله مراتبی توسعه‏ی متوالی خوشه‏ها است که می‏تواند توسط الگوریتم‏های حریصانه203 و یا بهینگی مرحله‏ای204 انجام شود. در این روش کار به دو طریق بالا به پایین و یا پایین به بالا انجام می‏پذیرد. در حالت بالا به پایین، ابتدا کل مجموعه داده‏ها بعنوان یک خوشه در نظر گرفته می‏شوند و کار با تقسیمات متوالی ادامه پیدا می‏کند تا در آستانه توقف برسد. در حالت پایین به بالا، هر یک از نقاط به عنوان خوشه اولیه در نظر گرفته‏می‏شود و سپس ادغام صورت می‏گیرد. ( این فرآیند ما را به مفهوم خوشه‏بندی انباشتی205 رهنمود می‏سازد). آنچه برای خوشه‏بندی سلسله مراتبی مهم است، انتخاب تابع فاصله مناسب و نحوه‏ی تعیین فاصله موجود میان الگوها و نقاط است. با توجه به این مورد، طیف وسیعی از روش‏ها (تک پیوندی، پیوند کامل206 و…) به وجود می‏آید. خوشه‏بندی مبتنی بر داده‏ها در نظر می‏گیرد. سپس پارامترها برآورد می‏شوند.
3-2-1-1.خوشه‏بندی سلسله مراتبی پايين به بالا
الگوریتم‏های خوشه‏بندی سلسله مراتبی، داده‏ها را بصورت گراف نمایش می‏دهند. ساخت گراف‏ها (این روش‏ها با در نظر گرفتن هر یک از نمونه ها، ساختار را آشکار می‏سازند) را می‏توان با توجه به دو رویکرد انجام داد: پایین به بالا، و بالا به پایین، در رویکرد پایین به بالا، که به آن رویکرد انباشتی نیز گفته می‏شود، هر الگو را یک خوشه تک عنصری در نظر گرفته و سپس بطور متوالی نزدیک‏ترین خوشه‏ها را ادغام می‏کنیم. این فرآیند تا جایی ادامه پیدا می‏کند که به یک خوشه منفرد یا یک آستانه از پیش تعریف شده دست پیدا کنیم. رویکرد بالا به پایین که به آن رویکرد تقسیم کننده نیز گفته می‏شود، در جهت مخالف رویکرد قبلی عمل می‏کند. در این رویکرد، کل مجموعه داده در ابتدا یک خوشه منفرد در نظر گرفته شده، و در ادامه بطورمتوالی به خوشه‏های کوچکتر تقسیم می‏شود. با توجه به طبیعت فرآیندهای بالا به پایین و پایین به بالا، درمی‏یابیم که این روش‏ها در اغلب موارد از نظر محاسباتی ناکارا هستند. تنها حالتی که امکان دارد در آن پیاده سازی روش‏های مذکور بصرفه باشد، زمانی است که با الگوهای دودویی مواجه هستیم.
نتایج حاصل از خوشه‏بندی سلسله مراتبی بصورت دندروگرام نمایش داده می‏شود. همانطور که در شکل3-5 ملاحظه می‏کنید، دندروگرام، یک درخت دودویی با ریشه معین است که برگ‏های آن از تمامیِ اجزای داده‏ها تشکیل شده‏است. فرآیند ادغام متوالی خوشه‏ها، با توجه به مقادیرفاصله هدایت می‏شود. با توجه به مقدار فاصله، دنباله‏ای از خوشه‏های تودرتو تولید می‏گردد. دندروگرام‏ها، دارای ساختار جالبی هستند که ما را در ادغام خوشه‏ها یاری می‏رساند، گره‏هایی که در پایین گراف قرار می‏گیرند متناظر

پایان نامه
Previous Entries دانلود پایان نامه ارشد درمورد گروه اسمی، مسئولیت پذیری، عام و خاص Next Entries دانلود پایان نامه ارشد درمورد سلسله مراتبی، سلسله مراتب، ماشین بردار پشتیبان