– (69)

شماره جدول عنوان جدول صفحه جدول ‏11- طبقه‌بندی روش‌های انتقال حرارت4جدول ‏12- ابعاد کانال برای انواع مختلف جریان گازی در فشار اتمسفر یک11جدول ‏13- دسته‌بندی کانال‌ها11جدول ‏14- تأثیر عوامل هندسی و شرایط مرزی بر ایجاد پدیده‌های مختلف در میکروکانال دندانه‌دار14جدول ‏21- مروری بر کارهای انجام ‌شده پیرامون جریان نانوسیالات در میکروکانال‌17جدول ‏22- مروری بر کارهای […] 

فصل اول: کلیات تحقیق فصل دوم : مرور منابع ، ادبیات و پیشینه تحقیق فصل سوم : روش اجرای تحقیق ، مواد وروش فصل چهارم : تجزیه و تحلیل داده ها ویافته های تحقیق فصل پنجم : بحث، نتیجه گیری و پیشنهادات میباشد. centercenterفصل اول کلیات تحقیق 00فصل اول کلیات تحقیق 243332040640000 1-1 بیان مسئله […]

پایاپیوند را نشانه‌گذاری کنید.

– (7)

بدست 92

Please enter banners and links.

1-5 فرضیه
به نظرمی رسد درشهرستان رضوانشهر گردشگری روستایی توسعه یافته است.
توسعه نظام گردشگری روستایی در شهرستان رضوانشهر مناسب است.
1-6 قلمرو تحقیقشهرستان رضوانشهر در مختصات جغرافیایی21 40 48 تا 7 13 49 طول شرقی و 27 25 37 تا 34 40 37 عرض شمالی قرار دارد. این شهرستان دارای دو بخش به نامهای پره سر و مرکزی و 4 دهستان به نامهای دیناچال، ییلاقی ارده، خوشابر، ‌گیل دولاب می باشد. مساحت این شهرستان 3/770 کیلومتر مربع و جمعیت آن بر اساس آمار سال 1385 به تعداد 64574 نفر بوده که از این تعداد 20346 نفر را جمعیت شهری و 44228 نفر را جمعیت روستایی تشکیل می دهد. این شهرستان از شمال به شهرستان تالش، از جنوب به شهرستان ماسال و صومعه سرا، ‌از شرق و جنوب شرق به شهرستان بندر انزلی و دریای خزر و از غرب به استان اردبیل محدود می شود( سالنامه آماری استان گیلان، 1387).

نقشه 1-1 محدوده مورد مطالعه1-7 محدویت های تحقیق هر تحقیقی مشکلات مخصوص به خود را دارد. یکی از محدودیتهای مهم تحقیق حاضر جدید بودن موضوع مورد مطالعه می باشد، چون در این ارتباط خیلی کم کار شده است.
کمبود اطلاعات مرتبط با عنوان فوق، عدم توانایی و تطبیق نمودن درجات سطح بندی در کشور، استان با کشورهای پیشرفته، صعب العبور بودن برخی مناطق و عدم دسترسی جهت مظالعات میدانی
1-8 واژه ها و مفاهیمتوریسم:
در سال 1963 کنفرانس جهانی توریسم در شهر رم واژه توریسم را به شرح ذیل تعریف نمود:
توریست کسی است که به طور موقت مسافرت می کند و در کشور مورد علاقه خود حداقل 24 ساعت اقامت می نماید. در ضمن هدف از مسافرت خود را استفاده از تعطیلات، تامین سلامتی، مطالعه و تحقیق، موارد مذهبی و ورزشی، تجارت و امور بازرگانی، مسائل خانوادگی، ماموریت، شرکت در کنفرانسها و غیره می داند (منشی زاده، 1376، ص 12).
– روستا
ــ روستا به مجموعه یک یا چند مکان و اراضی به هم پیوسته ( اعم از کشاورزی و غیر کشاورزی) گفته می شود که خارج از محدوده ی شهرها واقع شود، دارای محدوده ی ثبتی و یا عرفی مستقل باشد.
ــ روستا مبدا تقسیمات کشوری است که از لحاظ زیستی (وضع طبیعی، اجتماعی، فرهنگی و اقتصادی) همگن بوده، اکثریت ساکنان واقعی آن – به طور مستقیم و غیر مستقیم – به یکی از فعالیتهای زراعی، دامداری، باغداری و به طور اعم صنایع دستی و صید یا ترکیبی از این فعالیتها اشتغال داشته باشند در عرف به عنوان ده، آبادی، دهکده یا قریه نامیده می شود (پاپلی یزدی و ابراهیمی، 1381، ص 22).
گردشگری روستایی
لین(lane،1994) گردشگری روستایی را چنین تعریف می کند: فعالیتهای توریستی که در روستا صورت می‎گیرد. ولی حتی این عبارت ساده ابهامات زیادی در بردارد بطور مثال خود تعریف گردشگری متفاوت است و در مورد روستا تفاوتی که بین فعالیتهای گردشگری، مثل اوقات فراغت یا ورزش وجود دارد. را خدشه دار می سازد. به همین ترتیب تعریف روستا یا مناطق روستایی نیز دشوار است (جولیا شارپلی، ترجمه منشی زاده و نصیری، 1380، ص8).
مدل:
نمونه، سر مشق، طرح و الگو، الگو گرفتن ( فرهنگ فارسی عمید )
مدل جغرافیایی :
مدل جغرافیایی به مجموعه آنچه که آموزش یک مفهوم جغرافیایی را ساده می کند و در تفهیم یک موضوع پیچیده جغرافیایی کمک می کند یا یک نظریه یا فرضیه جغرافیایی تجزیه شده را اثبات می کند مدل جغرافیایی می گویند.
سطح بندی
درجه بندی و دادن امتیاز به یک موضوع چه انسانی و چه طبیعی را می توان تحت عنوان سطح بندی آن موضوع بیان نمود.
مدل EP
یک مدل سطح بندی در صنعت گردشگری و غیره بوده که براساس آن می توان با در نظر گرفتن (پنج مؤلفه) برای ارزیابی وسطح بندی جاذبه های تاریخی و طبیعی در یک منطقه به مطالعه پرداخت که پنج مؤلفه فوق عبارتند از: جذابیت های پیرامونی، امکانات رفاهی، خدمات فرهنگی، دسترسی و اجتماعات محلی می باشد.

2499995864425500centercenterفصل دوم
مرور منابع ،ادبیات و پیشینه تحقیق
00فصل دوم
مرور منابع ،ادبیات و پیشینه تحقیق
2-1 توریسم و گردشگریگردشگری معادل فارسی و کاملاً دقیق واژه Tourism در زبانهای انگلیسی، فرانسه و آلمانی است که بصورت مصطلح در زبان فارسی بصورت جهانگردی ترجمه شده است. ریشه این واژه از اصطلاحTornus یونانی و لاتین گرفته شده که یکی از معانی آن گردش کردن و یا گشتن است و با پسوند Ism یا گری بصورت اسم مصدر Tourism یا گردشگری در آمده‏است.
اصطلاح “ توریست“ از قرن نوزدهم معمول شده است. در آن زمان اشراف زادگان فرانسوی می بایست برای تکمیل تحصیلات و کسب تجربه های لازم زندگی، اقدام به مسافرت می نمودند. این جوانان در آن زمان توریست نامیده می شدند و بعد ها در فرانسه این اصطلاح در مورد کسانی به کار می رفت که برای سرگرمی، وقت گذرانی و گردش به فرانسه سفر می کردند و بعداً با تعمیم بیشتر به کسانی اطلاق می شد که اصولاً به این منظور به سفر می رفتند. کم کم کلمه توریسم به بعضی زبانهای دیگر نیز وارد شد و از آن واژه توریسم به وجود آمد. از همان زمان توریسم به بعضی از مسافرت ها مسافرینی گفته می شود که هدف آنها استراحت و گردش و سرگرمی و آشنایی با مردم بود و نه کسب درآمد و اشتغال به کار.
در زبان فارسی کلمه ”سیاح” در گذشته به کسانی گفته می شد که با هدف و منظور شخصی دست به سفر می زدند؛ مانند ناصر خسرو و سعدی، و این واژه در زبان فارسی تا نیمه اول قرن بیستم در معنی فوق بکار می رفت تا آنکه دو واژه جهانگرد و جهانگردی جای آن را گرفت.
واژه جهانگردی به این سبب که در معنی خود عبور از مرز های سیاسی و سفر به دیگر کشورها را تداعی می کند، نمی توان معنی کامل توریسم را ادا نماید. زیرا توریستها به دو گروه خارجی و توریستهای داخلی تقسیم می شوند. که واژه جهانگرد بیشتر در تعریف توریستهای خارجی کاربرد دارد. در صورتی که توریستهای داخلی نیز باید در واژه گزینی فارسی کلمه توریست گنجانده شود. از این رو واژه ”گردشگر” رساتر از واژه جهانگرد بوده و گویای اصلاح توریست می باشد.
جهانگردی: عبارتست از مجموعه فعالیتهای افرادی که به مکانهای خارج از محل زندگی و کار خود به قصد تفریح و استراحت و انجام امور دیگر مسافرت می کنند و بیش از یکسال متوالی در آن مکان نمی‎مانند (منشی زاده، 1376، ص43).
2-2 تعریف اصطلاحات توریسمدر شناخت توریست یا گردشگر تعاریف مختلفی از سوی سازمان‏ها و افراد مختلف ارائه شده است که به بخشی از آنها اشاره می‏گردد.
واژه «توریسم» به مجموعه مسافرت‏هایی گفته می‏شود که بین مبدأ و مقصدی با انگیزه‏های استراحتی، تفریحی، تفرجی، ورزشی، دیداری، تجاری، فرهنگی و یا گذران اوقات فراغت انجام می‏گیرد و در آن شخص توریست در مقصد اشتغال و اقامت دائم ندارد.
در سال 1925 کمیته مخصوص آمارگیری مجمع ملل افراد زیر را توریست شناخت:
1 – کسانی که برای تفریح و دلایل شخصی با مقاصد پزشکی و درمانی سفر می‏کنند.
2- کسانی که برای شرکت در کنفرانس‏ها، نمایشگاهها، مراسم مذهبی، مسابقات ورزشی و از این قبیل به کشورهای دیگر سفر می‏کنند.
3 – کسانی که به منظور بازاریابی و امور بازرگانی مسافرت می‏کنند.
4 – افرادی که با کشتی مسافرت می‏کنند و در بندری در مسیر راه تا 24 ساعت اقامت می‏نمایند.
در سال 1937 نیز کمیته ویژه‏ای در رم جهت بررسی پاره‏ای از مسائل صنعت توریسم تشکیل گردید و تعریفی به این شرح از توریست ارائه داد:
«افرادی که در یک دوره 24 ساعته یا بیشتر به یک کشور خارجی سفر می‏کنند توریست خوانده می‏شوند»
این کمیته مسافرت‏های زیر را به عنوان حرکت‏های توریستی به شمار آورد:
1 – افرادی که جهت خوش‏گذرانی، دلایل شخصی ویا مسائل بهداشتی به مسافرت می‏روند.
2 – افرادی که برای شرکت در کنفرانس‏ها مسافرت می‏کنند.
3 – افرادی که جهت انجام کارهای بازرگانی مسافرت می‏کنند.
4 – افرادی که به یک گردش دریایی می‏روند.
براساس‏تعریفی از سازمان ملل که بنا بر پیشنهاد کنفرانس بین‏المللی جهانگردی آن سازمان دررم ارائه گردید؛« توریست یا بازدیدکننده‏موقت‏کسی‏است‏که به منظور تفریح، استراحت، گذران تعطیلات، بازدید از نقاط دیدنی، انجام امورپزشکی، درمانی ومعالجه، تجارت، ورزش، زیارت، دیداراز خانواده، مأموریت و شرکت در کنفرانس‏ها به کشوری غیر از کشور خود سفر می‏کند؛ مشروط بر اینکه حداقل مدت اقامت او از 24 ساعت کمتر و از 3 ماه بیشتر نبوده و کسب شغل و پیشه هم مد نظر نباشد. »
براساس تعریف فوق گردشگری داخلی درقالب صنعت توریسم قرار نگرفته وصرفاً به گردشگرانی که از دیگر کشورها وارد یک کشور می‏گردند اصطلاح توریست اطلاق می‏شود.
بنا به تعریفی دیگر : « عامل توریستی یا جهانگردی کسی است که عمل جهانگردی را انجام می‏دهد و به سه دسته تقسیم می‏شود:
توریست‏هایی که از خارج وارد کشور می‏شوند.
توریست‏هایی که از کشور خود به کشور دیگر مسافرت میکنند.
توریست‏هایی که مقیم کشور خود هستند و در داخل کشورشان مسافرت می‏کنند.
انگیزه اینگونه افراد از مسافرت، تفریح، معالجه، تجارت، تحقیق، زیارت، مأموریت و نظایر آن است »
مرکز آمار ایران به منظور تفکیک توریسم از غیر توریسم، تعریف زیر را از توریسم ارائه داده است:
«توریست شخصی است که به کشور یا شهری غیر از محیط زیست عادی خود برای مدتی که کمتر از 24 ساعت و بیشتر از یکسال نباشدسفر کند و قصد او از سفر، تفریح، استراحت، ورزش، دیدار اقوام و دوستان، مأموریت شرکت در سمینار، کنفرانس یا اجلاس، معالجه، مطالعه و تحقیق و یا فعالیت مذهبی باشد».
مرکز فوق در تعریف غیر توریست نیز آورده است : « غیر توریست کسی است که کشور محل دائمی اقامت خود را به قصد اشتغال، اقامت دائم، پناهندگی، تحصیل، مأموریت در نمایندگی‎های سیاسی خارج از کشور ترک نماید.»
در جمع‏بندی تعاریف ارائه شده برای توریست یا گردشگر و به منظور تعریفی جامع از این واژه که در برگیرنده تمامی فعالیت‏های بخش گردشگری (اعم از داخلی و خارجی) باشد،
می‏توان تعریف زیر را از واژه توریست یا گردشگر ارائه نمود:
«توریست یا گردشگر به کسی اطلاق می‏گردد به منظوری غیر از اشتغال یا اقامت دائم به مقصدی مسافرت نموده و حداقل یک شب و حداکثر یک سال را در مقصد اقامت نماید و برای هزینه اقامت و فعالیت‏های گردشگری خود هیچگونه درآمدی در مقصد مورد نظر نداشته باشد.»
در این تعریف هیچ تفاوتی بین توریست داخلی و توریست خارجی وجود نداشته و به هر دو گروه به یک چشم نگریسته شده است. کما این که در بسیاری از مباحث مربوط به بخش توریست و یا صنعت توریسم، منظور از توریست، افرادی است که از دیگر کشورها به یک کشور وارد می‏شوند و به واسطه ارزآوری خود از اهمیت شایان توجهی برخوردار هستند (منشی زاده، 1376، ص44).
2-3 طبقه‏بندی انواع توریسمتوریسم دارای انواع مختلفی بوده که براساس عوامل متعدد می‏توان تقسیم‏بندی‏هایی را برای آن قائل شد. مهمترین عواملی که می‏توان براساس آن انواع مختلفی از توریسم را تعریف و طبقه‏بندی نمود عبارتند از:
الف – از نظر زمانی
فعالیت‏های گردشگری را به شکل کوتاه مدت (کمتر از یک روز)، میان مدت (یک تا سه روز ) و درازمدت (بیش از سه روز) از یکدیگر تفکیک می‏کند.
ب – از نظر مکانی
گردشگری را به صورت فعالیت‏های گردشگری در حوزه نزدیک، حوزه میانی و حوزه خارج یا دور تقسیم‏بندی می‏کند.
پ – از نظر تابعیت
گردشگران ‏به دو گروه گردشگران خارجی و بین‏المللی و گردشگران داخلی تقسیم می‏گردد.
ت – از لحاظ انگیزه سفر
براساس آن گردشگری با انگیزه‏های استراحتی، تفریحی، درمانی، زیارتی، فرهنگی، اقتصادی، ورزشی و. . . از یکدیگر تفکیک می‏شوند.
ث – از نظر فصل گردشگری
موسم گردشگری را براساس فصول مختلف سال طبقه‏بندی می‏گردد. در این طبقه‏بندی
دو فصل تابستان و زمستان از اهمیت بالاتری نسبت به فصول بهار و پاییز می‏یابند.
د – از نظر شکل و سازمان‏دهی سفر
مانند سفرهای انفرادی، گروهی، خانوادگی و. . . که ترکیب گردشگری را تعیین می‏کند.
ز – از نظر وسیله نقلیه مورد استفاده
براساس نوع وسیله نقلیه مورد استفاده برای انجام سفر طبقه‏بندی می‏شود.
و – از لحاظ نوع و محل اقامت
گردشگران را براساس نوع و محل اقامت، هم از نظر کیفی و هم کمی طبقه‏بندی می‏کند. مانند گردشگران مقیـم هتل‏ها، مهمانپذیـرها، خانه‎های ویلایی و یا پانسیون‏های خانگی، کمپینگ و. . . .
2-4 اشکال عمده توریسممکان دربخش گردشگری از اهمیت بسیار زیادی به لحاظ پیدایش شیوه‏های متعدد گردشگری برخوردار است. عامل مکان به لحاظ گستره جغرافیایی و تنوع پدیده‏های جاذب توریسم، نقش اصلی را در ایجاد انگیزه‏های سفر نیز ایجاد می‏نماید. براساس انگیزه و اهداف توریست‏ها از مسافرت که ناشی از عامل مکان است را می‏توان به سه گروه عمده زیر طبقه‏بندی نمود:
توریسم فرهنگی، تاریخی و یادمانی
توریسم طبیعت یا اکوتوریسم
توریسم بازرگانی و تجاری
هر یک از گروه‏های یاد شده به زیر گروههایی تقسیم می‏شوند که به لحاظ مهم بودن گروه توریسم طبیعت یا اکوتوریسم فقط به انواع آنها پرداخته می‏شود.
2-4-1 توریسم طبیعت یا اکوتوریسم
توریسم طبیعت یا اکوتوریسم نیز از مهمترین جاذبه‏های بخش گردشگری است و سالانه میلیون‏ها نفر به منظور دیدار از مناطق خوش آب و هوا و یا خوش منظره، تمدد اعصاب و استراحت، استفاده از آبهای معدنی و درمانی، تفریح ، هیجان، ماجراجویی، ورزش و غیره جذب توریسم طبیعت و یا اکوتوریسم می‏شوند. اکوتوریسم به بخش‏های بسیار زیادی تقسیم می‏گردد که به برخی از آنها اشاره می‏گردد:
2-4-1-1 توریسم اقلیمی (کلیماتوریسم)آب و هوا به عنوان یکی از مهمترین عوامل شکل‏دهنده توریسم قلمداد می‏گردد و مراکز تفریحی و توریستی موجود، چه در گذشته و چه در حال حاضر موجودیت و ارزش‏های خود را مرهون عوامل متعدد به ویژه آب و هوای مناسب و ملایم می‏دانند.
آب و هوا و تنوع اقلیمی یکی از مهمترین جاذبه‏های توریستی است که بخش قابل توجهی از گردشگران را به منظور استفاده از آب و هوای گرمتر و یا خنکتر از محل اقامت خود، به انجام خود، به انجام مسافرت توریستی ترغیب می‏نماید.
هوای آلوده شهرهای جامعه صنعتی به ویژه در فصل تابستان جمعیت شهر را به فرار و گریز از شهر وا می دارد و به موازات استحکام زیربنای اقتصادی خانواده‏ها، حرکت انسانها در افق‏های دورتر و در سینه کوهستان‏ها یا پهنه آبها انجام می‏گیرد.
به طورکلی کسی مایل به مسافرت تابستانی به محلی نیست که هوای محل اقامتش باشد. از این رو مناطق ییلاقی و کوهپایه‏ای و سواحل، مکان‏های مناسبی برای مسافرت تابستانی به شمار می‏روند.
2-4-1-2 توریسم ساحلی
از فضاهای پاک و نیالوده‏ای که جمعیت گردشگران را به سوی خود می‏خواند، مناطق ساحلی و شهرهای دریاکنار است. پلاژهای وسیع کناره دریا با شن نرم و هوای مساعد و داشتن پناهگاه‏هایی مصون از تعرض امواج دریا و باد، میکروکلیمای مناسبی برای بهره‏برداری‏های توریستی است، تا جایی که شهرسازی کناره دریاها در طول ده‏ها کیلومتر ساحل، امروزه شکل تعمیم یافته‏ای به خود گرفته است. این پلاژها به شرط پیوند با جنگل و پارک و کوهستان از قدرت جاذبه خاصی بهره‏مند می‏گردند.
سواحل دریا، به ویژه در فصل شنا و ماهیگیری از جاذبه‏های مهم گردشگری در جهان است که تفریح، هیجان و احیاناً قابلیتهای درمانی (ماسه‏های ساحلی و یا لجن‏های دریایی و دریاچه‏ای) انگیزه اصلی سفر را به وجود می‏آورد.
سواحل نزدیک به بندرگاه‏های تجاری و بازرگانی به واسطه داشتن بازارهای کالاهای وارداتی و عمدتاً ارزان قیمت بر جاذبه‏های گردشگری این گونه شهرها افزوده و توریست‏های بیشتری را به خود جذب می‏نماید.
رونق ورزش‏های آبی و نشاط و هیجان ناشی از آن در صورت وجود امکانات، از دیگر جاذبه‏های توریسم ساحلی است. ورزش‏هایی مانند اسکی روی آب، قایقرانی، موج‏سواری، جت‏اسکی و. . . را می‏توان از جمله موارد جذب گردشگر در مناطق ساحلی بشمار آورد.
2-4-1-3 توریسم کوهستان و برف شهرها
کوه‏های مهم و معروف را می‏توان از جمله موارد مورد توجه اکوتوریسم به شمار آورد که هم به لحاظ ورزشی و هم از لحاظ تفریحی مورد توجه توریست‏ها قرار می‏گیرد.
وجود امکانات دسترسی به منطقه پایکوهی و امکان استقرار موقت در اقامتگاه‏های نزدیک به قله، می‏تواند بر رونق توریسم کوهستان بیافزاید.
گرچه فعالیت برف شهرهای کوتاه مدت، و توریسم کوهستان فصلی است ولی به مقتضای نوع فعالیت، تجهیزات ویژه‏ای را چون تله‏اسکی برای صعود بر کوهستان را می‏طلبد و با ایجاد امکاناتی نظیر پیست‏های اسکی میتوان دوره گردشگری را در این گونه شهرها از حالت فصلی خارج نموده و به یک جریان عادی توریسم تبدیل نمود که در فصول گرم به منظور کوهنوردی و صخره‏نوردی در فصول سرد به منظور اسکی روی برف، گردشگران را به سوی خود فرا می‏خواند.
2-4-1-4 توریسم جنگلجنگل‏ها وپارک‏های جنگلی نیز از جمله جاذبه‏های اصلی بخش توریسم به حساب می‏آیند. اینگونه مناطق معمولاًُ به لحاظ زیست بوم‏های گیاهی و جانوری هم از سوی محققین و پژوهشگران و هم از سوی توریست‏هایی که عادی مورد توجه قرار گرفته و در صورت وجود امکاناتی از قبیل اقامتگاه‏ها، مراکز ارائه خدمات، کمپینگ و. . . به یکی از مهمترین کانون‏های جذب گردشگر تبدیل می‏گردند.
2-4-1-5 توریسم کویر و بیابان
کویرها و بیابانها علی‏رغم اینکه در نگاه اول یک منطقه خشک و خالی از سکنه را در ذهن تداعی می‏نمایند، اما یکی از جاذبه‏های توریستی به حساب می‏آیند و در صورتی که بتوان اقدام به ایجاد امکانات خدمات توریستی و مراکز اقامتی مناسب در مناطق کویری و بیابانی مبادرت نمود، اینگونه مناطق نیز می‏توانند در جذب گردشگران نقش مهمی را ایفا نمایند.
2-4-1-6 توریسم آبهای معدنی و آبهای گرمآبهایی که بر اثر شکست و یا لغزش زمین و معمولاً در کنار کوه‏های آتشفشانی از اعماق زمین بیرون می‏جهند، به سبب داشتن اجزاء رادیو اکتیو، گوگرد و املاح معدنی گوناگون، جنبه درمانی داشته و در دورانی که هنوز صنعت داروسازی به مانند امروز توسعه نیافته بود، آبهای معدنی، گروههای مرفه طبقات اجتماعی را برای درمان به سوی خود جلب می‏کرد. وسایل ارتباطی به حرکت موجی تمام طبقات اجتماعی به سوی آبهای گرم معدنی منتهی شد و در کنار آبها مراکز اولیه شهرها تکوین یافت و برخی از آنها امروزه به عنوان یک شهر توریستی معروف در جهان تبدیل شده است.
2-4-1-7 توریسم درمانی
این نوع شامل افراد و گروههایی هستند که برای استفاده از تغییر آب و هوا (با هدف پزشکی و درمانی)، استفاده از آبهای معدنی، گذران دوران نقاهت، معالجه و نظایر آن اقدام به مسافرت می‏کنند.
2-4-1-8 توریسم ورزشیهر نوع مسافرتی که به منظور فعالیتهای ورزشی باشد، جهانگردی ورزشی نامیده می‏شود، مانند اسکی، پیاده‏روی، کوهپیمایی، کوهنوردی، دوچرخه‏سواری، شکار، شنا، قایقرانی، شرکت در مسابقات ورزشی و تماشای مسابقات و امثال آن، اینگونه مسافرتها ممکن است به صورت انفرادی و یا دسته‏جمعی صورت گیرد (رحیمپور، 1384، ص37).
2-5 گردشگری روستاییبا توجه به اهمیت گردشگری روستایی به عنوان یک فعالیت گسترده گردشگری و تاکید روزافزون به آن در سیاستهای توسعه محلی و منطقه ای بدیهی است که تعریف مشترک و قابل قبولی از گردشگری روستایی را از سایر بخشهای گردشگری جدا می کند. در نظر اول ممکن است تعریف گردشگری روستایی آسان به نظر برسد. لین(lane،1994) گردشگری روستایی را چنین تعریف می کند: فعالیتهای توریستی که در روستا صورت می گیرد. ولی حتی این عبارت ساده ابهامات زیادی در بردارد بطور مثال خود تعریف گردشگری متفاوت است و در مورد روستا تفاوتی که بین فعالیتهای گردشگری، مثل اوقات فراغت یا ورزش وجود دارد. را خدشه دار می سازد. به همین ترتیب تعریف روستا یا مناطق روستایی نیز دشوار است. عباراتی که غالبا جایگزین گردشگری روستایی می شوند از قبیل گردشگری بومی و گردشگری طبیعت مشکلات بیشتری را ایجاد می کنند. برخی اوقات این بدین معناست که گردشگری روستایی با فعالیتها یا مکانهای ویژه مانند گردشگری کشاورزی یکسان شمرده می شود. حال آنکه در موارد دیگر گردشگری روستایی به عنوان وسیله ای برای توصیف کلی و همه جانبه توسعه گردشگری بکار گرفته می‎شود.در سال 1986 کمسیون جامعه اروپایی گردشگری روستایی را اینگونه تعریف کرد توریسم روستایی تنها شامل گردشگری کشاورزی نیست. بلکه همه فعالیتهای گردشگری در مناطق روستایی را در برمی گیرد. تلاش برای شناسایی همه فعالیتهای گردشگری چیز زیادی را عاید نمی کند(جولیا شارپلی، ترجمه منشی‎زاده و نصیری، 1380، ص8).
2-5-1 محدوده گردشگری روستاییدیدار کنندگان از روستا ها به فعالیتهای مختلفی روی می آورند. برخی از این فعالیتها مانند پیاده روی یا اسب سواری از بخشهای گردشگری هستند. در حالیکه سایر فعالیتهایی که در اوقات فراغت انجام می شوند نوعی ورزش محسوب می گردند. بطور مثال کوه نوردی، غارنوردی، تماشای مسابقه های ورزشی در روستا یا حتی رفتن به یک رستوران روستایی در مرتبه دوم اولویت قرار می گیرند. درعین حال هر نوع گردشگری که در روستا صورت می گیرد. حالت سنتی روستا را نداردو نوع توسعه یافته گردشگری خواهد بود مانند پارکهای تفریحی با موضوعات و سبکهای خاص که به کلی با محیط زیست روستایی ناهماهنگ هستند. بنابراین در ابتدا می توان گفت که محدوده گردشگری روستایی و فعالیتهای آن از برخی جهات محدود شده‎اند. آنها بوسیله عواملی چون مدت اقامت، طول سفر، نوع فعالیت، وسایل و محل اقامت و تصوری که هرکس از گردشگری روستایی داردمحدود شده اند. با این حال اگر تعریفی کلی از توریسم روستایی ارائه شود محدوده گردشگری روستایی هم وسیع تر خواهد شد. با این حال محدوده گردشگری روستایی در فهرستی که توسط اتحادیه اروپا ارائه شد.
1-گشت و گذارگردش در جاده های فرعی و طولانی کوهستانی و پارکهای طبیعی روستا، اسب سواری، سفر در کاروانها و ارابه کولیها، مسافرت با وسایل نقلیه موتوری (راندن در جاده های روستایی، راندن ماشین های کشاورزی، اتومبیل رانی)، دوچرخه سواری، قاطر سواری، اسکی در روستا.
2-فعالیتهای آبیماهیگیری، شنا، مسافرت در رودخانه (بوسیله قایق های خانه مانندو قایق های کوچک، کرجی)، قایق رانی با قایق های پارویی و کلک، موج سواری روی آب، مسابقه قایقرانی، کشتی رانی، انواع دیگر وسایل آبی.
3-فعالیتهای هواییهواپیمای سبک وزن، گلایدر دستی و هواپیمای بسیار سبک وزن، بالونهای هوای گرم.
4-فعالیتهای زمینیتنیس، گلف.
5-فعالیتهای ورزشیغارنوردی، صخره نوردی.
6-فعالیتهای اکتشافیاقدامات صنعتی محلی وکشاورزی یا مهارتی7-فعالیتهای فرهنگیباستانشناسی، تجدید بنا، دوره های یادگیری مهارت، کارگاههای هنری، دسته های قومی، سایر کارهای فرهنگی8-فعالیتهای مربوط به سلامتیزیبایی اندام، مراکز تندرستی می باشد.
لازم به یادآوری است که تعدادی از فراورده های مختلف گردشگری یا انواع توسعه گردشگری جزء گردشگری روستایی قرار می گیرند. ولی الزاما با آن همخوانی و هماهنگی ندارند (جولیا شارپلی، ترجمه منشی زاده و نصیری، 1380، ص13).

