انجام پایان نامه

درخواست همکاری انجام پایان نامه  بانک مقالات رایگان انجام پایان نامه

سفارش پایان نامه

|

انجام پایان نامه ارشد

 پایان نامه پروژه پایانی DATA -MING

پایان نامه| پروژه پایانی 91 صDATA -MING


چکیده:
در دو دهه قبل توانايي¬های فنی بشر برای توليد و جمع¬آوری داده‌ها به سرعت افزايش يافته است. عواملی نظير استفاده گسترده از بارکد برای توليدات تجاری، به خدمت گرفتن کامپيوتر در کسب¬و¬کار، علوم، خدمات¬ دولتی و پيشرفت در وسائل جمع¬آوری داده، از اسکن کردن متون و تصاوير تا سيستمهای سنجش از دور ماهواره¬ای، در اين تغييرات نقش مهمی دارند.
    بطور کلی استفاده همگانی از وب و اينترنت به عنوان يک سيستم اطلاع رسانی جهانی ما را مواجه با حجم زیادی از داده و اطلاعات می‌کند. اين رشد انفجاری در داده‌های ذخيره شده، نياز مبرم وجود تکنولوژی¬های جديد و ابزارهای خودکاری را ايجاد کرده که به صورت هوشمند به انسان ياری رسانند تا اين حجم زياد داده را به اطلاعات و دانش تبديل کند. داده¬کاوی به عنوان يک راه حل برای اين مسائل مطرح مي باشد. در يک تعريف غير رسمی داده¬کاوی فرآيندی است، خودکار برای استخراج الگوهايی که دانش را بازنمايی مي¬کنند، که اين دانش به صورت ضمنی در پايگاه داده¬های عظيم، انباره¬داده  و ديگر مخازن بزرگ اطلاعات، ذخيره شده است.
        به لحاظ اینکه در چند سال اخیر مبحث داده¬کاوی و اکتشاف دانش موضوع بسیاری از مقالات و کنفرانسها قرار گرفته و نرم¬افزار¬های آن در بازار به شدت مورد توجه قرار گرفته، از اینرو در مقاله سعی بر آن شده تا گذری بر آن داشته باشیم.
        در این مقاله درفصل مروری بر داده¬کاوی خواهیم داشت . که به طور عمده به تاریخچه ، تعاریف، کاربردها وارتباط آن با انبار داده و OLAP خواهیم پرداخت. در پایان فصل مراحل فرایند کشف دانش از پایگاه داده¬ها را ذکر کردیم که داده¬کاوی یکی از مراحل آن است.
        در فصل 2 یکی از شیوه¬های داده¬کاوی که از سبد خرید گرفته شده¬ است توضیح داده شده است . در این فصل به شرح قوانین ارتباطی خواهیم پرداخت که در آن بعد از دسته¬بندی الگوریتمها ، الگوریتم Apriori ( که یک الگوریتم پایه در این زمینه است ) و الگوریتم FP-Growth ( یک الگوریتم جدید میباشد) را با شرح یک مثال توضیح می¬دهیم و در آخر آن دو را با هم مقایسه می¬کنیم .
        در فصل 3 مباحث وب¬کاوی و متن¬کاوی را که در بسیاری از مراجع جزء کاربردهای داده¬کاوی به حساب می¬آید شرح داده خواهد شد.






فهرست مطالب
عنوان                                                                                                                                                                صفحه
فهرست اشکال   ...............................................................................................................................................    10
فهرست جداول   ..............................................................................................................................................    11
فصل1: مقدمه¬ای بر داده¬کاوی  ............................................................................    13
1-1 تعریف داده¬کاوی   ...................................................................................................................................    15
2-1 تاریخچه داده¬کاوی   ................................................................................................................................    16
3-1 چه چیزی سبب پیدایش داده¬کاوی شده است؟   ........................................................................................    17
4-1 اجزای سیستم داده¬کاوی   .........................................................................................................................    19
5-1 جایگاه داده¬کاوی در میان علوم مختلف   ..................................................................................................    21
6-1 قابلیتهای داده¬کاوی   .................................................................................................................................    22
7-1 چرا به داده¬کاوی نیاز داریم؟   ...................................................................................................................    23
8-1 داده¬کاوی چه کارهایی نمی¬تواند انجام دهد؟   ..........................................................................................    25
9-1 کاربردهای داده¬کاوی   .............................................................................................................................    25
1-9-1 کاربردهای پیش¬بینی¬کننده   ...................................................................................................    27
2-9-1 کاربردهای توصیف¬کننده   ....................................................................................................    27
10-1 ابزارهای تجاری داده¬کاوی   ...................................................................................................................    28
11-1 داده¬کاوی و انبار¬داده¬ها   .........................................................................................................................    29
1-11-1 تعاریف انبار¬داده   ................................................................................................................    29
2-11-1 چهار خصوصیت اصلی انبار¬داده   .........................................................................................    30
3-11-1 موارد تفاوت انبار¬داده و پایگاه¬ داده   ....................................................................................    31
12-1 داده¬کاوی و OLAP   ...........................................................................................................................    33
1-12-1 OLAP   ...........................................................................................................................    33
2-12-1 انواع OLAP   ...................................................................................................................    34
13-1 مراحل فرایند کشف دانش از پایگاه داده¬ها   ...........................................................................................    34
1-13-1 انبارش داده¬ها   ....................................................................................................................    35
2-13-1 انتخاب داده¬ها   ....................................................................................................................    36
3-13-1 پاکسازی- پیش¬پردازش- آماده¬سازی   ................................................................................    36
4-13-1 تبدیل داده¬ها   ......................................................................................................................    36
5-13-1 کاوش در داده¬ها (Data Mining)   .................................................................................    37
6-13-1 تفسیر نتیجه   ........................................................................................................................    38
فصل 2: قوانین ارتباطی   ...........................................................................    39
1-2 قوانین ارتباطی   ........................................................................................................................................    40
2-2 اصول پایه   ...............................................................................................................................................    41
1-2-2 شرح مشکل جدی   ...............................................................................................................    41
2-2-2 پیمایش فضای جستجو   .........................................................................................................    43
3-2-2 مشخص کردن درجه حمایت مجموعه اقلام   .........................................................................    45
3-2 الگوریتمهای عمومی   ..............................................................................................................................    45
1-3-2 دسته¬بندی   ............................................................................................................................    45
2-3-2 BFS و شمارش رویداد¬ها   ...................................................................................................    46
3-3-2 BFS و دونیم¬سازی TID-list   ...........................................................................................    47
4-3-2 DFS و شمارش رویداد   ......................................................................................................    47
5-3-2 DFS و دو نیم¬سازی TID-list  ..........................................................................................    48
4-2 الگوریتم Apriori   ................................................................................................................................    48
1-4-2 مفاهیم کلیدی   .....................................................................................................................    48
2-4-2 پیاده¬سازی الگوریتم Apriori   ............................................................................................    49
3-4-2 معایب Apriori و رفع آنها   .................................................................................................    54
5-2 الگوریتم رشد الگوی تکرارشونده   ..........................................................................................................    55
1-5-2 چرا رشد الگوی تکرار سریع است؟   .....................................................................................    58
6-2 مقایسه دو الگوریتم Apriori و FP-growth   ......................................................................................    59
7-2 تحلیل ارتباطات   ......................................................................................................................................    63
فصل 3: وب¬کاوی و متن¬کاوی   .................................................................    65
1-3 وب¬کاوی   ...............................................................................................................................................    66
1-1-3 الگوریتمهای هیتس و لاگسام   ...............................................................................................    69
2-1-3 کاوش الگوهای پیمایش مسیر   ..............................................................................................    76
2-3 متن¬کاوی   ...............................................................................................................................................    80
1-2-3 کاربردهای متن¬کاوی   ...........................................................................................................    82
1-1-2-3 جستجو و بازیابی   ..............................................................................................    83
2-1-2-3 گروه¬بندی و طبقه¬بندی   ......................................................................................    83
3-1-2-3 خلاصه¬سازی   ....................................................................................................    84
4-1-2-3 روابط میان مفاهیم   .............................................................................................    84
5-1-2-3 یافتن و تحلیل گرایشات   ....................................................................................    84
6-1-2-3 برچسب زدن نحوی (pos)   ...............................................................................    85
7-1-2-3 ایجاد Thesaurus و آنتولوژی به صورت اتوماتیک   .........................................    85
2-2-3 فرایند متن¬کاوی   ...................................................................................................................    86
3-2-3 روشهای متن¬کاوی   ...............................................................................................................    87
مراجع   .....................................................................................................    89

























فهرست اشکال
عنوان                                                                                                                                                                صفحه
1-1 مراحل فرایند کشف دانش   ......................................................................................................................    17
2-1 سیر تکاملی صنعت پایگاه داده   ................................................................................................................    19
3-1 معماری یک نمونه سیستم داده¬کاوی   .......................................................................................................    20
4-1 نرخ رشد اطلاعات   .................................................................................................................................    24
5-1 کاربرد پیش¬بینی کننده   ............................................................................................................................    27
6-1 داده¬ها از انبار¬داده¬ها استخراج می¬گردند   ..................................................................................................    32
7-1 داده¬ها از از چند پایگاه داده¬ استخراج می¬گردند   ......................................................................................    32
1-2 شبکه‌ای برای     .................................................................................................................
43
2-2 درخت     ..........................................................................................................................
44
3-2 دسته¬بندی الگوریتمها   ..............................................................................................................................    46
4-2 پایان الگوریتم Apriori   ........................................................................................................................    52
5-2 درخت الگوی تکرار   ..............................................................................................................................    57
6-2 اندازه¬گیری کارکرد درجه حمایت برای پایگاه داده D1 40K   ..............................................................    61
7-2 اندازه¬گیری Apriori با درجه حمایت/تراکنش   .....................................................................................    62
8-2 اندازه¬گیری FP-growth با درجه حمایت/تراکنش   ..............................................................................    62
1-3 مقداردهی اولیه الگوریتم HITS   ............................................................................................................    72
2-3 مثالی از الگوهای پیمایش   .......................................................................................................................    80
3-3 فرایند متن¬کاوی   .....................................................................................................................................    86
4-3 مثال یافتن روابط   .....................................................................................................................................    88










فهرست جداول
عنوان                                                                                                                                                                صفحه
1-2 کاوش FP-tree با ایجاد پایگاه¬های الگوشرطی   .....................................................................................    58
2-2 پارامترها   .................................................................................................................................................    59
3-2 نتایج برای فاکتور درجه حمایت 5%   ........................................................................................................    60
4-2 نتایج برای D1 150K با درجه حمایت   .................................................................................................    61
1-3 تراکنش¬های توصیف شده توسط مجموعه¬ای از URLها   .......................................................................    75
2-3 نمایش URLها به عنوان بردارهایی از فعالیت گروه تراکنش   ..................................................................    75
3-3 یک SOM مرسوم که توسط توصیف URLها تولید شده است   ............................................................    76




فصل 1

مروری بر داده¬کاوی
 
امروزه با گسترش سیستم‌های پایگاهی و حجم بالای داده‌های ذخیره شده در این سیستم‌ها، نیاز به ابزاری است تا بتوان داده‌های ذخیره شده را پردازش کرد و اطلاعات حاصل از این پردازش را در اختیار کاربران قرار داد.
با استفاده از پرسش‌های ساده در SQL و ابزارهای گوناگون گزارش‌گیری معمولی، می‌توان اطلاعاتی را در اختیار کاربران قرار داد تا بتوانند به نتیجه‌گیری در مورد داده‌ها و روابط منطقی میان آنها بپردازند. امّا وقتی که حجم داده‌ها بالا باشد، کاربران هرچند زبر¬دست و با¬تجربه باشند نمی‌توانند الگوها مفید را در میان حجم انبوه داده‌ها تشخیص دهند و یا اگر قادر به این کار هم باشند، هزینه عملیات از نظر نیروی انسانی و مادی بسیار بالا است. از سوی دیگر، کاربران معمولاً فرضیه‌ای را مطرح می‌کنند و سپس بر¬اساس گزارشات مشاهده شده به اثبات یا رد فرضیه می‌پردازند، در حالی که امروزه نیاز به روشهایی است که اصطلاحاً به کشف دانش   بپردازند یعنی با کمترین دخالت کاربر و بصورت خودکار الگوها و رابطه‌های منطقی را بیان نمایند.
داده کاوی  یکی از مهمترین این روشها است که به الگوهای مفید در داده‌ها با حداقل دخالت کاربران شناخته می‌شوند واطلاعاتی را در اختیار کاربران و تحلیل گران قرار می‌دهند تا براساس آن تصمیمات مهم و حیاتی در سازمانها اتخاذ شوند.
اصطلاح داده¬کاوی زمانی بکار برده می‌شود که با حجم بزرگی از داده‌ها، در حد مگا یا ترابایت، مواجه باشیم. در تمامی منابع داده¬کاوی بر این مطلب تأکید شده است. هرچه حجم داده‌ها بیشتر و روابط آنها پیچیده¬تر باشد دسترسی به اطلاعات نهفته در میان داده¬ها مشکل¬تر می‌شود و نقش داده¬کاوی بعنوان یکی از روش¬های کشف دانش، روشن‌تر می‌گردد.
داده¬کاوی بطور همزمان از چندین رشته علمی بهره می‌برد نظیر: تکنولوژی پایگاه داده، هوش مصنوعی، یادگیری ماشین، شبکه‌های عصبی، آمار، الگو، سیستم‌های مبتنی بر دانش ، حصول دانش ، بازیابی اطلاعات ، محاسبات سرعت بالا  و بازنمایی بصری داده .
1-1: تعریف داده¬کاوی:
اصطلاح Data Mining همانطور که از ترجمه آن به داده¬کاوی مشخص می¬شود، به مفهوم استخراج اطلاعات نهان و یا الگوها و روابط مشخص در حجم زیادی از داده‌های یک یا چند بانک اطلاعاتی بزرگ است. اطلاعات استخراج شده در تعریف Data Mining بطور ضمنی به معنی اطلاعاتی است که بر اساس آن بتوان به نتایجی دست یافت که بطور معمول ملموس نیستند. در این تعریف بر بزرگ بودن بانکهای اطلاعاتی و یا حجم زیاد داده‌های مورد پردازش تاکید می‌شود. علت این است که از نظر آماری و تئوری اطلاعات، تجزیه و تحلیل داده‌ها و یا آنطور که در این اصطلاح تعبیر می‌شود، کاوش در حجم کم داده¬های یک بانک به نتایج قابل قبولی منجر نمی‌شود. به کمک ابزارهای Data Mining می‌توان مقادیر متغیرهای را پیش¬بینی و توصیف نمود. این ابزارها در فرایندهای تصمیم‌گیری متکی بر اطلاعات و دانش   کاربر فراوان دارند و فعالیت¬های تجاری نوین و مدرن امروزه به شدت بر آن متکی است. فرایند Data Mining را نباید با روش‌های متداول آنالیز داده و اطلاعات و سیستم¬های تصمیم‌گیری معمولی یکی دانست. به کمک روش‌های Data Mining می‌توان به پرسش¬هایی (عمدتاً تجاری) پاسخ گفت که بطور سنتی عملاً امکان وجود ندارد.
در متون آکادمیک تعاریف گوناگونی برای داده کاوی ارائه شده‌اند. در برخی از این تعاریف داده¬کاوی در حد ابزاری که کاربران را قادر به ارتباط مستقیم با حجم عظیم داده¬ها می‌سازد معرفی گردیده است و در برخی دیگر، تعاریف دقیقتر که در آنها به کاوش در داده¬ها توجه می‌شود موجود است. برخی از این تعاریف عبارتند از:
•    داده¬کاوی عبارت است از فرایند استخراج اطلاعات معتبر، از پیش ناشناخته، قابل فهم و قابل اعتماد از پایگاه داده¬های بزرگ و استفاده از آن در تصمیم‌گیری در فعالیت¬های تجاری مهم.
•    اصطلاح داده¬کاوی به فرایند نیم خودکار تجزیه و تحلیل پایگاه داده¬های بزرگ به منظور یافتن الگوهای مفید اطلاق می‌شود.
•    داده¬کاوی یعنی جستجو در یک پایگاه داده¬ها برای یافتن الگوهایی میان داده¬ها.
•    داده¬کاوی عبارتست از فرایند یافتن دانش از مقادیر عظیم داده¬های ذخیره شده در پایگاه داده، انباره داده و یا دیگر مخازن اطلاعات.
•    داده¬کاوی یعنی استخراج دانش کلان، قابل استناد و جدید از پایگاه داده¬های بزرگ.
•    داده¬کاوی یعنی تجزیه و تحلیل مجموعه داده¬های قابل مشاهده برای یافتن روابط مطمئن بین داده¬ها.
همانگونه که در تعاریف گوناگون داده¬کاوی مشاهده می¬شود، تقریباً در تمامی تعاریف به مفاهیمی چون استخراج دانش، تحلیل و یافتن بین داده¬ها اشاره شده است.
واژه های «داده¬کاوی» و «کشف دانش در پایگاه داده»  اغلب بصورت مترادف یکدیگر مورد استفاده قرار می‌گیرد. کشف دانش در پایگاه داده فرایند شناسایی درست، ساده، مفید و  نهایتا الگوها و مدلهای قابل فهم در داده¬ها می‌باشد. داده-کاوی، مرحله‌ای از فرایند کشف دانش می‌باشد و شامل الگوریتم¬های مخصوص داده¬کاوی است، بطوریکه تحت محدودیت¬های مؤثر محاسباتی قابل قبول، الگوها و یا مدلها را در داده کشف می‌کند.
داده¬ها اغلب حجیم امّا بدون ارزش می‌باشند، داده به تنهایی قابل استفاده نیست، بلکه دانش نهفته در داده¬ها قابل استفاده می‌باشد. به این دلیل به داده¬کاوی، تحلیل داده‌ای ثانویه  گفته می‌شود.
2-1: تاریخچه داده¬کاوی
اخیرا داده¬کاوی موضوع بسیاری از مقالات، کنفرانس‌ها و رساله‌های عملی شده است، امّا این واژه تا اوایل دهه نود مفهومی نداشت و به کاربرده نمی‌شد.
در دهه شصت و پیش از آن زمینه‌هایی برای ایجاد سیستم‌های جمع‌آوری و مدیریت داده¬ها ایجاد شد و تحقیقاتی در این زمینه انجام پذیرفت که منجر به معرفی و ایجاد سیستم¬های مدیریت پایگاه داده¬ها گردید.
ایجاد و توسعه مدلهای داده‌ای برای پایگاه سلسله مراتبی، شبکه‌ای و بخصوص رابطه‌ای در دهه هفتاد، منجر به معرفی مفاهیمی همچون شاخص¬گذاری و سازمادهی داده‌ها و در نهایت ایجاد زبان پرسش SQL در اوایل دهه هشتاد گردید تا کاربران بتوانند گزارشات و فرم¬های اطلاعاتی موردنظر خود را ، از این طریق ایجاد نمایند.
توسعه سیستم‌های پایگاهی پیشرفته در دهه هشتاد و ایجاد پایگاه¬ها شی‌گرا، کاربرد گرا  و فعال  باعث توسعه همه جانبه و کاربردی شدن این سیستم‌ها در سراسر جهان گردید. بدین ترتیب DBMS¬هایی همچون Oracle, DB2,¬ Sybase, ... ایجاد شدند و حجم زیادی از اطلاعات با استفاده از این سیستم‌ها مورد پردازش قرار گرفتند. شاید بتوان مهمترین جنبه در معرفی داده¬کاوی را مبحث کشف دانش از پایگاه داده‌ها (KDD)  دانست بطوریکه در بسیاری موارد DM    و KDD بصورت مترادف مورد استفاده قرار می‌گیرند.
همانطور که در تعریف داده¬کاوی ذکر شد، هدف جستجو و کشف الگوهایی در پایگاه داده ها و استفاده از آنها در اخذ تصمیمات حیاتی است، بنابراین می‌توان گفت که DM بخشی از فرایند KDD است که در نهایت به ایجاد سیستم‌های DSS   می‌شود. شکل 1-1 نقش داده کاوی در فرایند کشف دانش از پایگاه داده ها را نشان می‌دهد.
برای اولین بار مفهوم داده¬کاوی در کارگاه IJCAI  در زمینه KDD توسّط Shapir مطرح گردید. به دنبال آن در سالهای 1991 تا 1994 ، کارگاههای KDD مفاهیم جدیدی را در این شاخه علم ارائه کردند بطوریکه بسیاری از علوم و مفاهیم با آن مرتبط گردیدند.

3-1- چه چیزی سبب پیدایش داده¬کاوی شده است؟
اصلی¬ترین دلیلی که باعث شد داده¬کاوی کانون توجهات در صنعت اطلاعات قرار بگیرد، مساله در دسترس بودن حجم وسیعی از داده¬ها و نیاز شدید به اینکه از این داده¬ها  اطلاعات و دانش سودمند استخراج کنیم. اطلاعات و دانش بدست آمده در کاربردهای وسیعی از مدیریت کسب و کار و کنترل تولید و تحلیل بازار تا طراحی مهندسی و تحقیقات علمی مورد استفاده قرار می‌گیرد.
 
شکل 1-1 مراحل فرایند کشف دانش

داده کاوی را می‌توان حاصل سیر تکاملی طبیعی تکنولوژی اطلاعات دانست، که این سیر تکاملی ناشی از یک سیر تکاملی در صنعت پایگاه داده می‌باشد، نظیر عملیات: جمع‌آوری داده¬ها و ایجاد پایگاه داده، مدیریت داده و تحلیل و فهم داده‌ها. در شکل 2-1 این روند تکاملی در پایگاه‌های داده نشان داده شده است.
تکاملی تکنولوژی پایگاه داده و استفاده فراوان آن در کاربردهای مختلف سبب جمع‌آوری حجم فراوانی داده شده است. این داده¬های فراوان باعث ایجاد نیاز ابزارهای قدرتمند برای تحلیل داده¬ها گشته، زیرا در حال حاضر به لحاظ داده ثروتمند هستیم ولی دچار کمبود اطلاعات می‌باشیم.
ابزارهای داده¬کاوی داده ها را آنالیز می‌کنند و الگوهای داده‌ای را کشف می‌کنند که می‌توان از آن در کاربردهایی نظیر: تعیین استراتژی برای کسب و کار، پایگاه دانش  و تحقیقات علمی و پزشکی، استفاده کرد. شکاف موجود بین داده¬ها و اطلاعات سبب ایجاد نیاز برای ابزارهای داده¬کاوی شده است تا داده‌های بی‌ارزش را به دانشی ارزشمند تبدیل کنیم.
بطور ساده داده¬کاوی به معنای استخراج یا «معدن¬کاری»  دانش از مقدار زیادی داده خام است. البته این نامگذاری برای این فرایند تا حدی نامناسب است، زیرا بطور مثال عملیات معدن¬کاری برای استخراج طلا از صخره و ماسه را طلا-کاوی می¬نامیم، نه ماسه¬کاوی یا صخره¬کاوی. بنابراین بهتر بود به این فرایند نامی شبیه به «استخراج دانش از داده» می‌دادیم که متأسفانه بسیار طولانی است. «دانش¬کاوی» بعنوان یک عبارت کوتاهتر بعنوان جایگزین، نمی‌تواند بیانگر تأکید و اهمیت بر معدن¬کاری مقدار زیاد داده باشد. معدن¬کاری عبارتی است که بلافاصله انسان را به یاد فرایندی می‌اندازد که به دنبال یافتن مجموعه‌ کوچکی از قطعات ارزشمند از حجم بسیار زیادی از مواد خام هستیم.
با اینکه این فرایند تا حدی دارای نامگذاری ناقص است ولی این نامگذاری یعنی داده¬کاوی بسیار عمومیت پیدا کرده است. البته اسامی دیگر نیز برای این فرایند پیشنهاد شده که بعضا بسیار متفاوت با واژه داده¬کاوی است، نظیر: استخراج دانش از پایگاه داده، استخراج دانش ، آنالیز داده/ الگو، باستان شناسی داده ، و لایروبی داده‌ها .




 
شکل 2-1 سیر تکاملی صنعت پایگاه داده

