سمینار ارشد و کارشناسی با موضوع داده کاوی و کاربرد آن
ارائه دهنده :
2
فهرست مطالب
مقدمه
معرفی داده کاوی و دلایل پیدایش آن
جایگاه داده کاوی در علوم کامپیوتر
مراحل و اجزای یک فرآیند داده کاوی
کاربردهای داده کاوی
کاربردهای تجاری
کاربردهای علمی
کاربردهای امنیتی
تکنیکهای داده کاوی
دسته بندی
قوانین تداعی
خوشه بندی
آینده داده کاوی: کاربردهای جدید، چالشها و دستاوردها
تشخیص ناهمگونی
داده کاوی توزیع شده
داده کاوی و حریم خصوصی
3
داده کاوی و دلایل پیدایش آن
توسعه تکنولوژیهای ذخیره و بازیابی اطلاعات
افزایش روزافزون حجم اطلاعات ذخیره شده
تنوع بسیار زیاد در اطلاعات موجود
بانکهای اطلاعاتی
فایلهای چندرسانه ای (تصاویر متحرک، فایلهای صوتی)
اطلاعات متنی و فاقد ساختار
آرشیوهای اطلاعاتی، به دلیل حجم بسیار زیاد، غالبا به مقبره های اطلاعات تبدیل می شوند.
علیرغم هزینه های سنگین در بخش تکنولوژی اطلاعات، بسیاری از تصمیمها همچنان در فقر اطلاعاتی اتخاذ می گردند.
از قابلیتهای بالقوه اطلاعات ذخیره شده استفاده نمی شود.
نیاز به تبدیل اطلاعات به دانش در بسیاری زمینه ها آشکار گردیده است.
وقایعی نظیر 11 سپتامبر، لزوم خودکار یا حداقل نیمه خودکار بودن فرآیند تبدیل اطلاعات به دانش را به خوبی نشان می دهند.
داده کاوی به دهه 80 برمی گردد.
داده کاوی با تلاش برای اعمال تکنیکهای هوش مصنوعی بر روی بانکهای اطلاعاتی آغاز گردید.
4
پردازش اطلاعات: از فایلهای متنی تا داده کاوی
حرکت از روشهای ابتدائی پردازش اطلاعات به داده کاوی، همواره برحسب نیاز حوزه های مختلف بوده است.
سیر کلی تکنولوژی پردازش اطلاعات را می توان به صورت زیر خلاصه کرد:
فایلها: اطلاعات ناهمگون، فاقد ساختار مشخص، اشتباهات متعدد، پردازش در حد تهیه فهرست
بانکهای اطلاعاتی خاص: اطلاعات ناهمگون، اشتباهات نسبتا کمتر، گزارشات آماری ساده
بانکهای اطلاعاتی رابطه ای: اطلاعات همگون، ارتباطات مشخص، اشتباهات کمتر، گزارشات آماری پیچیده و مقایسه ای و شامل ارتباطات عناصر مختلف
بانکهای اطلاعاتی تحلیلی: ویژه تحلیل اطلاعات، ارائه یک مدل چندوجهی و امکان ساخت و مشاهده سریع گزارشات خاص، توانائی محدود در ذخیره سازی و پردازش انواع اطلاعات (معمولا فقط اطلاعات عددی)
داده کاوی: امکان پردازش انواع اطلاعات، قابلیت کشف دانش از اطلاعات موجود
5
یک تعریف تئوریک از داده کاوی
داده کاوی عبارت است از فرآیند (نیمه)خودکار استخراج دانش (در قالب الگوهای پنهان) از مجموعه اطلاعات ورودی.
معمولا آگاهی اندکی در مورد دانش هدف وجود دارد.
ورودی عمدتا بسیار حجیم و پردازش دستی آن ناممکن است.
نتایج حاصل از داده کاوی، با روشهای سنتی پردازش اطلاعات (گزارش گیری) قابل دستیابی نیست.
خودکار یا نیمه خودکار بودن داده کاوی به معنای حداقل نیاز به دخالت کاربر است.
انواع اطلاعات (و نه صرفا اطلاعات عددی) قابل پردازش می باشند.
6
جایگاه داده کاوی
داده کاوی را می توان یک شاخه از یادگیری ماشین دانست.
به دلیل عدم وجود یک چارچوب تئوریک برای داده کاوی، در نظر گرفتن آن به عنوان زیر مجموعه ای از یادگیری ماشین می تواند مورد بحث قرار گیرد.
تلاشهای اندکی برای توسعه یک چارچوب تئوریک برای داده کاوی انجام گرفته است.
این میزان تلاش کافی نبوده و به نتیجه قابل قبولی نرسیده است.
تفسیر داده کاوی به عنوان زیر مجموعه ای از آمار، چندان قانع کننده نیست: مسائل با فضای حالت دارای ابعاد زیاد مهمترین وجه این تمایزند.
تفسیر داده کاوی به عنوان فرآیندی جهت تخمین تابع توزیع احتمال توام نمونه ها: تکراری بودن داده کاوی چنین طبقه بندی را رد می کند.
نظریه داده کاوی معادل فشرده سازی، داده کاوی را فرآیندی برای فشرده سازی اطلاعات ورودی، از طریق پیدا کردن یک ساختار مناسب برای آن در نظر می گیرد.
7
چند واقعیت
تعریف موجود، سبب ایجاد انتظاراتی غیرواقعی از داده کاوی می شود.
تا کنون، هیچ سیستم/فرآیند داده کاوی کاملا خودکاری که منطبق بر شرایط واقعی باشد، ساخته نشده است.
دخالت مستقیم کاربر، به خصوص در مراحل اولیه یک فرآیند داده کاوی، اجتناب ناپذیر است.
داده کاوی به یک هیولای پرقدرت شبیه است: رها کردن بدون هدف آن در سرزمین اطلاعات، مطمئنا نتایج خوبی در پی نخواهد داشت.
تمام قدمهای یک فرآیند داده کاوی توسط انسان تعریف می شود.
چند مرحله کلی در هر فرآیند داده کاوی وجود دارد.
8
مراحل یک فرآیند داده کاوی
هریک از مراحل، با مشکلات خاص خود مواجه است.
پیرایش و تجمیع اطلاعات، معمولا حجم عمده کار را به خود اختصاص می دهند.
بازنمائی دانش، به خصوص در مورد داده کاوی، در موارد متعددی هیچ راه حل قابل قبولی ندارد.
انتخاب
اطلاعات هدف
پیرایش
اطلاعات
تجمیع
اطلاعات
استخراج
دانش
بازنمائی دانش
استخراج شده
تفسیر نتایج
9
پایه های یک فرآیند داده کاوی
5 پایه اصلی
مجموعه نمونه های آموزشی: باید انتخاب، جمع آوری و پیرایش شوند.
نوع دانش: نوع دانش مورد انتظار، تکنیک داده کاوی مورد استفاده را مشخص خواهد کرد.
دانش پایه: انتقال دانش موجود در مورد مسئله به فرآیند داده کاوی، غالبا به صورت سلسله مراتبی از مفاهیم
معیارهای ارزیابی: ملاکهای ارزش دانش حاصل از داده کاوی، چه در زمان استخراج دانش و چه در زمان بازنمائی از اهمیت کلیدی برخوردار بوده و راهنمای فرآیند داده کاوی خواهند بود.
نحوه ارائه: معمولا بر حسب نوع دانش استخراج شده تعیین می شود. در موارد متعددی نیز روش مناسبی برای بازنمائی وجود ندارد.
10
دانش پایه
دانش فعلی کاربر در مورد نمونه های آموزشی
غالبا به صورت سلسله مراتب مفهومی (Concept Hierarchy)
به صورت ترتیب جزئی بین سطوح تجرد مطرح می شود
مثال: کشور > استان > شهر > منطقه
11
مقدمه: خلاصه مطالب
عدم کفایت روشهای سنتی در بهره برداری از پتانسیل اطلاعات در دسترس.
سیر کلی روشهای پردازش اطلاعات، بر حسب نیاز حوزه های متفاوت، از فایلهای ساده تا داده کاوی.
تعریف داده کاوی به عنوان یک فرآیند نیمه خودکار برای استخراج دانش از انواع اطلاعات ذخیره شده.
جایگاه داده کاوی در یادگیری ماشین و نیاز به چارچوبهای تئوریک و فراگیر.
ابهام زدائی از تعریف موجود و جداکردن واقعیات از اهداف ایده آل و بلند مدت.
مراحل اصلی یک فرآیند داده کاوی عبارتند از: انتخاب، پیرایش و تجمیع اطلاعات، استخراج دانش، بازنمائی و تفسیر دانش حاصل.
پایه های اصلی یک فرآیند داده کاوی عبارتند از: اطلاعات ورودی، نوع دانش، دانش پایه، معیارهای ارزیابی دانش و روشهای بازنمائی آن.
12
کاربردهای داده کاوی
کاربردهای تجاری
کاربردهای علمی
کاربردهای امنیتی
13
کاربردهای تجاری
تقریبا در تمام سازمانها و انواع تجارتها، به دلیل وجود اطلاعات، می توان داده کاوی را مورد استفاده قرار داد.
پیش بینی مربوط به بازار بورس
تحلیل سبد خرید
شناسائی طبقات و گروههای اصلی مشتریان
تعیین میزان تاثیر عوامل مختلفی نظیر تبلیغات، تخفیف، … بر میزان و الگوهای فروش
14
کاربردهای علمی
اطلاعات جمع آوری شده در حوزه های مختلف: اطلاعات جغرافیائی، اطلاعات اقلیمی، اطلاعات پزشکی
حجم بسیار بالا و خصایص متعدد
تنوع اطلاعات
نویز شدید در غالب اطلاعات جمع آوری شده توسط سنسورها
نیاز مبرم به تکنیکهای داده کاوی، حداقل جهت ایجاد امکان تصور اطلاعات برای متخصصان
15
کاربردهای علمی (ادامه)
حوزه پزشکی:
تشخیص بیماریها براساس انواع اطلاعات (تصاویر پزشکی، مشخصات بیمار احتمالی)
تشخیص ناهنجاریهائی که توسط انسان به سختی قابل تشخیص خواهند بود (لکه ها و نقاط خاص داخل چشم که نشانه شروع کوری ناشی از دیابت می باشد)
حوزه اطلاعات جغرافیائی و اقلیمی
کشف پدیده های اقلیمی جدید
تکنیکهای بصری سازی و بازنمائی اطلاعات
پردازش انواع اطلاعات (تصاویر، اطلاعات به دست آمده از سنجنده ها)
16
مثالی از کاربردهای داده کاوی: اطلاعات ژنتیک (1)
آرایه ای از نمونه های DNA
انجام تعدادی آزمایش بر روی یک تراشه
17
مثالی از کاربردهای داده کاوی: اطلاعات ژنتیک (2)
معیار شباهت ژن ها: رفتار مشابه در آزمایش ها
18
کاربردهای علمی (ادامه)
حوزه کاربردی فضا و سفرهای فضائی
حجم بسیار زیادی از اطلاعات
نویز بسیار بالا
ارزش بسیار زیاد دانش قابل استخراج
پردازش اطلاعات جمع آوری شده از فضا
پردازش اطلاعات مربوط به سفینه های فضائی
ارائه دانش مفید برای اتخاذ تصمیم نهائی جهت پرتاب یا عدم پرتاب یک سفینه به فضا
19
کاربردهای امنیتی
سیستمهای تشخیص نفوذ
روشهای سنتی، نظیر تشخیص حملات با استفاده از قوانین ارائه شده توسط متخصصان، علاوه بر نیاز به اصلاح دائم، برای مقابله با انواع جدید حملات کافی نیستند.
حجم اطلاعات بسیار زیاد و فضای حالت غیرقابل تصور
عدم امکان بررسی تمام گزارشهای فعالیت توسط متخصصان شبکه
نیاز به شناسائی خودکار الگوهای جدید و مشکوک به تلاش برای نفوذ
لزوم همکاری با متخصصان شبکه، از طریق خلاصه سازی وضعیت موجود و درخواست نظر متخصص در موارد مشکوک
لزوم اجتناب از سیستمهای بسیار بدبین که موجب بی اعتنایی متخصصان به هشدارهای سیستم خواهد شد.
مقابله با تروریسم
در سالهای اخیر، به خصوص پس از واقعه 11 سپتامبر، به صورت فزاینده ای مطرح شده است.
به دلیل عدم امکان انتشار تمامی اطلاعات مفید، پیشرفت کندتری (حداقل از نظر افراد عادی) دارد.
در حالت ایده آل، داده کاوی باید بتواند با پردازش اطلاعات از انواع مختلف، نسبت به احتمال وقوع حملات تروریستی، با ذکر جزئیات کافی، هشدار دهد.
نتایج حاصل از آن می تواند در صورت عدم وجود دقت کافی، فاجعه آمیز باشد.
20
کاربردهای داده کاوی: جمع بندی
حوزه های اصلی شامل کاربردهای علمی، تجاری و امنیتی می باشد.
در تمام حوزه ها با حجم بسیار زیاد اطلاعات و خصایص متعدد مواجهیم.
در تمام حوزه ها با انواع اطلاعات مفید روبرو هستیم.
کاهش شدید هزینه ها، افزایش درآمدها و نجات زندگی انسانها از دستاوردهای داده کاوی در هریک از حوزه های کاربردی آن است.
کاربردهای تجاری: تشخیص صحت ادعای خسارت در بیمه، تشخیص سوء استفاده از کارتهای اعتباری، تحلیل اطلاعات مشتریان یک سازمان،…
کاربردهای علمی: حوزه های پزشکی، جغرافیائی و اقلیمی، فضا و سفرهای فضائی
کاربردهای امنیتی: مبارزه با تروریسم، مقابله با نفوذگران به شبکه های کامپیوتری
21
تکنیکهای داده کاوی
دسته بندی
قوانین تداعی
یادگیری بدون نظارت: خوشه بندی
تعریف و دلایل اهمیت خوشه بندی
کاربردهای خوشه بندی
انواع خوشه بندی
مشکلات پیش روی خوشه بندی
22
دسته بندی
یادگیری تابع نگاشت ترکیب مقادیر خصایص به دسته های مختلف.
درخت تصمیم گیری، یادگیری بیزی
پس از دریافت تعدادی نمونه آموزشی، یادگیرنده باید دسته نمونه های جدید را مشخص نماید.
مثال:
یک شرکت با بیش از 100000 مشتری
یک کاتالوگ با هزینه سنگین چاپ و توزیع
لزوم ارسال انتخابی کاتالوگ (نه برای همه)
دسته بندی: با توجه به سوابق ارسال کاتالوگها و پاسخ مشتریان، چه افرادی احتمالا در گروه ”علاقه مند به محصول معرفی شده“ قرار می گیرند؟
کاهش هزینه ها
23
درخت تصمیم – ابزار دسته بندی
معمولا بر مبنای کاهش آنتروپی عمل می کند.
در هر ند، خصیصه ای که بیشترین کاهش را در آنتروپی نمونه ها ایجاد می کند، انتخاب می شود:
نمونه ها بر حسب مقدار خصیصه انتخاب شده در ند جاری، بین زیر شاخه های آن تقسیم می شوند.
هر ندی که تمام نمونه های آن از یک کلاس باشند، یک برگ است.
24
درخت تصمیم – یک مثال (1)
مجموعه نمونه های آموزشی:
25
درخت تصمیم – یک مثال (2)
؟
Entropy (S) = -(3/6) log (3/6) – (3/6) log(3/6) Entropy (S) = 1
Gain (S, Age) = 1 – ( (4/6) + (2/6) ) = 0
Gain (S, Education) = 1 – 1 = 0
Gain (S, Gender) = 1 – ( -(2/3)log(1/3) – (1/3)log(1/3) ) =0.08
Gain (S, Hours) = 1 – 0.6 = 0.4
Gain (S, Income) = 1 – 1 = 0
Gain (S, Hours) = max Gain Root Node = Hours
26
درخت تصمیم – یک مثال (3)
Hours
{1, 2, 5, 6}
?
{3, 4}
YES
Hours = 30-40
Hours = 40-50
الگوریتم برای ند شامل مثالهای {6و 5و 2و 1} تکرار می شود تا در تمام شاخه ها به برگ برسیم.
27
قوانین تداعی (انجمنی)
تعیین ارتباط اقلام مختلف با یکدیگر در مجموعه اطلاعات ورودی.
حمایت و اطمینان: معیارهای ارزیابی ارتباط.
مثال:
در یک فروشگاه زنجیره ای، معمولا چه کالاهائی با هم خریده می شوند؟
چینش محصولات در فروشگاه
تخفیفها و جایزه های هدف دار
28
تشخیص قوانین تداعی
الگوریتم Apriori
حمایت: P(A U B) احتمال وقوع دو قلم A و B
اطمینان: P(A|B)
هر تک قلمی که از حداقل حمایت برخوردار باشد، یک کاندید قانون تداعی است.
مجموعه اقلام متداول، شامل تمام ابرمجموعه های کاندیداهای قوانین تداعی است.
ابر مجموعه یک مجموعه غیرمتداول، نمی تواند متداول باشد.
هر مجموعه اقلام متداول به تمام دو زیرمجموعه های ممکن تقسیم شده و اطمینان قوانین حاصل محاسبه می شود.
{P1, P2, P3}: P1 -> {P2, P3}, {P2, P3} -> P1
29
دلایل اهمیت یادگیری بدون نظارت
کمک به درک نحوه کشف اصول اولیه توسط ارگانیسم ها
به عنوان پیش پردازش برای یادگیری با نظارت
کمک به کشف خصایص مهم در نمونه های با ابعاد زیاد
کشف گروهها، طبقات، … جدید
30
خوشه بندی: تعریف
از شاخه های داده کاوی و یادگیری بدون نظارت
تعریف
کشف خودکار خوشه های موجود در نمونه ها
خوشه: نمونه های آموزشی نزدیک به هم / گروههائی از اشیاء مشابه
نزدیک: معیارهای متفاوت و متنوع
عملکرد بر روی نمونه های دارای ابعاد نسبتا زیاد
مقایسه با دسته بندی
برچسبهای اولیه نامشخص در خوشه بندی
31
خوشه بندی: یک مثال تصویری
سه خوشه بدیهی از نمونه ها
تشخیص چنین خوشه هائی در ابعاد زیاد، ساده نیست!
32
خوشه بندی: کاربردها (1)
تخمین تابع توزیع نمونه های آموزشی
تشخیص موارد غیرهمگون
تکمیل مشخصات یک نمونه
تجسم و درک نمونه ها
تشکیل سلسله مراتبی از نمونه ها
کاهش ابعاد
33
خوشه بندی: کاربردها (2)
متن کاوی و خوشه بندی اسناد
تشکیل سلسله مراتبی از عناوین، با بررسی متن
استخراج دانش از نمونه های فاقد ساختار مشخص
تشخیص اسناد مرتبط
بازیابی اطلاعات
بازیابی مجموعه ای از نمونه های مشابه
فشرده سازی همراه با تخریب
34
خوشه بندی: روش ها (1)
روش های سلسله مراتبی
تشکیل سلسله مراتبی از خوشه ها
یادگیری تدریجی خوشه ها
دو رویکرد عمده
بالا به پائین (تجزیه ای): ساخت یک خوشه بزرگ و تجزیه آن
پائین به بالا (ترکیبی): ساخت خوشه های کوچک و ادغام آنها
35
خوشه بندی سلسله مراتبی یک مثال تصویری
هر دایره، نشانه یک خوشه
نمونه ها:
1043و 205و 3687و …
36
خوشه بندی: روش ها (2)
روش های مبتنی بر بخش بندی و تخصیص مجدد
ارائه ساختار مسطح از خوشه ها
یادگیری مستقیم خوشه ها
انتخاب تصادفی خوشه های اولیه
بهبود پاسخ از طریق جا به جائی نقاط بین بخش (خوشه) ها
از ساده ترین روشها
مثال هایی از روش مبتنی بر بخش بندی
K-Means
K-Medoids
37
خوشه بندی با تخصیص مجدد یک مثال تصویری
تخصیص نقاط
تعیین مراکز جدید
38
خوشه بندی: روش ها (3)
روش های مبتنی بر جدول (Grid)
تقسیم فضای حالت به تعدادی ابر مکعب
تشخیص ابرمکعب های متراکم
جستجوی خوشه ها به صورت مجموعه هائی از ابرمکعب ها
چند الگوریتم از نوع مبتنی بر جدول:
STING
Wave Cluster
CLIQUE
39
خوشه بندی مبتنی بر جدول الگوریتم CLIQUE
تشخیص نواحی متراکم در زیر مجموعه های فضای حالت اصلی
ترکیب نواحی متراکم مجاور و ساخت خوشه ها
40
خوشه بندی: معیارهای ارزیابی
امکان اعمال بر روی تعداد نمونه های زیاد
امکان اعمال بر روی نمونه های دارای ابعاد زیاد
امکان پردازش مجموعه های حاوی نویز
کشف خوشه های دارای شکل هندسی نامنظم
میزان وابستگی به پارامترهای ورودی
41
خوشه بندی: وضعیت فعلی
شاخص های ارزیابی
امکان اعمال بر روی نمونه های با ابعاد زیاد (مقیاس پذیری)
خوشه بندی با روش های غیرقطعی (الگوریتم مورچگان)
42
تکنیکهای داده کاوی: جمع بندی
دو دسته کلی یادگیری با نظارت و یادگیری بدون نظارت
خوشه بندی به عنوان ابزار اصلی یادگیری بدون نظارت
انواع روشهای خوشه بندی شامل: روشهای آماری، روشهای مبتنی بر جدول، روشهای بخش بندی و تخصیص مجدد
الگوریتمهای متداول خوشه بندی
مسائل جدید: شاخصهای ارزیابی، روشهای تصادفی در خوشه بندی، مقیاس پذیری
43
آینده داده کاوی: کاربردهای جدید، چالشها و دستاوردها
تشخیص ناهمگونی
تعریف و دلایل پیدایش
تکنیکهای موجود
داده کاوی توزیع شده
تعریف و دلایل اهمیت
رویکردها و تکنیکها
عاملها و داده کاوی توزیع شده
داده کاوی و حریم خصوصی
44
تشخیص ناهمگونی
از مسائل نسبتا جدید در داده کاوی.
تشخیص ناهمگونی عبارت است از دسته بندی، در حالتی که نسبت تعداد نمونه های یک کلاس به سایر کلاسها، بسیار اندک باشد (نسبتهای متداول، 1:100، 1:10000، … می باشد).
دو دسته کلی وجود دارد: دسته طبیعی و دسته ناهمگون (مثبت)
تمامی یادگیرنده های معمول در داده کاوی (نظیر درخت تصمیم) در مواجهه با این مسئله با شکست مواجه می شوند.
ناتوانی در حل این مسئله، به نوع استقراء یادگیرنده مربوط می شود.
بسیاری از روشهای داده کاوی، استقراء متمایل به حالت کلی دارند.
در مسئله تشخیص ناهمگونی، استقراء متمایل به حالت خاص از کارآئی بیشتری برخوردار خواهد بود.
45
کاربردهای تشخیص ناهمگونی
کاربردهای پزشکی: تشخیص بیماریها برپایه شناسائی موارد غیرعادی در اطلاعات یک بیمار.
کاربردهای علمی: بررسی اطلاعات ژئوفیزیکی و هشدار در مورد وقوع زمین لرزه احتمالی.
کاربردهای تجاری: بررسی بروز شرایط غیرعادی در بازار بورس، تشخیص سوءاستفاده از کارتهای اعتباری، تشخیص صحت ادعاهای خسارت در شرکتهای بیمه.
کاربردهای امنیتی: شناسائی فرد یا افراد مظنون به انجام عملیات تروریستی، تشخیص رفتار غیرمعمول در شرایط مختلف.
46
انواع خطا در تشخیص ناهمگونی
دو گروه عمده از خطاها وجود دارد.
مثبت غیرواقعی: نمونه های متعلق به دسته طبیعی که اشتباها به عنوان ناهمگونی دسته بندی می شوند.
منفی غیرواقعی: نمونه های متعلق به دسته ناهمگون (مثبت) که به اشتباه، طبیعی تلقی می شوند.
معمولا هزینه این دو نوع خطا، یکسان نیست.
بر حسب مسئله هدف، هریک از دو خطای احتمالی می تواند فاجعه آمیز باشد.
47
تشخیص ناهمگونی: رویکردها
تقسیم فضای حالت
نمونه برداری
کاهش نمونه های نرمال
افزایش نمونه های مثبت
هر دو روش نمونه برداری ممکن است به تطبیق بیش از حد منجر شوند.
یادگیری حساس به هزینه
تقویت نمونه های آموزشی(Boosting)
48
تشخیص ناهمگونی: معیارهای ارزیابی
معیارهای متداول ارزیابی یک الگوریتم یادگیری، در این مورد کارساز نیست.
معیاری نظیر تعداد خطاهای دسته بندی در نمونه های مجموعه آزمایشی: یک دسته بندی کننده غیرهوشمند که همواره پاسخ ”طبیعی“ ارائه کند، به دقت بیش از %90 دست خواهد یافت.
نیاز به معیارهای ارزیابی جدید.
یک معیار مناسب، نسبت تعداد مثبتهای واقعی (نرخ تشخیص) به تعداد مثبتهای غیرواقعی (نرخ هشدار غیرواقعی) می باشد.
منحنی ROC، نرخ تشخیص و نرخ هشدار غیرواقعی را در مورد یک یادگیرنده نشان می دهد.
49
تشخیص ناهمگونی: منحنی ROC
معمولا به ازای نرخ هشدار اشتباه صفر، نرخ تشخیص نیز صفر خواهد بود.
1.0
1.0
نرخ تشخیص
نرخ هشدار اشتباه
50
داده کاوی توزیع شده
بسیاری از پیش فرضهای یک فرآیند داده کاوی، در شرایط عادی برقرار نیست.
تکنیکهای موجود، فرض را بر در اختیار داشتن تمامی اطلاعات موجود در قالب یک فایل واحد و دارای ساختار ثابت به ازای تمام نمونه ها قرار می دهند.
چنین فرضی، تقریبا در هیچ کاربرد واقعی برقرار نیست.
اجرای مراحلی نظیر تجمیع اطلاعات، می تواند به دلایل متعددی غیرممکن باشد.
منابع اطلاعاتی در دسترس، غالبا ناهمگون، توزیع شده و دارای ضرایب اطمینان متفاوت می باشند.
علیرغم نیاز بسیاری سازمانها به دانش حاصل از داده کاوی، ریسک افشای اطلاعات محرمانه همچنان از ورود داده کاوی به این سازمانها جلوگیری می نماید.
انواع متعددی از اطلاعات وجود دارد که ضمن دشوار یا غیرممکن بودن تبدیل آنها به اطلاعات در قالب بانکهای اطلاعاتی، نمی توان از دانش بالقوه موجود در آنها صرف نظر کرد.
51
دلایل پیدایش داده کاوی توزیع شده
ملاحظات رقابتی
ترس از حملات استنتاجی
ترس از افشای اطلاعات خام
محدودیت دستگاههای ذخیره سازی و نیز پهنای باند شبکه ها
عدم امکان تجمیع اطلاعات مورد نیاز در یک محل مرکزی
عدم امکان انتقال اطلاعات روی شبکه های کامپیوتری موجود
تنوع اطلاعات موجود
نیاز به الگوریتمهای متخصص در هر نوع اطلاعات
لزوم ادغام نتایج میانی چند الگوریتم، به جای مبادله اطلاعات خام
ملاحظات امنیتی
لزوم حفظ حریم خصوصی افراد: پراکندگی اطلاعات یک نمونه خاص در نقاط مختلف و غیرقانونی بودن جمع آوری این اطلاعات در یک نقطه مرکزی.
عدم امکان شرکت دادن تمامی متخصصان در فرآیند استخراج دانش (از طریق برگزاری مسابقات)
عدم امکان به اشتراک گذاری اطلاعات، حتی بین چند سازمان با اهداف مشترک.
52
تکنیکها و رویکردها در داده کاوی توزیع شده
دو گروه عمده در تکنیکهای داده کاوی توزیع شده:
تکنیکهای مربوط به اطلاعات همگون
تکنیکهای مربوط به اطلاعات ناهمگون
تمام روشها بر مبنای انتقال نوعی از اطلاعات میانی، با حداکثرسازی امکان کشف دانش و حداقل سازی امکان حدس زدن اطلاعات خام توسط دیگران استوار می باشند.
عمده ترین (و شاید تنها) رویکرد موجود به داده کاوی توزیع شده، به کارگیری عاملها می باشد.
53
عاملها و داده کاوی توزیع شده
عامل: یک نرم افزار دارای قابلیت رفتار واکنشی و رفتار هدفمند
مسئله داده کاوی توزیع شده، با مسئله استفاده از چندعامل هوشمند مستقل در حل یک مسئله خاص، تطابق دارد.
عاملهای متخصص برای هر نوع اطلاعات.
توزیع شدگی عاملها و عدم نیاز به انتقال اطلاعات خام.
امکان همکاری عاملها در جهت حل یک مسئله داده کاوی، از طریق پروتکلهای ارتباطی نظیر تخته سیاه، …
مسئله منفعتگرایی عاملها و شرکت یا عدم شرکت در یک فرآیند داده کاوی.
مذاکره خودکار بین عاملها، جهت تبادل اطلاعات و دانش.
54
داده کاوی و حریم خصوصی
در موارد متعدد، داده کاوی می تواند به کشف دانش محرمانه و یا نقض حریم خصوصی افراد منجر شود.
صرف ممنوعیت جمع آوری تمام اطلاعات مربوط به اشخاص در یک نقطه مرکزی، تضمینی برای عدم نقض حریم خصوصی افراد ایجاد نخواهد کرد.
ریسک حملات استنتاجی، یا استفاده از دانش و اطلاعات خام از چند منبع جهت کشف اطلاعات و یا دانش محرمانه، بسیاری از سازمانها را از شرکت در هرگونه فرآیند داده کاوی اشتراکی باز می دارد.
هدف از حفظ حریم خصوصی و اطلاعات محرمانه، مقابله با حملات استنتاجی و یا هرگونه روش دیگری برای کشف دانش محرمانه می باشد.
موفقیت این دسته از روشها، می تواند به توسعه کاربردهای داده کاوی منتهی شود.
مانند مسئله ویروسها و نفوذگران به شبکه های کامپیوتری، در اینجا نیز مبارزه ای بی پایان وجود دارد.
55
تکنیکهای مقابله با نقض حریم خصوصی ناشی از داده کاوی
تکنیکهای سردرگم کننده یادگیرنده
حذف بعضی نمونه های آموزشی
حذف بعضی خصایص
تغییر مقادیر بعضی از خصایص
هدف، جلوگیری از کشف دانش محرمانه، ضمن حفظ امکان استخراج دانش مفید است.
تکنیکهای تشخیص دانش محرمانه
56
جمع بندی و نتیجه گیری
داده کاوی عبارت است از فرآیند نیمه خودکار استخراج دانش از اطلاعات موجود.
داده کاوی شامل مراحل انتخاب، پیرایش و تجمیع اطلاعات، استخراج و بازنمائی و تفسیر دانش می باشد.
کاربردهای داده کاوی شامل حوزه های تجاری، امنیتی و علمی می باشد.
تکنیکهای اصلی داده کاوی عبارتند از: دسته بندی، خوشه بندی و استخراج قوانین تداعی.
مسائل جدید در داده کاوی عبارتند از: تشخیص ناهمگونی، داده کاوی توزیع شده و مسئله حفظ دانش محرمانه و حریم خصوصی.
نیاز مبرم به روشهای داده کاوی مقیاس پذیر
نیاز به توسعه داده کاوی بر روی انواع اطلاعات موجود
نیاز به توسعه داده کاوی به عنوان یک فرآیند استاندارد و توزیع شده
57
پیشنهاداتی برای تحقیق
ساخت الگوریتمهایی برای غلبه بر مسئله ابعاد زیاد نمونه ها (نفرین ابعاد)
توسعه روشهایی برای داده کاوی بر روی اطلاعات در حجم بسیار زیاد (به خصوص در مورد خوشه بندی)
بررسی نقش عاملها در داده کاوی توزیع شده، توسعه جهت تحقق داده کاوی توزیع شده
توسعه روشهای داده کاوی مبتنی بر انواع اطلاعات
بهبود روشهای حفظ اطلاعات محرمانه و جلوگیری از حملات استنتاجی
بهبود روشهای تشخیص ناهمگونی، به خصوص مسئله تشخیص بدون نظارت
58
فهرست منابع
J. Han, M. Kamber and Simon Fraser, Data Mining: Concepts and Techniques, Morgan Kaufman Publisher., 2001
H. Miller, and J. Han, Geographic Data Mining and Knowledge Discovery. Taylor and Francis, London, U.K., 2001.
M. Steinbach, P. Tan, V. Kumar, S. Klooster, and C. Potter, Data mining for the discovery of ocean climate indices, Proceedings of th 5th Workshop on Scientific Data Mining (SDM 2002), (Arlington, VA, Apr. 13), Society of Industrial and Applied Mathematics, pp 7–16, 2002.
S. J. Stolfo, W. Lee, P. K. Chan, W. Fan and E. Eskin, “Data Mining-based Intrusion Detectors: An Overview of the Columbia IDS Project”, SIGMOD Record, Vol. 30, No. 4, December 2001, pp 5-14, 2000.
H. Kargupta, A. Joshi, K. Sivakumar and Y. Yesha, “Data Mining: Next Generation Challenges and Future Directions”, Prentice Hall of India, pp. 157-219, 2005.
L. A.F. Park, K. Ramamohanarao, and M. Palaniswami, “Fourier Domain Scoring: A Novel Document Ranking Method”, IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 16, NO. 5, pp 529-539, MAY 2004
S. Schockaert, M. De Cock, C. Cornelis and E. E. Kerre “Efficient Clustering with Fuzzy Ants”, Applied Computational Intelligence, World Scientific, p. 195-200, 2004
59
فهرست منابع (ادامه)
M. Halkidi, Y. Batistakis and M. Vazirgiannis, “On Clustering Validation Techniques”, Journal of Intelligent Systems, vol. 17:2/3, pp 107-145, 2001
S. Dˇzeroski and H. Blockeel, MultiRelational Data Mining 2004: Workshop Report, SIGKDD Explorations. Volume 6,Issue 2, pp. 140-141, 2004.
C.A. Ratanamahatana and E. Keogh, Towards Parameter-Free Data Mining, KDD ’04, Seattle, Washington, USA, pp. 206-215, 2004
H. Mannila, “Theoretical Frameworks for Data Mining”, SIGKDD Explorations, January 2000. Volume 1, Issue 2 – page 30-32
R. Grossman, Data Mining Standards, Services, and Platforms 2004 (DMSSP 2004) Workshop Report,, SIGKDD Explorations. Volume 6,Issue 2 – Page 157-158, 2004.
U.M. Fayyad, G.Piatetsky-Shapiro, R. Uthurusamy, Summary from the KDD-03 Panel — Data Mining: The Next 10 Years, SIGKDD Explorations. Volume 5,Issue 2 – pp. 191-196, 2003.
60
با تشکر از توجه شما