2-5-2 اصول کلی برای گردشگری در روستاتفریح:گسترش تفریحات گردشگران در روستا باید بر اساس فعالیتهایی باشد که نمایانگر ویژگی روستا، زیباییها، فرهنگ، تاریخ و حیات وحش آن باشند.
توسعه:توسعه روستا باید حفظ محیط زیست و اهداف تفریحی را تقویت کند. بطور مثال می تواند استفاده بهتری از مکانهای تاریخی داشته باشد. تا مکمل درآمدهای حاصل از زمینهای کشاورزی باشد. و این مهم با احیای زمینهای متروک و ایجاد فرصتهای جدید برای دسترسی به روستا حاصل می شود.
طرح ریزی:برنامه ریزی و اداره توسعه جدید گردشگری باید با منظره توازن داشته باشد. و هرجا که ممکن است آنرا گسترش دهد.
اقتصاد روستایی:سرمایه گذاری در گردشگری روستایی باید از اقتصاد آن حمایت کند با این حال باید در مناطق وسیع کم جمعیت صورت گیرد، تا از انبوهی جمعیت و خسارات ناشی از فرسایش منابع طبیعی و استفاده بیش از حد انها جلوگیری شودو موجب گسترش اقتصاد و فواید دیگر شود.
حفظ محیط زیست:کسانی که از گردشگری روستایی سود می برند باید در حفظ آن سهیم باشند و با حمایتهای سیاسی و عملی از محیط زیست و اجرای سیاستها و برنامه های تفریحی، کیفیت آنرا بهبود بخشند.
بازاریابی :تبلیغ و اطلاع رسانی در مورد صنعت گردشگری باید فهم مردم را نسبت به ان عمیق کند تا استفاده بهینه از روستا منجر به درک و لذت بردن از انها شود(جولیا شارپلی، ترجمه منشی زاده و نصیری، 1380، ص23).
2-5-3 فواید توسعه گردشگری روستاییمهمترین هدف توسعه گردشگری داخلی و خارجی، توسعه اقتصادی و اجتماعی مناطق گردشی است. بسیاری از کشورها کم و بیش به گردشگری توجه دارند زیرا مهمترین تاثیر گردشگری در اقتصاد جهانی، ایجاد درامد و اشتغال زایی است. کارشناسان تخمین زده اندکه گردشگری به عنوان بزرگترین صنعت جهان، 4/3 تریلیون دلار ارزش دارد و این میزان جوابگوی 1/10 درصد محصولات ناخالص جهانی است و 6/10 درصد هزینه اشتغال زایی در جهان را تامین می کند. مسلما بخش کوچکی از گردشگری راگردشگری روستایی تشکیل می دهد. که البته سهم مهمی را در اقتصاد مناطق روستایی دارد. بطور مثال گردشگری روستایی در انگلستان تقریبا هر سال 9 میلیون پوند درآمد ایجاد کرده است و در برخی نقاط این کشور عامل اصلی اشتغال زایی بوده است. توجه به بازده ناخالص و تعداد شغلهایی که گردشگری ایجاد کرده برفواید اقتصادی، اجتماعی و زیست محیطی حاصل از توسعه گردشگری در مناطق روستایی سرپوش خواهد گذاشت. بنابراین فواید حاصل از گردشگری به شرح زیرمی باشد.
فواید اقتصادیگردشگری روستایی منبع مهم و جدید ایجاد درآمد برای جوامع روستایی است بنابراین در کارهایی که با گردشگری مرتبط هستند مثل آماده کردن اتاق برای گردشگران، تهیه غذا، خرده فروشی، حمل و نقل و ایجاد سرگرمی، شغلهای جدیدی بوجود می آیند.
از فعالیتهای خدماتی موجود مثل سیستم حمل و نقل، مراقبتهای دارویی، صنایع و حرفه های سنتی روستایی حمایت می شود.
تنوع اقتصاد محلی بیشتر و اقتصاد جوامع محلی گسترده و استوار می شودفرصتهایی برای فعالیتهای چند گانه بوجود می آیدو بدین وسیله از رکود اقتصادی موقتی جلوگیری و از درآمد ها حمایت می شود.
از حرفه ها و خدمات موجود حمایت می شود.شغلهای جدید و متنوع در مناطق مختلف ایجاد می شوند و بوسیله کم کردن کمک هزینه های کشاورزی اقتصاد محلی را تقویت می کند.
فواید اجتماعیتوسعه گردشگری روستایی سبب فواید اجتماعی مختلفی در جوامع روستایی می شوداز قبیل:-تقویت و حمایت خدمات محلی مانند حمل و نقل عمومی و مراقبتهای بهداشتی-ایجاد امکانات و جاذبه های جدید مثل امکانات فرهنگی، مراکز تفریحی یا ورزشی-افزایش روابط اجتماعی در جوامع دور افتاده روستایی و ایجاد فرصتهایی برای مبادله فرهنگی
-ایجاد آگاهی بیشتر در زمینه اصطلاح فرهنگهای محلی، حرفه ها و هویت فرهنگی-پرکردن دوباره جمعیت در مناطق روستایی، زیرا این امر با سیاستهای کاهش جمعیت و افزایش تعداد کهنسالان جوامع روستایی مقابله می کند-افزایش نقش زنان در جوامعی که سنتی تر و دور افتاده تر هستند.
فواید زیست محیطیانگیزه اصلی بسیاری از گردشگران از دیدار روستا، بهره گیری از فضای روستایی است موفقیت گسترش گردشگری روستایی به محیط زیست جذاب بستگی داردبنابراین گردشگری هم درآمد ایجاد می کند و هم انگیزه حفظ، حمایت و آبادانی محیط زیست طبیعی روستا را ایجاد می کند.
از حفظ و آبادانی فضاهای تاریخی مثل خانه های روستایی، باغها و گردشگاهها، حمایت می کندهمچنین گردشگری سبب بازسازی ساختمانهای قدیمی و متروک روستا می شودبطور مثال انبارها یا آسیابهای قدیمی را می توان به مراکز صنعتی و یا اصطبلهای قدیمی را به دستگاههای ساختمانی تبدیل کرد. با انجام فعالیتهای از قبیل دفع زباله، تنظیم آیین نامه های ترافیک و اصلاح ساختمانها منجر به بهبود محیط زیست در دهکده ها و روستاها می شود (جولیا شارپلی، ترجمه منشی زاده و نصیری، 1380، ص42).
2-5-4 آسیب های توسعه گردشگری روستاییروستا منبعی است که برای مقاصد مختلفی از آن بهره برداری می شود و مسلما در کنار فوایدی که دارد آثار منفی نیز به دنبال دارد. مسلما توسعه گردشگری روستایی تحقق نمی یابد مگر اینکه برای آن هزینه هایی صرف شود و با به مخاطره انداختن محیط زیست روستا برآن تاثیر منفی گذارد. علاوه براین موارد همه اقسام گردشگری از جمله گردشگری روستایی تاحدی بر طبیعت و محیط اجتماعی – فرهنگی مناطق توریستی تاثیر منفی می گذارند. بنابرایناز دهه 1970 توجه به گسترش مطلوب انواع مفید گردشگری افزایش یافته است. ولی باید توجه داشت همانطور که فوایدی از توسعه گردشگری روستایی حاصل می شود توسعه نامناسب آن نیز زیانها و آثار منفی به دنبال دارد. ببا این حال سطح این تاثیرات متناسب با عوامل مختلفی چون اهمیت صنعت گردشگری محلی، ظرفیت گردشگران و فعالیتهایشان، استحکام محیط زیست محلی و اقتدار فرهنگها و سنن محلی تغییر می کند.
آسیبهای اقتصادیهمچنان که گردشگری درآمد زاست و در ایجاد فرصتهای شغلی نقش دارد این کارکردها باید زیانهای اقتصادی را به حال تعادل درآورند زیرا گردشگری روستایی موارد زیر را انجام می دهد:هزینه خدمات عمومی مثل جمع آوری زباله، خدمات دارویی و تامین مخارج پلیس ها را افزایش می دهد.
در هزینه های توسعه ای مثل ایجاد جاذبه توریستی، امکانات و به طور کلی اصلاحات زیربنایی دخالت داردمشاغل تمام وقت و فصلی را ایجاد می کند(علاوه براین ممکن است مردم محلی علاقه مندی یا مهارت لازم برای پذیرش شغل پیشنهاد شده از جانب گردشگری را نداشته باشند زیرا بسیاری از مشاغل مربوط به گردشگری توسط افراد غیر روستایی اداره می شوند)غالبا منجر به افزایش قیمت زمین کالا و خدمات می شود بویژه مالکیت خانه های ییلاقی در مناطق روستایی به این معناست که مردم محلی بیش از حد به این صنعت وابسته اند و در نتیجه نظارت جوامع محلی برمناطق توریستی کم می شود.
آسیبهای اجتماعیهجوم تعداد زیاد گردشگران می تواند تاثیرهای کوتاه مدت و بلند مدت براستحکام اجتماعی و فرهنگی جوامع روستایی داشته باشد. مدت زمان طولانی گمان می شدکه گردشگری در روند آشنایی با فرهنگهای جدید و گوناگون محلی تحول ایجادمی کند و این بیشتر در مورد جوامع دور افتاده سنتی و کوچک روستایی که برای تاثیر پذیری از محیط خارج آماده بودندصادق است ولی باید در نظر داشت که توسعه گردشگری موجب تاثیر های منفی برجوامع محلی و فرهنگ آنها می شود. بطور مثال:- جرم و جنایت و سایر رفتارهای ضد اجتماعی را افزایش می دهد.
– تراکم و افزایش جمعیت به حریم ساکنان روستا تجاوز می کند.
– خدمات محلی را کاهش می دهد. بطور مثال رستورانها را جایگزین فروشگاهها ی کوچک محلی می کند.
– روستاییان را با عقاید جدید، مد لباس و شیوه های نادرست رفتاری آشنا می کند که با ارزشهای سنتی – -فرهنگی مقابله می کنند.
– به خانه سازی تاکید می کندو روستاییان را در مورد داشتن درآمد موقت یا اقامت دایمی دچار تردید می‎کند.
آسیبهای زیست محیطیمحیط زیست روستا برای گردشگری انعطاف پذیر و قابل توسعه است به طور کلی حضور تعداد زیاد بازدیدکنندگان و فراهم آوری امکانات تفریحی برای برآورده کردن نیازهای آنها. اگر به طور صحیح کنترل و اداره نشود ویژگی های زیست محیطی که گردشگران را به مناطق روستایی می کشاند کاهش می دهد یا حتی نابود می کند بویژه گردشگری:- باعث ویرانی هایی در محیط زیست ساخته بشر می شود فعالیتهایی مانند اسکی، هاکی، صخره نوردی و اتومبیل رانی در محیط زیست تاثیر گذار هستند و خانه های روستایی، باغها و پارکها در اثر استفاده بیش از حد گردشگران دچار آسیب می شوند.
– آلودگی را در مناطق روستایی افزایش می دهد. ممکن است آلودگی ظاهری باشد وجود اشغال و زباله که ناشی از تردد زیاد مسافران است آلودگی صوتی یا تصویری باشد. که می تواند در اثر فشردگی ترافیک در جاده های روستا یا توسعه نابجا یا دخالت در وضع ظاهری روستا ایجاد شود(جولیا شارپلی، ترجمه منشی زاده و نصیری، 1380، ص45).
2-5-5 خدمات گردشگری روستاییخدمات گردشگری روستایی فعالیتهای مختلفی را شامل می شود. توریسم روستایی سازمانها و شرکتهای زیادی را در بر می گیرد از خصوصی گرفته تا دولتی، از شرکتهای بزرگ بین المللی تاشرکتهای کوچک خانوادگی که همه آنها فواید زیادی را نصیب بازدیدکنندگان روستایی می کنند. اگر چه تقاضا و خدمات گردشگری روستایی دو روی سکه اند و هیچ نقطه مشترکی میان آنها وجود ندارد. به عبارت دیگرتدارک دیدن گردشگری روستایی فرایند پیچیده ودشواری است این پیچیدگی ها به دلیل نیازی است که برای برنامه ریزی و توسعه گسترده تر مناطق روستایی احساس می شود. بنابراین عرضه گردشگری روستایی معمولا به طور جداگانه هر بخش یا فعالیت را مورد توجه قرار می دهد که این بخشها در مجموع نتایج حاصل از گردشگری روستایی را نشان می دهند. در باره بخشهای مختلف مثل گردشگری کشاورزی، فراهم‎آوری فعالیتهایی چون دوچرخه سواری در کوهستان یا سیاستهای موثری چون طراحی پارکهای ملی به عنوان وسیله ای برای وفق دادن میان حفظ محیط زیست و تفریح مطالعات می توانند اطلاعاتی ارائه دهند. اگر چه نمی توان ارزش چنین تحقیقاتی را انکار کرد. اما توجه به خدمات گردشگری از جنبه وسیع تر نیز ضروری است. به عبارت دیگر از نظر گردشگر فراورده گردشگری روستایی فراتر از تسهیلات اقامتی، جاذبه‎ها و انجام فعالیتهای متفاوت است. انگیزه بسیاری از حضور در روستا و ویژگی های ذاتی و اختصاصی روستاست. امکان لذت بردن از آرامش و سکوت روستا و ویژگیهای طبیعی و فرهنگی محیط روستایی هم بخشهای مهمی از فراورده های گردشگری روستایی به حساب می آیند. علاوه براین عوامل دیگری چون حمل و نقل وسهولت سفر در لذت بردن یا احساس رضایت گردشگران اثر می گذارند بنابراین پی بردن به وابستگی متقابل بین این جنبه های متفائت اهمیت اساسی دارد (جولیا شارپلی، ترجمه منشی زاده و نصیری، 1380، ص68).
2-5-6 فراورده کلی گردشگری روستاییدیدار گردشگران از روستاشامل بخشها و فراورده های متفاوتی می شود این بخشها حمل و نقل، اقامتگاه، سرگرمی، جاذبه ها و تسهیلات جزیی را در بر می گیرند که همه اینها در مجموع جزء خدمات گردشگری هستند. گاهی این تسهیلات متفاوت از طریق گروه های سیاحتی و بنگاههای مسافرتی ترتیب داده می‎شوند. گاهی اوقات خود گردشگران این ارکان را انتخاب کرده و فراهم می آورند. این عوامل در کل ترکیبی از فعالیتها و عملکرد ها را ایجاد می کنند که فراورده گردشگری نام دارد. فراورده های گردشگری را می توان از دو جهت بررسی کرد. از طرفی می توان به آن از نقطه نظر صنعت گردشگری یا تولیدکنندگان فراورده‎های گردشگری نگریست زیرا آنها توجه خود را به مشکلاتی که بخشهای مختلف دارندمعطوف کرده اند. از طرف دیگر فراورده گردشگری از دیدگاه گردشگران مورد بررسی قرار می گیرد در این حالت فراورده گردشگری، تجربه کلی گردشگری به حساب می آیدو میزان فراورده ای که از گردشگری حاصل می شود بیشتر از درآمدی است که ایجاد می کند به عبارت دیگر فراورده گردشگری روستایی تنها مجموعه جاذبه ها، تسهیلات و فرصتها ی تفریحی در روستا نیست. بلکه دوره ها و زمانها یی را که قبل و بعد از دیدارها در روستا رخ می دهنددر بر می گیرد (جولیا شارپلی، ترجمه منشی زاده و نصیری، 1380، ص68).
2-6 زیربناهای صنعت توریسمبرای موفقیت صنعت توریسم وجود عامل زیربنایی از اهمیت زیادی برخوردار می‏باشد. این زیربناها عبارتند از : شاهراه‏ها، فرودگاه‏ها، خطوط راه‏آهن، جاده‏ها، پارکینگ‏ها، پارک‏ها امکانات روشنایی، تسهیلات دریایی، اتوبوس، هتل‏ها، رستوران‏ها، مراکز خرید، اماکن تفریحی، موزه‏ها، مغازه‏ها. همچنین سیستم بنایی مهم در جهانگردی به شمار می‏آید که این تأسیسات می‏بایست قابل استفاده باشند و طوری طراحی شوند که برای هرگونه افزایش و توسعه در آینده مناسب باشند.
امکانات اقامتی و هتل‏ها نیز از جمله زیربناهای مهم در جهانگردی هستند که باید علاوه بر مکان‏یابی از نظر شیوه‏های مهندسی جدید با رعایت سبک‏های محل طراحی و ساخته شوند به صورتی که تزئینات داخلی هتل‏ها جالب و آرامش بخش باشد و محیطی زیبا و دلنشین فراهم آورد.
وجود جاده‎‏ها از عوامل دیگری در صنعت جهانگردی است، زیرا متداول‏ترین وسیله حمل و نقل در کشورهای توسعه یافته، اتومبیل است. اگر چه ساختن جاده‏ها بسیار مهم بوده اما می‏بایست به نحوی ساخته شوند که در مقابل تغییرات آب و هوایی مقاوم و براساس استانداردهای بین‏المللی باشد.
خدمات فرعی از قبیل پمپ‏های بنزین و تعمیرگاه، رستوران‏های کنار جاده، پارک‏ها و سرویس‏های بهداشتی و تابلوهای راهنما از جمله عواملی است که باید در نظر گرفته شود. برای احداث جاده‏های جدید باید برنامه‏ریزی بلند مدت انجام شود و توجه خاصی به جاده‏ها با مناظر زیبا صورت گیرد.
علاوه بر این موارد، آثار فرهنگی نیز موجب بسیاری از جهانگردان می‏گردد.
منابع فرهنگی هر منطقه شامل هنرهای دستی، ادبیات، تاریخ، موسیقی، هنرهای نمایشی، رقص، ورزش‏ها و سایر فعالیت‏های فرهنگی است.
روحیه مهمان‏نوازی، خوش‏آمد گویی کارکنان هتل و مؤدب و صمیمی بودن آنها و تمایل به ارائه خدمت قابل قبول و سایر رفتارهای گرم و دوستانه از سوی آنان نیز از عوامل بسیار مهم در جذب جهانگردان و توسعه صنعت توریسم است (پایلی یزدی، و سقایی، 1385، ص 112).
2-7 عوامل موفقیت کشورها در جلب توریسم
به طور کلی عوامل مهمی در بالا رفتن تعداد ورود جهانگرد و در نتیجه افزایش در آمد جهانگردی در یک سرزمین یا کشور دخالت دارد، به قرار زیر :
الف) وسایل آمد و رفتیکی از دلایل بسیار مهم استقبال جهانگردان از رفتن به کشورهای پیشرفته این است که این کشورها وسایل حمل و نقل مطمئن راحت و بسیار منظمی در اختیار دارند. وقت مسافر، به سبب تأخیر یا کمبود وسیله آمد و رفت در کشور مقصد تلف نمی‏شود و از زمان و بودجه‏ای که برای مسافرتش در نظر گرفته است، نهایت استفاده را می‏برد.
ب) آزادی، امنیت و رفاهپدیده اوقات فراغت و مسافرت، با آزادی و امنیت و رفاه رابطه تنگاتنگی دارد. فردی که در طول سال، در محل دائم کار و زندگی‏اش مقید به رعایت ضوابط و مقرراتی از جهات مختلف است، به این جهت مسافرت می‏کند که بتواند حتی‏الامکان آن طور که می‏خواهد لباس بپوشند، رفتار کند و. . . روی هم رفته، مسافر به جایی می‏رود که از آزادی رفتار و پوشش و. . . بیشتری برخوردار باشد. وانگهی مطمئن باشد که در چند روز مسافرت زندگی‏اش مورد تهدید و ارعاب نیست، از امنیت و احترام کامل برخوردار است و می‏تواند در آسایش و آزادی و رفاه زندگی کند.
ج) خدمات :
انواع خدمات در جهانگردی مشارکت دارند هتلها، تسهیلات اسکان و پذیرایی، اردوگاهها، رستورانها و خدمات تغذیه، استراحتگاهها، پارکهای موضوعی، خدمات اطلاع‏رسانی، تورهای داخلی و سفرهای کوتاه تفریحی، جاذبه‏های فرهنگی، مغازه‏ها، تسهیلات تفریحی و ورزشی.
در جهانگردی محل سکنا و غذا و آشامیدنی بخش از جهانگردی هستند. معمولاً هر دیدارکننده‏ای مجبور است از خدمات مختلف موجود استفاده کند. استفاده از اجزای دیگر جهانگردی اختیاری است و به نیازها و ترجیحات دیدار کننده بستگی دارد.