4-1- اجزای سیستم داده¬کاوی:
با توجه به مطالب عنوان شده،  یکی از تعاریف عنوان شده برای داده¬کاوی چنین بود:
«داده¬کاوی عبارت است از فرایند یافتن دانش از مقادیر عظیم داده‌های ذخیره شده در پایگاه داده، انباره داده و یا دیگر مخازن اطلاعات»
بر¬اساس این دیدگاه یک سیستم داده¬کاوی بطور نمونه دارای اجزای اصلی زیر است که شکل   3-1 بیانگر معماری سیستم است.
 
شکل 3-1 معماری یک نمونه سیستم داده¬کاوی

1- پایگاه داده، انباره¬ داده (Data warehouse) یا دیگر مخازن اطلاعات:
که مجموعه‌ای از پایگاه داده‌ها، انبار داده، صفحه گسترده ، یا دیگر انواع مخازن اطلاعات.
2- سرویس دهنده پایگاه داده یا انبار داده:
که مسئول بازیابی داده‌های مرتبط براساس نوع درخواست داده¬کاوی کاربر می‌باشد.
3- پایگاه دانش:
این پایگاه از دانش زمینه  تشکیل شده تا به جستجو کمک کند، یا برای ارزیابی الگوهای یافته شده از آن استفاده می‌شود.
4- موتور داده¬کاوی  
این موتور جزء اصلی از سیستم داده¬کاوی است و بطور ایدآل شامل مجموعه‌ای از پیمانه  هایی نظیر توصیف  ، ارتباط ، کلاسبندی ، آنالیز خوشه‌ها  و آنالیز تکامل و انحراف  است.
5- پیمانه ارزیابی الگو
این جزء معیارهای جذابیت   را بکار می‌بندد و با پیمانه‌ی داده¬کاوی تعامل می‌کند، بدینصورت که تمرکز آن بر جستجو بین الگوهای جذاب می‌باشد، و از یک حد آستانه جذابیت استفاده می‌کند تا الگوهای کشف شده را ارزیابی کند.
6- واسط کاربر گرافیکی : این پیمانه بین کاربر و سیستم داده¬کاوی ارتباط برقرار می‌کند، به کاربر اجازه می‌دهد تا با سیستم داده¬کاوی از طریق پرس وجو  ارتباط برقرار کند، این جزء به کاربر اجازه می‌دهد تا شمای پایگاه داده یا انبار داده را مرور کرده، الگوهای یافته شده را ارزیابی کرده و الگوها را در فرمهای بصری گوناگون بازنمایی کند.
با انجام فرایند داده¬کاوی، دانش، ارتباط یا اطلاعات سطح بالا از پایگاه داده استخراج می‌شود و قابل مرور از دیدگاههای مختلف خواهد بود. دانش کشف شده در سیستم‌های تصمیم¬یار، کنترل فرایند، مدیریت اطلاعات پردازش پرس و جو  قابل استفاده خواهد بود.

5-1- جایگاه داده¬کاوی در میان علوم مختلف
ریشه‌های داده¬کاوی در میان سه خانواده از علوم، قابل پیگیری می‌باشد.
مهمترین این خانواده‌ها، آمار کلاسیک  می‌باشد. بدون آمار، هیچ داده¬کاوی وجود نخواهد داشت، بطوریکه آمار، اساس اغلب تکنولوژی‌هایی می‌باشد که داده¬کاوی بر روی آنها بنا می‌شود. آمار کلاسیک مفاهیمی مانند تحلیل رگرسیون، توزیع استاندارد، انحراف استاندارد، واریانس، تحلیل خوشه، و فاصله‌های اطمینان را که همه این موارد برای مطالعه داده و ارتباط بین داده‌ها می‌باشد، را در بر می‌گیرد. مطمئناً تحلیل آماری کلاسیک نقش اساسی در تکنیکهای داده¬کاوی ایفاء می‌کند.
دومین خانواده‌ای که داده¬کاوی به آن تعلق دارد هوش مصنوعی می‌باشد. هوش مصنوعی که بر پایه روشهای ابتکاری می‌باشد و با آمار ضدیت دارد، تلاش دارد تا فرایندی مانند فکر انسان، را برای حل مسائل آماری بکار بندد.
چون این رویکرد نیاز به توان محاسباتی بالایی دارد، تا اوایل دهه 1980 عملی نشد. هوش مصنوعی کاربردهای کمی را در حوزه‌های علمی و حکومتی پیدا کرد، امّا نیاز به استفاده از کامپیوترهای بزرگ باعث شد همه افراد نتوانند از تکنیکهای ارائه شده استفاده کنند.
سومین خانواده داده¬کاوی، یادگیری ماشین  می‌باشد، که به مفهوم دقیقتر، اجتماع آمار و هوش مصنوعی می‌باشد. در حالیکه هوش مصنوعی نتوانست موفقیت تجاری کسب کند، یادگیری ماشین در بسیاری از موارد جایگزین آن گردید. از یادگیری ماشین بعنوان تحول هوش مصنوعی یاد شد، چون مخلوطی از روشهای ابتکاری هوش مصنوعی به همراه تحلیل آماری پیشرفت می‌باشد. یادگیری ماشین اجازه می‌دهد تا برنامه‌های کامپیوتری در مورد داده‌ای که آنها مطالعه می‌کنند، مانند برنامه‌هایی که تصمیمات متفاوتی بر مبنای کیفیت داده مطالعه شده می‌گیرند، یادگیری داشته باشند و برای مفاهیم پایه‌ای آن از آمار استفاده می‌کنند و از الگوریتمها و روشهای ابتکاری هوش مصنوعی را برای رسیدن به هدف بهره می‌گیرند.
داده¬کاوی در بسیاری از جهات، سازگاری تکنیکهای یادگیری ماشین با کاربردهای تجاری است. بهترین توصیف از داده¬کاوی بوسیله اجتماع آمار، هوش مصنوعی و یادگیری ماشین بدست می‌آید. این تکنیکها سپس با کمک یکدیگر، برای مطالعه داده و پیداکردن الگوهای نهفته در آنها استفاده می‌شوند.

6-1- قابلیتهای داده¬کاوی
باید توجه داشته باشید که داده¬کاوی یک ابزار جادویی نیست که بتواند در پایگاه داده شما بدنبال الگوهای جالب بگردد و اگر به الگویی جدید برخورد کرد آن را به شما اعلام کند بلکه صرفاً الگوها و روابط بین داده‌ها را به شما اعلام می‌کند بدون توجه به ارزش آنها. بنابراین الگوهایی که به این وسیله کشف می‌شوند باید با جهان واقع تطابق داشته باشند. بعنوان مثال داده¬کاوی می‌تواند با تعیین نرخ درآمدهایی که بطور مثال بین $ 000/50 و $ 000/65 است که برای خرید روزنامه خاصی در میان فروشندگان است تعیین کند که اکثر کالاهای مورد نیاز مردم چه رنجی از قیمت بوده و کدام‌ها هستد؟ به این ترتیب شما می‌توانید از اهداف خرید مردم بدون اینکه فاکتورهایی برای خرید کالاهای خود در نظر بگیرید مطلع شوید؟
برای تضمین بدست آمدن نتایج با معنی لازم است که شما بتوانید داده‌های خود را تحلیل کنید. کیفیت خروجی شما به اطلاعات خارج از پایگاه داده (بعنوان مثال داده‌ای با ارزش که متفاوت از داده‌های نوعی در پایگاه داده شماست) ستونهای ظاهراً بی‌ارتباط یا با ارتباط نزدیک به بقیه پایگاه داده (مانند تاریخ تولید یا انقضای کالا) بستگی نزدیک دارند. الگوریتم بر اساس حساسیتشان به داده‌ها روشهای متفاوتی دارد. امّا غیر عاقلانه است که به محصول داده¬کاوی صرفاً به تمام تصمیم‌گیری‌هایمان تکیه کنیم.
داده¬کاوی بطور اتوماتیک و بدون رهنمایی قادر به کشف راه حل‌ها نیست. شما ترجیحاً به جای بیان یک هدف مبهم مانند «کمک به ارتقاء پاسخ دهی به درخواست‌ها mail من» شما باید از داده¬کاوی برای یافتن خصیصه‌‌های افرادی که
(1)    : به درخواست‌های شما پاسخ می‌دهند.
(2)    : به درخواست‌های شما پاسخ داده و خرید زیادی می‌کنند
استفاده کنید. الگوهایی که داده¬کاوی برای یافتن به این دو هدف استفاده می‌کنند متفاوت است.
اگر چه یک ابزار خوب برای داده¬کاوی شما را از پیچیدگی‌های تکنیکهای آماری راحت می‌سازد امّا به شما برای فهمیدن کارهای ابزاری که انتخاب کرده‌اید و همچنین الگوریتم¬هایی که بر پایه آن کار می‌کند نیازمند است. انتخابی که شما برای ابزار مورد نیاز انجام می‌دهید و بهینه¬سازی‌هایی را که شما انجام می‌دهید در دقت و سرعت کار بسیار تأثیر دارد.

7-1- چرا به داده¬کاوی نیاز داریم؟
1- با توجه به حجم اطلاعات ذخیره شده در پایگاههای داده و نرخ رشد اطلاعات از یک طرف و لزوم استفاده کارآمد از این اطلاعات از طرف دیگر لزوم استفاده از روشهای داده¬کاوی جهت استخراج دانش سودمند اجتناب ناپذیر می‌باشد.
در دو دهه گذشته حجم اطلاعات ذخیره شده بطور غیر قابل تصوری افزایش یافته است و این افزایش همچنان ادامه دارد. طبق برآورد انجام شده حجم داده‌های ذخیره شده در جهان 1 ترابایت می‌باشد و هر 20 سال این مقدار 2 برابر می‌شود. شکل 4-1 روند افزایش حجم داده‌های ذخیره شده می‌باشد.




 
شکل 4-1 : نرخ رشد اطلاعات

2- برای سازماندهی اطلاعات موجود. در سازمانهایی با اطلاعاتی در حد ترابایت تخمین زده شده که بخش کوچکی (حدود 7%) از اطلاعات ذخیره شده معمولاً در تجزیه و تحلیل نقش دارد و مورد استفاده قرار می‌گیرند و دیگر داده‌ها، هیچ موقع تحلیل نمی‌شوند و بدون استفاده ذخیره می‌شوند.
بدین ترتیب مقدار قابل توجهی داده که بدون شک حاوی اطلاعات ارزشمند سازمانی است تا حد زیادی دست نخورده باقی می‌ماند. در محیط تجاری عصر اطلاعات، که هر روز رقابتی‌تر می‌شود می‌توان با استخراج اطلاعات از داده‌های استفاده نشده به تصمیم‌گیری‌های استراتژیک دست یافت.

 


8-1- داده¬کاوی چه کارهایی نمی‌تواند انجام دهد؟
داده¬کاوی فقط یک ابزار است و نه یک عصای جادویی. داده¬کاوی به این معنی نیست که شما راحت به کناری بنشیند و ابزارهای داده¬کاوی همه کار را انجام دهد.
داده¬کاوی نیاز به شناخت داده‌ها و ابزارهای تحلیل و افراد خبره در این زمینه‌ها را از بین نمی‌برد. داده¬کاوی فقط به تحلیلگران برای پیدا کردن الگوها و روابط بین داده‌‌ها کمک می‌کند و در این مورد نیز روابطی که یافته می‌شود باید بوسیله داده‌های واقعی دوباره بررسی و تست گردد.

9-1- کاربردهای داده¬کاوی
داده¬کاوی بخاطر کمک‌های اساسی آن به سرعت در حال محبوبیت است.
سازمانهای زیادی در حال استفاده از داده¬کاوی برای کمک به مدیریت تمام فازهای ارتباط با مشتری شامل بدست آوردن مشتریان جدید، افزایش سود از طریق مشتریان موجود و حفظ مشتریان خوب هستند. با تعیین مشخصات یک مشتری خوب یک شرکت می‌تواند با همان مشخصات اهداف آینده خویش را پیش¬بینی کند. با پرونده¬سازی برای مشتری که یک محصول خاص را خرید می‌نماید این شرکت می‌تواند توجه خود را به مشتریان مشابهی که از این محصول خرید نکرده‌اند معطوف دارد. با پرونده¬سازی برای مشتریانی که این سازمان را ترک کرده‌اند یک شرکت می‌تواند مشتریانی را که خطر رفتن آنها وجود دارد را نگه دارد؛ چرا که نگهداری یک مشتری موجود بسیار کم هزینه¬تر از بدست آوردن یک مشتری جدید است.
داده¬کاوی ارزشهایی را از طریق بررسی یک طیف وسیعی از کارخانه‌ها پیشنهاد می‌کند.
شرکتهای ارتباطات از راه دور و کارت‌های اعتباری دو شاخه بزرگ در استفاده از داده¬کاوی برای تشخیص استفاده کلاه بردارانه از خدمات آنها می‌باشند.
شرکتهای بیمه و درآمد هم علاقمند به استفاده از این تکنولوژی برای کاهش کلاه برداری می‌باشند.
کاربردهای دارویی نواحی مفید دیگری هستند که داده‌کاوی در آنها دست دارد. شرکتهای دارویی در حال کاوش پایگاههای داده بزرگی از ترکیبات شیمیایی و مواد ژنتیکی برای کشف مواد که می‌توانند گزینه خوبی برای ساخت به عنوا دارو باشند.
داده¬کاوی می‌تواند برای تشخیص تأثیر اعمال جراحی، آزمایش‌های دارویی و درمان استفاده گردد.
شرکتهایی که در خرید و فروشهای مالی فعالیت می‌کنند، از داده¬کاوی برای تعیین شاخصه‌های بازار و صنعت برای تشخیص کارایی درآمد استفاده می‌کنند.
خرده¬فروشها از داده¬کاوی برای تصمیم درمورد اینکه کدام محصول در فروشگاه‌ها درآمدزا است به منظور دسترسی به ارتقاء کیفیت کار خود استفاده بیشتری می‌نمایند.
برخی از کاربردهای داده¬کاوی در دنیای واقعی را می‌توان بصورت زیر دسته بندی کرد:
1- خرده¬فروشی: از کاربردهای کلاسیک داده¬کاوی است که می‌توان به موارد زیر اشاره کرد.
•    تعیین الگوهای خرید مشتریان
•    تجزیه  و تحلیل سبد خرید بازار
•    پیشگویی میزان خرید مشتریان از طریق پست (فروش الکترونیکی)
•    فروش و تبلیغ
•    کوپن
2- بانکداری:
•    پیش بینی الگوهای کلاهبرداری از طریق کارتهای اعتباری
•    تشخیص مشتریان ثابت
•    تعیین میزان استفاده از کارتهای اعتباری بر اساس گروههای اجتماعی
3- بیمه:
•    تجزیه و تحلیل دعاوی
•    پیشگویی میزان خرید بیمه¬نامه‌های جدید توسّط مشتریان
4- پزشکی:
•    تعیین نوع رفتار با بیماران و پیشگویی میزان موفقیت اعمال جراحی
•    تعیین میزان موفقیت روشهای درمانی در برخورد با بیماری‌های سخت
5- آنالیز داده DNA و زیست پزشکی (Biomedical):
•    چه ژنهایی با ژنهای دیگر همزمان رخ می‌دهند؟
•    ترتیب عملیات ژنتیکی در مراحل بیماری چیست؟

کاربردهای داده¬کاوی بطور کلی به دو دسته تقسیم می‌شوند:
1-9-1-کاربرد¬های پیش¬بینی کننده :
به این ترتیب عمل می¬کنند که بوسیله استنتاجاتی که از داده¬های ذخیره شده در پایگاه داده بدست می-آورند ، پیش¬بینی¬های مورد انتظار را انجام می¬دهند (¬دسته¬بندی داده¬ها از بارزترین کاربردهای پیش¬بینی کننده در داده¬کاوی است ) . به عنوان مثال از روی نمودار (¬شکل5-1) و مقادیر پارامترهای بارندگی و رطوبت و درجه حرارت سالهای گذشته می توانند پیش¬بینی کنند که سال¬های آتی سال خشک خواهد بود یا مرطوب، پیش¬بینی الگوهای کلاهبرداری از طریق کارتهای اعتباری و ... .

 
شکل5-1 کاربرد پیش¬بینی کننده
2-9-1-کاربردهای توصیف¬کننده :
توصیف¬کننده خصوصیات داده¬هایی است که در پایگاه داده ذخیره شده است. خوشه¬بندی داده¬ها (Clustering) و یافتن قوانین ارتباطی مثالهایی از کازبردهای توصیفی داده¬کاوی هستند . مثلا کاربرد در سوپر مارکت مثل تعیید الگوی خرید مشتریان:
 

10-1- ابزارهای تجاری داده¬کاوی  (Data Mining Commercial Tools):
طی سال‌های گذشته جریان سریعی از تمایل به داده¬کاوی در بازارهای نرم‌افزاری بوجود آمده است. بیشتر کاربران نرم‌افزارهای داده¬کاو با تفکر استفاده تجاری از این نرم‌افزارها، خواهان استفاده از آن شده‌اند. نرم‌افزارهای داده کاو معمولاً سه روش مختلف را برای استفاده از داده¬کاوی بکار می‌برند. 1)اکتشاف. 2)استفاده از مدل‌های پیشگویی. 3)استفاده از آنالیز بحث و جدل.
اکتشاف، فرایند جستجو در داده‌ها است تا الگوهای مخفی موجود در داده‌ها را بدون هیچ ایده از پیش تعیین¬شده‌ای مشخص نماید. در نرم‌افزارهای داده¬کاوی مبتنی بر مدل‌های پیشگویی، الگوهایی که از یک بانک داده کشف می‌شوند، برای پیش¬بینی آینده بکار می‌روند.
 مدل‌های پیش¬بینی به کاربر اجازه می‌دهند تا داده‌های نامشخص را بکار ببرد و این مقادیر نامشخص توسّط نرم‌افزار کشف شود.
در مدلهای جدلی نیز الگوهای یافت شده از داده‌ها برای تعیین مقادیر غیر¬عادی بکار می‌رود. برای تعیین مقادیر غیر-عادی، ابتدا می‌بایست مقادیر عادی شناخته شود تا بر این اساس مقادیر غیرعادی و منحرف شناخته شوند.
نرم‌افزارهای داده¬کاو در حال حاضر از فعالیت کمتری نسبت به سایر نرم‌افزارهای هوشمند برخوردار هستند. با این وجود فعالیت تجاری این نرم‌افزار را می‌توان در شش بخش کلی: دسته¬بندی داده‌ها، برآورد مقادیر نامشخص، پیش¬بینی مقادیر نامشخص، گروه¬بندی تقریبی داده‌ها، خوشه¬بندی داده‌ها و تشریح روابط بین داده‌ها تقسیم کرد.
چند ابزار تجاری کارآمد برای انجام کارهای داده کاوی عبارتند از:
Darwin (Oracle Corp.)
MineSet (Silicon Graphics Inc.-SGI)
Intelligent Miner (IBM Corp.)
SurfAid Analysis (IBM corp.)
Enterprise Miner (SAS Institute Inc.)
Clementine (SPSS Inc.-Integral Solutions)
DMMiner (DBMiner Technology Inc.)
BrainMaler (California Scientific Software)
CART (Salford Systems)
MARS (Salford systems)
Scenario (Cognos Inc.)
 Web Analyst (Megaputer Intelligence Inc.)
Visualizer Workstation (Computer Science Innovation, Inc.)

در مورد ابزارهای موجود برای داده¬کاوی باید به این نکات توجه داشت که:
•    مدل/ معماری مشترکی بین آنها موجود نمی‌باشد.
•    به منابع داده گوناگون و نه لزوماً همه گونه منبعی دسترسی دارند.
•    از یک یا بیشتر الگوریتم DM پشتیبانی می‌نماید.
•    ممکن است از تمام انواع داده پشتیبانی کند یا نکند.
•    قابلیتهای مختلف امّا نه تمام آنها را پشتیبانی می‌نماید.
•    وابسته به بستر کاری است.
•    هر کاربردی ممکن است با یک ابزار کار کند و با ابزار دیگر کار نکند.

11-1- داده کاوی و انبار داده‌ها
1-11-1- تعاریف انبار داده:
مجموعه‌ای از داده‌های موضوع¬گرا، مجتمع، غیر¬فرار و وابسته به زمان که برای پشتیبانی از تصمیم¬گیری‌های مدیریتی مورد استفاده قرار می‌گیرد.
•    نسخه‌ای از داده‌های چند پایگاه داده، که به منظور تسهیل پردازش و پرس و جوهای کاربران طراحی شده است.
•    یک انبار داده، داده‌های دلخواه را از یک یا چند منبع جمع‌آوری کرده و آنها را به موضوعاتی با گروه‌های اطلاعاتی تبدیل می‌کند، سپس آنها را به همراه اطلاعات زمان و تاریخ برای پشتیبانی بهتر از تصمیم¬گیریها ذخیره می‌کند. این سیستم‌ها، دیدهای متعددی از اطلاعات برای طیفهای مختلف کاربران فراهم می‌کند. قدرت این مفهوم در آن است که به کاربران اجازه تحلیلها و پرس و جوهای گوناگون بر روی داده‌هایی می‌دهد که قبل از آن هیچ ارتباطی با  هم نداشتند.
•    انبار داده‌ها پایگاه داده بزرگی است که برای پاسخگویی به سوالات، ایجاد شده است. متناسب با انبار، سوالات مذکور هم با هم فرق می‌کند. انبار می‌تواند در اندازه‌های بزرگ (در حدود گیگابایت) یا کوچکتر باشد. کاربران انبار ممکن است کارکنان داخلی، افراد ناشناس شبکه‌ها و یا هر دو باشند.
•    انبار داده یک پایگاه داده موضوع¬گرا است که به منظور دسترسی‌های گسترده طراحی شده است و ابزارهایی برای برآوردن نیازهای اطلاعاتی مدیران در همه سطوح سازمان آماده می‌کند. به بیان دیگر یک انبار داده به صورتی طراحی می‌شود که کاربران اطلاعات مورد نیاز خود را شناسایی کنند و بتوانند با استفاده از ابزارهای ساده‌ای به آنها دسترسی داشته باشند.
•    یک انبار داده مخزنی از اطلاعات مجتمع شده است که برای انجام پرس و جو و تحلیلها آماده می‌شود.
2-11-1- چهار خصوصیت اصلی انبار داده
چهار خصوصیت اصلی انبار¬داده عبارتند از:
•    موضوع¬گرا: هر انبار داده، داده‌های مرتبط با یک موضوع خاص را در خود نگاه می‌دارد و این داده‌ها را به منظور استخراج  مفاهیم و نتایج خاصی به شکل ویژه سازماندهی می‌کند. بدین ترتیب سرعت جستجوها بسیار بالا خواهد بود. انبار داده برای پاسخگویی به پرسشهای مختلف در مورد یک موضوع خاص بهینه¬سازی می‌شود.
•    مجتمع: در سیستمهای مختلف داده‌ها ممکن است از جنبه‌های مختلفی با هم نامتناسب باشند. مثلا منابع داده در کشورهای مختلف با زمان و تاریخهای مختلف ذخیره شده‌اند. و یا منابعی که از ماشین‌های مختلف هستند در اعداد، حروف و دیگر فیلدها متناسب با محدودیتهای ماشین، سیستم عامل و تطابق با استانداردهای مختلف هستد. با توجه به مختلف بودن منابع انبار داده، قبل از ذخیره سازی آنها در انبار داده برای تأمین یکپارچگی تکنیکهای پاکسازی داده‌ها و مجتمع سازی بکار می‌رود. با توجه به این موضوع که داده‌ها زیر نظر مدیریت واحدی ذخیره¬سازی می‌شوند، داده‌های سازگاری خواهیم داشت که داشتن چنین سازگاری در سایر سیستم‌ها مثل سیستم‌های شبکه‌ای و توزیعی ناممکن است.
•    متغیر با زمان: داده‌ها در انبار داده برای تهیه اطلاعات تاریخی بکار می‌روند. هر ساختار کلیدی در انبار داده شامل عنصر زمان یا همان مهر زمانی است. این مهر زمانی بعنوان کلیدی به سایر جداول عمل می‌کند. در سیستم انبار داده، داده‌ها هرگز به روز درآورده نمی¬شوند، بلکه داده‌های جدید و یا تغییر¬یافته با مهرهای زمانی جدید به انبار اضافه می‌شوند.
•    غیر¬فرار: ‌داده‌های انبار داده همیشه از لحاظ فیزیکی مجزا هستند، و هیچ گاه نیازی  به تغییر و به روز درآوری نخواهند داشت. با توجه به این موضوع، انبار داده مثل پایگاه داده‌های معمولی احتیاجی به پردازش تراکنش، بازگرداندن فرایند و مکانیزم کنترل تصادم ندارند. علاوه بر این نیازی به ایجاد و دسترسی انحصاری به داده‌ها نخواهیم داشت. فقط به دو فعالیت کلیدی احتیاج داریم:
بار کردن داده‌ها
دسترسی به داده‌ها
3-11-1- موارد تفاوت انبار داده و پایگاه داده
•    از لحاظ مدلهای داده: پایگاه‌های داده برای مدل OLAP امکان پردازش تعداد زیادی تراکنش همروند، که اغلب حاوی رکوردهای اندکی هستند را دارد. امّا انبارهای داده برای پردازش OLAP طراحی شده‌اند.
•    از لحاظ عملیات قابل اجراء بر روی آنها: عملیاتی که بر روی پایگاه داده‌ها صورت می‌گیرد، عموماً شامل عملیات به هنگام سازی است. در حالی که عمل خواندن از انبار، عمده عملیات قابل اجراء بر روی انبار داده را تشکیل می‌دهد.
•    از لحاظ مقدار داده: مقدار داده‌های یک پایگاه داده در حدود چند مگابایت تا چند گیگابایت است در حالی که این مقدار در انبار داده در حدود چند گیگابایت تا چند ترابایت است.
•    از لحاظ زمان پرس و جو: انبار داده با استفاده از دو تکنیک خلاصه¬سازی و سلسله مراتبی کردن فیلدها سرعت انجام پرس و جو را بهبود بخشیده است.
 فیلدهای خلاصه¬سازی: می‌توان تمام داده‌های مشابه را در یک آرایه و یک ردیف، و نه در یک جدول قرار داد. به این ترتیب، داده‌های مشابه به سرعت می‌توانند خلاصه¬سازی شوند. اصولاً ساختار بعد این امکان را فراهم کرده است که داده‌ها را بدون تکرار ذخیره نماییم و هرگاه به مشاهده آنها درکنار هم احتیاج داشتیم نیز بدون صرف حافظه و زمان قابل توجهی این امر میسر باشد.
 فیلدهای سلسله مراتبی: ساختار سلسله مراتبی ابعاد در انبار داده‌های مبتنی بر مدل داده چند بعدی، پیاده¬سازی شده است و این امکان را فراهم آورده است که فیلدها بر اساس یک سلسله مراتب منطقی سازماندهی شوند. این امر سرعت پرس و جوها را در انبار بسیار افزایش می‌دهد.
