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

ش دهند.
در حالت معمولی برای یافتن مجموعه های پرتکرار باید تمام مجموعه های تک عضوی پر تکرار را پیدا کرد، سپس بر اساس آن مجموعه های دو عضوی پر تکرار را پیدا کرد و …
بنابراین در هر مرحله باید کل فضا جستجو شود. اما این الگوریتم از یک خصوصیت به نام خصوصیت Apriori استفاده می کند. به این صورت که اگر یک مجموعه از عناصر پرتکرار باشد، تمام زیر مجموعه های غیر تهی آن نیز پر تکرار خواهند بود. مثلا اگر مجموعه A به صورت A={C,D,E} پر تکرار باشد، آن گاه تمام مجموعه های زیر نیز پرتکرار هستند:
{C, D}, {C, E}, {D, E}, {C}, {D}, {E}
این خصوصیت را به این صورت نیز می توان توصیف کرد که اگر مجموعه I به یک تعداد مرتبه تکرار شده باشد، اگر A را نیز به آن اضافه کنیم تعداد تکرار مجموعه ی جدید از تعداد تکرار مجموعه قبلی بیشتر نخواهد بود. پس اگر اولی پرتکرار نباشد دومی هم پرتکرار نخواهد بود. ای الگوریتم نیز ای این خصوصیت استفاده می کند. الین الگوریتم در یافتن مجموعه های پرتکرار به این صورت عمل می کند:
فرض می کنیم Ck و Fk به ترتیب برابر با مجموعه اقلام کاندید و مجموعه اقلام پرتکرار با اندازه K باشند.
در ابتدا K=1 قرار می دهد.
در ابتدا تمامی اقلام پرتکرار تک عضوی با عنوان F1 را پیدا می کند.
مراحل زیر را زمانی که هیچ مجموعه پرتکرار جدیدی یافت نشود تکرار می کند.
3-1 مجموعه اقلام کاندید (K+1) عضوی که همان Ck+1 است را از مجموعه اقلام پرتکرار K عضوی (Fk) می یابد.
3-2 مجموعه اقلام پرتکرار FK+1 را با در نظر گرفتن شرط حداقل پشتیبان و حذف اقلام غیر پرتکرار، پیدا می کند.
لازم به ذکر است که گام (3-1) در دو مرحله صورت می گیرد. یکی تولید اقلام کاندید41 و یکی هرس کردن42 اقلامی که پرتکرار نیستند. از مرحله اول تحت عنوان مرحله پیوست43 نیز یاد می شود(آخوندزاده نوقانی،1388).
مرحله تولید اقلام کاندید و یا پیوست
در این مرحله به دلیل جلوگیری از مجموعه های تکراری از قانون لگزیکوگرافی استفاده می شود و عناصر براساس قاعده الفبایی با یکدیگر ترکیب می شوند. بنابراین در ابتدا باید عناصر بر مبنای ترتیب حروف الفبا مرتب شده باشند. در ضمن دو مجموعه در صورتی با یکدیگر قابل پیوست هستند که عناصر آن ها غیر از عنصر آخر با یکدیگر برابر باشند(آخوندزاده نوقانی،1388).
مرحله هرس
نکته ای که در مورد مجموعه به دست آمده از مرحله قبل وجود دارد این است که ممکن است برخی از عناصر آن پرتکرار نباشند، البته تمام عناصر پرتکرار در آن قرار دارند. بنابراین لازم است تا مرحله هرس کردن انجام شود.
به این منظور باید تمامی اعضای این مجموعه بررسی شوند تا مشخص شود که آیا پرتکرار هستند یا خیر؟ اما چون ممکن است تعداد آن ها زیاد باشد لذا برای کاهش حجم محاسبات از اصل APriori استفاده می شود. به این صورت که اگر یکی از زیر مجموعه ها پرتکرار نباشد، آن مجموعه نیز پرتکرار نخواهد بود. بنابراین برای پیدا کردن مجموعه های پرتکرار کافی است مجموعه های غیر پرتکرار را از آن ها جدا کرد. به عنوان نمونه مجموعه F3 که مجموعه اقلام پرتکرار 3 عضوی است را در نظر بگیرید.
F3 = {{A, B, C}, {A, B, D}, {A,B, E}, {A,C,E}, {A,D,E}, {B,D,E}}
با ترکیب اقلام پرتکرار فوق 3 مجموعه جدید به دست می آید که عبارتند از:
C4 = {{A, B, C, D}, {A, B, C, E}, {A, B, E, D}}
تنها عضوی از مجموعه فوق که به عنوان اقلام کاندید 4 تایی پیشنهاد می شود، {A, B, D, E} است. به علت این که سایر موارد غیر پرتکرار هستند. به عنوان نمونه {A, B, C, D} در مرحله هرس حذف می شود. زیرا برخی از زیر مجموعه های آن عبارتند از {A, C, D} و {B, C, D} متعلق به F3 نیستند.
پس از آن که مجموعه های پرتکرار استخراج شدند، نوبت به استخراج قوانین قوی با اطمینان بالا می رسد. در این مرحله تمام زیر مجموعه های غیر تهی یک مجموعه پرتکرار نوشته شده و تمامی قواعد ممکن بر اساس آن استخراج می شود. سپس اطمینان را برای هر یک از قوانین محاسبه نموده و اگر بیشتر از حد قابل قبول بود به عنوان یک قانون پذیرفته می شود(آخوندزاده نوقانی،1388).
الگوریتم های طبقه بندی
الگوریتم ها و روش های مختلفی تا کنون برای طبقه بندی پیشنهاد شده اند که برای مثال می توان از روش های طبقه بندی با استفاده از درخت تصمیم C4.5، درخت طبقه بندی و رگرسیونCART، شبکه های بیزین، SVM، طبقه بندی مبتنی بر قواعد، طبقه بندی با استفاده از شبکه های عصبی و …. نام برد که در زیر برخی از آن ها تشریح شده اند:
الگوریتم درخت طبقه بندی و رگرسیون (CART)
روش درخت طبقه بندی و رگرسیون (CART) توسط Breiman و همکارانش در سال 1984 پیشنهاد شد(Larsed 2003).
درخت های تصمیم تولید شده توسط CART دودویی بوده و دقیقا دو شاخه برای هر گره تصمیم دارد. CART به صورت بازگشتی داده های آموزشی را بر اساس مقادیر مشابه مشخصه هدف به زیر مجموعه هایی تقسیم می کند. الگوریتم CART با انجام یک جستجوی گسترده در همه متغیرهای موجود و تمامی تقسیم های ممکن، نقطه تقسیم بهینه را برمبنای معیار زیر انتخاب نموده درخت تصمیم را توسعه می دهد.
فرض کنیم ?(s|t) یک مقیاس برای تعیین میزان مناسب بودن یک کاندید تقسیم S در گره t باشد:

مطلب مشابه :  پایان نامه با کلید واژه هایگلباد، (?0??-?993)، (3-?)،

# classes
?(s|t) = 2PL PR ?|P ( j |tL ) – P ( j |tR)
j=1
tL= فرزند چپ نود t
tR= فرزند راست نود t
PL= تعداد رکوردها در tL تقسیم بر تعداد رکوردها در مجموعه ی آموزشی
PR= تعداد رکوردها در tR تقسیم بر تعداد رکوردها در مجموعه ی آموزشی
P (J|tL) = تعدا
د رکوردهای کلاس j در tL تقسیم بر تعداد رکوردها در t
P (j|tR) = تعداد رکوردهای کلاس j در tR تقسیم بر تعداد رکوردها در t
نقطه تقسیم بهینه جایی است که بیشترین مقدار را در بین تمام نقاط تقسیم در گره t داشته باشد. به طور کلی CART به صورت بازگشتی تمام نقاط تقسیم باقی مانده را ملاقات کرده و تابع فوق را برای یافتن نقطه تقسیم بهینه در هر گره اجرا می نماید. در نهایت هیچ گره تصمیمی باقی نمی ماند و درخت به طور کامل توسعه می یابد. البته ممکن است تمامی گره ها همگن نباشد که منجر به نوع خاصی از خطای طبقه بندی خواهد شد.
هم چنین در الگوریتم CART عملیات هرس کردن گره ها و شاخه ها انجام می گردد تا قابلیت تعمیم نتایج طبقه بندی افزایش یابد. هر چند که درخت کاملا توسعه یافته پایین ترین نرخ خطا را در مجموعه آموزشی دارد ولی مدل نهایی ساخته شده بر اساس آن ممکن است بسیار پیچیده شود. با توسعه هر گره تصمیم، زیر مجموعه رکوردهای موجود برای تجزیه و تحلیل کوچکتر شده و محدوده کمتری از جمعیت را شامل می شود. بنابراین هرس نمودن درخت، باعث عمومیت یافتن نتایج خواهد شد(Larsed 2003).
الگوریتم درخت تصمیم C4.5
الگوریتم C4.5 از نسل الگوریتم ID3 برای تولید درخت تصمیم است که از قانون هرس استفاده می کند. دقیقا مشابه الگوریتم CART، الگوریتم C4.5 نیز به صورت بازگشتی هر گره تصمیم را ملاقات کرده و نقطه تقسیم بهینه را انتخاب می کند تا جایی که دیگر انشعاب امکان پذیر نباشد. با این حال، تفاوت های جالبی بین CART و C4.5 وجود دارد(Larsed 2003).
الگوریتم C4.5 به تقسیم های دودویی محدود نمی باشد و قادر است درخت های با شاخه های بیشتر را تولید نماید. در این الگوریتم به طور پیش فرض برای هر یک از مقادیر صفات یک شاخه تولید می شود. از آن جا که ممکن است تعداد تکرار برخی از مقادیر کم باشد، در مواردی منجر به ایجاد درختی انبوه و بزرگتر از آن چه مورد نظر بوده می گردد که با استفاده از هرس سعی می شود درخت کوچکتر شده و این مشکل برطرف گردد. حتی اگر هیچ خطایی در داده های آموزشی وجود نداشته باشد باز هم هرس انجام می شود که این امر باعث
می شود درخت عام تر شده و وابستگی کمتری به مجموعه آموزشی داشته باشد.
الگوریتم C4.5 توانایی کار با داده ها و صفات پیوسته، گسسته، صفات فاقد مقدار و داده های نویزی را دارد. این الگوریتم بهترین صفت را با استفاده از معیار بی نظمی انتخاب می کند و به دلیل استفاده از عامل Gain Ratio قادر به بکارگیری صفات با مقادیر بسیار زیاد می باشد(Wu, Kumar 2006).
کلید ساختن درخت تصمیم در الگوریتم C4.5 این است که کدام صفت برای تقسیم استفاده شود. اکتشاف و ابتکار در این الگوریتم برای انتخاب صفت به صورت حداکثر بهره اطلاعات است. الگوریتم C4.5 از مفهوم دستیابی اطلاعاتGain Information یا کاهش آنتروپی ( بی نظمی) برای انتخاب تقسیم بهینه استفاده می نماید. آنتروپی آندازه گیری ناخالصی یا بی نظمی مجموعه داده D است. هرچه داده ها خالص تر و خاص تر باشد آنتروپی کوچک تر بوده و در واقع آنتروپی زیاد به معنی اطلاعات کم است. در آنتروپی، بیت واحد اطلاعات است. در واقع بیت ها نمادهای حامل اطلاعات هستند، نه خود اطلاعات.
m
Entropy (D) = -? Pi log2(Pi )
i=1
m تعداد کلاس های موجود است و pi احتمال آن است که یک متغیر دلخواه در D متعلق به کلاس Ci باشد که این احتمال به صورت |Ci,D|/|D| تخمین زده می شود. ( |D|و |Ci,D| تعداد رخداد در D و Ci,D را نشان می دهد)
فرض می کنیم صفت A دارای v مقدار متمایز به صورت {a1, a2, … ,av} باشد یا به عبارت دیگر A یک صفت گسسته است. اگر بخواهیم D را برحسب صفت A تقسیم کنیم v بخش یا زیرمجموعه مانند {D1,D2,….Dv} حاصل می شود. آنتروپی مورد انتظار اگر Ai به عنوان ریشه به کاربرده شود برابر است با:
EntropyA (D)=?|Dj|/|D|* Entropy(Dj )
اطلاعات حاصل از انشعاب بر حسب صفت A را به صورت زیر تعریف می کنیم:
[Gain(A) = Entropy(D)-EntropyA(D))]
هرچه مقدار بهره صفت A یعنی (GainA) بیشتر باشد یا به عبارت دیگر هرچه (Entropy D) کمتر باشد، صفتA گزینه مناسب تری برای انتخاب به عنوان صفت تقسیم می شود.
الگوریتم های شبکه های بیزین
در برخی از الگوریتم های طبقه بندی تعدادی شی موجود است که همگی دارای یک بردار از خصیصه ها می باشند. مدل شبکه بیزین یک مدل بر مبنای احتمال است که رویدادهای مشاهده شده و ذخیره شده را بررسی کرده و مشابهت رویدادها را با استفاده از خصیصه های به ظاهر نامشابه تعیین می کند. شبکه بیزین یک مدل گرافیکی است که متغیرها در یک مجموعه داده44 را به صورت گره45 نشان داده و احتمال یا شرط استقلال بین آن ها را بیان می کند. ارتباط سببی ( علی) بین گره ها هم می تواند توسط شبکه بیزین نمایش داده شود.
هم چنین خطوط46 شبکه لزوماً ارتباط یا تاثیرهای مستقیم بین متغیرها را نشان نمی دهد. در صورتی که مقادیر گم شده47 در داده ها زیاد باشد، این نوع شبکه بسیار بزرگ و گسترده شده و بهترین پیش بنی ممکن را با استفاده از اطلاعات موجود ارائه می دهد(Wu, Kumar 2006).
در این مدل ابتدا فرض می شود که هر شی به یکی از کلاس های مشخص متعلق است. سپس احتمال درست بودن این فرضیه محاسبه می شود. برای این کار تمامی اشیا یک بار پویش شده و با توجه به داده های آموزشی صحت احتمال منظور شده به طور قابل توجهی افزایش یا کاهش می یابد. هدف استخراج قواعدی است که بر اساس ن ها بتوان با دادن خصیصه های یک شی کلاس آن را تعیین نمود.
الگوریتم بیزین با توجه به سادگی پیاده سازی وعدم نیاز به روش های پیچیده برای تخمین پارامترهای تکراری مورد
توجه می باشد. این ویژگی ها بدین معنی است که به راحتی بر روی داده های بسیار بزرگ اعمال می شود و به دلیل امکان تفسیر و تحلیل ساده، کاربران غیر متخصص نیز می توانند دلایل طبقه بندی انجام شده توسط این کاربر را درک نماید.
در این الگوریتم Ci کلاس های تعریف شده و X شی مورد نظر است که تعدادی خصیصه دارد.
احتمال های زیر برای اجرای مدل محاسبه می گردد:
P(ci|x): احتمال این که شی x متعلق به کلاس ci باشد.
P(x|ci): احتمال این که در صورتی که شی x متعلق به کلاس ci باشد، مقادیر خصیصه های آن برای ساخت قواعدی انتخاب شود.
P(ci ): احتمال این که هر شی متعلق به کلاس ci باشد.
P(x): احتمال این که مقادیر خصیصه های شی x بدون توجه به کلاس آن برای ساخت قواعد انتخاب شود.
فرضیه الگوریتم بیزین بر اساس فرمول زیر می باشد:
P(ci|x)=P(x|ci) P(ci) / P(x)