Related posts:

-- (324)

- (260)

- (279)

فرستاده شده.

→ – (58)

– (73) ←

پاسخ دهید لغو پاسخ

نوشته‌های تازه

• دانلود فایل دانلود رایگان پایان نامه ها- \\\"”(سایت پژوهش )”\\\"
• دانلود پژوهش 22222222222222- فایل
• دانلود نمونه پژوهش علمی [do_widget id=cool_tag_cloud-2]- فایل
• – (99)

آخرین دیدگاه‌ها

بایگانی

دسته‌ها

اطلاعات

• پیگیری دیدگاه‌ها با RSS
• WordPress.org

– (70)

که در کمال سعه‌صدر، با حسن خلق و فروتنی، از هیچ کمکی در این عرصه بر من دریغ نکردند و زحمت راهنمایی این رساله را بر عهده گرفتند و صداقت شخصی و علمی ایشان بر ذهن ما ماندگار است. استاد با اخلاق و متعهد؛ جناب آقای دکتر آرش کریمی‌پور که زحمت مشاوره این رساله را […]

1-4 چالش های موجود در استخراج الگوهای نوظهور 6 1-5 الگوریتم های استخراج الگوهای نوظهور 8 1-6 ایده اصلی تحقیق 11 1-7 نگاهی کلی به فصول رساله 13 فصل دوم 14 2- پیشینه تحقیق 15 2-1 مقدمه 15 2-2 روش های مبتنی بر قانون 15 2-2-1 روش Classification Based on Association (CBA) 15 2-2-2 روش […]

پایاپیوند را نشانه‌گذاری کنید.

– (73)

جولای31 بدست 92

Please enter banners and links.

فصل دوم 14
2- پیشینه تحقیق 15
2-1 مقدمه 15
2-2 روش های مبتنی بر قانون 15
2-2-1 روش Classification Based on Association (CBA) 15
2-2-2 روش کلاسه بندی Classification based on Multiple-class Association Rule (CMAR) 16
2-2-3 روش کلاسه بندی Classification based on Prediction Association Rule (CPAR) 16
2-3 روش های استخراج الگوها 17
2-3-1 روش مبتنی بر مرز 17
2-3-2 روش مبتنی بر محدودیت 17
2-3-3 الگوریتم استخراج درخت الگوی تقابل CP-tree 18
2-3-4 روش استخراج با کمک دیاگرام دودویی صفر ZBDD Miner 18
2-3-5 روش استخراج الگوهای نوظهور متمایز DP-Miner 18
2-4 روش های کلاسه بندی مبتنی بر الگوهای نوظهور 20
2-4-1 روش کلاسه بندی مبتنی بر اساس مجموع الگوهای نوظهور CAEP 20
2-4-2 الگوریتم کلاسه بندی بر پایه تئوری اطلاعات iCAEP 20
2-4-3 روش کلاسه بندی بر پایه الگوهای نوظهور جهشی JEPs-classifier 21
2-4-4 روش کلاسه بندی بر پایه الگوهای نوظهور جهشی قوی 21
2-4-5 روش تصمیم گیری مبتنی بر نمونه DeEPs 21
2-4-6 روش کلاسه بندی توسط مجموعه راست نمایی PCL 22
فصل سوم 23
3- دانش اولیه 24
3-1 الگوهای نوظهور 24
3-2 درخت الگوی مکرر دینامیک DFP-tree 30
فصل چهارم 33
4- راهکارهای ارائه شده برای استخراج الگوهای نوظهور قوی مبتنی بر ویژگی های جریانی 34
4-1 مقدمه 34
4-2- درخت الگوی مکرر دینامیک نامرتب Unordered Dynamic FP-tree 35
4-3 درخت الگوی مکرر دینامیک مرتب Ordered Dynamic FP-tree 44
4-4 روش استخراج الگوها SEP-Miner 56
فصل پنجم 62
5- آزمایشات تجربی 63
5-1 مقدمه 63
5-2 کلاسه بندها 63
5-2-1 کلاسه بند درخت تصمیم C4.5 63
5-2-2 کلاسه بند SVM 64
5-2-3 کلاسه بند بیزین ساده 65
5-2-4 کلاسه بند نزدیکترین همسایه 66
5-2-5 الگوریتم AdaBoost66
5-3 تست های آماری 68
5-3-1 تست آماری جفت شده t-tets 68
5-3-2 تست آماری Wilcoxon 68
5-3-3 تست آماری فردمن 69
5-4 تنظیمات تجربی 71
5-5 مقایسه دقت پیش بینی 73
5-6 مقایسه تعداد الگوها 81
5-7 مقایسه زمان اجرا 83
5-8 تحلیل اثر ترتیب در ساخت درخت الگوی مکرر دینامیک 86
5-9 چگونگی تعیین کردن حداقل آستانه فراوانی نسبی 88
5-10 تحلیل حساسیت روی حداقل آستانه های نرخ رشد 89
5-11 مقایسه کارایی DFP-SEPSF بدون دانستن کل فضای ویژگی ها 90
5-12 خلاصه نتایج تجربی 94
فصل ششم 96
6- نتیجه گیری و کارهای آینده 97
اختصارات 99
واژه نامه فارسی به انگلیسی 100
واژه نامه انگلیسی به فارسی 108
فهرست منابع 116

فهرست جدولها
جدول 3-1 الگوهای نوظهور کاندید از کلاس Poisonous به کلاس Edible38
جدول 5-1 توصیف مجموعه داده ها؛ #Features تعداد ویژگی ها، #Instances تعداد نمونه ها، #Classes تعداد کلاس ها 71
جدول 5-2 مقایسه دقت پیش بینی (%): کلاسه بندهای DFP-SEPSF، EPSF، SJEP، CAEP 75
جدول 5-3 مقایسه دقت پیش بینی (%): کلاسه بندهای DFP-SEPSF، CBA، CMAR، CPAR 77
جدول 5-4 مقایسه دقت پیش بینی (%): کلاسه بندهای DFP-SEPSF، NB، Knn، J48، SVM، AdaBoost 78
جدول 5-5 تعداد دفعات win/tie/loss کلاسه بند DFP-SEPSF در مقابل یازده کلاسه بند دیگر 80
جدول 5-6 تعداد دفعات win/tie/loss کلاسه بند DFP-SEPSF در مقابل یازده کلاسه بند دیگر؛ با استفاده از تست جفت شده t-test در سطح معنادار 95% 80
جدول 5-7 تعداد دفعات win/tie/loss کلاسه بند DFP-SEPSF در مقابل یازده کلاسه بند دیگر؛ با استفاده از تست Wilcoxon در سطح معنادار 95% 80
جدول 5-8 تست فردمن در سطح معنادار 95% با میانگین رتبه کلاسها 81
جدول 5-9 تست Bonferroni-Dunn 81
جدول 5-10 مقایسه تعداد الگوهای استخراجی: کلاسه بندهای DFP-SEPSF، CAEP، CBA، CMAR 83
جدول 5-11 زمان اجرا: کلاسه بندهای DFP-SEPSF، CAEP 86
جدول 5-12 مقایسه درخت الگوی مکرر مرتب با درخت الگوی مکرر نامرتب 88
فهرست شکلها
شکل 3-1. یک مثال از الگوهای مکرر از مجموعه داده Balloon 25
شکل 3-2. یک مثال از درخت الگوی مکرر دینامیک 32
شکل 4-1. مرحله به مرحله ساخت دینامیک درخت الگوی مکرر بدون در نظر گرفتن ترتیب آیتم ها35
شکل 4-2. ساخت درخت الگوی مکرر دینامیک بدون در نظر گرفتن ترتیب آیتم ها 40
شکل 4-3. مقایسه ساختار درخت الگوی مکرر با و بدون در نظر گرفتن ترتیب آیتم ها 45
شکل 4-4. ساختن درخت الگوی مکرر بر پایه ویژگی های جریانی 45
شکل 4-5. درخت الگوی مکرر پایه 47
شکل 4-6. اضافه کردن گره های جدید به درخت الگوی مکرر و تغییر موقعیت آنان 48
شکل 4-7. فرآیند ترکیب مرحله به مرحله 51
شکل 4-8. استخراج الگوهای نوظهور با استفاده از FP-tree بصورت مرحله به مرحله 57
شکل 5-1 بردار پشتیبان و صفحه جداکننده خطی65
شکل 5-2 تاثیر آستانه های نرخ رشد بر روی DFP-SEPSF: دقت روش پیشنهادی بر روی سی مجموعه داده تحت آستانه های 20، 30، 40، 50 و 60 گزارش داده شده است. 90
شکل 5-3 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 50، 50، 60، 60، و 60 هستند. 91
شکل 5-4 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 70، 80، 100، 70، و 80 هستند 92
شکل 5-5 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 70، 90، 70، 100، و 70 هستند 92
شکل 5-6 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 50، 60، 70، 50، و 40 هستند 93
شکل 5-7 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 80، 80، 100، 100، و 90 هستند 93
شکل 5-8 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 90، 80، 60، 80، و 90 هستند 94
فصل اولمقدمه