معمولاً داده‌هایی که در داده¬کاوی مورد استفاده قرار می‌گیرند از یک انبار داده استخراج می‌گردند و در یک پایگاه داده   یا مرکز داده   ای ویژه برای داده¬کاوی قرار می‌گیرند.
اگر داده‌های انتخابی جزیی از انبار داده‌ها باشند بسیار مفید است چون بسیاری از اعمالی که برای ساختن انبار داده‌ها انجام می‌گیرد با اعمال مقدماتی داده¬کاوی مشترک است و در نتیجه نیاز به انجام مجدد این اعمال وجود ندارد، از جمله این اعمال پاکسازی داده‌ها می‌باشد.
پایگاه داده مربوط به داده¬کاوی می‌تواند جزیی از سیستم انبار¬داده‌ها باشد و یا می‌تواند یک پایگاه داده جدا باشد. (شکل 6-1)

 
شکل 6-1  داده‌ها از انبار داده‌ها استخراج می‌گردند.
ولی با این حال وجود انباره داده‌ها برای انجام داده¬کاوی شرط لازم نیست و بدون آن هم اگر داده‌ها در یک یا چند پایگاه داده باشند می‌تواند داده¬کاوی را انجام دهیم و بدین منظور فقط کافیست داده‌ها را در یک پایگاه داده جمع‌آوری کنیم و اعمال جامعیت داده‌ها و پاکسازی داده‌ها را روی آن انجام دهیم. این پایگاه داده جدید مثل یک مرکز داده‌ای عمل می‌کند. (شکل 7-1)

¬
شکل 7-1  داده‌ها از چند پایگاه داده استخراج شده‌اند

از سیستمهای Data Warehousing  برای متمرکز ساختن اطلاعات در یک ساختار مرکزی مشخص کمک گرفته می‌شود، به گونه‌ای که تجزیه و تحلیل داده‌ها ساده‌تر گردد. بدین ترتیب ساختار داده‌ها و اطلاعات در چنین سیستم‌هایی به کیفیتی که داده‌ها در بانکهای اطلاعاتی رابطه‌ای نرمال شده هستند، منسجم نخواهد بود. در چنین سیستم‌هایی بر حسب نوع و سیستم بایگانی آنها در زمانی که پردازشی در جریان نباشد از مکان خود بصورت گروهی (Batch) به مرکزیت اطلاعات انتقال داده می‌شوند. البته چنین انتقالی می‌تواند بصورت real time هم صورت بگیرد. برنامه‌ریزی بهینه فرایندهای انتقال اطلاعات در سیستمهای بزرگ انبار¬داده خود یکی از پیچیده‌ترین اموری است که خود تجربه و  تخصص ویژه‌ای نیاز دارد.
انتقال اطلاعات به مرکزیتی که در آن پردازشها انجام می شوند، فقط یکی از فرایندهایی است که در اینجا مطرح می‌شود. موضوع دیگری که درمفهوم انبار داده مطرح می‌شود، آن است که اطلاعات چگونه پردازش شوند تا فرایند پاسخ دهی به پرسشهای تجاری مدیریت و دیگر کاربران بهینه باشد. در این مرحله استفاده از ابزار تجزیه و تحلیل داده‌ها بصورت روی خط (Online) مطرح می‌شود. تجزیه و تحلیل داده‌ها بصورت روی خط (Online Analytical Processing) مفهوم دیگری است که به اختصار OLAP نامیده می‌شود و در انبار¬داده‌ها بطور گسترده بکار می‌رود.

12-1- داده¬کاوی و OLAP
1-12-1- OLAP:
OLAP پاسخی جدید به مشکلات سیستم‌های حمایت از تصمیم‌گیری است. تکنولوژی OLAP تکنولوژی ابزارها و مفاهیمی را ارائه می‌کند که بوسیله آنها امکان انجام یک تحلیل مؤثر و دلخواه بر روی داده‌ها فراهم می‌گردد. OLAP یک تکنیک ساده نیست بلکه مجموعه‌ای از مفاهیم از قبیل سازمان پایگاه داده، نمایش داده و مدل کردن query.
تکنولوژی OLAP نامی است که به طیف گسترده‌ای از تکنیکها اطلاق می‌شود. این تکنیکها شامل روشهایی برای مرتب کردن، پرس و جو کردن و تحلیل کردن داده‌ها است. بطور کلی OLAP عبارتست از: «تحلیل سریع اطلاعات چند بعدی اشتراکی»
تحلیل: منظور از تحلیل آن است که سیستم باید بتواند از عهده هر تحلیل منطقی و آماری که مورد نیاز کاربر باشد، برآید. تحلیل ممکن است شامل تحلیل سری‌های زمانی، تخصیص هزینه، تبدیل واحد پول، جستجوی هدف، query های ساختارهای چند بعدی، تشخیص استثنا، داده¬کاوی و سایر کاربردها باشد. انجام همه این تحلیل‌ها باید برای کاربر نهایی به اندازه کافی ساده باشند.
سریع: منظور از سرعت آن است که سیستم باید بیشتر پاسخ خود را در زمان معقول به کاربر بازگرداند.
تحقیقات اخیر نشان داده است که اگر کاربر نهایی ظرف 30 ثانیه پاسخی دریافت نکند، تصور می‌کند که فرایند دچار شکست شده است. رسیدن به این معیار (یعنی زمان پاسخ کمتر از 30 ثانیه) هنگامی که با حجم زیادی از اطلاعات سروکار داریم کار ساده‌ای نیست. بخصوص وقتی نیاز به query¬های پیچیده و مستقل داریم. OLAP چندین راهکار برای رسیدن به این سرعت ارائه نموده است، که روش‌هایی مثل اختصاصی کردن نوع ذخیره¬سازی داده، شاخص¬بندی، از پیش محاسبه کردن تجمیع‌ها و سخت¬افزارهای ویژه از آن دسته روش‌ها هستند.
OLAP چند بعدی  است. سیستم باید یک شمای مفهومی چند بعدی از داده‌ها را مهیا نماید، یک نیاز اساسی که شامل مفاهیم سلسله مراتبی هم باشد. همچنین باید قابلیت داشتن تعداد دلخواه بعد و سطح تجمیع را فراهم کند.
اشتراکی: به منظور این است که سیستم همه نیازمندیهای امنیتی را برای محرمانه ماندن داده‌ها و برای دسترسی‌های چندگانه خواندن/ نوشتن پیاده¬سازی کند. بخصوص محرمانه ماندن مقوله مشکلی است برای تحلیل مناسب پایگاه داده¬های مربوط به OLAP باید شامل هر مقدار داده که ممکن است باشند. برای محدود کردن دسترسی به داده‌های محرمانه باید یک مراقبت خاص برای دسترسی‌های درست و سطوح دسترسی تعریف شود.
1-12-1- انواع OLAP:
سیستم‌های OLAP بر حسب آنکه از چه بانکهای اطلاعاتی در ساختار خود استفاده می‌کنند، از یکدیگر متمایز می‌شوند.
1. ROLAPS: سیستمهای OLAP که از بانکهای اطلاعاتی رابطه‌ای (Relational) استفاده می‌کنند. از معماری سه لایه برخوردار هستند که در آنها لایه بانک اطلاعاتی و Application Logic از یکدیگر تفکیک می‌شوند.
2. MOLAPS : سیستمهایی که از بانکهای اطلاعاتی چند بعدی استفاده می‌کنند. دارای ساختار معماری دو لایه client/server هستند. در این معماری لایه Application Logic و لایه Access Data بر روی یک سیستم نصب می‌شوند.
3. HOLAP: یک سیستم OLAP ترکیبی تلقی می‌شود. در طراحی سیستمهای HOLAP سعی می‌شود تا با ترکیبی از ویژگیهای هر دو سیستم، تعادلی بین کارایی سیستم و نیازمندیهای آن برقرار شود.
بسیاری فکر می‌کنند که داده¬کاوی و OLAP دو چیز مشابه هستند. در این بخش سعی می‌کنیم این مسئله را بررسی کنیم و همانطور که خواهیم دید این دو ابزارهای کاملاً متفاوت می‌باشند که می‌توانند همدیگر را تکمیل کنند.
OLAP جزیی از ابزارهای تصمیم‌گیری می‌باشد. سیستم‌های سنتی گزارش¬گیری و پایگاه داده‌ای آنچه را که در پایگاه داده بود توضیح می‌دادند، حال آنکه در OLAP هدف بررسی دلیل صحت یک فرضیه است. بدین معنی که کاربر فرضیه‌ای در مورد داده‌ها و روابط بین آنها ارائه می‌کند و سپس بوسیله ابزار ‌‌OLAP با انجام چند Query صحت آن فرضیه را بررسی می‌کند. امّا این روش برای هنگامی که داده‌ها بسیار حجیم بوده و تعداد پارامترها زیاد باشد نمی‌تواند مفید باشد چون حدس روابط بین داده‌ها کار سخت و بررسی صحت آن بسیار زمانبر خواهد بود.
تفاوت داده¬کاوی با OLAP در این است که داده¬کاوی بر خلاف OLAP برای بررسی صحت یک الگوی فرضی استفاده نمی‌شود بلکه خود سعی می‌کند این الگو را کشف کند.
درنتیجه  داده کاوی و OLAP می‌توانند همدیگر را تکمیل کنند و تحلیل گر می‌تواند بوسیله ابزار OLAP یک سری اطلاعات کسب کند که در مرحله داده¬کاوی می‌توان مفید باشد و همچنین الگوها و روابط کشف شده در مرحله داده¬کاوی می‌تواند درست نباشد که با اعمال تغییرات در آنها می‌توان بوسیله OLAP بیشتر بررسی شوند.

13-1- مراحل فرایند کشف دانش از پایگاه داده‌ها
فرایند کشف دانش از پایگاه داده¬ها شامل پنج مرحله است که عبارتند از:
1. انبارش داده
2. انتخاب داده‌ها
3. پاکسازی – پیش پردازش- آماده سازی
4. تبدیل داده‌ها
5. کاوش در داده‌ها (داده¬کاوی)
6. تفسیر نتیجه
همانگونه که مشاهده می‌شود داده¬کاوی یکی از مراحل این فرایند است که بعنوان بخش چهارم آن نقش مهمی در کشف دانش از داده‌ها ایفاء می‌کند.
شکل 1-1 مراحل این فرایند را نشان می‌دهد.
1-13-1- انبارش داده‌ها
وجود اطلاعات صحیح و منسجم یکی از ملزوماتی است که در داده¬کاوی به آن نیازمندیم. اشتباه و عدم وجود اطلاعات صحیح باعث نتیجه‌گیری غلط و در نتیجه اخذ تصمیمات ناصحیح در سازمانها می‌گردد و منتج به نتایج خطرناکی خواهد گردید که نمونه‌های آن کم نیستند.
اکثر سازمانها دچار یک خلا اطلاعاتی  هستند. در اینگونه سازمانها معمولاً سیستم‌های اطلاعاتی در طول زمان و با معماری و مدیریت‌های گوناگون ساخته شده‌اند، بطوریکه سازمان اطلاعاتی یکپارچه و مشخصی مشاهده نمی‌گردد. علاوه بر این برای فرایند داده¬کاوی به اطلاعات خلاصه و مهم در زمینه تصمیم¬گیریهای حیاتی نیازمندیم.
هدف از فرایند انبارش داده‌ها فراهم کردن یک محیط یکپارچه جهت پردازش اطلاعات است. در این فرایند، اطلاعات تحلیلی و موجز در دوره‌های مناسب زمانی سازماندهی و ذخیره می‌شود تا بتوان از آنها در فرایندهای تصمیم‌گیری که از ملزومات آن داده¬کاوی است، استفاده شود. بطور کلی تعریف زیر برای انبار¬داده‌ها ارائه می‌گردد:
انبار داده‌ها، مجموعه‌ای است موضوعی ، مجتمع ، متغییر در زمان ، و پایدار  از داده‌ها که به منظور پشتیبانی از فرایند مدیریت تصمیمی‌گیری مورد استفاده قرار می‌گیرد.
2-13-1- انتخاب داده‌ها
انبار داده‌ها شامل انواع مختلف و گوناگون از داده‌ها است که همه آنها در داده¬کاوی مورد نیاز نیستند. برای فرایند داده¬کاوی باید داده‌های مورد نیاز انتخاب شوند. بعنوان مثال در یک پایگاه داده‌های مربوط به سیستم فروشگاهی، اطلاعاتی در مورد خرید مشتریان، خصوصیات آماری آنها، تأمین کنندگان، خرید، حسابداری و ... وجود دارند. برای تعیین نحوه چیدن قفسه‌ها تنها به داده‌هایی در مورد خرید مشتریان آماری آنها نیاز است. حتی در مواردی نیاز به کاوش در تمام محتویات پایگاه نیست بلکه ممکن است به منظور کاهش هزینه عملیات، نمونه‌هایی از عناصر انتخاب و کاوش شوند.
3-13-1- پاکسازی – پیش پردازش- آماده سازی
یکی از مهمترین مراحل است که در این مرحله داده‌های کثیف از پایگاه داده حذف می‌شوند. داده‌های کثیف داده‌هایی هستند که یکی از شرایط زیر را داشته باشند.
•    داده‌هایی که جا افتاده‌اند. (فیلدهایی که مقادیر آن وارد نشده است)
•    داده‌های اشتباه. (مثل فیلدی که مربوط به سن است و به اشتباه مقدار 723 در آن ذخیره شده است)
•    داده‌هایی که بصورت استاندارد تعیین شده در پایگاه داده ذخیره نشده‌اند (مثل تاریخ که ممکن است با استانداردهای متفاوتی ذخیره گردند)
یکی دیگر از کارهای این مرحله حذف داده‌هایی است که در روند داده کاوی بی‌اهمیت هستند. (مثلا اطلاع در مورد صاحب اتومبیل بودن شخص در روند بررسی تحصیلات وی اهمیتی ندارد)
4-13-1 – تبدیل داده‌ها
در این مرحله، داده¬های سودمند به مدلی انتقال می¬یابند (یا تبدیل می¬شوند) که الگوریتمهای داده¬کاوی بتوانند آنها را تحلیل کنند. مراحل این تبدیل عبارتند از:
•    تجمع: عملیات مربوط به تجمع روی داده‌ها اعمال می‌شود. (مثلا فهرست فروش روزانه به فروش ماهانه تبدیل می‌گردد)
•    عمومی¬سازی: داده¬ها از سطوح پایین ادراکی به سطوح بالاتر ادارکی آورده می‌شوند. (مثلا اگر نام خیابان که خریدار در آن زندگی می‌کنند برای تمام مشتریان در کشور x زندگی می‌کنند ذخیره می‌گردد، نام خیابان به نام شهر تبدیل می‌گردد)
•    نرمال¬سازی: بوسیله نرمال¬سازی مقادیر یک فیلد که ممکن دامنه وسیعی داشته باشند، به مقادیر بین 0 تا 1 تبدیل می‌گردند.
•    ایجاد یک فیلد جدید: دراین مرحله یک فیلد جدید برای کمک به اجرای الگوریتم داده¬کاوی به پایگاه داده اضافه می‌شود.
5-13-1- کاوش در داده‌ها (Data Mining)
وقتی داده‌ها پاکسازی شدند و تبدیلات لازم روی آنها انجام شد، وقتی که ما بدانیم چه نوع وظیفه آموزشی برای برنامه کاربردی ما تعیین می‌شود، فهرستی از متدلوژی‌های کاوش داده‌ها و ابزارهای متناظر بر مبنای کامپیوتر در دسترس خواهند بود. بر پایه ویژگی‌های موجود مسئله و مجموعه داده‌های موجود، باید درباره کاربرد یک یا چند تکنیک کاوش داده‌ها و دانش آشکار¬سازی تصمیم‌گیری شود که این امر می‌تواند بصورت زیر طبقه‌بندی شود:
•    روش¬های آماری:
تکنیک‌های خاص، استنباط Bayesian ، رگوسیون منطقی ، تحلیل ANOVA و مدلهای لگاریتم خطی.
•    تحلیل دسته¬بندی:
شامل تکنیک‌های مشترکی که الگوریتم بخش پذیر، الگوریتم‌های متراکم سازی، دسته بندی بخشی و دسته بندی افزایشی
•    درخت‌های تصمیم و قوانین تصمیم:
مجموعه روش‌های یادگیری استقرائی هستند که اساساً در الکترونیک هوشمند، مصنوعی توسعه یافته هستند. تکنیک‌های ویژه شامل روش CLS، الگوریتم ID3، الگوریتم C4.5 و الگوریتم هرس کردن متناظر.
•    قوانین انجمنی یا ارتباطی :
مجموعه‌ای از متدلوژی‌های نسبتاً جدید را ارائه می‌دهند که شامل الگوریتم‌هایی از قبیل تحلیل سبد بازار، الگوریتم پیشین و الگوهای پیمایش- مسیر
•    شبکه‌های عصبی مصنوعی
که تأکیدی است روی پرسپترون چند لایه با یادگیری پیش انتشار و شبکه‌های kohonen
•     الگوریتم‌های ژنتیکی:
بعنوان متدلوژی برای حل مسائل سخت بهینه¬سازی بسیار مفید هستند.
•    سیستم‌های استنباطی فازی
برپایه تئوری مجموعه‌های فازی و منطق فازی، مدلسازی فازی و تعمیم¬سازی فازی مراحلی هستند که اغلب در فرایند کاوش داده مؤثر هستند.
•    روش‌های تجسم¬سازی n بعدی
که معمولاً در ادبیات بعنوان یک متدلوژی استاندارد کاوش داده‌ها بحث می‌شوند، اگر چه اطلاعات مفید ممکن است با استفاده از این تکنیک‌ها و ابزار آشکار شوند. تجسم¬سازی ویژه کاوش داده هندسی، تکنیک‌هایی بر پایه نشانه نقطه¬گرایی (با گرایش پیکسل) و تسلسلی هستند.

مسلماً این فهرست از تکنیک‌های کاوش داده‌ها و آشکارسازی دانش جامع نبوده و ترتیبی برای هر اولویتی در کاربرد این روش‌ها پیشنهاد نمی‌شود. تکرارپذیری و فعل و انفعالی از ویژگی‌های اساسی این تکنیک‌های کاوش داده هستند. همچنین با تجربه بیشتر در برنامه‌های کاربردی کاوش داده‌ها، خواننده اهمیت عدم تکیه بر روی یک متدلوژی واحد را درک خواهد نمود.
6-13-1- تفسیر نتیجه
اطلاعات استخراج شده با توجه به هدف کاربر، تجزیه و تحلیل و بهترین نتایج معین می‌گردند.
هدف از این مرحله تنها ارائه نتیجه (بصورت منطقی و یا نموداری) نیست، بلکه پالایش اطلاعات ارائه شده به کاربر نیز از اهداف مهم این مرحله است.



فصل 2

     قوانین ارتباطی
 
قوانین ارتباطی  یکی از تکنیک‌های اصلی داده¬کاوی است و احتمالاً مهمترین شکل از کشف و استخراج الگوریتم‌های محلی در سیستم‌های یادگیری  غیر هدایت شده است. این روش از داده¬کاوی شباهت خیلی نزدیکی به فرایندهایی دارد که اغلب مردم، وقتی سعی می‌کنند فرایندهای داده¬کاوی را بفهمند، دربارۀ آن فکر می‌کنند. برای مثال می‌توان به کاوش طلا در یک پایگاه داده وسیع اشاره نمود. در این حالت، طلا یک قاعده است که مطالبی در مورد بعضی چیزهای یک پایگاه داده به شما می‌گوید که تا به حال از آن بی‌خبر بوده‌اید و شاید بطور صریح نمی‌توانید آن را مطرح کنید. این روش تمام الگوهای ممکن جالب در پایگاه داده را ارزیابی می‌کند. در واقع توانایی بالایی است که هیچ نکته نامفهومی را باقی نمی‌گذارد. امّا آن را می‌توان بعنوان یک ضعف هم دید. چرا که کاربر به راحتی می‌تواند با مقدار زیادی از داده‌های جدید سرگردان شود و مسلماً تحلیل سودمند آن، سخت و زمانگیر خواهد بود.
در این بخش ابتدا توضیحی دربارۀ قوانین ارتباطی داده و بعد از آن اصول پایه آن را خواهیم گفت. در ادامه الگوریتم‌ها را دسته¬بندی کرده، در پایان کار دو الگوریتم Apriori و FP Growth را با ذکر مثال توضیح خواهیم داد و در پایان آنها را مقایسه می‌کنیم.
در کنار روش‌های استانداردی مثل تکنیک Apriori برای کاوش قوانین ارتباطی، در فصل بعد از روش‌های داده-کاوی که با کاوش وب (web) و کاوش متن ارتباط دارند، خواهیم پرداخت. دلیل اینکه در این مقاله به این تکنیک‌ها اشاره می‌شود خاصیت مدل¬سازی محلی آن است و بنابراین شباهت بنیادی نزدیکی با قوانین ارتباطی دارد، اگرچه روش‌ها و تکنیک‌های آن متفاوت می‌باشد.