مطلب مشابه :  منابع پایان نامه ارشد دربارهتیماری، میانگین، CoCl2، mmol/L

مدیریت شهری و شهرداری
چالش شهری در هیچ جای دنیا به اندازه ی آسیا مشهود نمی‌باشد. امروزه 38 درصد از جمعیت این ناحیه در شهرها زندگی می‌کنند، این نسبت اکنون در ایران حدود 70 درصد می‌باشد و پیش‌بینی می‌شود تا سال 2020 این مقدار از 80 درصد فراتر رود. متخصصان شهری اکنون پدیده ی جدیدی را در بین این کلان‌شهرها شناسایی کرده‌اند؛ انباشت و تراکم انبوهی از شهرها با اندازه‌های مختلف که قبلاً به صورت مجزا بوده‌اند ولی هم چنان هویت فیزیکی خود را حفظ نموده‌اند، روی‌هم انبوهی از جمعیت 20 و حتی 30 میلیون نفری را به صورت شبکه‌ای به‌وجود می‌آورند؛ به عنوان مثال منطقه ی شهری تهران که شامل شهرهای تهران، ری، اسلام‌شهر، شمیرانات، شهریار، رباط‌کریم و کرج می‌باشد، همگی با وجود حفظ بافت کهن خود به هم‌دیگر چسبیده‌اند. در تعدادی از این شهرها، پیش‌بینی می‌شود که مسائلی از قبیل عرضه ی خدمات پایه، طی مسافت از خانه تا محل کار و دفع ضایعات و زباله‌ها که تا کنون بسیار معضل‌آفرین بوده‌اند در دهه‌های آتی چندین برابر افزایش یابند(وست فال و دویلا،1386، صص1و2).
گستردگی و پیچیدگی مسائل شهری و رشد و توسعه ی روزافزون شهرها، مدیریت امور شهر را به وظیفهای دشوار تبدیل نمودهاست. علاوه بر موضوعاتی هم چون محیط زیست، حمل و نقل، ایمنی و برنامه ریزی شهری، یکی از عوامل مهمی که تأثیر فزاینده و تعیین کنندهای بر عوامل سازنده ی شهری دارد، مدیریت شهری است. اگر شهر هم چون سازمانی در نظر گرفته شود، لازم است که در رأس آن عنصری برای برنامهریزی آینده و اداره ی امور کنونی قرار گیرد. این عنصر را میتوان مدیریت شهر نامید. مسائل بسیاری در شهرها وجود دارد که برای حل آن ها و پاسخ به درخواستهای موجود در عرصههای زندگی جمعی، وجود مدیریت شهری را ضروری مینماید. این موضوع به خصوص در مسائل خدماتی و عمرانی عمومی، جنبه ی ویژه پیدا میکند. لذا اموری مانند تأمین بهداشت و نظافت محیط


دیدگاهتان را بنویسید