مقدمهمقدمه کلاسه بندی[1] یکی از وظایف اساسی در داده کاوی[2] است که بطور وسیعی در زمینه یادگیری ماشین[3]، شبکه های عصبی[4] و تشخیص الگو[5] مورد مطالعه واقع شده است. ورودی، مجموعه ای از نمونه های آموزشی[6] است که شامل چندین ویژگی[7] است. ویژگی ها با توجه به دامنه مقادیرشان به دو دسته ویژگی های گسسته[8] و ویژگی های پیوسته[9] قابل تفکیک هستند. در حالت کلی، یک کلاسه بند[10]، توصیف مختصر و معنادار (مدل[11]) برای هر برچسب کلاس[12] در رابطه با ویژگی ها تولید می کند. سپس، مدل برای پیش بینی برچسب کلاس نمونه های ناشناخته[13] بکار می رود. کلاسه بندی همچنین بعنوان یادگیری با ناظر[14] نیز شناخته می شود که در آن هر نمونه آموزشی دارای برچسب کلاس است. در حالی که، یادگیری بدون ناظر[15] یا خوشه بندی[16] جستجو می کند و گروه های همگن از اشیا را بر اساس مقادیر ویژگی هایشان دسته بندی می کند؛ در واقع، نمونه ها دارای برچسب کلاس نیستند. کلاسه بندی در محدوده وسیعی از کاربردها از جمله آزمایشات علمی[17]، تشخیص دارو[18]، پیش بینی آب و هوا[19]، تایید اعتبار[20]، تقسیم بندی مشتری[21]، بازاریابی هدف[22] و تشخیص تقلب[23] بطور موفقیت آمیزی بکار می رود.
کلاسه بندی بر پایه الگوها[24]، یک متدلوژی جدید محسوب می شود. کشف الگوهایی که نشاندهنده تمایز بین کلاس های مختلف هستند، یکی از موضوعات مهم در داده کاوی محسوب می شود. در این تحقیق، ما کلاسه بندی را بر اساس الگوهایی به نام الگوهای نوظهور[25] (Emerging Patterns) که تمایز بین کلاس ها را بصورت بارزی نشان می دهند، از مجموعه داده ها[26] استخراج می کنیم و سپس، بر اساس آنها، کلاسه بندی را انجام می دهیم.
مفهوم الگوهای نوظهور
مفهوم الگوهای نوظهور برای استخراج دانش از پایگاه داده ها توسط Dong و Li پیشنهاد شده است تا تغییرات قابل توجه بین کلاس ها را به تصویر بکشند [1]. یک الگوی نوظهور، ترکیب عطفی بین ویژگی هایی است که میزان احتمال حضور آن در یک کلاس نسبت به دیگر کلاس ها بطور قابل توجهی تغییر می کند [1،2]. این الگوها مفید هستند به این دلیل که قادر هستند تا وجه تمایز بین کلاس ها را بیان کنند. در صورتی که میزان فراوانی[27] هر الگو که در یک کلاس نسبت به دیگر کلاس ها قابل توجه باشد، نشاندهنده آن است که این الگو، بطور خاص به این کلاس اختصاص دارد و از طرفی این نوع الگوها برای پایگاه داده هایی که بحث محدودیت زمانی برای استخراج دانش از آنها مطرح است، اهمیت ویژه ای می یابند.
استخراج الگوهای نوظهور بدین صورت مطرح می شود: « پیدا کردن آیتم هایی که نرخ رشد[28] آن (که بصورت نسبت احتمال آن آیتم بین کلاس های مختلف تعریف می شود) از مقدار آستانه ای بیشتر باشد.» این مقدار آستانه باید بگونه ای انتخاب شود که الگوهای استخراجی ، تفاوت و تمایز بین کلاس های مختلف را نشان دهند. این الگوها در واقع مجموعه ای از آیتم ها هستند که بیان کننده ترکیب عطفی بین مقادیر ویژگی ها هستند [2].
نوعاً، تعداد الگوهای استخراجی بسیار زیاد است اما فقط شمار کمی از این الگوها برای تحلیل داده ها و کلاسه بندی مطلوب و مفید هستند. از آن جایی که مقدار زیادی از این الگوها بی ربط[29] و تکراری[30] هستند، دانش جدیدی را فراهم نمی کنند و لذا تاثیر نامطلوبی بر روی دقت کلاسه بند دارند که موجب کاهش دقت پیش بینی[31] می شوند. برای افزایش کارایی[32] و دقت، بایستی روالی را توسعه داد که الگوهای وابسته و غیر مفید حذف شوند تا شمار این الگوها کاهش یابد.
یک الگوی نوظهور با احتمال بالا در کلاس خودش و احتمال پایین در کلاس مقابلش می تواند برای تعیین یک نمونه تست بکار رود. قدرت این الگو توسط معیارهایی مثل فراوانی نسبی[33] و نرخ رشد ( نسبت احتمال الگو در یک کلاس نسبت به دیگر کلاس ها) آن بیان می شود.
در بسیاری از زمینه های کاربردی مانند کشف دانش از داده های ژنی[34] ، پردازش تصویر[35]، کشف نفوذ[36] ، کشف برون هشته[37]، کشف کلاهبرداری[38] ، داده های نامتوازن[39] ، جریان داده ها[40] ، بیوانفورماتیک[41] ، سیستم های پیشنهاد دهنده[42] ، نیاز است که تغییر ناگهانی در داده ها تشخیص داده شود. الگوهای نوظهور تغییرات ناگهانی و تفاوت های قابل توجه را از داده ها استخراج می کنند. الگوهای نوظهور، در زمینه پردازش تصویر برای قطعه بندی بدین گونه عمل می کند که سعی می کند در پیکسل هایی که تغییر ناگهانی شدت[43] بوجود می آید را بعنوان یک قطعه جدید معرفی کند. در زمینه کشف نفوذ و کلاهبرداری، رفتار داده ها پیگیری می شود، زمانی که رفتار داده ها بصورت ناگهانی تغییر کند، بعنوان نفوذ تشخیص داده می شود. در سیستم های پیشنهاد دهنده، سیستم به دنبال رفتارهای خاص و مختص هر کاربر است تا با کشف ویژگی های خاص هر کاربر، به او محصولات مطابق با علایق و استعدادهای او را پیشنهاد دهد. لذا الگوهای نوظهور در این راستا نقش بسزایی دارند.
مفهوم ویژگی های جریانی[44]
در داده های جریانی[45]، نمونه ها به مرور زمان دریافت می شوند در حالیکه تعداد ویژگی ها ثابت می باشد. اما در ویژگی های جریانی، تعداد داده های یادگیری ثابت می باشد ولی ویژگی ها بصورت دینامیک تولید می شوند و الگوریتم یادگیری به مرور زمان ویژگی ها را دریافت می دارد [31، 32]. در ویژگی های جریانی روال بدین صورت است ویژگی های توسط روش های تولید ویژگی مانند روش های یادگیری رابطه ای آماری[46] و تعاملات بین ویژگی ها[47]، تولید می شوند. مشکلاتی که در پی تولید ویژگی ها توسط این روش ها بروز می کند بدین شرح است که: 1) میلیون ها و یا حتی بیلیون ها ویژگی تولید می شوند که بدلیل محدودیت های حافظه امکان نگهداری این حجم از ویژگی وجود دارد و از طرفی زمان بسیار زیادی بایستی صرف شود تا فرآیند یادگیری شروع شود. 2) ویژگی ها توسط کوئری های موجود در SQL تولید می شوند که اجرای این کوئری ها محدود به زمان پروسسور[48] است تقریبا پروسسور هر صدهزار کوئری را در 24 ساعت اجرا می کند. از طرفی بسیاری از ویژگی ها تولیدی بی ربط و تکراری هستند[49]. این موضوع نشان می دهد که شمار کمی از این ویژگی های تولیدی در عمل در فرآیند یادگیری موثر است و لذا تولید ویژگی ها هزینه بر است [32]. بر این اساس برای فائق آمدن بر این مشکلات، مفهوم ویژگی های جریانی شکل گرفت و تلاش شد تا با تولید دینامیک ویژگی ها و بررسی این ویژگی ها در زمان تولید و تاثیر آن بر روال یادگیری فرآیند تولید ویژگی ها را هدایت کنند.
برای برخورد با چالش های مطرح شده، بایستی فرآیند یادگیری قابلیت پاسخگویی به ویژگی های جریانی را داشته باشد. در واقع، روال یادگیری بایستی بصورت افزایشی با دریافت هر ویژگی قابل بروزرسانی شدن داشته باشد بدون اینکه به اولین مرحله یادگیری بازگردد. لذا در راستای استخراج الگوهای قوی بایستی در ابتدا ویژگی ها بررسی شوند و ویژگی هایی که بی ربط هستند را حذف کرد، سپس از روی ویژگی های مفید و قوی ، الگوها را استخراج کرد.
چالشهای موجود در استخراج الگوهای نوظهور
در این تحقیق هدف بر آن است که بر موضوعات اساسی در زمینه الگوهای نوظهور پرداخته شود که عبارتند از: 1. به دلیل حجیم بودن داده ها و حجم بالایی از ویژگی ها و با توجه به مفهوم ویژگی های جریانی، اولین موضوع، نحوه برخورد با این نوع از داده ها می باشد به طوری که بتوان از میان خیل عظیم ویژگی ها و با توجه به قضیه رشد ویژگی ها که بصورت دینامیک تولید می شوند، روشی ارائه داده شود که با دریافت ویژگی های جدید بصورت دینامیک بروزرسانی شود. همانطور که قبلا اشاره شد، در حوزه های مربوط به پایگاه داده ها که نیاز به گرفتن کوئری از پایگاه داده است، میلیونها و یا بیلیارد ویژگی تولید می شود. این نوع ویژگی همین طور در حوزه پردازش تصویر کاربرد دارد. در حوزه پردازش تصویر، در بعضی مواقع لازم است که به هر پیکسل بعنوان یک ویژگی در نظر گرفت که در نتیجه فضای ویژگی ها بسیار گسترده و گاها نامتناهی می شود و لذا لزوم برخورد با اینگونه داده ها متفاوت می شود. 2. استخراج الگوهای قوی از میان الگوها و داده های موجود، از دیگر موضوعات اساسی است. این موضوع، زمانی بیشتر اهمیت می یابد که با توجه به حجیم بودن داده ها، در نتیجه رشد این الگوها به سرعت نمایی خواهد شد بخصوص زمانی که ابعاد ویژگی ها بی نهایت باشد، دیگر امکان نگهداری هر الگویی وجود نخواهد داشت در نتیجه استخراج الگوهای قوی که در کلاسه بندی واقعا موثر باشند، بسیار اهمیت خواهد یافت.
در روال استخراج این الگوها سه مساله اساسی وجود دارد:
چگونه مجموعه مفید و موثری از الگوهای نوظهور، بین داده های کلاس های مختلف استخراج شود؟
از آنجایی که همه این الگوها مفید نیستند در واقع شمار زیادی از این الگوها در راستای یادگیری مدل و کلاسه بند بکار نمی روند، در نتیجه بایستی بتوان مجموعه کوچک و در عین حال قوی از این الگوها تشکیل داد، در همین راستا مسائلی که مطرح می شود این است که کدامیک از این الگوها برای هدف یادگیری و کلاسه بند مفید است و در واقع چگونه می توان مجموعه قوی از این الگوها را تشکیل داد؟ از طرفی موضوع دیگر ابعاد ویژگی های[50] مسئله خواهد بود، در صورتی که ابعاد ویژگی ها بالا باشد، در نتیجه شمار الگوهای نوظهور سیر صعودی خواهد داشت که شمار زیاد از این الگوها هم برای آنالیز داده ها بصورت برخط مشکل ساز است و هم این که روال یادگیری و کلاسه بند را زمانبر و هزینه بر می کند که مناسب نیست. لذا با بیان این مسائل بایستی بتوان مجموعه کوچک و در عین حال قوی از الگوهای نوظهور را تشکیل داد که این موضوع خود موضوعی چالش برانگیز است، و اینکه کدامیک از الگوهای جدید مفید و موثر هستند ؟
کدامیک از این الگوها برای هدف کلاسه بند مفید هستند؟ و چگونه این الگوها یک کلاسه بند مفید و موثر و در عین حال دقیق را می سازند؟
3. طریقه استفاده از این الگوها و یا همان مدل است که بتواند از الگوها بخوبی بهره گرفته و کلاسه بندی دقیقی را انجام دهد بطوری که دقت کلاسه بند بالا باشد.
وقتی که ابعاد ویژگی ها بالا باشد، استخراج الگوهای نوظهور مشکل تر خواهد شد؛ چرا که ذخیره، بازیابی، هرس و مرتب کردن آنها برای کلاسه بند با تعداد کاندیداهای بسیار زیاد الگوها، سخت و یا غیرممکن خواهد شد. با ظهور داده های حجیم و بزرگ که شامل صدها هزار ویژگی هستند مانند پردازش تصویر ، داده های ژنی و داده های متنی و … ، فضای جستجوی این الگوها نسبتاً بزرگ، هزینه بر و گاهی اوقات حتی غیرممکن است [19].
ایجاد یک مدل بر اساس الگوهای نوظهور با داده های با ابعاد بالا و نمونه های حجیم یک موضوع چالش برانگیز است. مشکل حتی سخت تر می شود اگر همه فضای ویژگی ها، قبل از عملیات یادگیری در دسترس نباشد و یا نامتناهی باشد [19].
از طرفی روش های یادگیری مرسوم [37، 38، 40] قادر هستند که بحث چند کلاسه[51] را از طریق روش های دو به دو مثل یکی در مقابل یکی[52] و یکی در مقابل همه[53] مدیریت کنند. بلاوه، بسیاری از روش های موجود استخراج الگوهای نوظهور مانند روش های مبتنی بر مرز[54] [1، 3، 13] و روش های مبتنی بر محدودیت[55] [2]، الگوهای مربوط به هر کلاس را در فرآیند جداگانه ای استخراج می کنند که این امر مطلوب نیست و منجر به تکرار محاسبات سنگین می شود. لذا بایستی بتوان روش استخراجی ارائه داد که این قابلیت را دارا باشد که تمامی الگوهای کلاس های مختلف را بصورت همزمان استخراج کند.
بنابراین در این حوزه با موضوعات چالش برانگیزی بدین شرح روبرو هستیم:
1. چگونه بصورت موثر، مجموعه کوچکی از الگوهای نوظهور قوی را از داده های با ابعاد بالا استخراج کنیم؟
2. چگونگی استخراج کردن الگوهای نوظهور وقتی که کل ویژگی ها قبل از فرآیند یادگیری در دسترس نیستند؟
3. چگونگی ارائه مدل افزایشی و دینامیک در پاسخ به ویژگی های جریانی؟
4. چگونگی استخراج الگوهای نوظهور از کلاس های مختلف بصورت همزمان؟
الگوریتمهای استخراج الگوهای نوظهور
زمانی که ابعاد داده ها بالا باشد، شمار الگوهای نوظهور بسیار زیاد و در واقع نمایی و گاهاً غیرممکن خواهد بود. لذا استخراج الگوهای نوظهور از داده ها، نیاز به روالی جداگانه دارد که در این راستا روش هایی ارائه شده است. روش هایی که تلاش می کنند الگوهایی با مشخصات بیان شده، استخراج کنند؛ بدین شرح هستند: روش مبتنی بر مرز[56]، روش مبتنی بر محدودیت[57]، الگوریتم های سریع برای استخراج الگوهای نوظهور[58]، روش دیاگرام تصمیم گیری دودویی مانع صفر[59].
این روش ها کمک بسزایی در کاهش تعداد الگوهای نوظهور می کنند بدون اینکه اثری بر قدرت تشخیص کلاسه بند داشته باشد.
1.استخراج الگوها بر اساس روش مبتنی بر مرز
برای روش های مبتنی بر مرز، سه الگوریتم؛ استخراج افقی[60] ، اختلاف مرز[61] ، تولید الگوهای نوظهور جهشی[62] وجود دارد. این روش ها با الهام از الگوریتم Max_Miner طراحی شده اند.
مرز، ساختاری است که مجموعه بزرگی از آیتم ها را بصورت مختصر نمایش می دهد. مرز برای نمایش الگوهای نوظهور کاندید بکار می رود. عملیات تفکیک مرز، برای استخراج الگوها استفاده می شود. مرز افقی از داده ها، نشان دهنده همه آیتم ها با فراوانی نسبی با آستانه خاصی، در داده ها است. الگوریتم استخراج افقی، مرز افقی هم برای داده های کلاس مثبت و هم برای داده های کلاس منفی ایجاد می کند. در واقع این الگوریتم، سعی می کند مرزی برای هر یک از کلاس ها بیابد. ایده اصلی این الگوریتم، استخراج مجموعه آیتم های با فراوانی نسبی ماکزیمال است [1، 3].
الگوهای نوظهور جهشی ، الگوهای نوظهوری هستند که در داده های یک کلاس، حضور ندارند، در نتیجه نسبت فراوانی نسبی داده های کلاس های دیگر به کلاسی که این مقدار داده در آن حضور ندارد، بی نهایت می شود. به الگوهای نوظهور با نرخ رشد بی نهایت، الگوی نوظهور جهشی گفته می شود. استخراج چنین الگوهایی، کمک بسزایی به کلاسه بند می کند. به این دلیل که تفاوت بین کلاس ها توسط این الگوها، بیش از پیش قابل لمس است. لذا در این راستا، روش هایی برای استخراج الگوهای نوظهور جهشی [3، 13] ارائه شده است.
2.استخراج الگوها بر اساس روش مبتنی بر محدودیت
این روش از دو نوع محدودیت برای هرس فضای جستجو استفاده می کند که محدودیت های داخلی و خارجی را شامل می شود [2].
محدودیت هایی است که کاربر اعمال می کند، محدودیت های خارجی روش مبتنی بر محدودیت استخراج الگوهای نوظهور را ایجاد می کند. این محدودیت ها شامل تعیین حداقل مقدار برای فراوانی نسبی، نرخ رشد و بهبود نرخ رشد می باشد. از آنجا که ممکن است بعضی از الگوها زیر مجموعه دیگر الگوها باشند، چنین الگوهایی، در حکم الگوهای تکراری هستند که کمکی به کلاسه بند نمی کنند. چنین الگوهای تکراری از مجموعه الگوها باید حذف شوند که البته شمار الگوها بدین ترتیب کاهش می یابد [2].
محدودیت هایی که به صورت انطباقی در روال استخراج، بر اساس مشخصات داده ها اعمال می شود، محدودیت داخلی را تشکیل می دهند. الگوریتم مبتنی بر محدودیت استخراج الگوهای نوظهور، می تواند بصورت موثر همه الگوها را که این محدودیت ها را ارضاء می کنند، استخراج کند. این روش از جستجوی اول عرض بر روی (SE-Tree) اعمال می کند و الگوهای مفید را استخراج می کند. برای بالا بردن کارایی این روش، الگوریتم هایی ارائه شده است که هر دو دسته محدودیت ها را در یک فاز اجرایی اعمال می کنند [2].
این الگوریتم بصورت مرحله ای انجام می شود که در هر مرحله، یکسری کاندید تولید می کند و سپس آنها را تست می کند. بدین ترتیب با اعمال محدودیت ها در هر مرحله و البته تغییر بعضی محدودیت ها در هر مرحله، الگوهای نوظهور را استخراج می کند.
همچنین این موضوع قابل بیان است که روش دیاگرام تصمیم گیری دودویی مانع صفر، در مقایسه با دیگر روش ها بیشتر در زمینه داده ها با ابعاد بالا کاربرد دارد و قویتر از دیگر روش های گفته شده در این زمینه عمل می کند.
ایدهی اصلی تحقیقبرای حل موضوعات چالش برانگیز مطرح شده، ما روش درخت الگوی مکرر دینامیک[63] جهت استخراج الگوهای نوظهور قوی در ویژگی های جریانی، DFP-SEPSF را پیشنهاد می دهیم. در این روش، درخت الگوی مکرر[64] مرسوم در پاسخ به ویژگی های جریانی ساخته می شود. ایده اصلی روش پیشنهادی بدین شرح هستند:
1. با چارچوب پیشنهادی، یک تکنیک جدید، درخت الگوی مکرر دینامیک، DFP-tree، در جواب ویژگی های جریانی ارائه شده است. ما دو روش از درخت الگوی مکرر دینامیک معرفی می کنیم: درخت الگوی مکرر دینامیک نامرتب[65]، UDFP-tree، و درخت الگوی مکرر دینامیک مرتب[66]، ODFP-tree. این روش ها درخت الگوی مکرر را بصورت افزایشی به محض ورود ویژگی های جدید بصورت پایین به بالا می سازند.
2. زیر مجموعه جدیدی از الگوهای نوظهور با نام الگوهای نوظهور قوی[67]، SEPs، ارائه می دهیم. این الگوها، الگوها با کیفیت بالا[68] هستند که محدودیت فراوانی دینامیک[69] را ارضا می کنند و بسیاری از نمونه های آموزشی را پوشش می دهند. کلاسه بند بر پایه SEPs بسیار بهتر از دیگر الگوریتم های شناخته شده عمل می کند. بعلاوه، روش استخراج الگوهای نوظهور[70]، SEP-Miner، بطور چشمگیری فضای جستجوی الگوها را کاهش می دهد و الگوهای نوظهور قوی را بصورت کارایی استخراج می کند.
3. DFP-SEPSF قادر است تا به محض ورود مقادیر ویژگی های جدید، آنها را در ساختار DFP-tree وارد نماید و الگوهای نوظهور قوی جدید مربوط به این مقادیر جدید وارد شده را استخراج کند. سپس روش پیشنهادی، این الگوها را به مجموعه الگوهای استخراج شده اضافه نماید.
2. روش استخراج، الگوهای نوظهور با قابلیت پیش بینی قوی را با حذف الگوهای بی ربط و تکراری از ساختاری استخراج می کند. روش استخراج، فضای جستجوی الگوها را بصورت قابل توجهی کاهش می دهد و فرآیند کشف الگوهای نوظهور را بصورت موثری با کمک تست آماری کای مربع[71] هدایت می کند.
3. برای اینکه استخراج الگوهای نوظهور بصورت کارایی انجام پذیرد، الگوهای نوظهور از هر کلاس در زمان یکسانی بصورت موازی استخراج می شوند. DFP-SEPSF قادر است تا فرآیند استخراج الگوها از کلاس های مختلف را بدون انجام محاسبات تکراری مدیریت کند.
4. این مطالعه کارایی الگوریتم پیشنهادی را بطور کامل بررسی می کند. آزمایشات گسترده ای بر روی داده های وسیعی که شامل 24 مجموعه داده از مجموعه داده های UCI [52] و 6 مجموعه داده با ابعاد بسیار بالا صورت گرفته است. در این آزمایشات، روش پیشنهادی با دیگر روش های شناخته شده در رابطه با دقت کلاسه بندی، شمار الگوها، و زمان یادگیری مقایسه شده اند.
5. حداقل آستانه فراوانی نسبی در طول فرآیند استخراج بر اساس طول الگوهای کاندید برای هر مجموعه داده بصورت جداگانه تنظیم می شود تا کارایی DFP-SEPSF به نرخ آستانه خاصی وابستگی نداشته باشد. بعلاوه، تحلیل حساسیت آزمایشات بر روی آستانه های مختلف نرخ رشد نشان می دهد که کارایی روش پیشنهادی به نرخ رشد خاصی وابسته نیست.
در فرآیند ساخت درخت الگوی مکرر دینامیک، تعدادی محدودیت مانند حداقل آستانه فراوانی نسبی، الگوی نوظهور کمینه، و الگوی نوظهور بی ربط اعمال می شود تا فضای جستجوی الگوهای نوظهور به محض ورود ویژگی جدید هرس شود. اگر یک مقدار ویژگی محدودیت های ذکر شده را ارضا نکند، در ساختار درخت قرار داده می شود. درخت الگوی مکرر با دریافت یکی به یک ویژگی ها بتدریج ساخته می شود. برای ساخت درخت الگوی مکرر مرتب، موقعیت گره ها در درخت تغییر داده می شود تا درخت بازسازی شود. بعد از پردازش همه ویژگی ها، روش استخراج الگوها، SEP-Miner، الگوهای نوظهور با قابلیت پیش بینی قوی را از درخت الگوی مکرر استخراج می کند. روش پیشنهادی ما، در دو مرحله قابل اجرا است، اول،پایگاه داده شرطی[72] با کمک اعمال محدودیت هایی هرس می شود، دوم، پایگاه داده شرطی کاهش یافته به چندین پایگاه داده کوچکتر با کمک تست کای مربع[73]، تجزیه می شود. سپس به ازای هر زیر پایگاه داده شرطی[74] یک درخت الگوی مکرر شرطی[75] ایجاد می شود. این فرآیند مکرر اجرا می شود تا ضابطه توقف ارضا شود.
نگاهی کلی به فصول رسالهاین رساله به شش فصل تقسیم شده است. در فصل دوم، به بررسی روشها و الگوریتمهای مرسوم در استخراج الگوهای نوظهور و کلاسه بندی آنها می پردازد. در فصل سوم، دانش اولیه درباره الگوهای نوظهور و درخت های الگوی مکرر در قالب تعاریف بیان می شود. در فصل چهارم، جزئیات روشهای پیشنهادی به تفصیل ارائه میشوند. در فصل پنجم، کلاسهبندها، معیارهای ارزیابی عملکرد، مجموعه دادههای مورد آزمایش و همچنین تست آماری مورد استفاده برای مقایسه نتایج الگوریتمهای پیشنهادی با سایر روشها به تفصیل توضیح داده میشوند. در فصل ششم، نتایج حاصل از بررسی و مقایسه الگوریتمهای پیشنهادی و پاسخ سؤال‌های مطرح‌شده در فصل قبل، گردآوری‌شده است. همچنین در فصل آخر نتیجهگیری و کارهای آینده این رساله آمده است.
فصل دومپیشینهی تحقیق
پیشینهی تحقیقمقدمهدر این فصل در ابتدا به روش هایی که از الگوهای مکرر[76] در راستای کلاسه بندی بهره می گیرند، می پردازیم و سپس روش های استخراج الگوهای نوظهور و کلاسه بندهای مرتبط با این الگوها بازنگری می کنیم.
روش های مبتنی بر قانون[77]
هدف از کلاسه بندی قوانین استخراجی، استخراج کردن مجموعه کوچکی از قوانین است تا یک کلاسه بند دقیق ساخته شود. الگوریتم های استخراج قانون مانند Apriori [61] و FPgrowth [15، 16] بکار گرفته می شوند تا مجموعه کاملی از الگوها استخراج شوند. سپس مجموعه کوچکی از قوانین با کیفیت بالا انتخاب می شوند که برای کلاسه بندی بکار می روند. الگوریتم های شناخته شده برای کلاسه بند های انجمنی[78] شامل CBA، CMAR و CPAR می شوند که جزئیات این الگوریتم ها در ادامه بیان خواهند شد.
روش Classification Based on Association (CBA) [27]
روش CBA در دو فاز اجرا می شود: تولید کننده قانون[79] و سازنده کلاسه بند[80]. تولید کننده قانون، الگوریتم Appriori را بکار می گیرد تا همه قوانینی با حداقل آستانه[81] فراوانی نسبی[82] و درجه اطمینان[83] را استخراج کند. برای کلاسه بندی کردن یک نمونه تست، سازنده کلاسه بند، قوانین را بر اساس مقادیر فراوانی نسبی و درجه اطمینانشان مرتب می کند. سپس، سازنده کلاس، اولین قانون را بعنوان بهترین قانون انتخاب می کند تا بر چسب کلاس را به نمونه تست اختصاص دهد. بدلیل اینکه CBA کلاسه بندی را بر اساس فقط یک قانون برای یک نمونه تست انجام می دهد، ممکن است باعث بروز مشکل بیش یادگیر[84] شود.
روش کلاسه بندی Classification based on Multiple-class Association Rule (CMAR) [28]
با توجه به اینکه CBA فقط بر اساس یک قانون با درجه اطمینان و فراوانی بالا کلاسه بندی را انجام می دهد، مشکل بیش یادگیری صورت می گیرد و لذا دقت کلاسه بند برای نمونه های تست کم خواهد شد. برای حل این مشکل، CMAR کلاسه بندی را بر اساس چندین قانون انجام می دهد. CMAR، درخت الگوی مکرر[85] را توسعه می دهد بطوری که بتواند الگوهای مکرر[86] را بصورت کارایی استخراج کند. CMAR چندین قانون را با استفاده از وزن دهی بر اساس χ برای کلاسه بندی بکار می گیرد.
روش کلاسه بندیClassification based on Predictive Association Rule (CPAR) [29]
CPAR با الهام از الگوریتم FOIL [62] قوانین را تولید می کند. CPAR، مجموعه بسیار کوچکی از قوانین با قابلیت پیش بینی را با استفاده از الگوریتم حریصانه بطور مستقیم از مجموعه آموزشی استخراج می کند. برای جلوگیری از بیش یادگیری، CPAR بهترین k قانون را جهت کلاسه بندی کردن نمونه تست بکار می گیرد. CPAR در مقایسه با دیگر الگوریتم های استخراج قوانین دارای مزایایی بدین شرح است: 1) مجوعه خیلی کوچکتری از قوانین با کیفیت بالا بطور مستقیم از نمونه های آموزشی[87] استخراج می کند. 2) برای پرهیز از تولید قوانین تکراری، CPAR هر قانون را با توجه به مجموعه قوانینی که از قبل استخراج کرده است، تولید می کند. 3) برای کلاسه بندی، بهترین k قانون بکار گرفته می شود.
روشهای استخراج الگوها
در مقایسه با قوانین انجمنی، الگوهای نوظهور قادر هستند که تمایلات نوظهور[88] در مجموعه داده های با محدودیت زمانی[89] را استخراج کنند و یا تمایزات مفید بین کلاس های مختلف را کشف نمایند [1]. مطالعه و پژوهش در رابطه با الگوهای نوظهور اساسا به دو دسته قابل تقسیم است؛ الگوریتم های استخراج الگوهای نوظهور و الگوریتم های کلاسه بندی بر پایه این الگوها. ما در ابتدا الگوریتم های مرتبط با استخراج الگوهای نوظهور را شرح می دهیم و سپس الگوریتم های مشهور کلاسه بندی را ارائه می دهیم.
روش مبتنی بر مرز[90]
روش های مبتنی بر مرز با الهام از الگوریتم Max-miner [14] پیشنهاد شده اند. این روش ها، مفهوم مرز[91] [1] را بکار می گیرد تا ساختار مناسبی را برای نمایش مختصری برای الگوهای کاندید ارائه دهند. در هر مرز، کوچکترین و بزرگترین عضو هر مجموعه کاندید قابل نمایش است. الگوریتم اختلاف مرز[92]، الگوهای نوظهور کمینه و بیشینه[93] را استخراج می کند و بدین ترتیب مرز الگوهای استخراجی را تنظیم می کند. الگوریتم های مبتنی بر مرز قادر نیستند که الگوهای نوظهور را بصورت همزمان از کلاس های مختلف استخراج کنند. این الگوریتم ها، برای هر کلاس طی فرآیند جداگانه ای الگوها را استخراج می کنند و لذا به ازای هر کلاس، جداگانه اجرا می شود.
روش مبتنی بر محدودیت (ConsEPMiner[94]) [2]
الگوریتم مبتنی بر محدودیت در دو سطح اجرا می شود؛ تولید الگوهای کاندید و هرس الگوهای اکتشافی. الگوریتم ConsEPMiner از دو نوع محدودیت استفاده می کند تا بتواند بطور موثری فضای جستجو الگوهای نوظهور را هرس کند و محاسبات را ذخیره نماید. محدودیت های ذاتی[95] و خارجی[96] عنوان محدودیت هایی است که در فرآیند استخراج اعمال می شود. محدودیت های خارجی شامل محدودیت حداقل آستانه فراوانی نسبی، نرخ رشد و پیشرفت نرخ رشد[97] است که توسط کاربر قابل تنظیم است. محدودیت ذاتی شامل مجوعه یکسانی از فراوانی نسبی[98]، نرخ رشد بالا[99] و مبدا یکسان[100] است.
الگوریتم استخراج درخت الگوی تقابل[101] (CP-Tree) [17، 25]
الگوریتم استخراج الگوهای متمایز، با الهام از FP-tree، ساختار گسترش یافته ای ساختار درختی پیشوندی ارائه می دهد. این ساختار به خلاف الگوریتم درخت الگوی مکرر، نیازی به پیوند بین نودها ندارد. الگوریتم توسط جستجوی اول عمقی[102]، CP-tree را از ریشه پیمایش می کند تا الگوهای نوظهور جهشی قوی[103] را استخراج کند. الگوی نوظهور جهشی قوی، یک نوع خاص از الگوهای نوظهور جهشی[104] است که بایستی دارای حداقل فراونی نسبی باشد. این نوع درخت، کارایی استخراج الگوهای نوظهور را با استفاده از الگوهای نوظهور جهشی قوی بهبود می بخشد و همچنین قادر است که مجموعه داده های چند کلاسه را مدیریت نماید.
روش استخراج با کمک دیاگرام دودیی صفر[105] ZBDD Miner [18]
از آنجایی اینکه روش های ذکر شده، قادر نیستند که داده ها با ابعاد بیشتر از شصت را مدیریت کنند، بعداً، ZBDD EP-Miner شد. این روش از Zero-Suppressed Binary Decision Diagrams (ZBDDs) استفاده می کند تا الگوهای نوظهور را از داده ها با ابعاد بالا استخراج کند. با این وجود، ZBDD EP-miner هنوز شمار زیادی از الگوهای نوظهور را استخراج می کند حتی با اعمال محدودیت های آلفا و بتا [18].
این محدودیت ها استفاده می شوند تا فضای جستجوی الگوهای نوظهور را بیشتر هرس کند. محدودیت آلفا بر اساس مفهوم a-priori است. در نمونه های مثبت[106]، هر آیتم که فراوانی نسبی اش[107] کمتر از مقدار آلفا باشد، هم از نمونه های مثبت و هم از نمونه های منفی حذف می شود. محدودیت بتا بیشترین مقدار فراوانی[108] برای یک الگوریتم در نمونه های منفی مشخص می کند؛ اگر فراوانی الگوی کاندید بیشتر از بتا باشد، آن الگو از نمونه های آموزشی حذف می شود.
روش استخراج الگوی نوظهور متمایز [109]DP Miner
بر اساس مفهوم مجموعه آیتم بسته[110]، یک کلاس هم ارزی[111] مجموعه ای از آیتم های مکرر[112] است که همیشه در نمونه های یکسانی از نمونه های آموزشی اتفاق می افتند. مشابه با مفهوم مرز در الگوریتم های مبتنی بر مرز، یک کلاس هم ارزی بوسیله الگوهای بسته[113] و تولیدکننده ها[114] تعیین می شود. الگوهای بسته، همان مجموعه آیتم های ماکزیمال هستند و تولیدکننده ها، همان مجموعه آیتم های کمینه در یک کلاس هم ارزی هستند که همه این آیتم ها دارای فراوانی یکسانی هستند. الگوریتم DPMiner، Discriminative Pattern Miner، الگوهای بسته و تولیدکننده ها را که برای نمایش یک کلاس هم ارزی کافی هستند، بصورت همزمان استخراج می کند. بعلاوه، قادر است که الگوهای با قدرت تمایز دلتا[115] را استخراج کند. الگوهای نوظهور با قدرت تمایز دلتا دارای حداکثر فراوانی در کلاس های مقابل است. با توجه به اینکه الگوریتم های ZBDD EP-miner و DPMiner، محدودیت های آلفا و بتا را بکار می گیرند تا فضای جستجوی الگوها را کاهش دهند؛ ممکن است بعضی از الگوهای نوظهور مفید در نظر گرفته نشوند و تاثیر نامطلوبی در کلاسه بندی داشته باشد.