1-2- قوانین ارتباطی:
در زمان تولید قوانین ارتباطی در سال 1993، کار کاوش قوانین ارتباطی مورد توجه زیادی قرار گرفت. امروزه کاوش چنین قوانینی هنوز از محبوبترین روش کشف الگو در KDD است.
بطور کلی یک قانون ارتباطی عبارتی مثل   است، که   و   مجموعه‌ای از آیتم‌ها هستند. معنی چنین قوانینی کاملاً مشهود است: در یک پایگاه داده مثل D از تراکنش‌ها- که هر تراکنش   یک مجموعه از آیتم‌هاست- ،   بیان می‌کند که زمانیکه یک تراکنش T شامل X است، T احتمالاً شامل Y نیز هست. احتمال یا اطمینان قانون بعنوان یک درصد از تراکنش شامل Y است بعلاوه X ، دربارۀ همه تراکنش‌های شامل X. به این معنی که اطمینان قانون می‌تواند بعنوان احتمال شرطی    درک شود.
ایده کاوش قوانین ارتباطی از تحلیل داده‌های سبد خرید  آغاز شد که قوانین شبیه "یک مشتری که محصولات    و   را خرید، محصول y را نیز با احتمال c% خواهد خرید." پیدا می‌شوند. اطلاق پذیری مستقیمشان به مشکلات تجاری شامل قابلیت درک ذاتی آنها، قوانین ارتباطی را یک متد کاوش محبوب ساخت.
مشکل کاوش قوانین ارتباطی ممکن است به دو مرحله تجزیه شود:
1- کشف مجموعه اقلام‌های  بزرگ یعنی مجموعه‌ای از اقلامی که دارای پشتیبانی تراکنشی s، بالاتر از حداقل آستانه از قبل تعیین شده، می‌باشد.
2- به کارگیری مجموعه اقلام بزرگ برای تولید قوانین ارتباطی در پایگاه داده هایی که دارای ضریب اطمینان c ، بالاتر از حداقل آستانه از قبل تعیین شده می‌باشد.
اجرا و کارایی کلی کاوش قوانین ارتباطی اصولاً توسّط مرحله اول صورت می‌گیرد. بعد از اینکه مجموعه اقلام بزرگ شناسایی شدند، قوانین ارتباطی متناظر را می‌توان به روش‌های آسان بدست آورد.

2-2- اصول پایه
1-2-2- شرح مشکل جدی
  یک مجموعه حروف غیر¬تکراری است که اقلام  نامیده می‌شود. یک مجموعه   با   یک مجموعه اقلام K تایی  نامیده می‌شود و یا بطور ساده یک مجموعه اقلام. پایگاه داده D یک چند مجموعه‌ای از زیر مجموعه‌های L است. هر  T یک تراکنش نامیده می‌شود.
هر تراکنش   یک مجموعه اقلام مثل   را حمایت می‌کند اگر   را دارا باشد. یک قانون ارتباطی یک عبارت   است، جایی که X و Y مجموعه اقلام¬ هستند و هیچ اشتراکی با هم ندارند  . بخشی از تراکنش¬های T با حمایت یک مجموعه اقلام مثل X در مورد پایگاه داده D ، درجه حمایت  X نامیده می‌شود؛ یعنی:
 
حمایت یک قانون  اینگونه مشخص می‌شود:
 
درجه اطمینان  یک قانون نیز عبارت است از:
 

اگر بخواهیم تعریفی برای درجه حمایت و درجه اطمینان بیان کنیم خواهیم داشت:
- درجه حمایت: کسری از جمعیت که در یک قاعده، هم مقدم و هم تالی را دارند. در واقع درصدی از تراکنش‌ها که شامل همه اقلام ظاهر شده درمقدم و تالی باشند (تعاریف مقدم و تالی در بخش 6-2 آمده است).
- درجه اطمینان: در یک جمعیت مورد بررسی، کسری از مواردی است که وقتی مقدم قاعده در آنها ظاهر شده است، تالی نیز در آنها وجود دارد.
باید توجه داشت که مقدار درجه اطمینان، با تعویض جای مقدم و تالی در قاعده، ممکن است به شدت تغییر کنند.
هنگام استخراج قوانین ارتباطی تعداد بسیار زیادی از قوانین وجود دارند که باید بصورت نظری و تئوریکی بررسی شوند. در حقیقت تعداد قوانین بطور نمایی با   رشد می‌کنند. چون استخراج چنین مجموعه‌ای از قوانین نه عملی است و نه مطلوب، مجموعه‌های قوانین معمولاً بوسیله حداقل آستانه کیفیت درجه حمایت و درجه اطمینان (به ترتیب با minsupp و minconf اندازه‌گیری می‌شود) محدود شده¬اند . این محدودیت باعث می¬شود که مشکل به قسمت مجزا تقسیم شود : مجموعه اقلام x تکرار شونده است اگر  . هرگاه، {x تکرار شونده است }= F، مجموعه همه مجموعه اقلام تکرار شونده به همراه مقادیر درجه حمایتشان شناخته می شوند، نتیجه‌گیری قوانین ارتباطی دلخواه مستقیم رو به جلو است: برای هر   درجه اطمینان همه قوانین   چک می‌شوند و آنهایی که به minconf نرسیده‌اند، حذف می‌شوند. براساس تعریف بالا، برای تعیین درجه اطمینان هر قانون، دانستن همه مقادیر درجه حمایت زیر مجموعه‌های X کافی است. علم به مقادیر درجه حمایت همه زیر مجموعه‌های X بوسیله خاصیت بستار به سوی پایین  درجه حمایت مجموعه اقلام، تضمین شده است: همه زیر مجموعه‌های مجموعه اقلام تکرار شونده نیز باید تکرار شوند.
در نتیجه کار کاوش قوانین ارتباطی می‌تواند با حداقل آستانه داده شده  ، به مشکل پیدا کردن همه مجموعه اقلام تکرار شونده کاهش داده شود.
2-2-2- پیمایش فضای جستجو
همانطور که توضیح داده شد، ما نیاز به پیدا کردن همه مجموعه‌های اقلام داریم که دارای حداقل حمایت هستند. برای کاربردهای عملی نگاه کردن به همه زیرمجموعه‌های L بخاطر فضای جستجوی بزرگ،  به شکست می‌انجامد. در حقیقت رشد خطی تعداد اقلام هنوز دلالت بر رشد نمایی تعداد مجموعه اقلام دارد که نیاز به بررسی شدن دارند. برای مورد خاص   فضای جستجو در شبکه شکل 1-2 نشان داده شده است.

 
شکل 1-2 شبکه‌ای برای  

مجموعه اقلام‌های تکرار شونده در قسمت بالاتر شکل قرار دارند، درحالی که مجموعه اقلام‌های غیر تکرار شونده در قسمت پایین شکل. اگرچه ما صراحتاً مقادیر درجه حمایت را برای هریک از اقلام‌ها مشخص نکردیم، ما فرض می‌کنیم که خط مرز bold شده مجموعه اقلام‌های تکرار شونده را از مجموع اقلام‌های غیر تکرار شونده جدا می‌کند. وجود چنین مرزی مستقل از هر پایگاه داده خاص D و حداقل حمایت است. وجود این مرز به تنهایی خاصیت بستار بسوی پایین حمایت مجموعه اقلام را تضمین می‌کند.
قاعده اصلی الگوریتم‌های رایج این است که مرز را برای هرس کردن مؤثرتر فضای جستجو بکار می‌گیرند. به مجرد اینکه مرز پیدا شود، ما قادر خواهیم بود که خودمان را محدود کنیم به مشخص کردن مقادیر درجه حمایت مجموعه اقلام‌های بالای مرز و از مجموعه اقلام‌های پایینی صرفنظر کنیم.
طرح:    یک طرح است که همه آیتم‌های  یک به یک به اعداد طبیعی نگاشت می‌کند. حال آیتم‌ها می‌توانند بطور کلی مرتب شده توسّط رابطه   بین اعداد طبیعی، دیده شوند.
بعلاوه برای   داریم   که یک نگاشت به   می‌باشد، حاکی از آیتم n ام از آیتم‌های   بطور صعودی مرتب شده با  .  پیشوند n تایی از یک مجموعه اقلام x با   مشخص شده است با  .کلاس‌های   را داریم،   با {P یک پیشوند از X است و   گره‌های یک درخت می‌شوند. دو گره با یک یال به هم متصل شده‌اند، اگر همه مجموعه اقلام‌های یک کلاس E بتواند با الحاق دو مجموعه اقلام از کلاس والد   تولید شود.  (شکل 2-2)
اگر والد کلاس   از کلاس E شامل حداقل دو مجموعه اقلام تکرار شوند نباشد، E نیز نباید شامل هیچ مجموعه اقلام تکرار شونده باشد. اگر ما با چنین کلاس   در سر راهمان به پایین درخت مواجه شویم، پس ما به مرز جدا کننده مجموعه اقلام تکرار شونده از غیر تکرار شونده‌ها رسیده‌ایم. نیاز به رفتن به آن سوی مرز نداریم و بنابراین E را هرس می‌کنیم و همچنین همه نواده‌های E از فضای جستجو.
زیر برنامه اخیر به ما اجازه می‌دهد تا بطور مؤثری تعداد مجموعه اقلامی که، بر روی جستجویمان برای مرز بین تکرار شونده‌ها و غیر تکرار شونده‌ها ملاقات کردیم، تعیین کنیم. در نهایت، استراتژی واقعی برای جستجو مرز در انتخاب خودمان است . راهکارهای امروزی هر دو راهکار جستجوی اول عرض  (BFS) یا جستجو اول عمق  (DFS) را بکار می‌گیرند. با BFS قبل از شمارش مقادیر حمایت مجموعه اقلام Kتایی، مقادیر حمایت همه مجموعه اقلام (1- K) تایی تعیین می‌شوند. در مقابل، DFS بطور بازگشتی درادامه ساختمان درخت ایجاد شده بالا پایین می‌رود.
 
شکل 2-2 درخت L={1,2,3,4}
3-2-2- مشخص کردن درجه حمایت مجموعه اقلام
بعد از اینکه یک مجموعه اقلام بطور بالقوه تکرار¬شونده بود و برای آنچه ما تصمیم داریم درجه حمایتش مشخص شد، در هنگام پیمایش شبکه یک مجموعه اقلام کاندید یا یک بطور ساده کاندید نامیده می‌شود. یک راه معمول برای مشخص کردن درجه حمایت مجموعه اقلام، مستقیماً شمردن پیدایش آن در پایگاه داده است. برای این هدف، یک شمارنده تنظیم می‌شود و برای هر مجموعه اقلام با صفر مقدار¬دهی اولیه می‌شود. سپس همه تراکنش‌ها مرور می‌شوند و هنگامی که یکی از کاندیدها تشخیص داده شد بعنوان یک زیرمجموعه از یک تراکنش، شمارنده یکی افزایش می‌یابد. معمولاً تولید زیرمجموعه و جستجوی کاندید یکپارچه است و بر روی درخت hash یا یک ساختمان داده مشابه پیاده¬سازی می‌شود. در حقیقت، همه زیر مجموعه‌های هر تراکنش تولید نمی‌شوند و فقط آنهایی تولید می‌شوند که در کاندیدها باشند یا یک پیشوند بطور مشترک با حداقل یکی از کاندیدها داشته باشند.
راهکار دیگر مشخص کردن درجه حمایت کاندیدها توسّط تعیین set intersections است. tid شناسه تراکنش غیر¬تکرار شونده است. برای یک آیتم تنها، tidlist  یک مجموعه از شناسه‌هاست که مطابق با تراکنش‌هایی است که شامل این آیتم هستند. بنابراین tidlistها همچنین برای هر مجموعه اقلام X وجود دارند و با X.tidlist نشان داده می‌شوند. tidlist برای یک کاندید   توسّط   بدست می‌آید. tidlist ها بصورت صعودی مرتب می‌شوند.
نکته این¬که با بافر¬کردن tidlistهای کاندیدهای تکرار شونده بعنوان نتایج میانی، ما بطور بارزی تولید tidlist از کاندیدهای بعدی را سرعت می‌بخشیم. در نهایت درجه حمایت واقعی یک کاندید با تعیین   بدست می‌آید.

3-2- الگوریتم‌های عمومی:
دراین بخش ما بطور مختصر معمولترین و عمومی‌ترین الگوریتم‌ها را توضیح می‌دهیم و روشمند می‌کنیم. ما این کار را با ارجاع به اصول‌ تولید مجموعه اقلام تکرار شونده انجام می‌دهیم که در بخش قبل مشخص کردیم. هدفمان رفتن بر روی جزئیات ریز نیست، امّا اصول بنیادی و تفاوت‌های بین راهکارها را نشان می‌دهد.
1-3-2- دسته¬بندی:
الگوریتم‌هایی که در این مقاله بررسی می‌کنیم در شکل 3-2 منظم شده‌اند. ما هر کدام از الگوریتم‌ها را براساس:
1) استراتژی آن برای پیمایش فضای جستجو
و
2) استراتژی آن برای تعیین مقادیر درجه حمایت مجموعه اقلام
توصیف می‌کنیم. بعلاوه الگوریتم ممکن است برای سرعت بخشیدن بیشتر، بهینه سازی‌های ویژه‌ای را بکار‌گیرد.

 
شکل 3-2 : دسته بندی الگوریتم
2-3-2- BFS و شمارش رویدادها:
معروفترین الگوریتم از این نوع، Apriori است که همچنین خاصیت بستار بسوی پایین از درجه حمایت مجموعه اقلام تولید شده بود. Apriori از این خاصیت زیاد استفاده می‌کند، بوسیله هرس کردن آن کاندیدهایی که یک زیر مجموعه غیر تکرار شونده دارند، قبل از اینکه درجه حمایتشان شمرده شود. این بهینه سازی ممکن می‌شود زیرا BFS تضمین می‌کند که مقادیر درجه حمایت همه زیر مجموعه‌های یک کاندید پیشاپیش شناخته می‌شوند.
Apriori همه کاندیدها را با کاردینالیتی K در یک بار مرور پایگاه داده می‌شمارد. مهمترین بخش، جستجوی کاندیدها در یک تراکنش است. برای این هدف یک ساختاری به نام hashtree تولید می‌کند. این آیتم‌ها درهر تراکنش برای پایین رفتن در hashtree بکار می‌رود. هرگاه به یکی از برگ‌ها رسیدیم، ما یک مجموعه کاندیدهایی که یک پیشوند عادی دارند پیدا کردیم که در تراکنش وجود دارد. سپس این کاندیدها در تراکنش جستجو می‌شوند که قبلاً بعنوان bitmap به رمز درآورده شده بود. دراین مورد موفق شمارنده کاندید در درخت افزایش می‌یابد.
AprioriTID توسعه یافته راهکار Apriori پایه است. به جای متکی بودن بر سطر پایگاه داده AprioriTID نشان می‌دهد هر تراکنش را توسّط کاندیدهای جاری که شامل می‌شود.
با AprioriHybris هر دو راهکار ترکیب شده‌اند. همچنین SETM یک الگوریتم مشابه Apriori (TID) است که برای پیاده سازی بطور مستقیم در SQL اختصاص داده شده است.
DIC تنوع دیگری از الگوریتم Apriori است. DIC فاصله دقیق بین شمارش و تولید کاندیدها را تعدیل بخشیده است. زمانیکه یک کاندید به حداقل حمایت رسید، برابر زمانی است که دیگر تراکنش‌ها دیده نمی‌شوند، DIC شروع به تولید کاندیدهای اضافی براساس آن می‌کند. برای این هدف یک درخت پیشوند یا Prefix-tree بکار می‌گیرد. در مقایسه با hash tree  هر گره- گره برگ یا گره داخلی- از درخت پیشوند دقیقاً تخصیص داده می‌شود به یک کاندید به ترتیب مجموعه اقلام تکرار شونده. در مقایسه با استفاده از hashtree این به این معنی است که هر زمانی که ما به یک گره رسیدیم ما مطمئن می‌شویم که مجموعه اقلام مرتبط با این گروه در تراکنش وجود دارد. علاوه بر این تعیین درجه حمایت به هم قفل کرده (interlocking) و تولید کاندید، تعداد مرور پایگاه داده را کاهش می‌دهد.
3-3-2 - BFS ، دو نیم‌سازی TID-List:
الگوریتم partition یک الگوریتم شبیه Apriori است که set intersections (دو نیم سازی مجموعه) برای تعیین مقادیر درجه حمایت استفاده می‌کند. همانطور که دربالا ذکر شد Apriori مقادیر درجه حمایت همه کاندیدهای (1-k) تایی را قبل از شمارش کاندیدهای kتایی تعیین می‌کند. مشکل این است که در هر قسمت از زمان می‌خواهد از tidlist مجموعه اقلام(1-k) تایی تکرار شونده برای تولید tidlist کاندیدهای kتایی استفاده کند. بطور آشکار اندازه آن نتایج میانی به آسانی مضاف بر محدودیت‌های حافظه فیزیکی ماشین معمول رشد می‌کند. برای غلبه بر این، Patition پایگاه داده را به چندین قسمت کوچک تقسیم می‌کند که مستقلاً رفتار می‌کنند. اندازه هر قسمت کوچک به طریقی انتخاب می‌شود که همه tidlist های میانی در حافظه اصلی قرار گیرند. بعد از تعیین مجموعه اقلام تکرار شونده برای هر قسمت کوچک پایگاه داده، مرور بیرونی لازم است تا تضمین کند که مجموعه اقلام تکرار شونده محلی تکرار شونده سراسری نیز هستند.
4-3-2- DFS و شمارش رویدادها
شمارش رویداد مجموعه¬ کاندیدهایی با سایز منطقی را فرض می‌گیرد. برای هر کدام از آن مجموعه کاندیدها یک مرور پایگاه داده انجام می‌شود. برای مثال Apriori که متکی بر BFS بود پایگاه داده را یکبار برای هر کاندید یا سایز K مرور می‌کرد. هنگام استفاده از DFS مجموعه کاندیدها فقط شامل مجموعه اقلام یکی از گروه های درخت بخش 2-2-2 می‌باشد. بطور آشکارا مرور پایگاه برای هر گره در هزینه‌های فوق‌العاده بالایی نتیجه می‌دهد. ترکیب ساده از DFS با شمارش رویدادها در نتیجه هیچ وابستگی تجربی نیست.
اخیراً یک راهکار جدید به نام FP-Growth تولید شده است. در یک مرحله پیش پردازش FP-Growth یک نمونه بسیار فشرده از تراکنش‌های داده مشتق می‌شود، که FP-tree نامیده می‌شود.
تولید FP-tree با شمارش رویدادها و DFS انجام می‌شود. در مقایسه با راهکارهای پیشین DFS، FP-Growth گره‌های درخت بخش 2-2-2 را ادامه نمی‌دهد، امّا مستقیماً به بعضی قسمت‌های مجموعه اقلام در فضای جستجو پایین می‌رود در مرحله دوم FP-Growth، از FP-tree استفاده می‌شود برای بدست آوردن مقادیر درجه همه مجموعه اقلام تکرار شونده .
5-3-2- DFS و دونیم سازی TID-List
الگوریتم Eclat، DFS را با دو نیم سازی ‌tidlist ترکیب می‌کند. هنگام استفاده از DFS ، این به نگهداشتن tidlist ها بر روی مسیر ریشه به پایین کلاس بررسی شده در حافظه بسنده می‌کند. بعبارت دیگر، تقسیم پایگاه داده بعنوان انجام شده توسّط Partition بیشتر مورد نیاز نیست. Eclat بهینه سازی به نام «دو نیم سازی سریع »  را به خدمت می‌گیرد. هروقت ما tidlist را دو نیم کنیم سپس ما فقط علاقمند به نتیجه‌گیری tidlist هستیم که اگر کاردینالیتی آن به حداقل حمایت برسد. بعبارت دیگر، ما باید متوقف کنیم هر دونیم سازی به مجرد اینکه مطمئن سازد که این به این حد آستانه نخواهد رسید. در ابتدا، Eclat فقط مجموعه اقلام تکرار شونده با سایز بزرگتر و مساوی 3 تولید می‌کرد. ما Eclat را برای کاوش و استخراج مجموعه اقلام 2تایی و 1تایی تکرار شونده نیز تغییر دادیم توسّط فراخوانی آن بر روی کلاسی که شامل مجموعه اقلام 1 تایی به همراه tidlist شان بود.

4-2- الگوریتم Apriori:
الگوریتم Apriori، یک الگوریتم مؤثر برای کاوش مجموعه اقلام تکراری برای قوانین ارتباطی بولی است. الگوریتم Apriori تناوب مجموعه اقلام را در بین چندین تکرار در پایگاه داده محاسبه می‌کند. تکرار i، همه تناوب i مجموعه اقلام را محاسبه می‌کند (یعنی مجموعه اقلامی با i عنصر). هر تکرار دو مرحله دارد:
تولید کاندید   و
انتخاب و شمارش کاندید
1-4-2- مفاهیم کلیدی:
•    مجموعه اقلام تکرارشونده (Frequent Itemset) : مجموعه‌ای از اقلام (item) که کمترین حمایت  را دارند.  (نشان داده می‌شود توسّط Li برایith-Itemset )
•    خصوصیت (Apriori Property) Apriori : هر زیر مجموعه از مجموعه اقلام تکرارشونده باید تکرارشونده باشند.
•    عمل الحاق: برای پیدا کردن Lk ، یک مجموعه از مجموعه اقلام kتایی کاندید، با الحاق کردن Lk-1  با خودش تولید می‌شود.
2-4-2- پیاده سازی الگوریتم Apriori:
1- مجموعه تک عضوی‌هایی که بیش از آستانه تکرار شده‌اند، را استخراج و L1 می‌نامیم.
2- از مجموعه L1 ، مجموعه دوعضویهایی که بیش از آستانه تکرار شده‌اند انتخاب و L2 می‌نامیم.
3- مرحله 2 برای پیدا کردن مجموعه‌های سه عضوی از مجموعه دوعضویها و مجموعه‌ چهار عضوی‌ها از مجموعه سه عضوی تا مجموعه k عضوی تولید شود، تکرار شود.
چون در این الگوریتم برای یافتن هر مجموعه کل پایگاه داده باید خوانده شود، برای افزایش کارایی از خصیصه Apriori استفاده می‌شود که بکارگیری این خصیصه در دو مرحله صورت می‌گیرد.
مرحله اول- الحاقی: برای استخراج k عضوی که به کررات با هم تکرار شده‌اند، ابتدا با استفاده از مجموعه 1- k عضوی‌هایی که به کررات تکرار شده‌اند، تمام حالات k عضوی ممکن را ایجاد می‌کنیم.
مرحله دوم- هرس کردن: در این مرحله تعدادی از عناصر مجموعه حذف خواهند شد و اعضای حذف شده، اعضایی هستند که خصوصیت Apriori رانقض می‌کنند.
شبه کد الگوریتم Apriori به طریق زیر است:
CK: Candidate item set of size k;
LK: frequent item set of size k;
L1: {frequent item set};
 
              begin
          Ck+1= candidates generated from Lk ;
          For each transaction t in database do
                 increment the cont of all candidates in ck+1 that are contained in t.
          Lk+1= Candidates in ck+1 whith min – support
      end