روش های کلاسه بندی مبتنی بر الگوهای نوظهور
روش کلاسه بندی بر اساس مجموع الگوهای نوظهور CAEP[116][21]
از آنجایی که الگوهای نوظهور، دانش تمایز بین کلاس های مختلف را نشان می دهد، آنها در ایجاد کلاسه بندی دقیق بسیار موثر هستند. کلاسه بند های بر پایه الگوهای نوظهور قدرت مجموع الگوهای نوظهور را برای کلاسه بندی یک نمونه تست بکار می گیرد. Dong [21] اولین کلاسه بند بر پایه الگوهای نوظهور را ارائه داد که CAEP، Classification by Aggregating Emerging Patterns، نامیده شد. CAEP همه الگوهای نوظهور قوی را بوسیله الگوریتم های مبتنی بر مرز استخراج می کند. برای کلاسه بندی کردن یک نمونه تست، برای هر کلاس یک امتیاز[117] محاسبه می شود. کلاس با بالاترین امتیاز بعنوان برچسب نمونه تست در نظر گرفته می شود. اگر تعداد الگوهای کاندید کلاس های مختلف نامتوازن[118] باشد، کلاس با الگوهای بیشتر تمایل در بدست آوردن امتیاز بیشتر دارد. برای حل این مشکل، یک امتیاز پایه[119] برای هر کلاس از نمونه های آموزشی بدست می آید [21].
الگوریتم کلاسه بندی بر پایه تئوری اطلاعات[120] iCAEP
بعداً، Zhang et al. [26]، یک نوع از CAEP را که iCAEP، Information based Classification by Aggregating Emerging Patterns، نامیده شد، معرفی کرد. iCAEP، از تئوری اطلاعات[121] استفاده می کند تا نیازی به محاسبه base score برای هر کلاس نباشد.
برای کلاسه بندی یک نمونه تست، کوچکترین امتیاز بعنوان برچسب کلاس نمونه تست در نظر گرفته می شود. در مقایسه با CAEP، iCAEP دقت را بهبود می دهد و زمان را برای کلاسه بندی کاهش می دهد.
روش کلاسه بندی برپایه الگوهای نوظهور جهشیJEPs-Classifier [3]
بر اساس CAEP، الگوریتم کلاسه بند بر پایه الگوهای نوظهور جهشی توسط Li et al. ارائه شد. JEPs-classifier محنصراً از الگوهای نوظهور جهشی[122] با فراوانی نسبی بالا برای کلاسه بندی استفاده می کند. این نوع الگوها، رساترین الگوهای نوظهور جهشی[123] نامیده می شوند چرا که این الگوها همان محموعه آیتم های کمینه در مرز[124] هستند که دارای فراوان نسبی بالایی نسبت به دیگر آیتم ها در مرز هستند. JEPs-classifier از الگوریتم های مبتنی بر مرز بهره گرفته و الگوهای نوظهور جهشی را در قالب مرز فضای الگوها استخراج می کند. رساترین الگوهای نوظهور جهشی لزوما حداقل آستانه برای فراوانی نسبی ارضا نمی کند.
روش کلاسه بندی بر پایه الگوهای نوظهور جهشی قوی[125] [25]
این کلاسه بندی بر پایه قدرت مجموع الگوهای نوظهور جهشی قوی است و تلاش می کند تا با استفاده از الگوهای نوظهوری جهشی که حداقل آستانه را برای فراوانی نسبی دارا هستند، به دقت قابل توجهی دست یابد.
روش تصمیم گیری مبتنی بر نمونه[126] DeEPs [20]
بعداً، بر پایه روش های مبتنی بر نمونه[127]، کلاسه بند تنبل[128] به نام DeEPs، Decision-making by Emerging Patterns، ارائه شد [20]. جهت کاهش فضای جستجو الگوها، DeEPs یک نمونه تست را بعنوان یک فیلتر بکار می گیرد تا مقادیر آموزشی بی ربط را در نظر نگیرد. برای هر نمونه تست، DeEPs الگوهای نوظهور کاندید را استخراج می کند و مقادیر ویژگی هایی که در نمونه تست دیده نشده اند را نادیده می گیرد. این تکنیک، کارایی و دقت کلاسه بندی هایی مثل کلاسه بندی بر پایه مجموع الگوهای نوظهور CAEP و کلاسه بندی بر پایه الگوهای نوظهور جهشی JEP-classifier را بهبود می بخشد. اما، این روش منجر به تکرار محاسبات سنگین می شود بخصوص وقتی که نمونه های تست مشابه باشند.
روش پیش بینی توسط مجموعه راست نمایی (PCL[129]) [5]
PCL پیش بینی را توسط مجموعه ای از درست نمایی ها[130] انجام می دهد. PCL از K بالاترین الگوهای نوظهور که در نمونه تست شامل می شوند، برای کلاسه بندی استفاده می کند. برای هر کلاس، PCL یک امتیاز با استفاده از اجتماع درست نمایی حاصل از K بالاترین الگوهای نوظهور که نمونه تست را پوشش می دهند، بدست می آورد. PCL برای مجموعه داده ها با ابعاد بالا مناسب است بخصوص برای داده های بیان ژن.
بدلیل محدودیت های روش های استخراج الگوهای نوظهور، روش های سابق قادر نیستند تا مجموعه داده ها با ابعاد بالا را مدیریت کنند. روش پیشنهادی ما، DFP-SEPSF، فضای جستجوی الگوهای نوظهور را با استفاده از فرایند هرس در روال ساخت درخت الگوی مکرر دینامیک و استخراج الگوها، بطور قابل توجهی کاهش می دهد. همچنین روش پیشنهادی، الگوهای نوظهور هر کلاس را در زمان یکسانی و بطور موازی از کلاس ها استخراج می کند.
فصل سوم
دانش اولیه

دانش اولیه
الگوهای نوظهور
فرض کنید مجموعه داده D دارای N ویژگی (F1,F2, . . . ,FN) و برچسب کلاس C است. هر کدام از ویژگی ها در صورتی که ویژگی پیوسته باشد در فواصلی مجزا می شوند.I را بعنوان مجموعه ای از همه آیتم ها تعریف می کنیم. یک مجموعه آیتم[131] X یک زیر مجموعه از I است که مقدار فراوانی نسبی[132] آن

که |X| تعداد نمونه های شامل X را بیان می کند و |D| تعداد کل نمونه های را در مجموعه داده D را بیان می کند. مجموعه برچسب کلاس C شامل M برچسب کلاس مختلف است؛ C = {C1, C2, . . ., CM}. مجموعه داده D در M مجموعه داده D1, D2, . . ., DM تجزیه می شود که هر مجموعه داده Dk شامل نمونه ها با برچسب کلاس Ck است. به طور خاص، مجموعه داده D به دو مجموعه داده مثبت Dp و مجموعه داده منفی Dn قابل تقسیم است. Dp شامل نمونه مثبت و Dn شامل نمونه های منفی می شود. نرخ رشد[133] (GR) مجموعه آیتم X از مجموعه داده Ds به مجموعه داده Dt ( s,t =1, . . . , M) در ادامه شرح داده خواهد شد.
تعریف 1: (نرخ رشد GR) نرخ رشد یک مجموعه آیتم X از Ds به Dt،

تعریف 2: (الگوی نوظهور EP [1]) حداقل آستانه نرخ رشد داده شده است. مجموعه آیتم X گفته می شود الگوی نوظهور است اگر

تعریف 3: ( الگوی نوظهور جهشی JEP [1]) اگر ، مجموعه آیتم X الگوی نوظهور جهشی از مجموعه داده از Ds به Dt نامیده می شود.
برای اینکه تفاوت الگوهای مکرر و الگوهای نوظهور مشخص شود، در ادامه تعریف الگوهای نوظهور را بر اساس confidence ارائه می دهیم. اطمینان[134]، تخمین ماکزیمم درست نمایی مربوط به احتمال شرطی است:

کلاسه بند مبتنی بر الگوهای مکرر، استخراج قوانین انجمنی و کلاسه بندی را با یکدیگر ترکیب می کند. در این راستا، نتیجه[135] قانون انجمنی برچسب کلاس در نظر گرفته می شود و کلاسه بند بر اساس چنین الگوهای ساخته می شود. در شکل زیر
100012516446500-6457951137285شکل 3-1. یک مثال از الگوهای مکرر استخراج شده از مجموعه داده Balloon
00شکل 3-1. یک مثال از الگوهای مکرر استخراج شده از مجموعه داده Balloon

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

در صورتی که الگویی معیار اطمینان برابر یک به ازای یک کلاس به خود اختصاص دهد، این الگو، الگوی نوظهور جهشی را نشان می دهد.
تعریف 4: ( الگوی نوظهور قوی SEP) حداقل نرخ رشد و تعداد میانگین مقادیر برای یک آیتم K داده شده است. الگوهای نوظهور قوی از مجموعه داده Ds به Dt، مجموعه آیتم X با n آیتم است که شرایط ذیل را ارضا می کند:

که شرط 1 تعریف محدودیت فراوانی دینامیک[136] است.
در الگوهای نوظهور قوی، ما محدودیت فراوانی دینامیک را بر اساس طول الگو و تعداد میانگین مقادیر K تنظیم می کنیم. ایده پشت آن اینست که الگوهای نوظهور قوی تمایل دارند تا همه ترکیبات ممکن از آیتم ها را برای یک الگو خاص در نمونه های آموزشی را پوشش دهند، از این رو، حداقل فراوانی الگو بایستی باشد. برای مثال، فرض کنید ما یک الگوی نوظهور با دو آیتم، تعداد میانگین مقادیر 3، و 20 نمونه آموزشی داریم. بنابراین، حداقل فراوانی الگو است و حداقل آستانه فراوانی نسبی است.
بعلاوه، طول الگوهای نوظهور بوسیله محدودیت فراوانی محدود می شود. طول الگو حداکثر است. فرآیند استخراج الگوهای نوظهور SEPs با طول بزرگتر از استخراج نمی کند.
کلاسه بندی بر پایه الگوهای کوتاهتر با آیتم های کمتر مطلوب است بدلیل اینکه با ویژگی های بیشتر معمولا در کلاسه بندی مشارکت نمی کنند و حتی، برای کلاسه بندی مضر است. از آنجایی که SEPs الگوهای کوتاهتر و با فراوانی بالا را نشان می دهند، برای کلاسه بندی بسیار مفید هستند.
تعریف 5: (بهبود نرخ رشد[137] Rateimp [2]) فرض کنید الگوی نوظهور e داده شده است، بهبود نرخ رشد e، Rateimp(e)، بعنوان کمترین اختلاف بین نرخ رشد e و نرخ رشد همه زیر مجموعه هایش توصیف می گردد.

برای استخراج موثر الگوهای نوظهور، Rateimp(e) فضای جستجو الگوها را هرس می کند و محاسبات اضافی را کاهش می دهد. یک آستانه مثبت از بهبود نرخ رشد،R، مجموعه مختصری از الگوها را که توسط دیگر الگوهای استخراجی قابل دستیابی نیستند، ارائه می دهد. بعلاوه، بهبود نرخ رشد می تواند در استخراج الگوهای قوی کمک کند. بنابراین، بهبود نرخ رشد ارتباط و وابستگی بین الگوهای نوظهور را نشان می دهد و الگوهای تکراری را کاهش می دهد.
یک مثال مصور در جدول 3-1 با استفاده از مجموعه داده mushroom از مجموعه داده های جمع آوری شده در UCI [52] ارائه شده است. حداقل آستانه فراوانی 0.05 و حداقل آستانه نرخ رشد است. الگوهای کاندید از دو کلاس Edible و Poisonous با 8124 نمونه و 22 ویژگی استخراج شده اند.
بر اساس تعریف 2، در جدول 3-1، آیتم های {odor = almond}، {stalk-color = white}، {odor = almond, stalk-color = white} الگوهای نوظهور از کلاس Edible هستند. بعلاوه، {odor = almond} و همچنین {odor = almond, stalk-color = white} الگوهای نوظهور جهشی هستند. بر اساس تعریف 3، آیتم ، {odor = almond} یک الگوی نوظهور است اما {odor = almond, stalk-color = white} یک الگوی نوظهور تکراری[138] است. در حقیقت، همه سوپرست های آیتم با نرخ رشد بینهایت، الگوی نوظهور جهشی هستند. واضح است که بهبود نرخ رشد صفر است.
فراوانی نسبی
(کلاس Poisonous) فراوانی نسبی
(کلاس Edible) الگوهای نوظهور کاندید
0.0951 0 {odor = almond}
1.4959 0.6540 0.4372 {stalk-color = white}
0.0951 0 {odor = almond, stalk-color = white }
جدول 3-1. الگوهای نوظهور کاندید از کلاس Poisonous به کلاس Edible
در کلاسه بندی بر پایه الگوهای نوظهور، همه الگوهای هر کلاس Ci، کلاس iام، از نمونه های آموزشی استخراج می شوند و برای تصمیم گیری در مورد برچسب کلاس نمونه های تست بکار گرفته می شوند. برای کلاسه بندی کردن یک نمونه تست t، M امتیاز محاسبه می شود، بطوری که برای هر کلاس یک امتیاز محاسبه می شود. کلاس با بالاترین امتیاز بعنوان برچسب کلاس برای t در نظر گرفته می شود، label(t) = argmaxci score (t, Ci). تعریفی که در ادامه آمده است، امتیاز مجموع[139] را بعنوان تابع امتیازدهی[140] ارائه می دهد.
تعریف 6: (جمع آوری امتیاز[141] [21]) نمونه تست t و مجموعه الگوهای نوظهور Ei که از کلاس Ci از نمونه های آموزشی استخراج شده اند، داده شده اند. مجموع امتیاز برای t به ازای کلاس Ci بدین شرح تعریف می شود:

بدلیل اینکه تعداد الگوهای نوظهور از کلاس های مختلف ممکن است نامتوازن باشد، نمونه تست t ممکن امتیاز بالاتری برای کلاس Ci با الگوهای بیشتر از دیگر کلاس Cj بدست آورد، حتی اگر برچسب کلاس t کلاس Cj باشد. بنابراین، تابع امتیاز که توسط تعریف 4 معرفی شده است، بایستی جهت کلاسه بندی نمونه تست t تغییر داده شود.
مفهوم امتیاز پایه[142] [21] می تواند کمک کند تا این مشکل حل شود. امتیاز پایه، baseScore(Ci)، از نمونه های آموزشی هر کلاس بدست می آید. با امتیاز پایه، امتیاز جدید یک نمونه تست t برای کلاس Ci که امتیاز نُرم شده، normScore(t, Ci)، نامیده می شود، بصورت نسبت امتیاز Score(t, Ci) و امتیاز پایه baseScore(Ci) تعریف می شود،

کلاس با بیشترین امتیاز نُرم شده بعنوان برچسب کلاس نمونه تست t در نظر گرفته می شود و در صورتی که امتیازات بدست آمده از کلاس های مختلف برابر شد، کلاس با بزرگترین نمونه بعنوان برچسب کلاس در نظر گرفته می شود. یک راه برای مشخص کردن امتیاز پایه این است که میانه امتیازات بدست آمده از نمونه های آموزشی کلاس Ci در نظر گرفته شود. برای مثال، فرض کنید 5 نمونه آموزشی از هر کدام از کلاس های مثبت (+) و منفی (-) وجود دارد. با همه EPs موجود از هر کلاس، فرض کنید که امتیازات حاصل از نمونه های مثبت[143] که بوسیله تعریف 4 محاسبه شده اند 17.85، 18.61، 18.76، 19.75، 20.24 هستند و امتیازات حاصل از نمونه های آموزشی منفی 7.80، 7.87، 8.20، 8.57، 8.61 هستند. در صورتی که امتیازات پایه را میانه امتیازات محاسبه شده به ازای هر کلاس در نظر بگیریم، در نتیجه، امتیاز پایه برای کلاس های مثبت و منفی به ترتیب 18.76 و 8.20 می شود. به ازای یک نمونه تست t ( می دانیم که از کلاس منفی است) با امتیازات 10.17 و 7.92 به ترتیب برای کلاس های مثبت ومنفی داده شده است؛ در صورتی که امتیاز پایه اعمال نشود، کلاس مثبت بعنوان برچسب نمونه t در نظر گرفته می شود. در حالیکه با اعمال امتیازات پایه، normScore(t, +) = 10.17/18.76 =0.54 و normScore(t,-)= 7.92/8.2 = 0.97 . بنابراین کلاس منفی بعنوان برچسب نمونه t در نظر گرفته می شود.
بعداً، Zhang et al. [26] یک تابع امتیاز ساده تر بر اساس تئوری اطلاعات[144] ارائه دادند که از محاسبه امتیاز پایه برای هر کلاس اجتناب می کند. تابع امتیاز نمونه تست t بوسیله معادله های 1 و 2 قابل محاسبه است.
فرمول 3-1 برچسب کلاس Ci به نمونه تست t اختصاص داده می شود در صورتی که L(t||Ci) کمترین مقدار به ازای کلاس Ci داشته باشد. به ازای مجموعه آیتم X، P(X|Ci) تقریبا با معادله 2 محاسبه می شود،
فرمول 3-2
در این معادله، تعداد نمونه هایی متعلق به کلاس Ci و دارای مجموعه آیتم X ، |X| تعداد کل نمونه های آموزشی شامل X ، |D| تعداد کل نمونه های آموزشی، و |Ci| تعداد نمونه های آموزشی متعلق به کلاس Ci را نشان می دهند. بعلاوه، برای اطمینان از اینکه حداقل یک EP برای کلاسه بندی نمونه تست t یافت می شود، ما همه آیتم های تکی را جدای از آن که حداقل آستانه ها را ارضا می کنند یا خیر برای کلاسه بندی نمونه تست t در نظر می گیریم.
درخت الگوی مکرر دینامیک[145] (DFP-tree)
درخت الگوی مکرر گسترش یافته ساختارهای مبتنی بر درخت های پیشوندی[146] است [15، 16]. درخت الگوی مکرر نمایش فشرده ای از داده است که اطلاعات کاملی از داده های اصلی را در خود ذخیره می کند. در FP-tree، هر مسیر مجموعه آیتم هایی را که دارای پیشوند یکسانی هستند را نشان می دهد و هر گره[147] یک آیتم و فراوانی آن را نشان می دهد. بعلاوه، همه گره هایی که آیتم یکسانی را شامل می شوند از طریق پیوند-گره[148] به هم متصل شده اند. از طریق پیوند-گره همه نمونه هایی که دارای آیتم مشابهی هستند به آسانی قابل دستیابی و شمارش هستند. راس[149] همه پیوند-گره ها برای هر آیتم در یک جدول هدر[150] ذخیره می شوند. بعلاوه، آیتم ها در جهت کاهش فراوانی شان در داده ها مرتب می شوند و در ساختار درخت ذخیره می شوند. اگر چه FP-tree به نظم خاصی وابسته نیست ولی در حالتی که مرتب شده باشد سرعت اجرای عملیات استخراج بسیار بیشتر از حالتی است که درخت نامنظم باشد. برای نمایش الگوهای نوظهور، ما ساختار FP-tree را تغییر می دهیم همانطوری که در تعریف ادامه آمده است.
تعریف 7: (درخت الگوی مکرر دینامیک DFP-tree [15]) یک درخت الگوی مکرر دارای یک ریشه تهی[151]، مجموعه ای از زیر درخت های پیشوندی بعنوان بچه های ریشه، و یک جدول هدر توصیف شده در زیر است.
هر گره در زیردرخت دارای چهار فیلد: مشخصه ID، مقدار یا آیتم value or i–، توزیع کلاس class distribution، و پیوند-گره node-link است. ID، یک گره را از مابقی گره ها متمایز می کند، value، نشاندهنده آن است که کدام مقدار ویژگی در گره جاری ذخیره شده است، class distribution، فراوانی آیتم را به ازای هر کلاس که توسط قسمتی از شاخه ای که به گره می رسد، ثبت می کند، و node-link، گره جاری را به گره بعدی که دارای آیتم مشابهی است متصل می کند و اگر گره ای وجود ندارد null می باشد. بعلاوه، تعدادی از گره ها را بعنوان گره های خارجی[152] تعریف می شوند. دو نوع از گره ها بعنوان گره های خارجی تعریف می شوند : (1) گره های برگ[153] (2) گره های پدری[154] که مقدار فراوانی شان بزرگتر از جمع فراوانی همه گره های فرزندانشان[155] باشد.
هر ورودی در جدول هدر شامل چهار فیلد است: آیتم i–، فراوانی کل total frequency، توزیع کلاس class distribution، هد پیوند-گره head of node-link است. در این مطالعه، آیتم، مقدار ویژگی را ثبت می کند، فراوانی کل، فراوانی آیتم و مقدار ویژگی را در داده ثبت می کند، توزیع کلاس، مقدار فراوانی آیتم یا مقدار ویژگی در هر کلاس را ثبت می کند، و هد پیوند-گره یک اشاره گر اشاره کننده به اولین گره حامل آیتم است.

شکل 3-2. یک مثال از درخت الگوی مکرر: هر گره دارای یک ID، یک آیتم، توزیع کلاس آیتم که نشاندهنده قسمتی از مسیر منتهی به گره است، و پیوند-گره. هر ورودی در جدول هدر دارای یک آیتم، فراوانی کل، توزیع کلاس، و هد پیوند-گره. همه گره ها به رنگ قرمز نشان داده شده اند.
مثال 1. یک مثال از درخت الگوی مکرر در شکل 3-1 نشان داده شده است. درخت دارای یک ریشه تهی و 8 گره است.هر گره دارای یک ID، یک آیتم، فراوانی آیتم در هر دو کلاس (توزیع کلاس)، و یک گره-پیوند است. همانطوری که به تصویر کشیده شده است، گره با مشخصه[156] I5 شامل آیتم c، توزیع کلاس 0 و 3 به ترتیب برای کلاس های مثبت و منفی؛ بدین معنا که آیتم c به همراه آیتم h 3 بار در کلاس منفی ظاهر شده است (ch:0:3)، و یک گره-پیوند گره I5 را به گره I3 که دارای آیتم c هست متصل می کند. در جدول هدر، هر ورودی شامل یک آیتم، فراوانی کل، توزیع کلاس، و هد آیتم است. ورودی آیتم c دارای فراوانی کل 4، توزیع کلاس 3 و 1 در کلاس های مثبت و منفی، و یک هد است که به اولین گره (I5) که دارای آیتم c است. همه گره های برگ I4، I5، I6، I7، I8 بعنوان گره های خارجی در نظر گرفته می شوند. بعلاوه، گره I1 یک گره خارجی است بدلیل اینکه فراوانی I1 که 9 است بزرگتر از جمع فراوانی بچه هایش 8 است. همه گره های خارجی به رنگ قرمز نشان داده شده اند.
فصل چهارم
راهکارهای ارائه‌شده برای استخراج الگوهای نوظهور قوی مبتنی بر ویژگی های جریانی

Related posts:

- (228)

- (319)

- (81)

فرستاده شده.

راهبری نوشته‌ها

→ – (70)

– (83) ←

پاسخ دهید لغو پاسخ

نوشته‌های تازه

• نمونه مقاله 22222222222222- ارشددانلود
• دانلود پژوهش علمی ایرانداک ش- مقاله
• – (99)

آخرین دیدگاه‌ها

بایگانی

• آگوست 2017
• جولای 2017

دسته‌ها

اطلاعات

• ورود
• پیگیری نوشته‌ها باRSS
• پیگیری دیدگاه‌ها با RSS
• WordPress.org

– (74)

فهرست مطالب فصل اول 1 1- مقدمه 2 1-1 مقدمه 2 1-2 مفهوم الگوهای نوظهور 3 1-3 مفهوم ویژگی های جریانی 5 1-4 چالش های موجود در استخراج الگوهای نوظهور 6 1-5 الگوریتم های استخراج الگوهای نوظهور 8 1-6 ایده اصلی تحقیق 11 1-7 نگاهی کلی به فصول رساله 13 فصل دوم 14 2- پیشینه […]

پایاپیوند را نشانه‌گذاری کنید.

جولای31 بدست 92

Please enter banners and links.

در این مطالعه، ما ساختار دینامیک از درخت الگوی مکرر پیشنهاد می دهیم تا درخت به محض ورود ویژگی های جدید ساخته شود و استخراج الگوهای نوظهور بصورت برخط صورت گیرد. DFP-SEPSF، یک روش موثر پایین به بالا ارائه می دهد تا یک درخت الگوی مکرر دینامیک نامرتب UDFP-tree و یک درخت الگوی مکرر دینامیک مرتب ODFP-tree بسازد. اولین روش ترتیب آیتم ها را در نظر نمی گیرد، در حالیکه دومین روش ترتیب آیتم ها را اعمال می کند.
بعلاوه، چارچوب پیشنهادی الگوهای نوظهور قوی را استخراج می کند تا یک کلاسه بند قوی و سریع ایجاد کند که می تواند با نویز مقابله کند.
روش پیشنهادی فضای جستجوی الگوهای نوظهور را بطور قابل توجهی کاهش می دهد و الگوهای نوظهور با قدرت تمایز قوی را با کمک حذف الگوهای بی فایده استخراج می کند.
روش ارائه شده الگوهای نوظهور را برای هر کلاس بصورت همزمان کشف می کند و بعلاوه، فرآیند تولید درخت های الگوی مکرر را بصورت کارایی در راستای کاهش محاسبات، هدایت می کند.
ارزیابی تجربیات ما بر روی محدوده وسیعی از داده ها، اثربخشی روش پیشنهادی را در مقایسه با دیگر روش های شناخته شده از نظر دقت پیش بینی، تعداد الگوهای استخراجی و زمان اجرا نشان می دهد.
واژههای کلیدی:
الگوهای نوظهور، درخت الگوی مکرر دینامیک، ترتیب آیتم ها، ویژگی های جریانی
فهرست مطالب
فصل اول 1
1- مقدمه 2
1-1 مقدمه 2
1-2 مفهوم الگوهای نوظهور 3
1-3 مفهوم ویژگی های جریانی 5
1-4 چالش های موجود در استخراج الگوهای نوظهور 6
1-5 الگوریتم های استخراج الگوهای نوظهور 8
1-6 ایده اصلی تحقیق 11
1-7 نگاهی کلی به فصول رساله 13
فصل دوم 14
2- پیشینه تحقیق 15
2-1 مقدمه 15
2-2 روش های مبتنی بر قانون 15
2-2-1 روش Classification Based on Association (CBA) 15
2-2-2 روش کلاسه بندی Classification based on Multiple-class Association Rule (CMAR) 16
2-2-3 روش کلاسه بندی Classification based on Prediction Association Rule (CPAR) 16
2-3 روش های استخراج الگوها 17
2-3-1 روش مبتنی بر مرز 17
2-3-2 روش مبتنی بر محدودیت 17
2-3-3 الگوریتم استخراج درخت الگوی تقابل CP-tree 18
2-3-4 روش استخراج با کمک دیاگرام دودویی صفر ZBDD Miner 18
2-3-5 روش استخراج الگوهای نوظهور متمایز DP-Miner 18
2-4 روش های کلاسه بندی مبتنی بر الگوهای نوظهور 20
2-4-1 روش کلاسه بندی مبتنی بر اساس مجموع الگوهای نوظهور CAEP 20
2-4-2 الگوریتم کلاسه بندی بر پایه تئوری اطلاعات iCAEP 20
2-4-3 روش کلاسه بندی بر پایه الگوهای نوظهور جهشی JEPs-classifier 21
2-4-4 روش کلاسه بندی بر پایه الگوهای نوظهور جهشی قوی 21
2-4-5 روش تصمیم گیری مبتنی بر نمونه DeEPs 21
2-4-6 روش کلاسه بندی توسط مجموعه راست نمایی PCL 22
فصل سوم 23
3- دانش اولیه 24
3-1 الگوهای نوظهور 24
3-2 درخت الگوی مکرر دینامیک DFP-tree 30
فصل چهارم 33
4- راهکارهای ارائه شده برای استخراج الگوهای نوظهور قوی مبتنی بر ویژگی های جریانی 34
4-1 مقدمه 34
4-2- درخت الگوی مکرر دینامیک نامرتب Unordered Dynamic FP-tree 35
4-3 درخت الگوی مکرر دینامیک مرتب Ordered Dynamic FP-tree 44
4-4 روش استخراج الگوها SEP-Miner 56
فصل پنجم 62
5- آزمایشات تجربی 63
5-1 مقدمه 63
5-2 کلاسه بندها 63
5-2-1 کلاسه بند درخت تصمیم C4.5 63
5-2-2 کلاسه بند SVM 64
5-2-3 کلاسه بند بیزین ساده 65
5-2-4 کلاسه بند نزدیکترین همسایه 66
5-2-5 الگوریتم AdaBoost66
5-3 تست های آماری 68
5-3-1 تست آماری جفت شده t-tets 68
5-3-2 تست آماری Wilcoxon 68
5-3-3 تست آماری فردمن 69
5-4 تنظیمات تجربی 71
5-5 مقایسه دقت پیش بینی 73
5-6 مقایسه تعداد الگوها 81
5-7 مقایسه زمان اجرا 83
5-8 تحلیل اثر ترتیب در ساخت درخت الگوی مکرر دینامیک 86
5-9 چگونگی تعیین کردن حداقل آستانه فراوانی نسبی 88
5-10 تحلیل حساسیت روی حداقل آستانه های نرخ رشد 89
5-11 مقایسه کارایی DFP-SEPSF بدون دانستن کل فضای ویژگی ها 90
5-12 خلاصه نتایج تجربی 94
فصل ششم 96
6- نتیجه گیری و کارهای آینده 97
اختصارات 99
واژه نامه فارسی به انگلیسی 100
واژه نامه انگلیسی به فارسی 108
فهرست منابع 116

فهرست جدولها
جدول 3-1 الگوهای نوظهور کاندید از کلاس Poisonous به کلاس Edible38
جدول 5-1 توصیف مجموعه داده ها؛ #Features تعداد ویژگی ها، #Instances تعداد نمونه ها، #Classes تعداد کلاس ها 71
جدول 5-2 مقایسه دقت پیش بینی (%): کلاسه بندهای DFP-SEPSF، EPSF، SJEP، CAEP 75
جدول 5-3 مقایسه دقت پیش بینی (%): کلاسه بندهای DFP-SEPSF، CBA، CMAR، CPAR 77
جدول 5-4 مقایسه دقت پیش بینی (%): کلاسه بندهای DFP-SEPSF، NB، Knn، J48، SVM، AdaBoost 78
جدول 5-5 تعداد دفعات win/tie/loss کلاسه بند DFP-SEPSF در مقابل یازده کلاسه بند دیگر 80
جدول 5-6 تعداد دفعات win/tie/loss کلاسه بند DFP-SEPSF در مقابل یازده کلاسه بند دیگر؛ با استفاده از تست جفت شده t-test در سطح معنادار 95% 80
جدول 5-7 تعداد دفعات win/tie/loss کلاسه بند DFP-SEPSF در مقابل یازده کلاسه بند دیگر؛ با استفاده از تست Wilcoxon در سطح معنادار 95% 80
جدول 5-8 تست فردمن در سطح معنادار 95% با میانگین رتبه کلاسها 81
جدول 5-9 تست Bonferroni-Dunn 81
جدول 5-10 مقایسه تعداد الگوهای استخراجی: کلاسه بندهای DFP-SEPSF، CAEP، CBA، CMAR 83
جدول 5-11 زمان اجرا: کلاسه بندهای DFP-SEPSF، CAEP 86
جدول 5-12 مقایسه درخت الگوی مکرر مرتب با درخت الگوی مکرر نامرتب 88
فهرست شکلها
شکل 3-1. یک مثال از الگوهای مکرر از مجموعه داده Balloon 25
شکل 3-2. یک مثال از درخت الگوی مکرر دینامیک 32
شکل 4-1. مرحله به مرحله ساخت دینامیک درخت الگوی مکرر بدون در نظر گرفتن ترتیب آیتم ها35
شکل 4-2. ساخت درخت الگوی مکرر دینامیک بدون در نظر گرفتن ترتیب آیتم ها 40
شکل 4-3. مقایسه ساختار درخت الگوی مکرر با و بدون در نظر گرفتن ترتیب آیتم ها 45
شکل 4-4. ساختن درخت الگوی مکرر بر پایه ویژگی های جریانی 45
شکل 4-5. درخت الگوی مکرر پایه 47
شکل 4-6. اضافه کردن گره های جدید به درخت الگوی مکرر و تغییر موقعیت آنان 48
شکل 4-7. فرآیند ترکیب مرحله به مرحله 51
شکل 4-8. استخراج الگوهای نوظهور با استفاده از FP-tree بصورت مرحله به مرحله 57
شکل 5-1 بردار پشتیبان و صفحه جداکننده خطی65
شکل 5-2 تاثیر آستانه های نرخ رشد بر روی DFP-SEPSF: دقت روش پیشنهادی بر روی سی مجموعه داده تحت آستانه های 20، 30، 40، 50 و 60 گزارش داده شده است. 90
شکل 5-3 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 50، 50، 60، 60، و 60 هستند. 91
شکل 5-4 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 70، 80، 100، 70، و 80 هستند 92
شکل 5-5 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 70، 90، 70، 100، و 70 هستند 92
شکل 5-6 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 50، 60، 70، 50، و 40 هستند 93
شکل 5-7 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 80، 80، 100، 100، و 90 هستند 93
شکل 5-8 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 90، 80، 60، 80، و 90 هستند 94
فصل اولمقدمه