retum Uk Lk,
برای تولید کاندیدها (Ck+1) ، دو گام باید انجام داد که قبلاً نیز به آن اشاره شد.
1-    الحاق Lk با خودش :
2-    هرس کردن :
برای درک الگوریتم، یک مثال کاربردی خواهیم زد.
مثال: فرض کنیم که در یک سوپر مارکت پایگاه داده لیست فروش بصورت زیر باشد (بجای اینکه از اسامی اجناس استفاده کنیم، از حروف   استفاده کردیم.
فرض برآن است که عدد حداقل حمایت 2 است. (بعبارت دیگر  )

List of Items    Transaction ID
{I1, I2, I5}    T1
{I2, I4}    T2
{I2, I3}    T3
{I1, I2, I4}    T4
{I1, I3}    T5
{I2, I3}    T6
{I1, I3}    T7
{I1, I2, I3, I5}    T8
{I1, I2, I3}    T9
همچنین حداقل اطمینان مورد نیاز، 70% است.


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



گام 1: تولید الگوی تکراری مجموعه اقلام تکراری 1 تایی.

 
همانطور که مشاهده می‌کنید، در دور اول الگوریتم، هر آیتم یک عضو از مجموعه کاندید است.
گام 2: تولید الگوریتم تکراری مجموعه اقلام 2 تایی:
برای پیداکردن مجموعه اقلام تکراری 2 تایی، L2، الگوریتم از الحاق L1 ، با خودش (L1 join L1) استفاده می‌کند تا یک مجموعه کاندید از مجموعه اقلام 2تایی، C2 ، تولید کند. سپس تراکنش‌ها در D (پایگاه داده مثال) مرور می‌شوند و عدد حمایت برای هر مجموعه اقلام کاندید در C2 را حساب می‌کند (جدول میانی در شکل) سپس مجموعه اقلام 2 تایی تکراری، L2، تعیین می شود، شامل مجموعه اقلام 2تایی کاندید در C2 که حداقل حمایت را داشتند.
 

نکته: ما هنوز از خصوصیت Apriori استفاده نکردیم.
گام 3 : تولید الگوی تکرار مجموعه اقلام 3 تایی
 
تولید مجموعه مجموعه اقلام 3تایی کاندید، C3 ، با استفاده از خصوصیت Apriori  سرو کار دارد. به منظور پیداکردن C3، L2 L2 join را محاسبه می‌کنیم. پس خواهیم داشت:
C3=L2 join L2 = {{I1,I2,I3},{I1,I2,I5},{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}
حال مرحله join کامل شد و مرحله هرس کردن برای کاهش اندازه C3 استفاده خواهد شد. مرحله هرس کردن کمک می‌کند تا از محاسبات سنگین بخاطر Ck بزرگ، جلوگیری شود.
بر¬اساس خصوصیت Apriori، همه زیر مجموعه‌های مجموعه اقلام تکراری نیز باید تکرار شوند. ما می‌توانیم تعیین کنیم که چهار کاندید آخر امکان تکرار شدن ندارند. چگونه؟
برای مثال، {I1,I2,I3} را در نظر بگیرید. زیر مجموعه‌های آیتم‌های دوتایی از این عبارتند از: {I1,I2} و {I1,I3} و {I2,I3} . چون همه زیر مجموعه‌های 2تایی از {I1,I2,I3} اعضای L2 هستند، پس ما {I1,I2,I3} را در C3 نگه می‌داریم.
حال مثال دیگری مثل {I2,I3,I5} را در نظر بگیرید که نشان می‌دهد عمل هرس روی آن انجام گرفته است. زیر مجموعه‌های 2تایی عبارتند از: {I2,I3} و {I2,I5} و {I3,I5} . امّا همانطور که مشاهده می‌کنید {I3,I5} عضو L2 نیستند و بنابراین این تکرار نشده است و خصوصیت Apriori را نقص کرده است. بنابراین، C3= {{I1,I2,I3},{I1,I2,I3}} بعد از چک کردن همه اعضای نتیجه الحاق برای هرس کردن است.
حال تراکنش‌ها در D مرور می‌شوند تا L3 مشخص شود. شامل مجموعه اقلام 3 تایی کاندید در C3 دارای حداقل حمایت است.
گام 4: تولید الگوی تکراری مجموعه اقلام 4تایی:
الگوریتم برای تولید مجموعه کاندید اقلام 4 تایی، C4، از L3 join L3 استفاده می‌کند. اگرچه، نتایج الحاق در {{I1,I2,I3,I5}} است، این مجموعه اقلام هرس می‌شوند چون زیر مجموعه‌اش {{I2,I3,I5}} تکرار نشده است. بنابراین   و الگوریتم پایان می‌یابد با داشتن همه ایتم‌های تکرارشونده. این پایان الگوریتم Apriori است. (شکل 5-2)
و حالا از این مجموعه اقلام تکراری برای تولید قوانین ارتباطی قوی استفاده خواهیم کرد (جایی که قوانین ارتباطی قوی هر دوی حداقل حمایت و حداقل اطمینان را قانع می‌کند.)
 
شکل4-2 پایان الگوریتم Apriori
گام 5: تولید قوانین ارتباطی از جموعه اقلام تکراری:
زیربرنامه آن به اینگونه است:
for each frequent item set "I" , generate all nonempty subsets of "I"
for every nonempty subset S of I, output the rule "S  (I-S)"  if
support _ count (I) / support _ count (S) > = min-conf where min-conf is minimum confidence threshold.

به مثال بر می‌گردیم:
ما داشتیم:
L= {{I1},{I2},{I3},{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I3},
      {I1,I2,I3},{I1,I2,I5}}.
حال I={I1,I2,I5} در نظر بگیرید، همه زیر مجموعه‌های غیر تهی آن عبارتند از:
{I1,I2},{I1,I5},{I2,I5},{I1},{I2},{5}.
آستانه حداقل اطمینان 70% است. قوانین ارتباطی نتیجه‌گیری شده در زیر نشان داده شده‌اند:
-R1:I1^I2 I5  
  confidence = Sc {I1,I2,I5} / {I1,I2}= 2/4 = 50%
پس R1   مورد قبول نیست.
-R2:I1^I5 I2  
  confidence = Sc {I1,I2,I5} / Sc {I1,I5}= 2/2 = 100%
R2 مورد قبول است.
-R3:I2^I5 I1  
  confidence = Sc {I1,I2,I5} / Sc {I2,I5}= 2/2 = 100%
پس R3   مورد قبول است.
-R4:I1 I2^I5  
  confidence = Sc {I1,I2,I5} / Sc {I1}= 2/6 = 33%
پس R4   مورد قبول نیست.
-R5:I2I1^I5  
  confidence = Sc {I1,I2,I5} / Sc {I2}= 2/7 =29%
پس R5   مورد قبول نیست.
-R6:I5I1^I2
  confidence = Sc {I1,I2,I5} / {I5}= 2/2 = 100%
پس R6   مورد قبول است.
و به این طریق ما سه قانون ارتباطی قوی داریم .
3-4-2- معایب Apriori و رفع آنها:
آیا Apriori به اندازه کافی سریع هست؟ هسته الگوریتم Apriori عبارتست از:
1- استفاده از مجموع اقلام (k-1) تای تکراری برای تولید مجموعه اقلام k تایی تکراری کاندید.
2- استفاده از مرور پایگاه داده و شناسایی الگو برای جمع‌آوری شمارش¬ها برای مجموعه اقلام کاندید.
عامل کند¬کننده Apriori چیست؟ تولید کاندید. به عبارت دیگر دو عیب وجود دارد:
1-    مجموعه‌های کاندید بزرگ:
برای مثال اگر تعداد مجموعه اقلام 1 تایی تکرارشونده 104  باشد، 107 مجموعه اقلام 2 تایی کاندید تولید خواهد شد. همچنین برای پیدا کرد یک الگوی تکرار از سایز 100، بعنوان مثال {a1, a2,...,a100} ، نیاز به تولید 2100 (که تقریباً برابر 1030 است) کاندید می‌باشد.
2-    مرورهای متعدد از پایگاه داده:
اگر طول بلندترین الگو n باشد، نیاز به n+1  مرور خواهد بود.

برای بهبود کاراریی Apriori چندین روش وجود دارد:
1- شمارش مجموعه اقلام براساس hash (تکنیک Hash)
2- کاهش تراکنش‌ها  
3- Partitioning

4- نمونه برداری  
5- شمارش مجموعه اقلام بصورت پویا
که از توضیح آنها در این مقاله صرفنظر می‌کنیم.

5-2- الگوریتم رشد الگوی تکرار شونده(FP-growth)
اطلاعات تراکنش‌های پایگاه داده قسمت مهمی برای کاوش الگوی تکرار می‌باشد. بنابراین اگر ما می‌توانیم اطلاعات را برای کاهش الگوی تکرار خارج ‌کنیم و در یک ساختار فشرده ذخیره کنیم، سپس این ممکن کاوش الگوی تکرار را آسان کند. با این ایده، در این قسمت، ما یک ساختمان داده فشرده را به نام FP-tree توسعه خواهیم داد که اطلاعات کامل ولی نه زائد برای کاوش الگوی تکرار فشرده می‌شود.
در این روش یک پایگاه داده بزرگ در ساختار فشرده درخت الگو تکرار فشرده می شود و به این ترتیب از مرورهای پرهزینه پایگاه داده جلوگیری می‌شود. این روش از طریق متدلوژی تقسیم و حل عمل می‌کند. همچنین از تولید کاندید نیز خودداری می‌کند.
مثال: مثال قبل را با این روش بررسی می‌کنیم.
آستانه حداقل حمایت برابر 2 است.
List of Items    Transaction ID
{I1, I2, I5}    T1
{I2, I4}    T2
{I2, I3}    T3
{I1, I2, I4}    T4
{I1, I3}    T5
{I2, I3}    T6
{I1, I3}    T7
{I1, I2, I3, I5}    T8
{I1, I2, I3}    T9

 اولین مرور پایگاه داده مثل الگوریتم Apriori است، که مجموعه مجموعه اقلام 1 تایی و عدد حمایتشان نتیجه می‌دهد. سپس آیتم‌های تکرار بر¬اساس عدد حمایتشان بصورت نزولی مرتب می‌شوند: نام این مجموعه را L می‌نامیم.
L= {I2:7  , I1:6  ,I3:6  ,I4:2  ,I5:2}



ساخت درخت الگوی تکرار
 حال درخت الگوی تکرار را می‌سازیم. درابتدا ریشه درخت را ایجاد می‌کنیم و آنرا Null می نامیم.
پایگاه داده  Dرا برای بار دوم مرور می‌کنیم برای هر تراکنش یک شاخه ایجاد می‌گردد هر آیتم در هر تراکنش تبدیل به یک گره می‌شود. هنگام برخورد به گره مشابه در یک تراکنش دیگر، فقط عدد حمایت آن گره و پیشوندهایش را افزایش می‌دهیم.
برای اولین تراکنش {I1,I2,I5} چنین شاخه‌ای ایجاد می‌شود:
 

اینکه چرا ابتدا گره I2 و سپس I1 و نهایتاً I5 در درخت قرار گرفتند، بخاطر اینست که در مجموعه L، اول I2 و بعد I1 و سپس I5 آمده است (یعنی بر اساس عدد حمایتشان). وقتی تراکنش دوم را بررسی می‌کنیم، چون گره I2 قبلا ً ایجاد شده یکی به آن اضافه و I4 را به فرزند آن اضافه می‌کنیم.
 

وقتی تمام تراکنش‌‌ها مرور شدند، درخت الگوی تکرار مانند شکل 6-2 می‌شود.
برای سهولت پیمایش درخت، جدول سرآیند آیتم  ساخته می‌شود که هر آیتم اشاره¬گری است به پیدایش در درخت از یک زنجیر اتصالات گره.
و به این طریق، مشکل کاوش الگوهای تکرار در پایگاه داده تبدیل به کاوش درخت الگوی تکرار شد.
   
5-2 درخت الگوی تکرار
کاوش درخت الگوی تکرار باایجاد پایگاه‌های الگو شرطی (جدول 1-2)
برای ساخت پایگاه الگوی شرطی   ابتدا گره هایی که دارای پیشوند هستند را در نظر می‌گیریم. پس نگاه می‌کنیم که در چند شاخه گره مورد نظر بوجود آمده است (گره بعنوان پسوند در نظر گرفته می‌شود). بعنوان مثال با گره I5 شروع می‌کنیم. I5 در دو شاخه بوجود آمده است که عبارتند از: {I1 I2 I3 I5:1} , {I2 I1 I5:1}
سپس بادر نظر گرفتن I5 بعنوان پسوند، دو مسیر پیشوند بوجود می‌آید که {I2 I1:1} و {I2 I1 I3: 1} هستند که این دو در پایگاه الگوی شرطی قرار می‌گیرند.
سپس I2 , I1 در FP-tree شرطی   قرار می‌گیرند، ولی I3 قرار نمی‌گیرد. چون I3 به حداقل حمایت نرسیده است.
2= 1+1 = عدد حمایت در پایگاه الگو شرطی : I1 برای
2= 1+1 = عدد حمایت در پایگاه الگو شرطی : I2 برای
1= عدد حمایت در پایگاه الگو شرطی : I3 برای
بنابراین عدد حمایت برای I3 کمتر از حداقل حمایت مورد نظر است که در مسئله 2 بود.
با بررسی کردن همه ترکیب‌های ممکن از FP-tree, I5 شرطی، همه الگوهای تکرار متناسب با پسوند I5 تولید می‌شوند.
چنین روالی را برای پسوندهای I1 , I4 , I3 در پیش می‌گیریم.
جدول کامل شده در جدول 2-1 است.
نکته اینکه I2 نمی‌تواند بعنوان پسوند در نظر گرفته شود چون هیچ پیشوندی ندارد.

جدول 1-2 کاوش FP- Tree با ایجاد پایگاه‌های الگو شرطی
Freruent pattern generated    Conditional FP- tree    Conditional base pattern    Item
I2I5:2 , I1I5:2 , I2I1I5:2    < I2:2 , I1:2>    {(I2 I1:1)  , (I2I1I3:1)}    I5
I2 I4:2    < I2: 2>    {(I2I1:1) , (I2:1)}    I4
I2I3 : 4 , I1I3:4 , I2I1I3:2    <I2:4 , I1:2>, <I1:2>    {(I2 I1:2), (I2:2), (I1:2)}    I3
I2I1:4    < I2:4>    {(I2:4)}    I1

1-5-2 چرا رشد الگوی تکرار سریع است؟
مطالعات کارایی نشان می‌دهد که رشد الگوی تکرار خیلی سریعتر از Apriori  است. به این دلیل که:
1- تولید کاندید و تست کاندید وجود ندارد.
2- از ساختمان داده فشرده‌ای استفاده می‌کند.
3- مرور مکرر پایگاه داده را حذف کرده است. (حداکثر 2 بار مرور)
4- عمل اصلی شمارش و ساخت FP-tree است.

6-2-مقایسه دوالگوریتم Apriori  و FD Growth
دو الگوریتم استخراج الگوی تکرار شونده در جاوا پیاده سازی شده‌اند و بر روی چندین مجموعه داده تست شده است. مشخصات platform مورد استفاده برای تست این بود:
Windows 2000, 256 MBRAM , Pentium4 1.7GHz processor  
برای بدست آوردن نتایج واقعیتر Microsoft SQL 2000 Server استفاده شد و با واسط ODBC استاندارد مورد دستیابی بودند. برای مطالعه کارایی و الگوریتم ها، مجموعه‌های داده با 10000 تا 500000 تراکنش تولید شدند، و فاکتورهای حمایت بین 5% و 40% استفاده شدند. هر تراکنش ممکن است شامل بیش از یک مجموعه اقلام تکرار شونده باشد.  تعداد اقلام ها در تراکنش ممکن است تغییر کند، همچنین اندازه مجموعه اقلام تکرار شونده. تعداد اقلام در یک مجموعه اقلام نیز متغیر است. با در نظر گرفتن این ملاحظات، مجموعه‌های داده تولید شده به تعداد اقلام در یک تراکنش،  تعداد اقلام در یک مجموعه اقلام تکرار شونده و غیره بستگی دارد.
پارامترهای ضروری برای تولید تست مجموعه‌های داده در جدول 2-2 مشخص شده است.

تعداد تراکنش¬ها     |D|
اندازه میانگین تراکنش¬ها     |L|
تعداد مجموعه اقلام بزرگ بالقوه بزرگ     |L|
تعداد اقلام     |N|
جدول2-2 : پارامترها
تست مجموعه داده برای تعداد اقلام N=100 ایجاد شده است و ماکسیم تعداد مجموعه اقلام تکرار شونده |L|=10 , |L|=3000 انتخاب شده است.
بعضی از نتایج مقایسه بین FP- growth , Apriori برای عامل حمایت از 5%  و برای مجموعه‌های داده متفاوت در جدول 2-2 نشان داده شده است.
جدول 3-2 نشان می‌دهد که زمان اجرای الگوریتم با اندازه مجموعه داده رشد می‌کند. بهترین کارایی توسّط الگوریتم FP- Growth بدست آمده است. شکل 6-2 نشان می‌دهد که زمان اجرای برای FP- growth برای یک مجموعه داده دقیق ثابت است وقتی که فاکتور حمایت از 40% به 5% کاهش می‌یابد، در حالی که در زمان مشابه، زمان اجرای الگوریتم Apriori بطور شگرفی افزایش می‌یابد.


زمان اجراء (sec)    تراکنش ها(k)
FD- growth    Apriori    
32/2    94/13    10
98/3    98/21    20
23/8    37/48    30
10/12    50/66    40
50/19    65/107    50
90/37    30/198    80
00/55    40/1471    110
90/98    20/3097    150
70/152    60/5320    190
00/284    80/9904    300
10/458    20/17259    400
20/610    60/20262    520
جدول 3-2 : نتایج برای فاکتور حمایت 5%
برای یک درجه حمایت از 30% یا بالاتر و مجموعه داده‌های 40000 تراکنش، الگوریتم Apriori کارایی بهتری دارد نسبت به الگوریم .FP-growth امّا برای درجه حمایت 20% یا کمتر کارایی اش بطور شگرفی کاهش می‌یابد. بنابراین، برای درجه حمایت 5% زمان اجراء برای الگوریتم Apriori سه برابر طولانی تر از زمان اجراء الگوریتم FP-growth است.
زمان اجراء برای دو الگوریتم برای مقادیر مختلف درجه حمایت بر روی مجموعه داده‌ها با 150000 تراکنش در جدول 4-2 نشان داده شده است. متذکر می‌شویم که الگوریتم Apriori کارایی کمتری نسبت به FP-growth دارد.
شکل 7-2 زمان اجرای الگوریتم Apriori برای مقادیر مختلف درجه حمایت بر روی مجموعه داده‌های با سایر مختلف را نشان می‌دهد. از اینجا ما نتیجه می‌گیریم که کارایی الگوریتم تحت تاثیر اندازه مجموعه داده‌ها و درجه حمایت قرار گرفته است.
 
شکل 6-2 : اندازه¬گیری کارکرد درجه حمایت برای پایگاه داده D1 40K

شکل 8-2 زمان اجرای الگوریتم FP-growth برای مقادیر مختلف درجه حمایت بر روی مجموعه داده های با سایر متفاوت را نشان می‌دهد. از اینجا نتیجه می‌گیریم که کارایی الگوریتم فقط به اندازه مجموعه داده‌ها وابسته است، درجه حمایت کوچکترین تاثیر را دارد.

زمان اجراء (sec)    (%) درجه حمایت
FP-growth    Apriori    
60/174    20/3097    5
80/170    10/2186    10
20/170    90/1308    15
90/170    60/1305    20
30/171    50/870    25
50/172    00/875    30
80/169    00/440    35
20/175    60/441    40
جدول 4-2 : نتایج برای D1 I50K با درجه حمایت

 
شکل 7-2 : اندازه¬گیری الگوریتم  Apriori با transaction / support


 
شکل 8-2 : اندازه¬گیری الگوریتم FP-growth با transaction / support





7-2-تحليل ارتباطات:
تحليل ارتباط يک رهيافت توصيفي براي اکتشاف داده است که مي¬تواند به مشخص¬سازي ارتباطات ميان مقادير در پايگاه¬ داده کمک نمايد. دو رهيافت عام براي رسيدن به تحليل ارتباطي اکتشاف ارتباطي و اکتشاف توالي مي¬باشد. اکتشاف ارتباطات قوانيني را در مورد مواردي را که بايد با هم در يک رويداد ظاهر شوند مانند تراکنش خرید می¬یابد. تحليل سبد عرضه يک نمونه شناخته شده از کشف ارتباط مي¬باشد. کشف توالي بسيار شبيه کشف ارتباط است با توجه به اين نکته که در اينجا توالي يک ارتباط است که در طول يک بازه زماني صورت مي¬¬گيرد.
ارتباطات به صورت A=>B نوشته مي شود که به A مقدم يا طرف سمت چپ و به B تالي يا طرف سمت راست مي¬گويند. براي مثال در قانون ارتباطي "اگر مردم يک چکش بخرند آنگاه مي¬توانند ميخ بخرند" جمله مقدم "خريد چکش" و جمله تالي "خريد ميخ" مي¬باشد.
براحتي ميتوان نسبت تراکنشهايي را که شامل مورد يا ليستي ازموارد خاص مي¬باشد با شمردن آنها تعيين کرد (که در اینجا موارد ميخ¬ها و چکش¬ها مي¬باشد) را تعيين کرد. تعداد موجود از يک نوع ارتباط خاص که در يک پايگاه داده به نظر مي¬رسد را موجودي يا شيوع آن مورد مي¬گويند. اگر براي مثال گفته شود که از هر 1000 تراکنش 15 تاي آن شامل "ميخ و چکش" مي¬باشد موجودي اين ارتباط 1.5% خواهد بود. يک موجودي کم (مثلا يک در ميليون) مي تواند بيانگر اين باشد که آن ارتباط خاص در پايگاه داده چندان مهم نيست.
براي کشف قوانين معنا¬دار ما بايد به فراواني متناسب دفعات اتفاق موارد و ترکيباتشان نيز بنگريم. با داشتن تعداد دفعات اتفاق مورد A مورد B چند بار اتفاق مي¬افتد؟ به عبارت ديگر سوال اين است که ببينيم "هنگامي که مردم يک چکش مي¬خرند چه تعداد از اين افراد ميخ هم مي¬خرند؟". عبارت ديگر براي اين پيش بيني شرطي اطمينان نام دارد.
فرض کنيد پايگاه داده فرضي¬مان رابه صورت زير و با جزئيات بيشتر براي بيان اين مفاهيم در نظر بگيريم:
تمام تراکنشهاي سخت افزار: 1000
تعداد تراکنشهايي که شامل "چکش" مي¬باشد: 50
تعداد تراکنشهايي که شامل "ميخ" مي¬باشد: 80
تعداد تراکنشهايي که شامل "تخته " مي¬باشد: 20
تعداد تراکنشهايي که شامل " ميخ و چکش" مي¬باشد: 15
تعداد تراکنشهايي که شامل " ميخ و تخته " مي¬باشد: 10
تعداد تراکنشهايي که شامل " چکش و تخته" مي¬باشد: 10
تعداد تراکنشهايي که شامل " چکش و تخته و ميخ " مي¬باشد: 5
حال قادر به محاسبه¬ايم:
موجودي "ميخ و چکش"= 1.5%
موجودي     " ميخ و چکش وتخته"= 0.5%
درصد اطمينان "چکش=>ميخ" = 30%
درصد اطمينان " ميخ=> چکش" = 19%
درصد اطمينان " چکش و ميخ=>تخته" = 33%
درصد اطمينان " تخته=> چکش و ميخ " = 25%

بنابراين ما مي¬بينيم که احتمال اينکه يک خرنده چکش ميخ هم بخرد(30%) بيشتر از احتمال آن است که فردي که ميخ مي¬خرد چکش هم بخرد(19%). ارتباط چکش و ميخ به اندازه¬اي بزرگ است که يک قانون با معني باشد.
الگوريتمهاي ارتباط اين قوانين را با معادل مرتب¬سازي داده هنگام شمارش دفعاتي که مي¬توانند درصد اطمينان و موجودي را محاسبه كنند مي¬يابد. اثراتي كه هر يك از اين قوانين مي¬توانند داشته باشند يكي از معيارهاي تفاوت اين الگوريتم¬هاست. اين معيار مهم است زيرا كه نتايج تركيبي بسيار زيادي از تعداد بي¬شماري از قوانين بدست مي¬آيد حتي براي سبد¬هاي خريد. برخي از الگوريتمها يك پايگاه داده از قوانين، فاكتورهاي ايمن، و فراهم آوردن امكان جستجو (براي مثال تمام ارتباطاتي كه در آن كلمه بستني در قوانين به عنوان نتيجه آمده و فاكتوري برابر 80%را دارند نشان بده) را ايجاد مي نمايند.
اغلب تصميم¬گيري در مورد كار با قوانيني كه شما كشف كرده¬ايد دشوار است. به عنوان مثال در يك نقشه خريد براي مشتريان در يك فروشگاه قراردادن تمام اجناس مرتبط منطقي به صورت فيزيكي در كنار يكديگر ممكن است ارزش كامل سبد خريد را كاهش دهد – مشتريان ممكن است در مجموع ارزش كمتري خريد كنند چون آنها بر خلاف نقشه خريد مورد نظر شما در حين راه رفتن در مغازه اجناس مورد دلخواه خود را خريد مي-كنند. در چنين حالتي تقريب و تحليل ارتباطات معمولا براي بدست آوردن هر گونه سودي از قوانين مرتبط با هم مورد نياز خواهد بود.
روشهاي گرافيكي مي¬توانند در نمايش ساختار ارتباطات نقش داشته باشند. در شكل زير هر يك از دواير يك مقدار يا يك رويداد را نمايش مي¬دهد. خطوط ارتباطي ميان اين دايره¬ها يك ارتباط را نشان مي¬دهند. خطوط كلفت¬تر ارتباطات قوي¬تر و فراوان¬تري را نمايش مي¬دهند.

 




فصل سوم

     وب¬کاوی و متن¬کاوی
 
1-3-کاوش وب (وب¬کاری)
در یک محیط اطلاعاتی توزیع شده، معمولاً اشیاء یا مستندات به منظور تسریع در دسترسی تعاملی به یکدیگر پیوند زده می‌شوند. نمونه¬ها و مثال¬هایی برای یک چنین فراهم¬سازی اطلاعات محیطی شامل وب جهانی (WWW) و خدمات برخطی مانند American online می‌باشد بنحوی که زمانی کاربران به دنبال اطلاعات مورد نیاز و مورد علاقه خود هستند، از یک شی ء به شی‌ء دیگر با استفاده از امکاناتی مانند ابراتصال¬ها   و آدرس¬های URL در حرکت هستند. در حقیقت، وب یک بدنه ابر متن  با بیش از 800 میلیون صفحه بوده که در حال رشد سریعی است. اطلاعات آن بالغ بر شش ترابایت می‌باشد که بر روی حدود سه میلیون سرویس دهنده قرار گرفته است. تقریباً یک میلیون صفحه روزانه به این حجم از اطلاعات اضافه می‌شود و نوعاً هر چند ماه یک بار این صفحات تغییر می‌یابند‌ و در نتیجه، چند صد گیگابایت ماهانه به روز و به هنگام می‌شوند. مادامی که اطلاعات ارائه شده در وب روزانه در حال تغییر می‌باشد، بدست آوردن این اطلاعات تا حدود زیادی کسل کننده خواهد شد. حتی بزرگ ترین موتورهای جست و جو مانند آلتاویستا  و هات بات  کمتر از 18% از صفحات وب قابل دسترس را در ماه خاصی مانند فوریه ثبت کرده‌اند. باید توجه داشتکه مشکل اصلی در این رابطه در محتویات غیر ساخت یافته و یا شبه ساخت یافته وب نهفته است که به نظم آوردن آن کار بسیار ساده‌ای نخواهد بود و همچنین اعمال یک ساختار یا استاندارد مناسب بسیار مشکل به نظر می‌رسد. مجموعه‌ای از صفحات وب از یک ساختار واحد رنج برده و از سبک و شیوه نگارشی و تنوع محتوایی نسبت به آنچه که در مجموعه مستندات کاغذی مرسوم مشاهده می¬شوند، فاصله زیادی دارند. این سطح از پیچیدگی موجب ایجاد یک مدیریت بانک اطلاعاتی در دسترس و آماده می‌گردد و راه حل¬های بازیابی اطلاعات بسیار دشوار بوده و می‌توان ادعا نمود که به کارگیری آنها تقریباً غیر ممکن می‌باشد . مسلماً با این شرایط، روش¬ها و شیوه‌های جدید کاملاً ضروری به نظر می‌رسند. در حقیقت وب¬کاوی ممکن است بعنوان به کارگیری تکنیک‌های داده¬کاوی و به منظور کشف و استخراج خودکار اطلاعات از مستندات، محتویات و سرویس‌های وب معرفی گردد. به تعبیر دیگر وب¬کاوی به فرآیند کلی اکتشاف و استخراج اشاره دارد نه تنها به کاربردهای ابزار کاوش داده‌های استاندارد. بعضی از نویسندگان فرآیند وب¬کاوی را به چهار زیر وظیفه زیر تجزیه می‌کنند:
1- پیدا کردن منبع: این زیر وظیفه شامل فرآیند بازیابی داده‌هایی که می‌تواند بصورت برخط یا غیر بر خط از منبع چند رسانه‌ای بر روی وب باشد، در نظر گرفته می¬شود، مانند خبرنامه‌های الکترونیکی، گروه‌های خبری و محتویات متن اسناد HTML حاصل از حذف برچسب‌های HTML.
2- انتخاب و پیش¬پردازش اطلاعات. این مرحله فرآیندی است که توسّط انواع گوناگونی از داده‌های اصلی بازیابی شده در زیر وظیفه قبلی، تبدیل و تغییر وضعیت داده می‌شود این تبدیل و تغییر وضعیت می‌تواند یا یک نوع پیش¬پردازش مانند حذف کلمات توقف، کلمات هم¬ریشه یا غیره انجام شود یا یک پیش¬پردازش با هدف بدست آوردن نمایش دلخواه مانند پیدا کردن یک عبارت در متن و بدنه آموزشی، نمایش متن در شکل منطقی اولیه و غیره صورت گیرد.
3- تعمیم¬سازی (عمومیت¬سازی) : تعمیم¬سازی به فرآیند جست و جو و کشف خودکار الگوهای عمومی در داخل سایت¬های وب مجزا علاوه بر سایت¬های چندگانه متقاطع اطلاق می‌گردد. در این خصوص، تکنیک‌های یادگیری ماشین همه منظوره مختلف، تکنیک‌های داده¬کاوی و روش‌های با گرایش وب خاص مورد استفاده قرار می‌گیرد.
4- تحلیل: این مورد، مرحله‌ای است که  در آن معتبر¬سازی و یا تفسیر الگوهای کاوش شده اجراء می‌شود.
باید توجه داشت که در اینجا سه عامل بر روی روشی که یک کاربر سایت¬های وب را از طریق فرآیند داده¬کاوی ارزیابی و درک می¬کنند، اثرگذار می‌باشد:
1.محتوای صفحه وب.
2. طراحی صفحه وب.
3. طراحی کلی سایت شامل ساخت آن.

عامل اول در برگیرنده کالاها، خدمات یاداده‌های ارائه شده توسّط سایت است. عوامل دیگر روشی را در نظر می‌گیرند که در آن سایت، محتویات خود را برای کاربرانش قابل دسترس و قابل درک می‌سازند. در حقیقت، در اینجا تفاوتی بین طراحی صفحات مجزا و طراحی کلی سات وجود دارد. دلیل این امر، این است که یک سایت به سادگی مجموعه‌ای از صفحات نبوده بلکه شبکه‌ای از صفحات به هم پیوسته و مرتبط می‌باشد. کاربران، مسلماً درگیر جست و جوی یک سایت نخواهند شد، مگر ساختار آن را ساده و قابل درک دریابند. بطور روشن، درک الگوهای دسترسی کاربر در یک چنین محیطی تنها به بهبود طراحی سیستم کمک نخواهند کرد (برای مثال، ایجاد دسترسی کارا بین اشیاء کاملاً به هم پیوسته و همگرا، طراحی سیستم علمی بهتر برای صفحات WWW و غیره). امّا همچنین قادر خواهندبود به یک بازاریابی تصمیم بهتر هدایت شوند. نتایج تجاری با گذاشتن تبلیغات در محل‌ها و موقعیت‌های مناسب، دسته¬بندی بهتر کاربران/ مشتریان و درک نیازمندی¬های واقعی کاربران از طریق تحلیل‌های رفتاری آنها بهبود خواهد یافت.
باید توجه داشته باشید که شرکت‌ها دیگر علاقمند به وب سایت‌هایی که ترافیک را به سادگی هدایت و سفارشات را انجام دهند، نیستند. در حال حاضر، آنها به دنبال حداکثر رسانی منافع و سود خود بوده و همچنین آنها مایل هستند که رفتار و عملکرد مشتریان خود را تحلیل و میزان فروش به کاربران مجزای خود را سفارشی کنند. در این راستا با ارزیابی خرید کاربران و نمایش الگوها، تامین¬کنندگان الکترونیکی تمایل دارند که به صورت  بلادرنگ خدمات خود را ارائه دهند. منو و فهرست خدمات و کالاهای خود را بصورت جذابی مشتری¬پسند نموده و مقاومت خریداران الکترونیکی راکاهش دهند. باید توجه داشت که جمع‌آوری و متراکم¬سازی اطلاعات مشتریان در قالب سیستم‌های هوشمند کسب و کار الکترونیکی، یک وظیفه مهم و حیاتی برای هر شرکت با فعالیت‌های مبتنی بر وب باشد. شرکت¬های مبتنی بر کسب و کار الکترونیکی در قبال بهبود فرآیند تصمیم‌گیری انتظار منافع بیشتری دارند و بنابراین، تامین کنندگان الکترونیکی برای راه حل¬های داده¬کاوی صف می¬بندند.
با استفاده از نظریه‌های بازیابی، می‌توان کارایی یک صفحه وب را با میزان مشارکت آن در موفقیت سایت موردنظر اندازه‌گیری و مورد سنجش قرار داد. برای یک فروشگاه بر خط، نسبت بازدیدکنندگانی که بعد از بازدید این صفحه کالایی را خریداری می¬کنند، نسبت به کل تعداد بازدیدکنندگان که به آن صفحه خاص دسترسی داشته‌اند، از اهمیت بالایی برخوردار است. برای یک سایت فعال، کارایی یک صفحه می‌تواند به عنوان درصد بازدیدکنندگانی که بعد از بازدید این صفحه بر روی آگهی و تبلیغ خاصی کلیک می‌کنند، در نظر گرفته شود. مسلماً صفحات با کارایی پایین می¬بایستی به منظور ارائه خدمات بهتر به اهداف این سایت طراحی مجدد گردد. جست و جو و کشف الگویی باید در ساختار مجدد یک سایت با درج اتصالات و پیوندهای مناسب و طراحی مجدد صفحات و در نهایت، پشتیبانی نیازها و انتظارات کاربران کمک کند. یک روش طبقه‌بندی ممکن در وب¬کاوی مبتنی بر بخشی از وب است که برای کاوش مورد استفاده قرار می‌گیرد و آن شامل سه زمینه زیر می‌باشد:
1- کاوش محتوایی وب: این زمینه، جست و جو و کشف اطلاعات مفید از مستندات وب را توصیف می‌کند. اساساً، محتوای وب شامل چندین نوع از داده‌ها مانند متن، تصویر، صوت، ویدئو، فراداده‌ها علاوه بر فوق پیوندها می‌باشد. در حال حاضر، تحقیق درکاوش انوع داده‌های چندگانه بعنوان "داده¬کاوی چند رسانه‌ای" نامیده می‌شود. دراینجا می¬توان داده-کاوی چند رسانه¬ای را بعنوان یک نمونه از کاوش محتوای وب در نظر گرفت. داده¬های محتوای وب شامل داده‌های غیرساخت¬یافته مانند متن¬های آزاد، داده‌های شبه¬ساخت¬یافته مانند مستندات HTML و داده‌های غیرساخت¬یافته مانند جداول و صفحات HTML تولید شده توسّط بانک‌های اطلاعاتی می‌باشد. ساخت مدلی از داده‌ها بر روی وب، تقاضاهای پیشرفته‌تر به غیر از جست و جوی مبتنی بر صفحه کلید می‌تواند مورد نیاز و درخواست باشد.
2- کاوش ساختاری- وب: این زمینه سعی می‌کند تا مدل مرتبط با ساختار پیوندی بر روی وب را بررسی و کشف کند. این مدل، مبتنی بر توپولوژی ابرپیوندها با یا بدون یک توصیف از پیوندها می‌باشد. در حقیقت، مدل فوق می‌تواند برای دسته¬بندی صفحات وب مورد استفاده قرار گیرد و مسلماً این مدل برای تولید اطلاعاتی مانند رابطه همسانی و مشابهات بین سایت‌های وب بسیار مفید می‌باشد.
3- کاوش کاربردی- وب: باید توجه داشت که این زمینه نیز سعی دارد تا داده‌های تولید شده عملکرد جست و جو کنندگان وب دارای معنی بوده و قابل انجام باشند. مادامی که کاوش محتوایی- وب  و کاوش ساختاری- وب، داده‌های واقعی یا اصلی بر روی وب را بهینه و سودمند می‌سازند، کاوش کاربردی وب، داده‌های ثانویه حاصل از عملکرد کاربران مرتبط با وب را مورد کاوش قرار می‌دهد. در حقیقت، این خود شامل داده‌هایی خواهند بود که شامل لیست رویدادهای دسترسی به سرویس دهنده‌های وب، لیست رویدادهای سرویس دهنده- پروکسی، لیست رویدادهای مرورگرها، شرح فعالیت‌های کاربران، داده‌های ثبت، تراکنش‌های کاربر، برنامه‌های کمکی، داده‌های نشانه¬گذاری و هر داده دیگری که از تعاملات شخصی با وب بدست می‌آید، می‌باشند.
برای بررسی مشکلات مرتبط با کیفیت صفحات وب، ساختار سایت¬های وب و کاربرد آنها، دوخانواده از ابزار وب با یکدیگر ادغام می‌شوند. اولی شامل ابزارهایی هستند که می‌توانند این اقدامات را تحقق ببخشند و کاربران را در جست و جوهای خود همراهی کنند. عملکرد آنها را بررسی و به هنگام مرور سایت‌ها پیشنهادات مناسبی را ارائه و بالاخره گاهاً گزارشات کاربران را سفارشی کنند. این ابزارها معمولاً متصل یا تعبیه شده در قسمت‌های موتورهای جست و جوی مختلف می‌باشد. گروه یا خانواده دوم از ابزار یاد شده فعالیت¬های کاربران غیر برخط را تحلیل می‌کنند. هدف آنها در حقیقت فراهم کردن برداشتی در معناشناسی یک ساختار است که بتواند با جست و جو و اکتشاف لازم، مشخص کند که چگونه این ساختار واقعاً بهینه و سودمند می‌شود. به عبارت دیگر، دانش رفتار جست و جویی کاربران برای پیشگویی روندها و گرایشات آینده مورد استفاده قرار می‌گیرد. در حقیقت، تکنیک‌های داده¬کاوی جدید ماورای این ابزار هستند، بنحوی که فایل لیست رویدادهای وب تحلیل شده و اطلاعات کشف و پیدا می‌شوند. در دو بخش بعدی، وب¬کاوی با سه تکنیک مناسب ارائه خواهد شد که این خود نشان¬دهنده یک طیف بزرگ از روش شناختی¬های وب¬کاوی توسعه¬یافته در سال¬های اخیر است.
1-1-3- الگوریتم های هیتس  ولاگسام
باید توجه داشت که موتورهای جست وجوی متکی بر ایندکس برای وب ابزارهای اصلی هستند که توسّط آنها کاربران می‌توانند در جست و جوی اطلاعات مورد نیاز خود باشند. جست وجوکنندگان باتجربه وب می‌توانند از چنین موتورهای جست و جویی برای وظایف و کاربردهای خود به نحوه مناسبی بهره‌مند شوند بنحوی که آنها می‌توانند با جست وجوی عبارات و کلمات¬کلیدی کاملاً محدود شده نیاز خود را مرتفع کنند. هر چند، این موتورها جست وجو می‌توانند برای دامنه وسیعی از وظایف با دقت و اهمیت کمتری نامناسب باشند. در اینجا این سوال مطرح می‌گردد که چگونه فردی می‌تواند زیر مجموعه‌ای از مستندات  با ارزش را از بین میلیون‌ها قلم اطلاعاتی که یک موتور جست وجو برای او فراهم نموده است، انتخاب کند. برای تبدیل یک موضوع جست و جوی وب بزرگ به اندازه مناسبی که برای کاربر مناسب و قابل قبول باشد، نیاز به یک ابزار لازم در شناسایی عناوین صفحات وب با اختیارات بالا می‌باشد. این مجوز واگذاری خود ابعاد مهمی را به مفاهیم مرتبط اضافه می‌کند. در حقیقت تمایل اصلی در اینجا نه تنها تعیین مجموعه‌ای از صفحات مرتبط می‌باشد بلکه هدف اصلی مشخص کردن صفحات با بالاترین سطح کیفیت است.
باید توجه داشت که وب نه تنها حاوی صفحات می باشد، بلکه دارای ابرپیوندهایی است که امکان ارتباط یک صفحه با صفحات دیگر را فراهم می‌کند. این ساختار ابرپیوند، شامل میزان زیادی اطلاعاتی است که می‌تواند به یک فرد مجاز، امکان جست وجو را بطور خودکار اعطا کند. بطور مشخص، ایجاد یک ابرپیوند توسّط طراح یک صفحه وب، یک اعلان صریح از صفحه‌ای است که مورد اشاره قرار می‌گیرد. با کاوش داوری منتخب موجود در چنین اعلانی، می‌توان درک کامل‌تری از ارتباط، کارایی و کیفیت محتویات وب بدست آورد. باید توجه داشت که برای این فرآیند لازم است که دو نوع مهم از صفحات را شناسایی نمود. مجوزها و اختیارات که بهترین منبع اطلاعاتی در خصوص یک موضوع و عنوان مشخص را فراهم می‌کند و مراکز و کانون¬هایی  که مجموعه‌ای از این پیوندها به این مجوزها را ایجاد می‌کند.
صفحات کانونی به اشکال مختلفی ظاهر می‌شوند که می‌توانند از لیست¬های منابع اسمبلی شده حرفه‌ای بر روی سایت‌های تجاری تا لیست¬های پیوندهای توصیه شده بر روی صفحات خانگی مجزا متفاوت باشد. نیازی نیست که این صفحات خود برجسته و ممتاز باشند، همچنین در اینجا باید توجه داشت که کارکردن با اطلاعات ابرپیوندها خود می‌تواند موجب بروز مشکلات زیادی شود. هر چند خیلی از پیوندها نوعی اعلان محسوب می‌شوند و البته بعضی از پیوندها برای دلایلی ایجاد شده‌اند که هیچ گونه ارتباطی با مسئله اختیارات ندارند. مثال¬ها و نمونه¬های مرسوم، جست و جوها وابرپیوندهای تبلیغات پولی می‌باشد. یک جنبه قابل تمایز صفحه کانونی توانایی آنها در اختیارات ارائه شده می‌باشد. در حقیقت می‌توان یک صفنحه کانونی خوب را بعنوان صفحه‌ای در نظر گرفت که به اختیارات بسیار خوبی اشاره می‌کند. در همین راستا، می‌توان ادعا نمود که یک صفحه اختیار خوب، صفحه ای است که توسّط صفحات کانونی متعددی مورد اشاره قرار گیرد. مسلماً این موضوع بصورت متقابل ارتباط بین صفحات کانونی و اختیارات را مشخص می‌کند. اختیاراتی که بعنوان ایده اصلی اعمال شده در الگوریتم HITS و به منظور جست و جو برای صفحات کانونی و اختیارات مناسب در نظر گرفته می‌شود. (HITS: Hyperling- Induced Topic Search)
دو مرحله اصلی الگوریتم HITS به شرح زیر می‌باشد:
1- جزء نمونه برداری: مجموعه‌ای متمرکز از صفحات وب که احتمالاً توسّط اطلاعات مرتبط غنی و کامل خواهند شد را ایجاد می‌کند و
2- جزء انتشار وزنی: صفحات کانونی و اختیارات را توسّط یک رویه تکرار شونده مشخص نموده و زیرمجموعه¬ای از صفحات وب دارای اختیار و کاملاً مناسب را ارائه می‌کند.
در مرحله نمونه برداری، وب بعنوان یک گراف جهت¬دار از صفحات در نظر گرفته می‌شود. الگوریتم HITS کار خود را با ایجاد و ساخت زیرگرافی شروع می‌کند که ما در آن به دنبال صفحات کانونی و اختیارات هستیم. باید توجه داشت که برای ساخت چنین زیرگرافی در ابتدا از عبارات تقاضا استفاده می‌کنیم که برای جمع‌آوری ریشه‌ای از مجموعه صفحات یک موتور جست و جو متکی بر شاخص بهره‌مند می‌شوند. از آنجایی که خیلی از این صفحات مرتبط با عناوین و موضوعات جست و جو هستند، انتظار می‌رود که حداقل بعضی از آنها اختیارات لازم بوده یا اینکه دارای پیوندهایی به اکثر اختیارات مهم و مقید باشند. بنابراین، مجموعه ریشه به داخل یک مجموعه مبنا توسعه پیدا می‌کند. این توسعه با در نظر گرفتن تمام صفحاتی که مجموعه – ریشه به آن متصل هستند، در نظر گرفته می‌شود. این مجموعه بطور مرسوم حاوی 1000 تا 5000 صفحه با پیوندهای متناظر می‌باشد و می‌تواند بعنوان نتیجه نهایی مرحله اول الگوریتم HITS در نظر گرفته شود.
در مرحله انتشار- وزنی، صفحات کانونی و اختیارات از مجموعه مبنای V با ارائه یک تفسیر عددی کامل برای همه آنها بدست می‌آید. باید توجه داشت که در اینجا کمیت غیر منفی ap بعنوان وزن اختیار و کمیت غیر منفی hp به عنوان وزن صفحات کانونی به ازای هر صفحه   در نظر گرفته می¬شود. در حقیقت ما تنها علاقمند به مقادیر نسبی این وزن¬ها هستیم و لذا فرآیند هنجارسازی به گونه‌ای اعمال می‌شود که مجموع کلی آنها محدود باقی بمانند. از آنجایی که ما هیچ گونه بر آورد اولیه‌ای را اعمال نمی‌کنیم، تمام مقادیر a و h را در ابتدا برابر با یک ثابت یکنواخت قرار می‌دهیم. مسلماً وزن¬های نهایی با این مقداردهی اولیه بدون تاثیر باقی خواهند ماند.
اکنون ما در مقامی هستیم که می‌توانیم وزن صفحات کانونی و اختیارات را به شکل زیر بهنگام¬سازی کنیم. اگر صفحه¬ای توسّط صفحات کانونی مناسب متعددی مورد اشاره و پیوند قرار گیرد، می‌توانیم وزن اختیارات آن را افزایش دهیم. بنابراین مقدار ap بر ای صفحه p بهنگام¬سازی خواهد شد، بنحوی که صفحه p مجموع hp بر روی تمام صفحات q خواهد بود که به p متصل هستند:
 
بنحوی که عبارت qp  نشان می‌دهد، صفحه q به صفحه p دارای اتصال می‌باشد. در یک حالت دوگانه محض، اگر یک صفحه به اختیارات مناسب متعددی اشاره کند، ما وزن صفحات کانونی را افزایش می‌دهیم.
 
باید توجه داشت که یک روش فشرده‌تر برای نوشتن این بهنگام¬سازی ها وجود دارد. بهتر باشد در اینجا صفحات را شماره¬گذاری کنیم {1,2,....n} و همچنین ماتریس مجاورتی A را بعنوان یک ماتریس n*n تعریف کنیم، بنحوی که عنصر (i,j) اگر صفحه i به صفحه j دارای پیوند باشد، برابر با 1 و در غیر این صورت مقدار آن صفر خواهد بود. تمام صفحات در ابتدای محاسبات هم صفحه کانونی و هم اختیارات بوده و بنابراین، می‌توانیم آنها را بعنوان بردارهایی مانند زیر ارائه دهیم:
a={a1 , a2 , ... , an}
h={h1 , h2 , ... , hn}
قوانین بهنگام سازی، برای اختیارات و صفحات کانونی می‌توانند بصورت زیر نوشته شوند:
a=ATh
h=Aa
یا، با جایگزینی یک عبارت در عبارت دیگر خواهیم داشت:
a=ATh = ATAa =(ATA)a
h=Aa = AATh = (AAT)h
این عبارت، روابطی برای محاسبات تعاملی بردارهای a و h می‌باشند. جبر خطی به ما این واقعیت را می‌گوید که این توالی از تکرارها (زمانی که هنجار می‌شوند) به بردار ویژه اصولی ATA همگرا و نزدیک می‌شوند. این مسئله گویای این واقعیت است که وزن صفحات کانونی و اختیاراتی که ما محاسبه می‌کنیم، بطور واقعی یک جنبه ذاتی از صفحات پیوندی جمع‌آوری شده است نه یک اقدام نمادی از انتخاب ما از وزن های اولیه. بطور مشخص، صفحات با وزن زیاد نشان¬دهنده یک الگوی با تراکم بالا از پیوندها می‌باشند، پیوندهایی از صفحات با وزن زیاد کانونی به صفحات با بالاترین وزن کانونی و صفحاتی با بالاترین وزن اختیارات برای یک عنوان جست و جوی مشخص ارائه می‌کند. باید توجه داشت که توسعه‌ها و بهبودهای متعددی از الگوریتم HITS در منابع و مراجع وجود دارد. در اینجا مراحل اساسی از الگوریتم فوق با استفاده از یک مثال ساده ارائه خواهد شد.
فرض کنید که یک موتور جست و جو بر اساس تقاضای ما، شش مسند لازم را انتخاب کرده باشد و ما خواسته باشیم از بین این مجموعه موجود بهترین صفحه کانونی و اختیار را انتخاب کنیم. در حقیقت مستندات انتخاب شده به یک زیرگراف جهت دار متصل و پیوند زده می‌شوند که در این خصوص ساختار لازم در شکل الف 1-3 ارائه شده است همچنین ماتریس همجواری A و بردار وزن اولیه a و h در شکل ب 1- 3 نشان داده شده‌اند.
 
شکل 1-3 مقداردهی اولیه الگوریتم HITS
اولین تکرار الگوریتم HITS موجب تغییراتی در بردارهایa و h می‌گردد.
 
 
حتی این تکرار منفرد در الگورتیم HITSنشان می‌دهد که در بین مجموعه مستندات، مستند -5 دارای بالاترین اختیار و مستند -1 دارای بهترین صفحه کانونی است. تکرارهای اضافی مسلماً عوامل وزن برای هر دو بردار را اصلاح خواهند نمود امّا رده‌بندی بدست آمده از اختیارات و صفحات کانونی برا این مثال بدون تغییر باقی خواهند ماند.
رشد سریع و پیوسته  در اندازه و کاربرد اینترنت موجب بروز مشکلاتی در جست و جوی اطلاعات شده است. جست و جو و کشف منابع می‌توانند زمانی که جست و جوهای ساده صفحه کلیدی، ارائه دهنده صدها هزار مستندات بعنوان نتایج مورد نظر است. یک امر ناکارا و بیهوده به نظر آید. باید توجه داشت که خیلی از آنها، صفحات غیر مربوط بوده و بعضی از آنها ممکن است جابجا شوند و بعضی¬ها نیز بلا استفاده گردند. مادامی که اولین الگوریتم وب¬کاوی HITS اصولاً متکی بر اطلاعات ایستا توصیف شده در ساختار وب¬سایت است، الگوریتم دوم، یعنی LOGSOM در ارتباط با عملکرد کاربران از اطلاعات پویا استفاده می‌کند. در حقیقت، الگوریتم LOGSOM یک روش کاملاً پیچیده بوده که طراح کلی اطلاعات به یک شکل گرافیکی قابل تعبیر برای کاربر سازماندهی می‌کند. باید توجه داشت که سیستم LOGSOM از نگاشت¬ها و طرح¬های خود سازماندهی (SOM ) برای سازماندهی صفحات وب در قالب جداول دو بعدی براساس الگوهای جست وجوی کاربر استفاده می‌کند.
سیستم براساس علاقه‌مندی و تمایل کاربران وب و با ثبت مسیرهای جست و جوی آنها، صفحات وب را سازماندهی می‌کند.
تکنیک SOM بعنوان مناسب¬ترین تکنیک برای مسائل سازماندهی صفحه، وب مورد استفاده قرار می‌گیرد. این نه تنها به واسطه قدرت و توانایی آن در دسته¬بندی نقاط داده‌ای در کلاسترها (خوشه¬ها) بوده بلکه به واسطه نمایش گرافیکی روابط بین کلاسترها می‌باشد. در اینجا توجه داشته باشید که سیستم با فایل لیست رویدادهای وب که نشان دهنده تاریخ، زمان و آدرس صفحات وب درخواست شده علاوه بر آدرس IP ماشین کاربر می‌باشد، کار خود را شروع می‌کند. داده‌ها در قالب تراکنش‌های معناداری دسته¬بندی می‌شود. در این جا فرض می‌شود که مجموعه محدودی از URLهای منحصر به فرد وجود دارد:
U= {url1 , url2 , .... urln}
و همچنین یک مجموعه محدود از m تراکنش کاربران بصورت زیر خواهد بود:
T= {t1 , t2, .... tm}
تراکنش ها بعنوان یک بردار با مقادیر دو دویی ui نشان داده می‌شود:
t={u1,u2, ... un}
بنحوی که
 
فایل رویدادهای از پیش پردازش شده می‌توانند بعنوان یک ماتریس دو دویی ارائه گردند. نمونه‌ای از این مورد در جدول 1-3 ارائه شده است.
از آنجایی که ممکن است ابعاد یک جدول (m*n) برای کاربردهای دنیای واقعی خیلی بزرگ باشد، مخصوصاً بعنوان داده‌های ورودی به نگاشت¬های خود سازماندهی، یک کاهش ضروری به نظر می‌رسد. با استفاده از الگوریتم دسته-بندی (خوشه¬بندی) k مرتبه¬ای، ممکن است تراکنش‌های مورد نظر به k گروه تراکنش، دسته¬بندی شود. (k یک عدد از پیش تعیین شده بوده که دارای شرط k<<m می‌باشد). در اینحا مثالی از یک جدول تبدیل شده با مجموعه داده¬های کاهش یافته جدید در جدول 2-3 ارائه شده است. در این جدول عناصر موجود در سطرها نشان¬دهنده تعداد کل دفعاتی هستند که یک گروه به یک URL خاص دسترسی دارد (شکل جدول و مقادیر تنها یک نمایش ممکن را نشان می‌دهند و مسلماً آنها بطور مستقیم به مقادیر جدول 1-3 متصل نیستند).





جدول 1-3 تراکنش های توصیف شده توسّط مجموعه‌ای از URL ها.
urln    …    url2             url1    
1        1    0    t1
0        1    1    t2
                …
0        0    0    tm


جدول 2-3 نمایش URL ها بعنوان بردارهایی از فعالیت گروه تراکنش.
گره¬های تراکنش
k    …    2             1    
2        0    15    url 1
10        1    2    url 2
                …
2        1    0    urln

با توجه به مطالب ارائه شده مسلماً جدول کاهش¬یافته جدید بعنوان ورودی پردازش SOM محسوب خواهد شد. در این بخش، جزئیات مربوط به کاربردهای SOM مانند تکنیک دسته¬بندی (خوشه¬بندی) و تنظیم پارامترهای آن مطرح نخواهد شد. علاقمندان به این مطالب می‌توانند جزئیات فوق رادر اکثر کتب درسی مرتبط با شبکه‌های هوش مصنوعی پیدا کنند. در اینجا فقط نتایج نهایی و تفسیر آنها بر حسب تحلیل صفحات- وب انجام می‌گیرد. هر URL بر اساس شباهت آن با دیگر URLها برحسب استفاده کاربر و یا بطور دقیق¬تر بر حسب الگوهای جست وجوی کاربران، به SOM نگاشت می‌شود (وزن های گروه تراکنش در جدول 2-3 ارائه شده است). فرض کنید SOM یک نگاشت دو بعدی با P*P گره بوده بنحوی که   می باشد، آنگاه یک نتیجه متداول و مرسوم از پردازش SOM درجدول 3-3 ارائه شده است. توجه داشته باشید که ابعاد و مقادیر قید شده در جداول، نتیجه هیچگونه محاسبه¬ای با مقادیر قبلی جداول 1-3 و 2-3 نبوده بلکه یک ارائه متداول از نمایش نهایی SOM می‌باشد.
SOM صفحات وب را بر اساس الگوهای جست وجوی کاربران در قالب کلاس¬های مشابهی سازماندهی می‌کنند. گره‌های تهی در جدول نشان¬دهنده این واقعیت هستندکه URL متناظری وجود ندارد، در حالی که گره¬های شماره¬گذاری شده تعداد URLهای موجود در هر گره را مشخص می‌کند (یا در حقیقت در هر کلاس). فاصله بر روی نگاشت و الگو نشان¬دهنده شباهت صفحات وب بوده که توسّط الگوهای جست وجوی کاربر مورد سنجش و اندازه‌گیری قرار گرفته است. برای مثال، عدد 54 در سطر آخر جدول مشخص می¬کند که 54 مشخصه وب در همان کلاس گروه¬بندی شده¬اند. دلیل این مطلب این است که آنها توسط گره‌های مشابهی از افراد بر اساس الگوهای تراکنش مورد دسترسی قرار گرفته‌اند. باید دقت نمود که شباهت قید شده در اینجا نه تنها توسّط شباهت محتوا اندازه‌گیری می¬شود، بلکه توسّط شباهت کاربرد نیز مورد سنجش قرار می‌گیرد. بنابراین، سازمان مستندات وب در این نمایش گرافیکی بطور کامل بر عملکرد جست و جوی کاربران استوار شده است.

جدول 3-3 یک SOM مرسوم که توسّط توصیف URL ها تولید شده است.
p    …    3    2    1    
15        1        2    1
    …    10    1    3    2
                    …
11    …        54        p

در اینجا این سئوال مطرح می‌شود که کاربردهای ممکن روش شناختی LOGSOM شامل چه مواردی می‌باشد؟ توانایی شناسایی اینکه چه صفحاتی از وب توسّط مشتریان بالقوه یک شرکت در دسترس قرار گرفته‌اند؟ این فرصت را برای آن شرکت و موسسه فراهم می‌سازد که با اطلاعات ارائه شده به شرکت تصمیمات بهینه و کاملی را اتخاذ کنند. اگر یک صفحه وب در داخل یک گره با موفقیت کامل مشتریان را به اطلاعات یا صفحه مورد علاقه و دلخواه خود هدایت کند، به احتمال قوی، سایر صفحه‌ها در همان گره نیز دارای همین شرایط خواهند بود. بدون نیاز به اینکه لازم باشد در خصوص محل یک تبلیغ و آگهی اینترنتی تصمیم‌گیری کنیم، موسسه می‌تواند در حال حاضر با حمایت مستقیم توسّط الگوهای جست و جوی کاربر این مسئله را مدیریت کند.
2-1-3 کاوش الگوهای پیمایش مسیر
قبل از بهبود وب سایت شرکت، باید روشی را اتخاذ کنیم که کاربرد آن را ارزیابی کنیم. در حقیقت، ارزیابی یک وب سایت بر¬اساس داده¬هایی است که بصورت خودکار بر روی آن ثبت می‌گردد. باید توجه داشت که هر سایتی به طورخودکار توسّط یک سرویس¬دهنده وب مدیریت می‌شود و این سرویس¬دهنده وب تمام فعالیت‌هایی که در سایت روی می‌دهد در فایلی به نام "رویداد سرویس¬دهنده وب" ثبت می‌کند. تمام اثرات و ردپای باقیمانده از کاربران وب در این لیست رویدادها ثبت می‌گردد. بنابراین، با استفاده از این فایل¬های رویداد ما می‌توانیم با اعمال تکنیک¬های داده¬کاوی بطور غیر-مستقیم کیفیت سایت را از اطلاعات استخراج شده از آن بررسی و ارزیابی کنیم. در این رابطه کاوش داده ها به ما کمک می¬کند تا اجراء و کارایی سرویس¬دهنده وب را بهینه کنیم همچنین مشخص کنیم که چه محصولاتی باید با هم خریداری شود یا اینکه مشخص کنیم آیا سایت مورد نظر همانگونه که انتظار می¬رفت عمل می‌کند یا خیر؟ مشخصه‌های دقیق مسئله با استفاده از تکنیک¬های مختلف داده¬کاوی اعمال شده بر روی همان لیست رویدادهای سرویس¬دهنده وب به ما کمک زیادی می‌کند.
مادامی که متدولوژی یا اصطلاحاً شیوه¬شناسی LOGSOM بر روی شباهت صفحات وب تاکید دارند، سایر تکنیک¬ها بر شباهت و همسانی مسیرهای کاربران به وب متمرکز شده‌اند. توجه داشته باشید که در یک محیط وب به در نظر گرفتن الگوهای دسترسی کاربران، "کاوش الگوهای پیمایش کاربران" گفته می‌شود. توجه داشته باشید از آنجایی که کاربران برای جست و جوی اطلاعات مورد نظر خود در طول مسیرهای اطلاعاتی حرکت می‌کنند. بعضی از مستندات و موضوعات به واسطه موقعیتشان نه به واسطه محتویاتشان بررسی و ملاقات می‌شوند. ذکر این نکته در اینجا لازم است که این جنبه از پیمایش الگوها بطور غیر قابل اجتنابی سختی استخراج اطلاعات معنادار را از دنباله¬ای از پیمایش داده¬ها افزایش داده و دلیل اینکه چرا تحلیل کاربرد جاری وب اساساً قادر به ایجاد و ارائه اطلاعات آماری برای نقاط پیمایش هستند را توضیح می‌دهد (البته نه برای مسیرهای پیمایش). هر چند، باید توجه داشت مادامی که سرویس¬های ایجاد چنین اطلاعاتی بطور قابل افزایشی متداول و همگانی می شوند، درخواست رو به افزایش برای تعیین عملکرد پیمایش کاربر به منظور بهبود کیفیت چنین سرویس‌هایی مطرح می‌گردد.
درابتدا تاکید بر نظریه موجو در ارتباط با الگوهای کاوش کاربران در وب می‌باشد. در اینجا فرمول¬بندی و قالب¬بندی حقایق معلوم در خصوص جست و جو و کاوش ضروری به نظر می‌رسد: اینکه تمام صفحات در طول مسیر دارای اهمیت یکسانی نبوده و اینکه کاربران تمایل دارند صفحاتی را که قبلاً مورد دسترسی قرار دارند، مجدداً ملاقات و بازدید کنند. به منظور رسیدن به این هدف، یک الگوی جست و جو در کاوش در وب و آن هم بعنوان یک مفهوم کلی و عمومیت یافته از یک توالی و رشته در نظر گرفته می‌شود (در قالب یک گراف بدون دور جهت دار). توجه داشته باشید که یک رشته در حقیقت لیست مرتب شده‌ای از اقلام اطلاعاتی است که البته در مثال ما صفحات وب بر اساس زمان دسترسی مورد استفاده قرار می‌گیرند. در حقیقت، فایل لیست رویدادهای L در اینجا مجموعه چند گانه ای از رشته¬های ثبت شده می‌باشد و مسلماً آن یک مجموعه ساده نمی‌باشد چرا اینکه یک رشته ممکن است بیش از یک بار ظاهر شود.
 در حقیقت ما مایل هستیم رشته S را بعنوان الحاق متوالی زیر رشته های x و y درنظر بگیریم در حالت فوق خواهیم داشت:
s = x y
تابع length(s) تعداد عناصر موجود در رشته s را نشان می‌دهد. بطور مشابه prefix(s,i) نیز زیررشته‌ای را برگشت می‌دهد که از iعنصر اول رشته s تشکیل شده است. اگر عبارت   بر قرار باشد، آنگاه می‌توان گفت که   پیشونده s بوده و می‌توان آن را بصورت   نشان داد. تحلیل فایل رویدادها نشان می¬دهدکه کاربران وب تمایل دارند تا به عقب برگشته و صفحات با فراوانی زیاد را مجدداً بازدید کنند. بنابراین، یک فایل ریداد ممکن است دارای تکرار باشد. بازدیدهای مجدد شبیه این مورد ممکن است بخشی از یک تور برنامه‌ریزی شده باشد. مسلماً اطلاعات مورد نظر بسیار مهم بوده و بایدمورد دسترسی قرار گرند. برای مدل سازی یک چرخه در یک رشته، هر عنصر از رشته بر حسب شماره رویداد اول، دوم، سوم و غیر از همان صفحه مهم و دارای اهمیت می‌باشد.
توجه داشته باشید که بعضی از رشته¬ها ممکن است دارای پیشوندهای مشترک باشند. اگر تمام پیشوندهای مشترک با یکدیگر ادغام شوند، بخشی از فایل رویدادها به داخل یک ساختار درختی تبدیل می‌شوند بنحوی که هر گره از آن با تعداد رشته¬های حاوی همان پیشوند تا این گره در نظر گرفته می‌شود. درخت مورد نظر مانند فایل رویدادهای اولیه حاوی اطلاعات مشابهی می‌باشند. بنابراین، زمانی که ما به دنبال تکرار رشته‌ها هستیم، می‌توانیم به جای مجموعه  چندگانه رویدادهای اصلی، درخت را پویش کنیم. بر روی این درخت، پیشوند مشترکی بین k رشته و توالی ظاهر شده و مسلماً تنها یک مرتبه تست می‌شود.
توالی از کاوش¬ها بصورت زیر ارائه می‌شود. باتوجه به مجموعه‌ای از رشته های مرتب شده بر حسب زمان جایی که هر رشته حاوی مجموعه‌ای از صفحات وب می‌باشد، هدف اصلی استخراج و کشف رشته¬هایی با حداکثر طول است که نسبت به درصد مقدار آستانه بر روی کل مجموعه کمتر اتفاق می‌افتد. یک رشته تکرار چنانچه تمام رشته¬های حاوی آن دارای فراوانی و تکرار کمتری باشد، حداکثر مقدار را خواهد داشت. توجه داشته باشید که این تعریف از مسئله کاوش رشته‌ها بر این نکته تاکید دارد که اقلام اطلاعاتی تشکیل دهنده یک رشته تکراری الزاماً نیازی نیست که مجاور یکدیگر قرار گیرند. آنها تنها به ترتیب یکسانی ظاهر می‌شوند. در حقیقت، این خاصیت زمانی که عملکرد کاربران وب مورد مطالعه قرار می‌گیرد، مورد توجه می‌باشد و دلیل آن هم این است که مایل هستیم که تمایلات (و البته نه خطاها و اشکالات) آنها را ثبت کنیم.
خیلی از این رشته‌ها حتی آنهایی که دارای بالاترین تکرار هستند، می‌توانند یک طبیعت بدیهی داشته باشند. بطور کلی، تنها طراح سایت می‌تواند مشخص کند که کدام یک بدیهی هستند و کدام یک بدیهی نیستند. طراح باید تمام الگوهای بدست آمده توسّط فرآیند کاوش را خوانده و آنهایی که دارای اهمیت کمی هستند را کنار بگذارد. مسلماً بررسی و تست خودکار نتایج داده¬کاوی نسبت به انتظارات طراحی دارای کارایی بسیار مناسبی می‌باشد. هر چند ما به سختی انتظار داریم که یک طراح سایت بتواند تمام ترکیبات صفحات وب که نوعاً مورد نظر نیز هستند، را بنویسد.
اگر چه تکنیک‌های تدوین شده بسیاری درمباحث وادبیات مرتبط وجود دارد. یکی از راه حل‌های تدوین شده برای کاوش الگوهای پیمایش که دارای دو مرحله است، در اینجا توضیح داده می‌شود:
1- در مرحله اول، یک الگوریتم به منظور تبدیل رشته اصلی داده‌های رویداد به مجموعه‌ای از زیر رشته‌های پیمایش توسعه می‌یابند‌. هر زیر رشته پیمایش یک ارجاع پیشرو حداکثر از نقطه شروع یک دسترسی کاربر را نشان می‌دهد. توجه داشته باشید که این مرحله از تبدیل ممکن است تاثیر ارجاع پسرو که معمولاً به واسطه سهولت پیمایش صورت می‌گیرد را فیلتر و صافی کند. در حقیقت، مجموعه کاهش یافته جدید از مسیرهای پیشرو تعریف شده توسّط کاربر ما را قادر می‌سازد تا بر روی کاوش رشته‌های با معنا در دسترس کاربران تمرکز کنیم.
2- دومین مرحله شامل یک الگوریتم مجزا برای تعیین الگوهای تکرار پیمایش می‌باشد که اصطلاحاً تحت نام رشته‌های ارجاع بزرگ معرفی می‌شوند. درحقیقت یک رشته ارجاع بزرگ، رشته‌ای است که به تعداد دفعات در بانک اطلاعاتی رویدادها قرار می‌گیرند. در مرحله آخر، الگوریتم ارجاع‌های حداکثر حاصل از دسته‌های ارجاع بزرگ را شکل می‌دهند. یک رشته بزرگ حداکثر یک رشته ارجاع بزرگ می‌باشد که در هیج رشته ارجاع حداکثر دیگری قرار ندارد.
برای مثال، فرض کنید رویداد پیمایش یک کاربر مشخص حاوی مسیر زیر می‌باشد(برای سادگی کار، صفحات وب بصورت نمایش داده شده‌اند) :
= {A B C D C B E G H W A O U O V} مسیر
توجه داشته باشید که مسیر فوق به صورت ساختار درختی دارای نمایشی مانند آنچه که در شکل 2-3 ارائه شده است، خواهد بود. مجموعه ارجاع‌های پیشرو حداکثر یا MRF مشخص شده در مرحله (1) بعد از حذف ارجاع پسرو بصورت زیر خواهد بود:
MFR= {ABCD , ABEGH , ABEGW , AOU , AOV}

هنگامی که ارجاع پیشرو حداکثر برای تمام کاربران بدست آمد، مسئله پیدا کردن الگوهای تکرار- پیمایش به یکی از رویدادهای پیدا نمودن زیر رشته‌های مربوط ازمیان تمام ارجاع‌های پیشروی حداکثر نگاشت می‌شود. در مثال ما، اگر مقدار آستانه 4/0 باشد (یا در حقیقت 40%) رشته‌های رجوع بزرگ یا همان LRS با طول 3.2 و 4 بصورت زیر خواهند بود:
LRS= {AB , BE , EG , AO , BEG , ABEG}
بالاخره، با رشته‌های ارجاع بزرگ تعیین شده رشته‌های ارجاع حداکثر می‌تواند از طریق فرآیند انتخاب بدست آید. مجموعه حاصل در مثال ما به شرح زیر خواهد بود:
MRS = {ABEG , AO}
بطور کلی ، این رشته‌ها حاصل از فایل‌های رویداد بزرگ متناظر با الگوهای با دسترسی کم در یک سرویس تامین اطلاعات می‌باشند.
مسئله پیدا کردن رشته‌های ارجاع شبیه به مسئله پیدا کردن مجموعه اقلام تکراری در کاوش قوانین مربوطه می‌باشد. هر چند در حقیقت، آنها نسبت به یکدیگر متمایز می‌باشند، بنحوی که یک رشته پیمایش در الگوهای پیمایش- کاوش باید به ترتیب خاصی مورد رجوع واقع شوند. مادامی که یک مجموعه اقلام بزرگ درکاوش قوانین مربوطه تنها ترکیبی از اقلام واقع در یک تراکنش می‌باشد. الگوریتم مربوطه به واسطه اینکه آنها عملکردها را بر روی ساختمان داده‌های مختلفی اجراء می‌کنند، متفاوت خواهد بود: لیست‌ها در حالت اول، مجموعه‌ها در حالت دوم. که عمومیت¬پذیری کاربردهای اینترنت توسعه می‌یابد، انتظار می‌رود که یکی از مهمترین جنبه‌های داده¬کاوی برای سال‌های آینده طرح این مسئله باشد که چگونه می‌توان بطور موثری دانش مورد نیاز بر روی وب را جست¬وجو کشف نمود.

 
شکل2-3 مثالی از الگوهای پیمایش

3-3 متن¬کاوی  
اکنون بیشتر از 80 درصد از دانش ما به صورت متن، مستندات و دیگر صورتهای رسانه‌ای نظیر ویدیو و صدا نگهداری می‌شود. اگر از منظر علوم کامپیوتری به این مستندات نگاه کنیم همه‌ی آنها به طبیعتی غیر ساخت¬یافته وابسته‌اند. یک فرد برای دریافت دانش از اطلاعات یک متن، بایستی ابتدا آنرا درک کند و سپس آنرا پردازش کند تا بفهمد چه معانی و مفاهیمی در آن موجود است، چه ارتباطی میان مفاهیم وجود دارد و از میان این مفاهیم کدام جدید است و کدام قدیمی. با این حال در این عصر تکنولوژی، ما معتقدیم که هر چیزی باید بتواند اتوماتیک انجام شود حتی اگر این کار "درک معنی متن" باشد. این تنها یکی از نامهایی است که شما برای این نوع از پردازش می یابید. "متن¬کاوی"، "کاوش داده¬های متنی"  و نیز نام معروف "کشف دانش در متن"   یا KDT، از نامهای بیشتر مورد قبول دراین زمینه هستند.
متن¬کاوی، در تکنولوژی¬های متفاوتی ریشه دارد و از اینرو این تعجب انگیز نیست که تعاریف زیاد نیز برای آن وجود دارد. افرادی که دارای پیشینه¬کار در زمینه‌ی داده¬کاوی بودند می خواستند که همان مفاهیم و روشهای موجود در داده¬کاوی را بر متون اعمال کنند و تعاریف¬شان نیز منطبق بر همین زمینه بود. امّا کسانی که از جامعه‌ی زبان¬دانان محاسباتی  آمده بودند، قصد داشتند که این توانایی را به کامپیوتر بدهند که بتوانند متن را بفهمند و این غایت چیزی است که از متن-کاوی مورد انتظار است.
در دنیای کنونی این کمبود اطلاعات نیست که مسئله است بلکه کمبود دانشی است که از این اطلاعات می‌توان حاصل کرد. میلیونها صفحه وب، میلیونها کلمه در کتابخانه‌های دیجیتال و هزاران صفحه اطلاعات در هر شرکت تنها چند دست از این منابع اطلاعاتی هستند. امّا نمی‌توان بطور مشخص منبعی از دانش را در این بین معرفی کرد. دانش خلاصه‌ی اطلاعات است و نیز نتیجه‌گیری و حاصل فکر و تحلیل بر روی اطلاعات.
داده¬کاوی، یک روش بسیار کاراست برای کشف اطلاعات از داده‌های ساخت¬یافته‌ای که در جداول نگهداری می‌شوند. داده¬کاوی، الگوها را از تراکنش‌ها  استخراج می‌کند، داده را گروه¬بندی می‌کند و نیز آنرا دسته¬بندی می‌کند. بوسیله‌‌ی داده¬کاوی می‌توانیم پی بوجود روابطی میان اقلام داده‌ای که پایگاه داده را پر کرده‌اند ببریم. در عین حال ما با داده-کاوی مشکلی داریم و آن عدم وجود عامیت در کاربرد آن است. تعداد منابع داده‌ای ساخت یافته‌ی ما که به حد کافی بزرگ نیز باشند که مفاهیم داده¬کاوی قابل اعمال بر آنها باشد، چندان زیاد نیستند. در واقع بیشتر دانش ما اگر بصورت غیر دیجیتال نباشند، کاملاً غیر ساخت¬یافته‌اند. کتابخانه‌های دیجیتال‌، اخبار، کتابهای الکترونیکی، بسیاری از مدارک مالی، مقالات علمی و تقریباً هر چیزی که می‌توانید درداخل وب بیابید، ساخت¬یافته نیستند. در نتیجه ما نمی‌توانیم آموزه‌های داده-کاوی را در مورد آنها بطور مستقیم استفاده کنیم.
با این حال، سه روش اساسی در مواجهه با این حجم وسیع از اطلاعات غیر ساخت¬یافته گسترده شده در جهان وجود دارد. بازیابی اطلاعات  ،استخراج اطلاعات  و کشف دانش در متن این سه روش برخورد با این مسئله هستند.
بازیابی اطلاعات اصولاً مرتبط است با بازیابی مستندات و مدارک. کار معمول در IR اینست که بسته به نیاز مطرح شده از سوی کاربر، مرتبط¬ترین متون و مستندات و یا در واقع "بقچه‌ی کلمه" را از میان دیگر مستندات یک مجموعه بیرون بکشد. این یافتن دانش نیست بلکه تنها آن بقچه‌ای از کلمات را که به نظرش مرتبط¬تر به نیاز اطلاعاتی جستجوگر است را به او تحویل می‌دهد. این روش به واقع هیچ دانشی و حتی هیچ اطلاعاتی را برایمان به ارمغان نمی‌آورد.
در نظر بگیرید که موسسه‌ای بسیار موفق دارید و از اینرو تعداد زیادی ایمیل در روز دریافت می‌کنید. شما می‌خواهید سابقه‌ی این ایمیل‌ها را ثبت کنید. چه کسانی آنرا فرستاده‌اند، تاریخ فرستادن آن  چه روزی بوده است، عنوان و متن آنچه بوده است و نظایر آن. این با بیرون کشیدن این اطلاعات از تک تک ایمیل‌ها و پر کردن یک پایگاه داده از این اطلاعات مسیر است. این ممکن است با تعریف یا کشف یک قالب از داده‌هایی بدست آید که با آن سرو کار دارید. مثلا می‌توان برنامه‌ای داشت که بطور اتوماتیک به دنبال کلمه¬ی title در سند بگردد و آنچه را که بعد از آن آماده بعنوان یک فیلد در پایگاه داده پر کند. هر چند یافتن این قالب در داده‌های کاملاً ساخت¬یافته‌ای مواجه هستید که از دل ایمیل‌ها بیرون کشیده شده است. امّا از سویی دیگر، این تنها اطلاعات است که هنوز شما دارید؛ به این معنی که هیچ چیز جدیدی از آنچه که دارید کشف نشده است و همان را که قبلاً می¬دانستید، هنور هم می‌دانید.
دو مفهوم A و B را در نظر بگیرید که از مجموعه متون، استحصال شده‌‌اند. همچنین تصور کنید که شما ارتباطی را نیز میان این دو مفهوم یافته‌اید. مثلا اینکه "مناطق بارانی" و "کشت برنج" دارای رابطه‌ای به این صورتند که کشت برنج به مناطق بارانی نیاز دارد (A->B). به علاوه فرض کنید که مفهوم B نیز با مفهوم C، به همین شکل دارای ارتباط است؛ مثلاً "مناطق شمال کشور" و "مناطق بارانی" این رابطه را به هم دارند که مناطق شمال کشور" هستند" منطقه‌ی بارانی (C ISA A). آنچه ما تاکنون داریم تنها اطلاعات است که استخراج شده است، امّا سیستم می‌تواند کمی باهوش¬تر باشد و بتواند با درک این دو گزاره نتیجه دهد که گزاره‌ی سومی نیز قابل طرح است به این صورت که "مناطق شمال کشور" قابل "کشت برنج" است. این مثال نشان می¬دهد که کشف دانش به چه می‌ماند. تاکید در این مثال همانطور که می‌بینید بر نو بودن آن چیزی است که بدست آمده است.
1-2-3 کاربردهای متن¬کاوی
همانطور که می‌بینید تعاریف گسترده‌ای از متن¬کاوی در دست است، در نتیجه این عجیب نیست که درباره‌ی کاربردهای متن¬کاوی نیز عقاید گوناگونی وجود داشته باشد. از اینرو ما تلاش می‌کنیم که تعدادی از کاربردهای مورد قبول از این روند را بررسی کنیم و سعی در تطابق این کاربردها با این تعاریف قبلی نداشته باشیم.
•    جستجو و بازیابی
•    گروه¬بندی  (دسته¬بندی بدون نظارت)  و طبقه¬بندی  (دسته¬بندی بانظارت)
•    خلاصه¬سازی
•    استخراج روابط
•    یافتن و تحلیل گرایشات
•    برچسبت زدن نحوی  
•    ساخت اتوماتیک آنتولوژی   و Thesaurus
•    .......
همانطور می¬بیند بعضی از عناوین مشترک بین زمینه‌هایی چون بازیابی اطلاعات، هوش مصنوعی و نیز پردازش زبانهای طبیعی است. در اینجا به توضیح مختصری از هر کدام بسنده می‌کنیم.
1-1-2-3 جستجو و بازیابی
روشهای جدیدی در رابطه با جستجو و بازیابی اطلاعات با در نظر گرفتن متن¬کاوی، قابل تصور است. همانطور که قبلاً گفته شد، بازیابی اطلاعات دارای این هدف است که از میان مجموعه‌ای از مدارک و متون، آنهایی را که مرتبط¬ترند به نیاز اطلاعاتی کاربر، جدا کنند و به کاربر نشان دهند. بنابراین همیشه شرایطی هست که کاربر نتواند به نیاز اطلاعاتی خود، حتی از میان نتایج دریافت شده، برسد. ممکن است در میان 100 مدرک نیاز به مطالعه باشد تا کاربر آنچه را که می‌خواهد بدست آورد. در بسیاری از شرایط داشتن سیستمی که بتواند جواب دقیق را برگرداند در بسیاری از موارد ترجیح بیشتری دارد. این نوع از سیستمهای IR، به سیستمهای پاسخگو به پرسش ، معروفند.
اگرچه این نوع از سیستمهای بازیابی اطلاعات براساس استفاده از گستره‌ای از تکنولوژی‌ها مانند NLP و یادگیری ماشین استوار است امّا در نهایت آنچه در این سیستمها، نقش اصلی را داراست، یک پایگاه دانش است که از طریق روشهای مبتنی بر NLP و یا روشهای آماری بر روی مدارک موجود در مجموعه ساخته شده است. در استخراج این روابط، می‌توان از متن¬کاوی استفاده کرد. استخراج چنین روابطی در واقع یکی از کاربردهای متن¬کاوی است.
2-1-2-3 گروه¬بندی و طبقه‌بندی داده
یکی از مواردی که می‌تواند به کاربر در یافتن سریعتر اطلاعات مورد نظرش کمک کند. دسته¬بندی اطلاعات موجود است. این دسته¬بندی به کاربر یک نگاه کلی از آنچه در مجموعه متون موجود است می‌دهد. در ساختن این دسته¬بندی دو روش کلی وجود دارد.
در روش اول شما کلاسهای از پیش تعریف شده‌ای از مفاهیم دارید و تلاش می‌کنید که سیستمی داشته باشید که مستندات و مدارک جدید را به یکی از این کلاسها، نگاشت کند. این کار در واقع به طبقه‌بندی داده‌ها  معروف است.
در سوی دیگر، گروه¬بندی داده‌ها، ساختن این کلاسها بطور اتوماتیک است. در واقع با گروه¬بندی مدارک، قصد بر این است که مشخص شود تمرکز مفاهیم در مجموعه‌ی متون، حول چه چیزهایی است. در واقع در اینجا ما کلاس از پیش تعریف شده‌ای نداریم. این دو در واقع مفاهیمی هستند که از داده¬کاوی رایج در پایگاه داده¬ها، به قرض گرفته شده‌اند.
3-1-2-3 خلاصه¬سازی
منظور ما از خلاصه¬سازی، روند ساختن مجموعه‌ای مفاهیم پایه‌ای از متن است تنها در چند خط. در این نوع از متن-کاوی به نظر می‌رسد که اطلاعات جدیدی از متن بدست ندهد. به این دلیل که خود نویسنده احتمالاً می¬دانسته است که چه چیزی می¬خواسته است بگوید و خلاصه‌ی نوشته‌های او، اطلاع جدیدی را اضافه نمی‌کند. گر چه این کار می‌تواند بررسی محتویات مستندات را برای کاربران ساده‌تر کند و آنها را در مسیر رسیدن به آنچه نیاز دارند، سرعت دهد.
4-1-2-3 روابط میان مفاهیم
از جمله واقعیتهایی که می‌توان از یک مجموعه متون دریافت، ارتباط و وابستگی بعضی مفاهیم است با مفاهیم دیگر. این واقعیات بطور مثال می‌تواند بگوید که پدیدار شدن بعضی کلمات ممکن است که وابسته باشد به ظاهر شدن بعضی دیر از کلمات. منظور این است که هر گاه شما مجموعه‌ی اول کلمات را ببینید، ما می‌توانیم انتظار داشته باشیم که مجموعه‌ی دوم لغات را نیز ببینیم. این مفهوم نیز از داده¬کاوی در پایگاه داده¬ به امانت گرفته شده است. ما در این مورد در ادامه بیشتر صحبت خواهیم کرد.
5-1-2-3 یافتن و تحلیل گرایشات
فرض کنید که شما مدیر یک کمپانی تجاری هستید. مشخصاً شما بایستی همواره چشمی بر فعالیتهای رقیبانتان داشته باشید. این می‌تواند هر نوع اطلاعاتی باشد که شما از اخبار، معاملات بورس و یا از مستندات تولید شده توسّط همان کمپانی رقیب گرفته‌اید.
اگر چه در حال حاضر که اطلاعات بطور فرآینده‌ای در حال افزایش است، مدیریت تمامی این منابع داده‌ای قطعاً تنها به کمک چشمانتان ممکن نیست. متن¬کاوی به شما این اجازه را می‌دهد که بطور اتوماتیک گرایشات و تغییرات جدید را بیابید. در واقع آنچه اصولاً باید از متن¬کاوی انتظار برود اینست که به شما بگوی چه اخباری در میان گسترده‌ای از اخبار به آنچه می‌خواهید مرتبط است و در این میان کدام خبر جدید است، چه پیشرفتهایی در زمینه‌ی کاری شما صورت می‌گیرد و علایق و گرایشات فعلی چگونه است و با چه روندی تغییر می‌کند. با استفاده از این اطلاعات، مدیر تنها از اطلاعات کشف شده برای بررسی وضعیت رقیب می‌تواند سود جوید.

6-1-2-3 برچسب زدن نحوی  (POS)
اگر چه تعدادی زیادی معتقد به این نیستند که اینکار جزئی از متن¬کاوی است ولی در
  Text mining in a digitag library برای مثال سیستمی به نام GATE در دانشگاه شفیلد، در یک کتابخانه‌ی دیجیتال به این قصد جاگذاری شده است. GATE شامل ابزاراتی است برای برچسب زدن بر جملات. برای مثال این سیستم می‌تواند در داخل یک متن، نام موقعیتهای جغرافیایی، نام اشخاص و چیزهایی شبیه اینرا بیابند. به این خاطر این سیستم بیشتر شامل استخراج اطلاعات است تا استخراج دانش. در عین حال، POS اغلب نقش بزرگی را در پردازش زبانهای طبیعی بازی می‌کند. در حقیقت این اولین قدم در پردازش زبان طبیعی است و همانطور که خواهیم دید پردازش زبان طبیعی یکی از پایه‌های متن¬کاوی است.
7-1-2-3 ایجاد Thesaurus و آنتولوژی بصورت اتوماتیک
می‌توان Thesaurus و آنتولوژی را بعنوان یک ابزار مناسب برای نمایش دانش استخراج شده از یک مجموعه متن دانست. Thesaurus ، مجموعه‌ای است از لغات به اضافه‌ی تعاریفشان و رابطه‌ی میان آنها. این روابط معمولاً به کمک دست از دل مجموعه‌ی متون استخراج می‌شود. ما می‌توانیم Thesaurusهای خاص یا همه¬منظوره داشته باشیم. رابطه‌ی میان این کلمات می‌تواند چیزهای شبیه "کلی‌تر"، "خاص‌تر" و "مرتبط" یا نظیر آن باشد. اگر ما Thesaurusی داشته باشیم که در آن تمام ارتباطات میان لغات مشخص شده باشد، می‌توانیم آنرا آنتولوژی این لغات بنامیم. هر دوی Thesaurus و آنتولوژی کاملاً مفید هستند چون به مادنیای لغات و مفاهیمی را نشان می‌دهند که در مجموعه‌ی متون ما وجود دارد.
اگر شما یک موتور جستجو رادر نظر بگیرید، یک Thesaurus ، می‌تواند مجموعه لغاتی باشد که ما می‌توانیم در حین جستجو بکار بریم.
Thesaurus‌ها اکنون می‌توانند تنها بوسیله‌ی دست ساخته شوند و به همین خاطر ساخت آنها بسیار سخت و وقت-گیر است. فرد که می‌خواهد یک Thesaurus بسازد بایستی که ارتباطات میان تمام لغات را بیابد. این بسیار مورد ترجیح است اگر ما می توانستیم آنها را اتوماتیک بسازیم.
اگر چه زمینه‌ای است که ما نمی¬توانیم هیچ مرزی بر آن قائل شویم. هدف نهایی اینست که هر ذره از دانشی که توسّط بشر قابل درک بوسیله‌ی کامپیوتر نیز درک شود.
2-2-3 فرآیند متن¬کاوی
متن¬کاوی فرآیندی است که شامل فیلدهای تکنولوژیکی فراوانی است. بازیابی اطلاعات، داده¬کاوی و هوش مصنوعی و زبانشناسی محاسباتی همه فیلدهایی هستند که در این زمینه، نقشی را دارا هستند. امّا بطور کلی دو فاز اصلی در فرآیند متن-کاوی وجود دارد که در شکل 3-3 نشان داده شده است.
 
شکل3-3 فرایند متن¬کاوی
اولین فاز اصلاح و پالایش متن است. خروجی نخستین فاز می‌تواند دو قالب مختلف داشته باشد؛ مبتنی برسند   و مبتنی بر مفهوم  . در اولین فرمت نمایش، آنچه برای ما مهم است نحوه‌ی نمایش بهتری است برای مستندات. این میتواند، تبدیل آنها به یک فرمت میانی و نیمه ساخت¬یافته  باشد یا بکار بردن یک ایندکس بر روی آن یا هر نوع نمایش دیگری که کارکردن با مستند را کاراتر می‌کند. در این حال هر موجودیت   در این نمایش در نهایت باز هم یک مستند خواهد بود. در نوع دوم بهبود بخشی به نمایش مستند، مفاهمی و معانی موجود در سند و نیز ارتباط میان آنها و هر نوع اطلاعات مفهومی دیگری که قابل استخراج می‌شود. در این نوع نمایش دیگر با مستندات بعنوان یک موجودیت مواجه نیستم بلکه با مفاهیمی روبروییم که از این مستندات استخراج شده‌اند.
قدم بعدی استخراج دانش است از این فرمهای میانی نمایش مستندات. بسته به نحوه‌ی نمایش یک مستند روال استخراج دانش برای یک مستند متفاوت است. نمایش مبتنی بر مستند، برای گروه¬بندی، طبقه‌بندی، ویژوال¬سازی  و نظایر آن استفاده می شود، درحالیکه نمایش مبتنی بر مفهوم برای یافتن روابط میان مفاهیم، ساختن اتوماتیک Thesaurus و آنتولوژی و نظایر آن بکار می‌رود.
3-3-3 روشهای متن¬کاوی
تعداد زیادی روش در فاز استخراج دانش وجود دارد. در عین حال تمام این روشها را شاید بتوان به دو دسته اصلی تقسیم کرد. این دو دسته اصلی، روشهای مبتنی بر کارایی و روشهای مبتنی بر دانش هستند. در روش اولی، طراحان نگران کارایی سیستم هستند و طوری سیستم را طراحی می‌کنند که بهترین کارایی و سرعت را داشته باشد. روشهای رایج¬تر در این نوع نگرش، روشهای آماری و نیز شبکه‌های عصبی هستند.
روشهای آماری بر پایه هر نوع اطلاعات آماری است که از متون قابل استخراج است. مواردی چون تکرار لغات به تنهایی، تکرار لغات با هم و چیزهایی شبیه آن.
یافتن روابط
اینچنین در نظر بگیرید که مجموعه‌ای ازکلمات مثل A= {w1 , w2 , ..., wn} و نیز مجموعه‌ای از مستندات ایندکس شده مثل T= {t1 , t2 , .... , tn} وجود دارد. در اینجا هر t1، با یک زیرمجموعه از A در ارتباط است و این ارتباط به شکل ti(A)  نشان داده می‌شود.
اکنون فرض کنید که   یک مجموعه از کلمات کلیدی باشند. مجموعه‌ی تمام مستندات t در T، به صورتی که   باشد، مجموعه‌ی پوششی برای W خوانده می‌شود و به شکل [W] نشان داده می‌شود.
هر زوج(W,w) که   مجموعه از لغات است و نیز  ، یک قانون رابطه خوانده می‌شود و به شکل   نمایش داده می‌شود.
با داشتن یک قانون رابطه مثل   خواهیم داشت:
 ، میزان پشتیبانی از رابطه خوانده می‌شود با توجه به مجموعهT.
  ، میزان اطمینان از قانون R خوانده می‌شود با توجه به مجموعه T.
بوسیله‌ی   منظور ما احتمالی است که یک متن کلمه‌ی کلیدی w را دارا باشد اگر هم اکنون کلمات مجموعه W را داراست.
برای اینکه قانونی این دو شرط پشتیبانی و پوشش را برآورده سازد باید مقدار این دو پارامتر در مورد آن قانون از میزانی خاص بیشتر باشد این میزان به نوع مجموعه‌ی متون وابسته است.
 
شکل 4-3 چند مثال نوعی را در این موردنشان می‌دهد.

در سوی دیگر روشهای مبتنی بر دانش قرار دارند که از زاویه دید دیگری به این مسئله نگاه می‌کنند. آنها سعی می‌کنند اولاً تا حد ممکن مفاهیم موجود را از داخل مجموعه‌ی متون استخراج کنند و ثانیاً بین این مفاهیم روابطی بر قرار کنند.
استفاده از این روش بسیار وابسته به NLP است. در حقیقت این هدفی است که NLP نیز آنرا دنبال می‌کند و آن درک متن است. سیستمهایی که از این روشها استفاده می‌کنند  در حال حاضر زیاد نیستند ولی DR-LINK[16] از دانشگاه Syracus یکی از آنهاست.


مراجع

[1] داده¬کاوی (Data Mining)، تالیف مهمد کانتاردزیک، ترجمه امیر علیخانزاده، 1385، ویرایش اول
[2] Introduction to Data Mining and Knowledge Discovery، Two Crows Corporation، 1999
[3] Data Mining: Concepts and Techniques، M.Kamber and J.Han، 2001
[4] مقاله Algorithms for Association Rule Mining – A General Survey and comparison نوشته Jochen Hipp و Gholamreza Nakhaeizadeh ، در کنفرانس ACM SIGKDD July 2000
[5] مقاله Comparative Study of Association Rules Mining Algorithms نوشته Stefan Holban (http://www.bmf.hu/conferences/saci04/Gyorodi.pdf)
[6]
http://ece.ut.ac.ir/DBRG/seminars/Keykhah/Data Mining/Data mining.doc
       
http://ece.ut.ac.ir/DBRG/seminars/Ghadimi-Abbasi-Pashaei/Document/datamining_Introduction.doc









پایان نامه

برای دیدن ادامه مطلب از لینک زیر استفاده نمایید

انجام پایان نامه | دانلود مقاله

سفارش پایان نامه

نقشه