مقدمهمقدمه کلاسه بندی[1] یکی از وظایف اساسی در داده کاوی[2] است که بطور وسیعی در زمینه یادگیری ماشین[3]، شبکه های عصبی[4] و تشخیص الگو[5] مورد مطالعه واقع شده است. ورودی، مجموعه ای از نمونه های آموزشی[6] است که شامل چندین ویژگی[7] است. ویژگی ها با توجه به دامنه مقادیرشان به دو دسته ویژگی های گسسته[8] و ویژگی های پیوسته[9] قابل تفکیک هستند. در حالت کلی، یک کلاسه بند[10]، توصیف مختصر و معنادار (مدل[11]) برای هر برچسب کلاس[12] در رابطه با ویژگی ها تولید می کند. سپس، مدل برای پیش بینی برچسب کلاس نمونه های ناشناخته[13] بکار می رود. کلاسه بندی همچنین بعنوان یادگیری با ناظر[14] نیز شناخته می شود که در آن هر نمونه آموزشی دارای برچسب کلاس است. در حالی که، یادگیری بدون ناظر[15] یا خوشه بندی[16] جستجو می کند و گروه های همگن از اشیا را بر اساس مقادیر ویژگی هایشان دسته بندی می کند؛ در واقع، نمونه ها دارای برچسب کلاس نیستند. کلاسه بندی در محدوده وسیعی از کاربردها از جمله آزمایشات علمی[17]، تشخیص دارو[18]، پیش بینی آب و هوا[19]، تایید اعتبار[20]، تقسیم بندی مشتری[21]، بازاریابی هدف[22] و تشخیص تقلب[23] بطور موفقیت آمیزی بکار می رود.
کلاسه بندی بر پایه الگوها[24]، یک متدلوژی جدید محسوب می شود. کشف الگوهایی که نشاندهنده تمایز بین کلاس های مختلف هستند، یکی از موضوعات مهم در داده کاوی محسوب می شود. در این تحقیق، ما کلاسه بندی را بر اساس الگوهایی به نام الگوهای نوظهور[25] (Emerging Patterns) که تمایز بین کلاس ها را بصورت بارزی نشان می دهند، از مجموعه داده ها[26] استخراج می کنیم و سپس، بر اساس آنها، کلاسه بندی را انجام می دهیم.
مفهوم الگوهای نوظهور
مفهوم الگوهای نوظهور برای استخراج دانش از پایگاه داده ها توسط Dong و Li پیشنهاد شده است تا تغییرات قابل توجه بین کلاس ها را به تصویر بکشند [1]. یک الگوی نوظهور، ترکیب عطفی بین ویژگی هایی است که میزان احتمال حضور آن در یک کلاس نسبت به دیگر کلاس ها بطور قابل توجهی تغییر می کند [1،2]. این الگوها مفید هستند به این دلیل که قادر هستند تا وجه تمایز بین کلاس ها را بیان کنند. در صورتی که میزان فراوانی[27] هر الگو که در یک کلاس نسبت به دیگر کلاس ها قابل توجه باشد، نشاندهنده آن است که این الگو، بطور خاص به این کلاس اختصاص دارد و از طرفی این نوع الگوها برای پایگاه داده هایی که بحث محدودیت زمانی برای استخراج دانش از آنها مطرح است، اهمیت ویژه ای می یابند.
استخراج الگوهای نوظهور بدین صورت مطرح می شود: « پیدا کردن آیتم هایی که نرخ رشد[28] آن (که بصورت نسبت احتمال آن آیتم بین کلاس های مختلف تعریف می شود) از مقدار آستانه ای بیشتر باشد.» این مقدار آستانه باید بگونه ای انتخاب شود که الگوهای استخراجی ، تفاوت و تمایز بین کلاس های مختلف را نشان دهند. این الگوها در واقع مجموعه ای از آیتم ها هستند که بیان کننده ترکیب عطفی بین مقادیر ویژگی ها هستند [2].
نوعاً، تعداد الگوهای استخراجی بسیار زیاد است اما فقط شمار کمی از این الگوها برای تحلیل داده ها و کلاسه بندی مطلوب و مفید هستند. از آن جایی که مقدار زیادی از این الگوها بی ربط[29] و تکراری[30] هستند، دانش جدیدی را فراهم نمی کنند و لذا تاثیر نامطلوبی بر روی دقت کلاسه بند دارند که موجب کاهش دقت پیش بینی[31] می شوند. برای افزایش کارایی[32] و دقت، بایستی روالی را توسعه داد که الگوهای وابسته و غیر مفید حذف شوند تا شمار این الگوها کاهش یابد.
یک الگوی نوظهور با احتمال بالا در کلاس خودش و احتمال پایین در کلاس مقابلش می تواند برای تعیین یک نمونه تست بکار رود. قدرت این الگو توسط معیارهایی مثل فراوانی نسبی[33] و نرخ رشد ( نسبت احتمال الگو در یک کلاس نسبت به دیگر کلاس ها) آن بیان می شود.
در بسیاری از زمینه های کاربردی مانند کشف دانش از داده های ژنی[34] ، پردازش تصویر[35]، کشف نفوذ[36] ، کشف برون هشته[37]، کشف کلاهبرداری[38] ، داده های نامتوازن[39] ، جریان داده ها[40] ، بیوانفورماتیک[41] ، سیستم های پیشنهاد دهنده[42] ، نیاز است که تغییر ناگهانی در داده ها تشخیص داده شود. الگوهای نوظهور تغییرات ناگهانی و تفاوت های قابل توجه را از داده ها استخراج می کنند. الگوهای نوظهور، در زمینه پردازش تصویر برای قطعه بندی بدین گونه عمل می کند که سعی می کند در پیکسل هایی که تغییر ناگهانی شدت[43] بوجود می آید را بعنوان یک قطعه جدید معرفی کند. در زمینه کشف نفوذ و کلاهبرداری، رفتار داده ها پیگیری می شود، زمانی که رفتار داده ها بصورت ناگهانی تغییر کند، بعنوان نفوذ تشخیص داده می شود. در سیستم های پیشنهاد دهنده، سیستم به دنبال رفتارهای خاص و مختص هر کاربر است تا با کشف ویژگی های خاص هر کاربر، به او محصولات مطابق با علایق و استعدادهای او را پیشنهاد دهد. لذا الگوهای نوظهور در این راستا نقش بسزایی دارند.
مفهوم ویژگی های جریانی[44]
در داده های جریانی[45]، نمونه ها به مرور زمان دریافت می شوند در حالیکه تعداد ویژگی ها ثابت می باشد. اما در ویژگی های جریانی، تعداد داده های یادگیری ثابت می باشد ولی ویژگی ها بصورت دینامیک تولید می شوند و الگوریتم یادگیری به مرور زمان ویژگی ها را دریافت می دارد [31، 32]. در ویژگی های جریانی روال بدین صورت است ویژگی های توسط روش های تولید ویژگی مانند روش های یادگیری رابطه ای آماری[46] و تعاملات بین ویژگی ها[47]، تولید می شوند. مشکلاتی که در پی تولید ویژگی ها توسط این روش ها بروز می کند بدین شرح است که: 1) میلیون ها و یا حتی بیلیون ها ویژگی تولید می شوند که بدلیل محدودیت های حافظه امکان نگهداری این حجم از ویژگی وجود دارد و از طرفی زمان بسیار زیادی بایستی صرف شود تا فرآیند یادگیری شروع شود. 2) ویژگی ها توسط کوئری های موجود در SQL تولید می شوند که اجرای این کوئری ها محدود به زمان پروسسور[48] است تقریبا پروسسور هر صدهزار کوئری را در 24 ساعت اجرا می کند. از طرفی بسیاری از ویژگی ها تولیدی بی ربط و تکراری هستند[49]. این موضوع نشان می دهد که شمار کمی از این ویژگی های تولیدی در عمل در فرآیند یادگیری موثر است و لذا تولید ویژگی ها هزینه بر است [32]. بر این اساس برای فائق آمدن بر این مشکلات، مفهوم ویژگی های جریانی شکل گرفت و تلاش شد تا با تولید دینامیک ویژگی ها و بررسی این ویژگی ها در زمان تولید و تاثیر آن بر روال یادگیری فرآیند تولید ویژگی ها را هدایت کنند.
برای برخورد با چالش های مطرح شده، بایستی فرآیند یادگیری قابلیت پاسخگویی به ویژگی های جریانی را داشته باشد. در واقع، روال یادگیری بایستی بصورت افزایشی با دریافت هر ویژگی قابل بروزرسانی شدن داشته باشد بدون اینکه به اولین مرحله یادگیری بازگردد. لذا در راستای استخراج الگوهای قوی بایستی در ابتدا ویژگی ها بررسی شوند و ویژگی هایی که بی ربط هستند را حذف کرد، سپس از روی ویژگی های مفید و قوی ، الگوها را استخراج کرد.
چالشهای موجود در استخراج الگوهای نوظهور
در این تحقیق هدف بر آن است که بر موضوعات اساسی در زمینه الگوهای نوظهور پرداخته شود که عبارتند از: 1. به دلیل حجیم بودن داده ها و حجم بالایی از ویژگی ها و با توجه به مفهوم ویژگی های جریانی، اولین موضوع، نحوه برخورد با این نوع از داده ها می باشد به طوری که بتوان از میان خیل عظیم ویژگی ها و با توجه به قضیه رشد ویژگی ها که بصورت دینامیک تولید می شوند، روشی ارائه داده شود که با دریافت ویژگی های جدید بصورت دینامیک بروزرسانی شود. همانطور که قبلا اشاره شد، در حوزه های مربوط به پایگاه داده ها که نیاز به گرفتن کوئری از پایگاه داده است، میلیونها و یا بیلیارد ویژگی تولید می شود. این نوع ویژگی همین طور در حوزه پردازش تصویر کاربرد دارد. در حوزه پردازش تصویر، در بعضی مواقع لازم است که به هر پیکسل بعنوان یک ویژگی در نظر گرفت که در نتیجه فضای ویژگی ها بسیار گسترده و گاها نامتناهی می شود و لذا لزوم برخورد با اینگونه داده ها متفاوت می شود. 2. استخراج الگوهای قوی از میان الگوها و داده های موجود، از دیگر موضوعات اساسی است. این موضوع، زمانی بیشتر اهمیت می یابد که با توجه به حجیم بودن داده ها، در نتیجه رشد این الگوها به سرعت نمایی خواهد شد بخصوص زمانی که ابعاد ویژگی ها بی نهایت باشد، دیگر امکان نگهداری هر الگویی وجود نخواهد داشت در نتیجه استخراج الگوهای قوی که در کلاسه بندی واقعا موثر باشند، بسیار اهمیت خواهد یافت.
در روال استخراج این الگوها سه مساله اساسی وجود دارد:
چگونه مجموعه مفید و موثری از الگوهای نوظهور، بین داده های کلاس های مختلف استخراج شود؟
از آنجایی که همه این الگوها مفید نیستند در واقع شمار زیادی از این الگوها در راستای یادگیری مدل و کلاسه بند بکار نمی روند، در نتیجه بایستی بتوان مجموعه کوچک و در عین حال قوی از این الگوها تشکیل داد، در همین راستا مسائلی که مطرح می شود این است که کدامیک از این الگوها برای هدف یادگیری و کلاسه بند مفید است و در واقع چگونه می توان مجموعه قوی از این الگوها را تشکیل داد؟ از طرفی موضوع دیگر ابعاد ویژگی های[50] مسئله خواهد بود، در صورتی که ابعاد ویژگی ها بالا باشد، در نتیجه شمار الگوهای نوظهور سیر صعودی خواهد داشت که شمار زیاد از این الگوها هم برای آنالیز داده ها بصورت برخط مشکل ساز است و هم این که روال یادگیری و کلاسه بند را زمانبر و هزینه بر می کند که مناسب نیست. لذا با بیان این مسائل بایستی بتوان مجموعه کوچک و در عین حال قوی از الگوهای نوظهور را تشکیل داد که این موضوع خود موضوعی چالش برانگیز است، و اینکه کدامیک از الگوهای جدید مفید و موثر هستند ؟
کدامیک از این الگوها برای هدف کلاسه بند مفید هستند؟ و چگونه این الگوها یک کلاسه بند مفید و موثر و در عین حال دقیق را می سازند؟
3. طریقه استفاده از این الگوها و یا همان مدل است که بتواند از الگوها بخوبی بهره گرفته و کلاسه بندی دقیقی را انجام دهد بطوری که دقت کلاسه بند بالا باشد.
وقتی که ابعاد ویژگی ها بالا باشد، استخراج الگوهای نوظهور مشکل تر خواهد شد؛ چرا که ذخیره، بازیابی، هرس و مرتب کردن آنها برای کلاسه بند با تعداد کاندیداهای بسیار زیاد الگوها، سخت و یا غیرممکن خواهد شد. با ظهور داده های حجیم و بزرگ که شامل صدها هزار ویژگی هستند مانند پردازش تصویر ، داده های ژنی و داده های متنی و … ، فضای جستجوی این الگوها نسبتاً بزرگ، هزینه بر و گاهی اوقات حتی غیرممکن است [19].
ایجاد یک مدل بر اساس الگوهای نوظهور با داده های با ابعاد بالا و نمونه های حجیم یک موضوع چالش برانگیز است. مشکل حتی سخت تر می شود اگر همه فضای ویژگی ها، قبل از عملیات یادگیری در دسترس نباشد و یا نامتناهی باشد [19].
از طرفی روش های یادگیری مرسوم [37، 38، 40] قادر هستند که بحث چند کلاسه[51] را از طریق روش های دو به دو مثل یکی در مقابل یکی[52] و یکی در مقابل همه[53] مدیریت کنند. بلاوه، بسیاری از روش های موجود استخراج الگوهای نوظهور مانند روش های مبتنی بر مرز[54] [1، 3، 13] و روش های مبتنی بر محدودیت[55] [2]، الگوهای مربوط به هر کلاس را در فرآیند جداگانه ای استخراج می کنند که این امر مطلوب نیست و منجر به تکرار محاسبات سنگین می شود. لذا بایستی بتوان روش استخراجی ارائه داد که این قابلیت را دارا باشد که تمامی الگوهای کلاس های مختلف را بصورت همزمان استخراج کند.
بنابراین در این حوزه با موضوعات چالش برانگیزی بدین شرح روبرو هستیم:
1. چگونه بصورت موثر، مجموعه کوچکی از الگوهای نوظهور قوی را از داده های با ابعاد بالا استخراج کنیم؟
2. چگونگی استخراج کردن الگوهای نوظهور وقتی که کل ویژگی ها قبل از فرآیند یادگیری در دسترس نیستند؟
3. چگونگی ارائه مدل افزایشی و دینامیک در پاسخ به ویژگی های جریانی؟
4. چگونگی استخراج الگوهای نوظهور از کلاس های مختلف بصورت همزمان؟
الگوریتمهای استخراج الگوهای نوظهور
زمانی که ابعاد داده ها بالا باشد، شمار الگوهای نوظهور بسیار زیاد و در واقع نمایی و گاهاً غیرممکن خواهد بود. لذا استخراج الگوهای نوظهور از داده ها، نیاز به روالی جداگانه دارد که در این راستا روش هایی ارائه شده است. روش هایی که تلاش می کنند الگوهایی با مشخصات بیان شده، استخراج کنند؛ بدین شرح هستند: روش مبتنی بر مرز[56]، روش مبتنی بر محدودیت[57]، الگوریتم های سریع برای استخراج الگوهای نوظهور[58]، روش دیاگرام تصمیم گیری دودویی مانع صفر[59].
این روش ها کمک بسزایی در کاهش تعداد الگوهای نوظهور می کنند بدون اینکه اثری بر قدرت تشخیص کلاسه بند داشته باشد.
1.استخراج الگوها بر اساس روش مبتنی بر مرز
برای روش های مبتنی بر مرز، سه الگوریتم؛ استخراج افقی[60] ، اختلاف مرز[61] ، تولید الگوهای نوظهور جهشی[62] وجود دارد. این روش ها با الهام از الگوریتم Max_Miner طراحی شده اند.
مرز، ساختاری است که مجموعه بزرگی از آیتم ها را بصورت مختصر نمایش می دهد. مرز برای نمایش الگوهای نوظهور کاندید بکار می رود. عملیات تفکیک مرز، برای استخراج الگوها استفاده می شود. مرز افقی از داده ها، نشان دهنده همه آیتم ها با فراوانی نسبی با آستانه خاصی، در داده ها است. الگوریتم استخراج افقی، مرز افقی هم برای داده های کلاس مثبت و هم برای داده های کلاس منفی ایجاد می کند. در واقع این الگوریتم، سعی می کند مرزی برای هر یک از کلاس ها بیابد. ایده اصلی این الگوریتم، استخراج مجموعه آیتم های با فراوانی نسبی ماکزیمال است [1، 3].
الگوهای نوظهور جهشی ، الگوهای نوظهوری هستند که در داده های یک کلاس، حضور ندارند، در نتیجه نسبت فراوانی نسبی داده های کلاس های دیگر به کلاسی که این مقدار داده در آن حضور ندارد، بی نهایت می شود. به الگوهای نوظهور با نرخ رشد بی نهایت، الگوی نوظهور جهشی گفته می شود. استخراج چنین الگوهایی، کمک بسزایی به کلاسه بند می کند. به این دلیل که تفاوت بین کلاس ها توسط این الگوها، بیش از پیش قابل لمس است. لذا در این راستا، روش هایی برای استخراج الگوهای نوظهور جهشی [3، 13] ارائه شده است.
2.استخراج الگوها بر اساس روش مبتنی بر محدودیت
این روش از دو نوع محدودیت برای هرس فضای جستجو استفاده می کند که محدودیت های داخلی و خارجی را شامل می شود [2].
محدودیت هایی است که کاربر اعمال می کند، محدودیت های خارجی روش مبتنی بر محدودیت استخراج الگوهای نوظهور را ایجاد می کند. این محدودیت ها شامل تعیین حداقل مقدار برای فراوانی نسبی، نرخ رشد و بهبود نرخ رشد می باشد. از آنجا که ممکن است بعضی از الگوها زیر مجموعه دیگر الگوها باشند، چنین الگوهایی، در حکم الگوهای تکراری هستند که کمکی به کلاسه بند نمی کنند. چنین الگوهای تکراری از مجموعه الگوها باید حذف شوند که البته شمار الگوها بدین ترتیب کاهش می یابد [2].
محدودیت هایی که به صورت انطباقی در روال استخراج، بر اساس مشخصات داده ها اعمال می شود، محدودیت داخلی را تشکیل می دهند. الگوریتم مبتنی بر محدودیت استخراج الگوهای نوظهور، می تواند بصورت موثر همه الگوها را که این محدودیت ها را ارضاء می کنند، استخراج کند. این روش از جستجوی اول عرض بر روی (SE-Tree) اعمال می کند و الگوهای مفید را استخراج می کند. برای بالا بردن کارایی این روش، الگوریتم هایی ارائه شده است که هر دو دسته محدودیت ها را در یک فاز اجرایی اعمال می کنند [2].
این الگوریتم بصورت مرحله ای انجام می شود که در هر مرحله، یکسری کاندید تولید می کند و سپس آنها را تست می کند. بدین ترتیب با اعمال محدودیت ها در هر مرحله و البته تغییر بعضی محدودیت ها در هر مرحله، الگوهای نوظهور را استخراج می کند.
همچنین این موضوع قابل بیان است که روش دیاگرام تصمیم گیری دودویی مانع صفر، در مقایسه با دیگر روش ها بیشتر در زمینه داده ها با ابعاد بالا کاربرد دارد و قویتر از دیگر روش های گفته شده در این زمینه عمل می کند.
ایدهی اصلی تحقیقبرای حل موضوعات چالش برانگیز مطرح شده، ما روش درخت الگوی مکرر دینامیک[63] جهت استخراج الگوهای نوظهور قوی در ویژگی های جریانی، DFP-SEPSF را پیشنهاد می دهیم. در این روش، درخت الگوی مکرر[64] مرسوم در پاسخ به ویژگی های جریانی ساخته می شود. ایده اصلی روش پیشنهادی بدین شرح هستند:
1. با چارچوب پیشنهادی، یک تکنیک جدید، درخت الگوی مکرر دینامیک، DFP-tree، در جواب ویژگی های جریانی ارائه شده است. ما دو روش از درخت الگوی مکرر دینامیک معرفی می کنیم: درخت الگوی مکرر دینامیک نامرتب[65]، UDFP-tree، و درخت الگوی مکرر دینامیک مرتب[66]، ODFP-tree. این روش ها درخت الگوی مکرر را بصورت افزایشی به محض ورود ویژگی های جدید بصورت پایین به بالا می سازند.
2. زیر مجموعه جدیدی از الگوهای نوظهور با نام الگوهای نوظهور قوی[67]، SEPs، ارائه می دهیم. این الگوها، الگوها با کیفیت بالا[68] هستند که محدودیت فراوانی دینامیک[69] را ارضا می کنند و بسیاری از نمونه های آموزشی را پوشش می دهند. کلاسه بند بر پایه SEPs بسیار بهتر از دیگر الگوریتم های شناخته شده عمل می کند. بعلاوه، روش استخراج الگوهای نوظهور[70]، SEP-Miner، بطور چشمگیری فضای جستجوی الگوها را کاهش می دهد و الگوهای نوظهور قوی را بصورت کارایی استخراج می کند.
3. DFP-SEPSF قادر است تا به محض ورود مقادیر ویژگی های جدید، آنها را در ساختار DFP-tree وارد نماید و الگوهای نوظهور قوی جدید مربوط به این مقادیر جدید وارد شده را استخراج کند. سپس روش پیشنهادی، این الگوها را به مجموعه الگوهای استخراج شده اضافه نماید.
2. روش استخراج، الگوهای نوظهور با قابلیت پیش بینی قوی را با حذف الگوهای بی ربط و تکراری از ساختاری استخراج می کند. روش استخراج، فضای جستجوی الگوها را بصورت قابل توجهی کاهش می دهد و فرآیند کشف الگوهای نوظهور را بصورت موثری با کمک تست آماری کای مربع[71] هدایت می کند.
3. برای اینکه استخراج الگوهای نوظهور بصورت کارایی انجام پذیرد، الگوهای نوظهور از هر کلاس در زمان یکسانی بصورت موازی استخراج می شوند. DFP-SEPSF قادر است تا فرآیند استخراج الگوها از کلاس های مختلف را بدون انجام محاسبات تکراری مدیریت کند.
4. این مطالعه کارایی الگوریتم پیشنهادی را بطور کامل بررسی می کند. آزمایشات گسترده ای بر روی داده های وسیعی که شامل 24 مجموعه داده از مجموعه داده های UCI [52] و 6 مجموعه داده با ابعاد بسیار بالا صورت گرفته است. در این آزمایشات، روش پیشنهادی با دیگر روش های شناخته شده در رابطه با دقت کلاسه بندی، شمار الگوها، و زمان یادگیری مقایسه شده اند.
5. حداقل آستانه فراوانی نسبی در طول فرآیند استخراج بر اساس طول الگوهای کاندید برای هر مجموعه داده بصورت جداگانه تنظیم می شود تا کارایی DFP-SEPSF به نرخ آستانه خاصی وابستگی نداشته باشد. بعلاوه، تحلیل حساسیت آزمایشات بر روی آستانه های مختلف نرخ رشد نشان می دهد که کارایی روش پیشنهادی به نرخ رشد خاصی وابسته نیست.
در فرآیند ساخت درخت الگوی مکرر دینامیک، تعدادی محدودیت مانند حداقل آستانه فراوانی نسبی، الگوی نوظهور کمینه، و الگوی نوظهور بی ربط اعمال می شود تا فضای جستجوی الگوهای نوظهور به محض ورود ویژگی جدید هرس شود. اگر یک مقدار ویژگی محدودیت های ذکر شده را ارضا نکند، در ساختار درخت قرار داده می شود. درخت الگوی مکرر با دریافت یکی به یک ویژگی ها بتدریج ساخته می شود. برای ساخت درخت الگوی مکرر مرتب، موقعیت گره ها در درخت تغییر داده می شود تا درخت بازسازی شود. بعد از پردازش همه ویژگی ها، روش استخراج الگوها، SEP-Miner، الگوهای نوظهور با قابلیت پیش بینی قوی را از درخت الگوی مکرر استخراج می کند. روش پیشنهادی ما، در دو مرحله قابل اجرا است، اول،پایگاه داده شرطی[72] با کمک اعمال محدودیت هایی هرس می شود، دوم، پایگاه داده شرطی کاهش یافته به چندین پایگاه داده کوچکتر با کمک تست کای مربع[73]، تجزیه می شود. سپس به ازای هر زیر پایگاه داده شرطی[74] یک درخت الگوی مکرر شرطی[75] ایجاد می شود. این فرآیند مکرر اجرا می شود تا ضابطه توقف ارضا شود.
نگاهی کلی به فصول رسالهاین رساله به شش فصل تقسیم شده است. در فصل دوم، به بررسی روشها و الگوریتمهای مرسوم در استخراج الگوهای نوظهور و کلاسه بندی آنها می پردازد. در فصل سوم، دانش اولیه درباره الگوهای نوظهور و درخت های الگوی مکرر در قالب تعاریف بیان می شود. در فصل چهارم، جزئیات روشهای پیشنهادی به تفصیل ارائه میشوند. در فصل پنجم، کلاسهبندها، معیارهای ارزیابی عملکرد، مجموعه دادههای مورد آزمایش و همچنین تست آماری مورد استفاده برای مقایسه نتایج الگوریتمهای پیشنهادی با سایر روشها به تفصیل توضیح داده میشوند. در فصل ششم، نتایج حاصل از بررسی و مقایسه الگوریتمهای پیشنهادی و پاسخ سؤال‌های مطرح‌شده در فصل قبل، گردآوری‌شده است. همچنین در فصل آخر نتیجهگیری و کارهای آینده این رساله آمده است.
فصل دومپیشینهی تحقیق
پیشینهی تحقیقمقدمهدر این فصل در ابتدا به روش هایی که از الگوهای مکرر[76] در راستای کلاسه بندی بهره می گیرند، می پردازیم و سپس روش های استخراج الگوهای نوظهور و کلاسه بندهای مرتبط با این الگوها بازنگری می کنیم.
روش های مبتنی بر قانون[77]
هدف از کلاسه بندی قوانین استخراجی، استخراج کردن مجموعه کوچکی از قوانین است تا یک کلاسه بند دقیق ساخته شود. الگوریتم های استخراج قانون مانند Apriori [61] و FPgrowth [15، 16] بکار گرفته می شوند تا مجموعه کاملی از الگوها استخراج شوند. سپس مجموعه کوچکی از قوانین با کیفیت بالا انتخاب می شوند که برای کلاسه بندی بکار می روند. الگوریتم های شناخته شده برای کلاسه بند های انجمنی[78] شامل CBA، CMAR و CPAR می شوند که جزئیات این الگوریتم ها در ادامه بیان خواهند شد.
روش Classification Based on Association (CBA) [27]
روش CBA در دو فاز اجرا می شود: تولید کننده قانون[79] و سازنده کلاسه بند[80]. تولید کننده قانون، الگوریتم Appriori را بکار می گیرد تا همه قوانینی با حداقل آستانه[81] فراوانی نسبی[82] و درجه اطمینان[83] را استخراج کند. برای کلاسه بندی کردن یک نمونه تست، سازنده کلاسه بند، قوانین را بر اساس مقادیر فراوانی نسبی و درجه اطمینانشان مرتب می کند. سپس، سازنده کلاس، اولین قانون را بعنوان بهترین قانون انتخاب می کند تا بر چسب کلاس را به نمونه تست اختصاص دهد. بدلیل اینکه CBA کلاسه بندی را بر اساس فقط یک قانون برای یک نمونه تست انجام می دهد، ممکن است باعث بروز مشکل بیش یادگیر[84] شود.
روش کلاسه بندی Classification based on Multiple-class Association Rule (CMAR) [28]
با توجه به اینکه CBA فقط بر اساس یک قانون با درجه اطمینان و فراوانی بالا کلاسه بندی را انجام می دهد، مشکل بیش یادگیری صورت می گیرد و لذا دقت کلاسه بند برای نمونه های تست کم خواهد شد. برای حل این مشکل، CMAR کلاسه بندی را بر اساس چندین قانون انجام می دهد. CMAR، درخت الگوی مکرر[85] را توسعه می دهد بطوری که بتواند الگوهای مکرر[86] را بصورت کارایی استخراج کند. CMAR چندین قانون را با استفاده از وزن دهی بر اساس χ برای کلاسه بندی بکار می گیرد.
روش کلاسه بندیClassification based on Predictive Association Rule (CPAR) [29]
CPAR با الهام از الگوریتم FOIL [62] قوانین را تولید می کند. CPAR، مجموعه بسیار کوچکی از قوانین با قابلیت پیش بینی را با استفاده از الگوریتم حریصانه بطور مستقیم از مجموعه آموزشی استخراج می کند. برای جلوگیری از بیش یادگیری، CPAR بهترین k قانون را جهت کلاسه بندی کردن نمونه تست بکار می گیرد. CPAR در مقایسه با دیگر الگوریتم های استخراج قوانین دارای مزایایی بدین شرح است: 1) مجوعه خیلی کوچکتری از قوانین با کیفیت بالا بطور مستقیم از نمونه های آموزشی[87] استخراج می کند. 2) برای پرهیز از تولید قوانین تکراری، CPAR هر قانون را با توجه به مجموعه قوانینی که از قبل استخراج کرده است، تولید می کند. 3) برای کلاسه بندی، بهترین k قانون بکار گرفته می شود.
روشهای استخراج الگوها
در مقایسه با قوانین انجمنی، الگوهای نوظهور قادر هستند که تمایلات نوظهور[88] در مجموعه داده های با محدودیت زمانی[89] را استخراج کنند و یا تمایزات مفید بین کلاس های مختلف را کشف نمایند [1]. مطالعه و پژوهش در رابطه با الگوهای نوظهور اساسا به دو دسته قابل تقسیم است؛ الگوریتم های استخراج الگوهای نوظهور و الگوریتم های کلاسه بندی بر پایه این الگوها. ما در ابتدا الگوریتم های مرتبط با استخراج الگوهای نوظهور را شرح می دهیم و سپس الگوریتم های مشهور کلاسه بندی را ارائه می دهیم.
روش مبتنی بر مرز[90]
روش های مبتنی بر مرز با الهام از الگوریتم Max-miner [14] پیشنهاد شده اند. این روش ها، مفهوم مرز[91] [1] را بکار می گیرد تا ساختار مناسبی را برای نمایش مختصری برای الگوهای کاندید ارائه دهند. در هر مرز، کوچکترین و بزرگترین عضو هر مجموعه کاندید قابل نمایش است. الگوریتم اختلاف مرز[92]، الگوهای نوظهور کمینه و بیشینه[93] را استخراج می کند و بدین ترتیب مرز الگوهای استخراجی را تنظیم می کند. الگوریتم های مبتنی بر مرز قادر نیستند که الگوهای نوظهور را بصورت همزمان از کلاس های مختلف استخراج کنند. این الگوریتم ها، برای هر کلاس طی فرآیند جداگانه ای الگوها را استخراج می کنند و لذا به ازای هر کلاس، جداگانه اجرا می شود.
روش مبتنی بر محدودیت (ConsEPMiner[94]) [2]
الگوریتم مبتنی بر محدودیت در دو سطح اجرا می شود؛ تولید الگوهای کاندید و هرس الگوهای اکتشافی. الگوریتم ConsEPMiner از دو نوع محدودیت استفاده می کند تا بتواند بطور موثری فضای جستجو الگوهای نوظهور را هرس کند و محاسبات را ذخیره نماید. محدودیت های ذاتی[95] و خارجی[96] عنوان محدودیت هایی است که در فرآیند استخراج اعمال می شود. محدودیت های خارجی شامل محدودیت حداقل آستانه فراوانی نسبی، نرخ رشد و پیشرفت نرخ رشد[97] است که توسط کاربر قابل تنظیم است. محدودیت ذاتی شامل مجوعه یکسانی از فراوانی نسبی[98]، نرخ رشد بالا[99] و مبدا یکسان[100] است.
الگوریتم استخراج درخت الگوی تقابل[101] (CP-Tree) [17، 25]
الگوریتم استخراج الگوهای متمایز، با الهام از FP-tree، ساختار گسترش یافته ای ساختار درختی پیشوندی ارائه می دهد. این ساختار به خلاف الگوریتم درخت الگوی مکرر، نیازی به پیوند بین نودها ندارد. الگوریتم توسط جستجوی اول عمقی[102]، CP-tree را از ریشه پیمایش می کند تا الگوهای نوظهور جهشی قوی[103] را استخراج کند. الگوی نوظهور جهشی قوی، یک نوع خاص از الگوهای نوظهور جهشی[104] است که بایستی دارای حداقل فراونی نسبی باشد. این نوع درخت، کارایی استخراج الگوهای نوظهور را با استفاده از الگوهای نوظهور جهشی قوی بهبود می بخشد و همچنین قادر است که مجموعه داده های چند کلاسه را مدیریت نماید.
روش استخراج با کمک دیاگرام دودیی صفر[105] ZBDD Miner [18]
از آنجایی اینکه روش های ذکر شده، قادر نیستند که داده ها با ابعاد بیشتر از شصت را مدیریت کنند، بعداً، ZBDD EP-Miner شد. این روش از Zero-Suppressed Binary Decision Diagrams (ZBDDs) استفاده می کند تا الگوهای نوظهور را از داده ها با ابعاد بالا استخراج کند. با این وجود، ZBDD EP-miner هنوز شمار زیادی از الگوهای نوظهور را استخراج می کند حتی با اعمال محدودیت های آلفا و بتا [18].
این محدودیت ها استفاده می شوند تا فضای جستجوی الگوهای نوظهور را بیشتر هرس کند. محدودیت آلفا بر اساس مفهوم a-priori است. در نمونه های مثبت[106]، هر آیتم که فراوانی نسبی اش[107] کمتر از مقدار آلفا باشد، هم از نمونه های مثبت و هم از نمونه های منفی حذف می شود. محدودیت بتا بیشترین مقدار فراوانی[108] برای یک الگوریتم در نمونه های منفی مشخص می کند؛ اگر فراوانی الگوی کاندید بیشتر از بتا باشد، آن الگو از نمونه های آموزشی حذف می شود.
روش استخراج الگوی نوظهور متمایز [109]DP Miner
بر اساس مفهوم مجموعه آیتم بسته[110]، یک کلاس هم ارزی[111] مجموعه ای از آیتم های مکرر[112] است که همیشه در نمونه های یکسانی از نمونه های آموزشی اتفاق می افتند. مشابه با مفهوم مرز در الگوریتم های مبتنی بر مرز، یک کلاس هم ارزی بوسیله الگوهای بسته[113] و تولیدکننده ها[114] تعیین می شود. الگوهای بسته، همان مجموعه آیتم های ماکزیمال هستند و تولیدکننده ها، همان مجموعه آیتم های کمینه در یک کلاس هم ارزی هستند که همه این آیتم ها دارای فراوانی یکسانی هستند. الگوریتم DPMiner، Discriminative Pattern Miner، الگوهای بسته و تولیدکننده ها را که برای نمایش یک کلاس هم ارزی کافی هستند، بصورت همزمان استخراج می کند. بعلاوه، قادر است که الگوهای با قدرت تمایز دلتا[115] را استخراج کند. الگوهای نوظهور با قدرت تمایز دلتا دارای حداکثر فراوانی در کلاس های مقابل است. با توجه به اینکه الگوریتم های ZBDD EP-miner و DPMiner، محدودیت های آلفا و بتا را بکار می گیرند تا فضای جستجوی الگوها را کاهش دهند؛ ممکن است بعضی از الگوهای نوظهور مفید در نظر گرفته نشوند و تاثیر نامطلوبی در کلاسه بندی داشته باشد.

روش های کلاسه بندی مبتنی بر الگوهای نوظهور
روش کلاسه بندی بر اساس مجموع الگوهای نوظهور CAEP[116][21]
از آنجایی که الگوهای نوظهور، دانش تمایز بین کلاس های مختلف را نشان می دهد، آنها در ایجاد کلاسه بندی دقیق بسیار موثر هستند. کلاسه بند های بر پایه الگوهای نوظهور قدرت مجموع الگوهای نوظهور را برای کلاسه بندی یک نمونه تست بکار می گیرد. Dong [21] اولین کلاسه بند بر پایه الگوهای نوظهور را ارائه داد که CAEP، Classification by Aggregating Emerging Patterns، نامیده شد. CAEP همه الگوهای نوظهور قوی را بوسیله الگوریتم های مبتنی بر مرز استخراج می کند. برای کلاسه بندی کردن یک نمونه تست، برای هر کلاس یک امتیاز[117] محاسبه می شود. کلاس با بالاترین امتیاز بعنوان برچسب نمونه تست در نظر گرفته می شود. اگر تعداد الگوهای کاندید کلاس های مختلف نامتوازن[118] باشد، کلاس با الگوهای بیشتر تمایل در بدست آوردن امتیاز بیشتر دارد. برای حل این مشکل، یک امتیاز پایه[119] برای هر کلاس از نمونه های آموزشی بدست می آید [21].
الگوریتم کلاسه بندی بر پایه تئوری اطلاعات[120] iCAEP
بعداً، Zhang et al. [26]، یک نوع از CAEP را که iCAEP، Information based Classification by Aggregating Emerging Patterns، نامیده شد، معرفی کرد. iCAEP، از تئوری اطلاعات[121] استفاده می کند تا نیازی به محاسبه base score برای هر کلاس نباشد.
برای کلاسه بندی یک نمونه تست، کوچکترین امتیاز بعنوان برچسب کلاس نمونه تست در نظر گرفته می شود. در مقایسه با CAEP، iCAEP دقت را بهبود می دهد و زمان را برای کلاسه بندی کاهش می دهد.
روش کلاسه بندی برپایه الگوهای نوظهور جهشیJEPs-Classifier [3]
بر اساس CAEP، الگوریتم کلاسه بند بر پایه الگوهای نوظهور جهشی توسط Li et al. ارائه شد. JEPs-classifier محنصراً از الگوهای نوظهور جهشی[122] با فراوانی نسبی بالا برای کلاسه بندی استفاده می کند. این نوع الگوها، رساترین الگوهای نوظهور جهشی[123] نامیده می شوند چرا که این الگوها همان محموعه آیتم های کمینه در مرز[124] هستند که دارای فراوان نسبی بالایی نسبت به دیگر آیتم ها در مرز هستند. JEPs-classifier از الگوریتم های مبتنی بر مرز بهره گرفته و الگوهای نوظهور جهشی را در قالب مرز فضای الگوها استخراج می کند. رساترین الگوهای نوظهور جهشی لزوما حداقل آستانه برای فراوانی نسبی ارضا نمی کند.
روش کلاسه بندی بر پایه الگوهای نوظهور جهشی قوی[125] [25]
این کلاسه بندی بر پایه قدرت مجموع الگوهای نوظهور جهشی قوی است و تلاش می کند تا با استفاده از الگوهای نوظهوری جهشی که حداقل آستانه را برای فراوانی نسبی دارا هستند، به دقت قابل توجهی دست یابد.
روش تصمیم گیری مبتنی بر نمونه[126] DeEPs [20]
بعداً، بر پایه روش های مبتنی بر نمونه[127]، کلاسه بند تنبل[128] به نام DeEPs، Decision-making by Emerging Patterns، ارائه شد [20]. جهت کاهش فضای جستجو الگوها، DeEPs یک نمونه تست را بعنوان یک فیلتر بکار می گیرد تا مقادیر آموزشی بی ربط را در نظر نگیرد. برای هر نمونه تست، DeEPs الگوهای نوظهور کاندید را استخراج می کند و مقادیر ویژگی هایی که در نمونه تست دیده نشده اند را نادیده می گیرد. این تکنیک، کارایی و دقت کلاسه بندی هایی مثل کلاسه بندی بر پایه مجموع الگوهای نوظهور CAEP و کلاسه بندی بر پایه الگوهای نوظهور جهشی JEP-classifier را بهبود می بخشد. اما، این روش منجر به تکرار محاسبات سنگین می شود بخصوص وقتی که نمونه های تست مشابه باشند.
روش پیش بینی توسط مجموعه راست نمایی (PCL[129]) [5]
PCL پیش بینی را توسط مجموعه ای از درست نمایی ها[130] انجام می دهد. PCL از K بالاترین الگوهای نوظهور که در نمونه تست شامل می شوند، برای کلاسه بندی استفاده می کند. برای هر کلاس، PCL یک امتیاز با استفاده از اجتماع درست نمایی حاصل از K بالاترین الگوهای نوظهور که نمونه تست را پوشش می دهند، بدست می آورد. PCL برای مجموعه داده ها با ابعاد بالا مناسب است بخصوص برای داده های بیان ژن.
بدلیل محدودیت های روش های استخراج الگوهای نوظهور، روش های سابق قادر نیستند تا مجموعه داده ها با ابعاد بالا را مدیریت کنند. روش پیشنهادی ما، DFP-SEPSF، فضای جستجوی الگوهای نوظهور را با استفاده از فرایند هرس در روال ساخت درخت الگوی مکرر دینامیک و استخراج الگوها، بطور قابل توجهی کاهش می دهد. همچنین روش پیشنهادی، الگوهای نوظهور هر کلاس را در زمان یکسانی و بطور موازی از کلاس ها استخراج می کند.
فصل سوم
دانش اولیه

دانش اولیه
الگوهای نوظهور
فرض کنید مجموعه داده D دارای N ویژگی (F1,F2, . . . ,FN) و برچسب کلاس C است. هر کدام از ویژگی ها در صورتی که ویژگی پیوسته باشد در فواصلی مجزا می شوند.I را بعنوان مجموعه ای از همه آیتم ها تعریف می کنیم. یک مجموعه آیتم[131] X یک زیر مجموعه از I است که مقدار فراوانی نسبی[132] آن

که |X| تعداد نمونه های شامل X را بیان می کند و |D| تعداد کل نمونه های را در مجموعه داده D را بیان می کند. مجموعه برچسب کلاس C شامل M برچسب کلاس مختلف است؛ C = {C1, C2, . . ., CM}. مجموعه داده D در M مجموعه داده D1, D2, . . ., DM تجزیه می شود که هر مجموعه داده Dk شامل نمونه ها با برچسب کلاس Ck است. به طور خاص، مجموعه داده D به دو مجموعه داده مثبت Dp و مجموعه داده منفی Dn قابل تقسیم است. Dp شامل نمونه مثبت و Dn شامل نمونه های منفی می شود. نرخ رشد[133] (GR) مجموعه آیتم X از مجموعه داده Ds به مجموعه داده Dt ( s,t =1, . . . , M) در ادامه شرح داده خواهد شد.
تعریف 1: (نرخ رشد GR) نرخ رشد یک مجموعه آیتم X از Ds به Dt،

تعریف 2: (الگوی نوظهور EP [1]) حداقل آستانه نرخ رشد داده شده است. مجموعه آیتم X گفته می شود الگوی نوظهور است اگر

تعریف 3: ( الگوی نوظهور جهشی JEP [1]) اگر ، مجموعه آیتم X الگوی نوظهور جهشی از مجموعه داده از Ds به Dt نامیده می شود.
برای اینکه تفاوت الگوهای مکرر و الگوهای نوظهور مشخص شود، در ادامه تعریف الگوهای نوظهور را بر اساس confidence ارائه می دهیم. اطمینان[134]، تخمین ماکزیمم درست نمایی مربوط به احتمال شرطی است:

کلاسه بند مبتنی بر الگوهای مکرر، استخراج قوانین انجمنی و کلاسه بندی را با یکدیگر ترکیب می کند. در این راستا، نتیجه[135] قانون انجمنی برچسب کلاس در نظر گرفته می شود و کلاسه بند بر اساس چنین الگوهای ساخته می شود. در شکل زیر
100012516446500-6457951137285شکل 3-1. یک مثال از الگوهای مکرر استخراج شده از مجموعه داده Balloon
00شکل 3-1. یک مثال از الگوهای مکرر استخراج شده از مجموعه داده Balloon

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

در صورتی که الگویی معیار اطمینان برابر یک به ازای یک کلاس به خود اختصاص دهد، این الگو، الگوی نوظهور جهشی را نشان می دهد.
تعریف 4: ( الگوی نوظهور قوی SEP) حداقل نرخ رشد و تعداد میانگین مقادیر برای یک آیتم K داده شده است. الگوهای نوظهور قوی از مجموعه داده Ds به Dt، مجموعه آیتم X با n آیتم است که شرایط ذیل را ارضا می کند:

که شرط 1 تعریف محدودیت فراوانی دینامیک[136] است.
در الگوهای نوظهور قوی، ما محدودیت فراوانی دینامیک را بر اساس طول الگو و تعداد میانگین مقادیر K تنظیم می کنیم. ایده پشت آن اینست که الگوهای نوظهور قوی تمایل دارند تا همه ترکیبات ممکن از آیتم ها را برای یک الگو خاص در نمونه های آموزشی را پوشش دهند، از این رو، حداقل فراوانی الگو بایستی باشد. برای مثال، فرض کنید ما یک الگوی نوظهور با دو آیتم، تعداد میانگین مقادیر 3، و 20 نمونه آموزشی داریم. بنابراین، حداقل فراوانی الگو است و حداقل آستانه فراوانی نسبی است.
بعلاوه، طول الگوهای نوظهور بوسیله محدودیت فراوانی محدود می شود. طول الگو حداکثر است. فرآیند استخراج الگوهای نوظهور SEPs با طول بزرگتر از استخراج نمی کند.
کلاسه بندی بر پایه الگوهای کوتاهتر با آیتم های کمتر مطلوب است بدلیل اینکه با ویژگی های بیشتر معمولا در کلاسه بندی مشارکت نمی کنند و حتی، برای کلاسه بندی مضر است. از آنجایی که SEPs الگوهای کوتاهتر و با فراوانی بالا را نشان می دهند، برای کلاسه بندی بسیار مفید هستند.
تعریف 5: (بهبود نرخ رشد[137] Rateimp [2]) فرض کنید الگوی نوظهور e داده شده است، بهبود نرخ رشد e، Rateimp(e)، بعنوان کمترین اختلاف بین نرخ رشد e و نرخ رشد همه زیر مجموعه هایش توصیف می گردد.

برای استخراج موثر الگوهای نوظهور، Rateimp(e) فضای جستجو الگوها را هرس می کند و محاسبات اضافی را کاهش می دهد. یک آستانه مثبت از بهبود نرخ رشد،R، مجموعه مختصری از الگوها را که توسط دیگر الگوهای استخراجی قابل دستیابی نیستند، ارائه می دهد. بعلاوه، بهبود نرخ رشد می تواند در استخراج الگوهای قوی کمک کند. بنابراین، بهبود نرخ رشد ارتباط و وابستگی بین الگوهای نوظهور را نشان می دهد و الگوهای تکراری را کاهش می دهد.
یک مثال مصور در جدول 3-1 با استفاده از مجموعه داده mushroom از مجموعه داده های جمع آوری شده در UCI [52] ارائه شده است. حداقل آستانه فراوانی 0.05 و حداقل آستانه نرخ رشد است. الگوهای کاندید از دو کلاس Edible و Poisonous با 8124 نمونه و 22 ویژگی استخراج شده اند.
بر اساس تعریف 2، در جدول 3-1، آیتم های {odor = almond}، {stalk-color = white}، {odor = almond, stalk-color = white} الگوهای نوظهور از کلاس Edible هستند. بعلاوه، {odor = almond} و همچنین {odor = almond, stalk-color = white} الگوهای نوظهور جهشی هستند. بر اساس تعریف 3، آیتم ، {odor = almond} یک الگوی نوظهور است اما {odor = almond, stalk-color = white} یک الگوی نوظهور تکراری[138] است. در حقیقت، همه سوپرست های آیتم با نرخ رشد بینهایت، الگوی نوظهور جهشی هستند. واضح است که بهبود نرخ رشد صفر است.
فراوانی نسبی
(کلاس Poisonous) فراوانی نسبی
(کلاس Edible) الگوهای نوظهور کاندید
0.0951 0 {odor = almond}
1.4959 0.6540 0.4372 {stalk-color = white}
0.0951 0 {odor = almond, stalk-color = white }
جدول 3-1. الگوهای نوظهور کاندید از کلاس Poisonous به کلاس Edible
در کلاسه بندی بر پایه الگوهای نوظهور، همه الگوهای هر کلاس Ci، کلاس iام، از نمونه های آموزشی استخراج می شوند و برای تصمیم گیری در مورد برچسب کلاس نمونه های تست بکار گرفته می شوند. برای کلاسه بندی کردن یک نمونه تست t، M امتیاز محاسبه می شود، بطوری که برای هر کلاس یک امتیاز محاسبه می شود. کلاس با بالاترین امتیاز بعنوان برچسب کلاس برای t در نظر گرفته می شود، label(t) = argmaxci score (t, Ci). تعریفی که در ادامه آمده است، امتیاز مجموع[139] را بعنوان تابع امتیازدهی[140] ارائه می دهد.
تعریف 6: (جمع آوری امتیاز[141] [21]) نمونه تست t و مجموعه الگوهای نوظهور Ei که از کلاس Ci از نمونه های آموزشی استخراج شده اند، داده شده اند. مجموع امتیاز برای t به ازای کلاس Ci بدین شرح تعریف می شود:

بدلیل اینکه تعداد الگوهای نوظهور از کلاس های مختلف ممکن است نامتوازن باشد، نمونه تست t ممکن امتیاز بالاتری برای کلاس Ci با الگوهای بیشتر از دیگر کلاس Cj بدست آورد، حتی اگر برچسب کلاس t کلاس Cj باشد. بنابراین، تابع امتیاز که توسط تعریف 4 معرفی شده است، بایستی جهت کلاسه بندی نمونه تست t تغییر داده شود.
مفهوم امتیاز پایه[142] [21] می تواند کمک کند تا این مشکل حل شود. امتیاز پایه، baseScore(Ci)، از نمونه های آموزشی هر کلاس بدست می آید. با امتیاز پایه، امتیاز جدید یک نمونه تست t برای کلاس Ci که امتیاز نُرم شده، normScore(t, Ci)، نامیده می شود، بصورت نسبت امتیاز Score(t, Ci) و امتیاز پایه baseScore(Ci) تعریف می شود،

کلاس با بیشترین امتیاز نُرم شده بعنوان برچسب کلاس نمونه تست t در نظر گرفته می شود و در صورتی که امتیازات بدست آمده از کلاس های مختلف برابر شد، کلاس با بزرگترین نمونه بعنوان برچسب کلاس در نظر گرفته می شود. یک راه برای مشخص کردن امتیاز پایه این است که میانه امتیازات بدست آمده از نمونه های آموزشی کلاس Ci در نظر گرفته شود. برای مثال، فرض کنید 5 نمونه آموزشی از هر کدام از کلاس های مثبت (+) و منفی (-) وجود دارد. با همه EPs موجود از هر کلاس، فرض کنید که امتیازات حاصل از نمونه های مثبت[143] که بوسیله تعریف 4 محاسبه شده اند 17.85، 18.61، 18.76، 19.75، 20.24 هستند و امتیازات حاصل از نمونه های آموزشی منفی 7.80، 7.87، 8.20، 8.57، 8.61 هستند. در صورتی که امتیازات پایه را میانه امتیازات محاسبه شده به ازای هر کلاس در نظر بگیریم، در نتیجه، امتیاز پایه برای کلاس های مثبت و منفی به ترتیب 18.76 و 8.20 می شود. به ازای یک نمونه تست t ( می دانیم که از کلاس منفی است) با امتیازات 10.17 و 7.92 به ترتیب برای کلاس های مثبت ومنفی داده شده است؛ در صورتی که امتیاز پایه اعمال نشود، کلاس مثبت بعنوان برچسب نمونه t در نظر گرفته می شود. در حالیکه با اعمال امتیازات پایه، normScore(t, +) = 10.17/18.76 =0.54 و normScore(t,-)= 7.92/8.2 = 0.97 . بنابراین کلاس منفی بعنوان برچسب نمونه t در نظر گرفته می شود.
بعداً، Zhang et al. [26] یک تابع امتیاز ساده تر بر اساس تئوری اطلاعات[144] ارائه دادند که از محاسبه امتیاز پایه برای هر کلاس اجتناب می کند. تابع امتیاز نمونه تست t بوسیله معادله های 1 و 2 قابل محاسبه است.
فرمول 3-1 برچسب کلاس Ci به نمونه تست t اختصاص داده می شود در صورتی که L(t||Ci) کمترین مقدار به ازای کلاس Ci داشته باشد. به ازای مجموعه آیتم X، P(X|Ci) تقریبا با معادله 2 محاسبه می شود،
فرمول 3-2
در این معادله، تعداد نمونه هایی متعلق به کلاس Ci و دارای مجموعه آیتم X ، |X| تعداد کل نمونه های آموزشی شامل X ، |D| تعداد کل نمونه های آموزشی، و |Ci| تعداد نمونه های آموزشی متعلق به کلاس Ci را نشان می دهند. بعلاوه، برای اطمینان از اینکه حداقل یک EP برای کلاسه بندی نمونه تست t یافت می شود، ما همه آیتم های تکی را جدای از آن که حداقل آستانه ها را ارضا می کنند یا خیر برای کلاسه بندی نمونه تست t در نظر می گیریم.
درخت الگوی مکرر دینامیک[145] (DFP-tree)
درخت الگوی مکرر گسترش یافته ساختارهای مبتنی بر درخت های پیشوندی[146] است [15، 16]. درخت الگوی مکرر نمایش فشرده ای از داده است که اطلاعات کاملی از داده های اصلی را در خود ذخیره می کند. در FP-tree، هر مسیر مجموعه آیتم هایی را که دارای پیشوند یکسانی هستند را نشان می دهد و هر گره[147] یک آیتم و فراوانی آن را نشان می دهد. بعلاوه، همه گره هایی که آیتم یکسانی را شامل می شوند از طریق پیوند-گره[148] به هم متصل شده اند. از طریق پیوند-گره همه نمونه هایی که دارای آیتم مشابهی هستند به آسانی قابل دستیابی و شمارش هستند. راس[149] همه پیوند-گره ها برای هر آیتم در یک جدول هدر[150] ذخیره می شوند. بعلاوه، آیتم ها در جهت کاهش فراوانی شان در داده ها مرتب می شوند و در ساختار درخت ذخیره می شوند. اگر چه FP-tree به نظم خاصی وابسته نیست ولی در حالتی که مرتب شده باشد سرعت اجرای عملیات استخراج بسیار بیشتر از حالتی است که درخت نامنظم باشد. برای نمایش الگوهای نوظهور، ما ساختار FP-tree را تغییر می دهیم همانطوری که در تعریف ادامه آمده است.
تعریف 7: (درخت الگوی مکرر دینامیک DFP-tree [15]) یک درخت الگوی مکرر دارای یک ریشه تهی[151]، مجموعه ای از زیر درخت های پیشوندی بعنوان بچه های ریشه، و یک جدول هدر توصیف شده در زیر است.
هر گره در زیردرخت دارای چهار فیلد: مشخصه ID، مقدار یا آیتم value or i–، توزیع کلاس class distribution، و پیوند-گره node-link است. ID، یک گره را از مابقی گره ها متمایز می کند، value، نشاندهنده آن است که کدام مقدار ویژگی در گره جاری ذخیره شده است، class distribution، فراوانی آیتم را به ازای هر کلاس که توسط قسمتی از شاخه ای که به گره می رسد، ثبت می کند، و node-link، گره جاری را به گره بعدی که دارای آیتم مشابهی است متصل می کند و اگر گره ای وجود ندارد null می باشد. بعلاوه، تعدادی از گره ها را بعنوان گره های خارجی[152] تعریف می شوند. دو نوع از گره ها بعنوان گره های خارجی تعریف می شوند : (1) گره های برگ[153] (2) گره های پدری[154] که مقدار فراوانی شان بزرگتر از جمع فراوانی همه گره های فرزندانشان[155] باشد.
هر ورودی در جدول هدر شامل چهار فیلد است: آیتم i–، فراوانی کل total frequency، توزیع کلاس class distribution، هد پیوند-گره head of node-link است. در این مطالعه، آیتم، مقدار ویژگی را ثبت می کند، فراوانی کل، فراوانی آیتم و مقدار ویژگی را در داده ثبت می کند، توزیع کلاس، مقدار فراوانی آیتم یا مقدار ویژگی در هر کلاس را ثبت می کند، و هد پیوند-گره یک اشاره گر اشاره کننده به اولین گره حامل آیتم است.

شکل 3-2. یک مثال از درخت الگوی مکرر: هر گره دارای یک ID، یک آیتم، توزیع کلاس آیتم که نشاندهنده قسمتی از مسیر منتهی به گره است، و پیوند-گره. هر ورودی در جدول هدر دارای یک آیتم، فراوانی کل، توزیع کلاس، و هد پیوند-گره. همه گره ها به رنگ قرمز نشان داده شده اند.
مثال 1. یک مثال از درخت الگوی مکرر در شکل 3-1 نشان داده شده است. درخت دارای یک ریشه تهی و 8 گره است.هر گره دارای یک ID، یک آیتم، فراوانی آیتم در هر دو کلاس (توزیع کلاس)، و یک گره-پیوند است. همانطوری که به تصویر کشیده شده است، گره با مشخصه[156] I5 شامل آیتم c، توزیع کلاس 0 و 3 به ترتیب برای کلاس های مثبت و منفی؛ بدین معنا که آیتم c به همراه آیتم h 3 بار در کلاس منفی ظاهر شده است (ch:0:3)، و یک گره-پیوند گره I5 را به گره I3 که دارای آیتم c هست متصل می کند. در جدول هدر، هر ورودی شامل یک آیتم، فراوانی کل، توزیع کلاس، و هد آیتم است. ورودی آیتم c دارای فراوانی کل 4، توزیع کلاس 3 و 1 در کلاس های مثبت و منفی، و یک هد است که به اولین گره (I5) که دارای آیتم c است. همه گره های برگ I4، I5، I6، I7، I8 بعنوان گره های خارجی در نظر گرفته می شوند. بعلاوه، گره I1 یک گره خارجی است بدلیل اینکه فراوانی I1 که 9 است بزرگتر از جمع فراوانی بچه هایش 8 است. همه گره های خارجی به رنگ قرمز نشان داده شده اند.
فصل چهارم
راهکارهای ارائه‌شده برای استخراج الگوهای نوظهور قوی مبتنی بر ویژگی های جریانی

Related posts:

-- (78)

-- (22)

- (214)

پایان نامه -تحقیق-پژوهش فرستاده شده.

راهبری نوشته‌ها

→ – (70)

– (83) ←

پاسخ دهید لغو پاسخ

نوشته‌های تازه

• (سایت تحقیق علمی ) دانلود رایگان پایان نامه ها- پژوهش ایرانداک
• (سایت دانلود تحقیق علمی ) [do_widget id=cool_tag_cloud-2]- دانلود تحقیق علمی ایرانداک

آخرین دیدگاه‌ها

بایگانی

• آگوست 2017
• جولای 2017

دسته‌ها

• پایان نامه -تحقیق-پژوهش

اطلاعات

• ورود
• پیگیری نوشته‌ها باRSS
• پیگیری دیدگاه‌ها با RSS
• WordPress.org