بخشی از مقاله
(داده كاوي)
تعريف :
Data Mining represents a process developed to examine large amounts of
data routinely collected. The term also refers to a collection of tools used to
perform the process. Data mining is used in most areas where data are
collected-marketing, health, communications, etc.
داده كاوي فرآيند بكارگيري يك يا چند تكنيك آموزش كامپيوتر، براي تحليل و استخراج داده هاي يك پايگاه داده مي باشد.در واقع هدف داده كاوي يافتن الگوهايي در داده هاست.
دانش كسب شده از فرآيند داده كاوي بصورت مدل يا تعميمي از داده ها نشان داده مي شود.
چندين روش داده كاوي وجود دارد با اين وجود همه روشها “ آموزش بر مبناي استنتاج “ را بكار مي برند.
آموزش بر مبناي استنتاج، فرآيند شكل گيري تعاريف مفهوم عمومي از طريق مشاهده مثالهاي خاص از مفاهيمي كه آموزش داده شده اند، است.
مثال زير نمونه اي از دانش بدست امده از طريق فرايند اموزش بر مبناي استنتاج است:
آيا تا كنون فكر كرده ايد، فروشگاههاي بزرگ اينترنتي در mail هاي خود به مشتريان از چه تبليغاتي استفاده مي كنند؟ و آيا اين تبليغات براي همه مشتريان يكسان است؟
پاسخ اين است كه از روي دانش كسب شده از اطلاعات خريد افراد و نتيجه گيري از اين دانش، اين كار را انجام مي دهند.مثلا در نظر بگيريد يك قانون در پايگاه داده بصورت زير استخراج مي شود:
دقت = 80% : سيگار مي خرند ^ نان مي خرند كساني كه شير مي خرند
از روي اين قانون فروشگاه مي تواند به تمام كساني كه شير مي خرند تبليغات سيگار و انواع نان را نيز بفرستد.همچنين اين قانون در چيدن قفسه هاي فروشگاه نيز بي تاثير نخواهد بود.
{شير و نان و سيگار در قفسه هاي كنار هم چيده شوند}
كشف دانش در پايگاه داده 1
KDD يا كشف دانش در پايگاه داده اصطلاحي است كه مكررا بجاي داده كاوي بكار مي رود. از نظر تكنيكي، KDD كاربردي از روشهاي علمي داده كاوي است.
بعلاوه براي انجام داده كاوي فرايند KDD شامل :
1- يك روش براي تهيه داده ها و استخراج داده ها ،
2- تصميم گيري درباره عملي كه پس از داده كاوي بايد انجام شود ، مي باشد.
آيا داده كاوي براي حل مسائل ما مناسب است؟
تصميم گيري در مورد اينكه آيا داده كاوي را به عنوان استراتژي حل مساله بكار ببريم يا نه، يك مساله دشوار است.
اما به عنوان نقطه شروع چهار سؤال عمومي را بايد در نظر بگيريم :
1. آيا به وضوح مي توانيم مساله را تعريف كنيم ؟
2. آيا بطور بالقوه داده با معني وجود دارد ؟
3. آيا داده ها شامل “ دانش پنهان” هستند يا فقط براي هدف گزارشگري مناسبند ؟
4. آيا هزينه پردازش داده (براي داده كاوي) كمتر از سود حاصل از دانش پنهان بدست آمده از پروژه داده كاوي است ؟
يك مدل پردازش داده كاوي ساده :
در يك ديد كلي ، ما مي توانيم داده كاوي را به عنوان يك فرآيند چهار مرحله اي تعريف كنيم :
1. جمع آوري يك مجموعه از داده ها براي تحليل
2. ارائه اين داده ها به برنامه نرم افزاري داده كاوي
3. تفسير نتايج
4. بكارگيري نتايج براي مساله يا موقعيتهاي جديد
شكل فوق يك دياگرام از فرآيند داده كاوي را نشان مي دهد.
- جمع آوري داده ها :
فرآيند داده كاوي احتياج به دسترسي به داده ها دارد. داده ممكن است در تعدادي ركورد، در چندين فايل پايگاه داده ذخيره شود و يا ممكن است داده فقط شامل چند صد ركورد در يك فايل ساده باشد.
با توجه به اينكه معمولا داده هاي واقعي شامل چندين هزار ركورد مي باشند، اولين گام در داده كاوي تهيه زير مجموعه مناسبي از داده براي پردازش است. گاهي اين مرحله احتياج به تلاش انسانهاي بسياري دارد. در كل سه راه متداول براي دستيابي فرآيند داده كاوي به داده وجود دارد :
1. ذخيره داده در “ انبار داده 1 ”
2. ذخيره داده در پايگاه داده رابطه اي
3. ذخيره داده در فايل ساده
- داده كاوي :
همانطور كه در شكل مشخص است مرحله بعد داده كاوي است. با اين حال قبل از ارائه داده به ابزار داده كاوي ، چندين انتخاب داريم:
1. يادگيري بايد تحت كنترل باشد يا بدون كنترل ؟
2. كدام نمونه ها در داده ها ي جمع آوري شده براي ساخت مدل بكار ميروند و كدامها براي تست مدل ؟
3. كدام صفتها از صفتهاي موجود انتخاب مي شوند ؟
و ....
- تفسير نتايج :
در اين مرحله خروجيهاي مرحله داده كاوي آزمايش مي شوند تا مشخص شود كه آيا اين نتايج قابل استفاده و جالب هستند يا نه؟ همانطور كه در شكل مي بينيم اگر نتايج بهينه نباشد مي توانيم فرآيند داده كاوي را با صفات و نمونه هاي جديد تكرار كنيم. همچنين ما مي توانيم به” انبار داده “ مراجعه كنيم و فرآيند استخراج دانش را تكرار كنيم.
ـ بكارگيري نتايج :
هدف نهايي ما بكارگيري نتايج براي موقعيتهاي جديد است. به عنوان مثال دانشي كه در يك پايگاه داده فروشگاه بيان مي كند كساني كه مجله ورزشي مي خرند همچنين سيگار هم مي خرند؛ در شكل گيري استراتژيهاي فروشگاه در چيدن قفسه ها ، تهيه كاتالوگ ها و ... تاثير مي گذارد.
استراتژيهاي داده كاوي :
همانطور كه در شكل زير مي بينيم استراتژيهاي داده كاوي بطور كلي مي توانند به دو دسته “ تحت كنترل ” يا “ بدون كنترل ” تقسيم مي شوند. آموزش تحت كنترل مدلهايي را با بكارگيري صفات ورودي براي تشخيص مقدار صفت خروجي مي سازد. حتي برخي از الگوريتمهاي ” آموزش تحت كنترل” امكان تشخيص چندين صفت خروجي را به ما مي دهند. به صفات خروجي ، صفات وابسته نيز
مي گوييم. زيرا مقدار آنها به مقدار يك يا چند صفت ورودي بستگي دارد. به همين ترتيب به صفات ورودي، صفات مستقل نيز مي گوييم.
هنگامي كه “ آموزش بدون كنترل ” را بكار مي بريم تمامي صفات ورودي هستند و صفت خروجي نداريم.
آموزش تحت كنترل با توجه به اينكه صفات خروجي مقوله اي هستند يا عددي و آيا مدلهاي ايجاد شده براي مشخص كردن موقعيت كنوني ايجاد شدند يا پيش بيني خروجيهاي آينده ، به چندين قسمت تقسيم مي شوند. (منظور از صفات مقوله اي ، صفاتي هستند كه مقدار آنها تعداد محدود و مشخصي است، مثل صفاتي كه مقدار آنها Boolean است كه دو مقدار {true, false} دارد).
طبقه بندي1 :
طبقه بندي احتمالا از همه استراتژيهاي داده كاوي قابل درك تر است. طبقه بندي سه خصوصيت دارد :
1. آموزش تحت كنترل است.
2. متغير وابسته ، مقوله اي است.
3. تاكيد بر روي ساخت مدلهايي است كه قادر به اختصاص نمونه هاي جديد به يكي از كلاسهاي تعريف شده باشند.
تخمين2 :
مشابه طبقه بندي ، هدف يك مدل تخمين نيز مشخص كردن مقدار براي يك صفت خروجي است؛ اما بر خلاف طبقه بندي صفات خروجي براي مساله تخمين، عددي است بجاي مقوله اي .
بعنوان يك مثال براي تخمين ، پايگاه داده اي را در نظر بگيريد كه هر ركورد آن اطلاعاتي را راجع به شخصي دارد مثل : محل زندگي، غذاي روزانه در اغلب روزها، نوع ماشين شخصي ، درآمد ماهانه و ....
هدف الگوريتم تخمين در اين مثال ايجاد مدلي براي تشخيص درآمد ماهانه نمونه هاي جديد (ركوردهاي جديد) مي باشد.{كه بقيه صفات آنها بجز درآمد ماهانه مشخص است}.
بيشترتكنيكهاي تحت كنترل قادرند كه يا مسائل طبقه بندي را حل كنند يا تخمين ، اما نه هردورا.
پيش گويي Perdiction :
تشخيص تفاوت بين پيش گويي و طبقه بند ي يا تخمين كار ساده اي نيست. با اين حال هدف يك مدل پيش گويي ، برخلاف طبقه بندي يا تخمين، بجاي مشخص كردن رفتار كنوني، مشخص كردن خروجيهاي آينده است. بيشتر روشهاي داده كاوي كه براي طبقه بندي يا تخمين مناسبند، براي ساخت مدلهاي پيش گويي نيز بكار ميروند. عملا اين طبيعت داده است كه مشخص مي كند يك مدل براي تخمين مناست است يا طبقه بندي ويا پيش گويي.
:Unsupervised Clustering دسته بندي بدون كنترل
در دسته بندي بدون كنترل، ما ديگر صفات خروجي نداريم كه ما را در فرآيند يادگيري راهنمايي كند، در عوض برنامه مربوطه ساختارهاي دانش را با بكارگيري معيارهاي “ كيفيت دسته” براي گروه بندي داده ها به دو يا چند كلاس (دسته)، بدست مي آورد.
.
يك هدف اساسي دسته بندي بدون كنترل، كشف ساختارهاي مفهومي در داده است.
كاربردهاي متداول دسته بندي بدون نظارت عبارتند از :
- مشخص مي كند كه آيا ارتباطات با معني در شكل مفاهيم مي تواند در داده ما پيدا شود يا نه ؟
- كارآيي روش آموزش تحت كنترل را مشخص مي كند.
- بهترين صفات ورودي براي آموزش تحت كنترل را مشخص مي كند.
- شناسايي از حد خارج شده ها (outlier)
تحليل سبد بازاري Market Basket Analyse :
هدف اين مرحله پيدا كردن ارتباطات جالب ميان محصولات (خرده فروشي) است. خروجي اين مرحله به فروشندگان كمك مي كند تا بهتر بتوانند قفسه ها را بچينند يا كاتالوگها را تنظيم كنندو نيز در ايجاد استراتژيهاي فروشگاه نيز كارا است. مثالي از دانش اين مرحله به فرم زير است (در يك فروشگاه)
سيگار مي خرند كساني كه قهوه مي خرند
:Supervised Data Mining تكنيكهاي داده كاوي تحت كنترل
تكنيكهاي داده كاوي براي بكارگيري استراتژي داده كاوي براي يك مجموعه داده بكار مي رود. يك تكنيك داده كاوي از دو قسمت تشكيل شده است:
1. الگوريتم.
2. ساختار دانش مربوطه مثل درخت يا يك مجموعه قوانين درخت تصميم كه در قسمتهاي قبلي توضيح داديم.
در اينجا چندين روش ديگر براي داده كاوي نظارت شده ارائه مي دهيم :
1. شبكه عصبي :
يك شبكه عصبي مجموعه اي از نودهاي به هم پيوسته است كه طراحي مي شوند تا رفتار مغز انسان را شبيه سازي كنند.
چون مغز انسان از بيليونها عصب تشكيل شده و شبكه هاي عصبي كمتر از صد نود دارند مقايسه يك شبكه عصبي و رفتار مغز كمي غير متعارف است. با اين وجود شبكه هاي عصبي با موفقيت ، براي حل مسائل بكار برده مي شوندو براي داده كاوي نيز كاملا ابزار مناسبي است .
شبكه هاي عصبي در شكلها و فرمهاي گوناگوني وجود دارند و هم براي آموزش تحت كنترل و هم دسته بندي بدون كنترل بكار مي روند. درهمه موارد ، مقادير ورودي براي شبكه عصبي بايد عددي باشند. شبكه feed-forward يك نوع شبكه عصبي مناسب براي مسائل آموزش تحت كنترل مي باشد.
2. برگشت آماري1 :
برگشت آماري يكي از روشهاي آموزش تحت كنترل است كه يك مجموعه از داده هاي عددي را توسط ايجاد معادلات رياضي مرتبط با يك يا چند صفت ورودي به يك صفت خروجي عددي نسبت
مي دهد.
يك مدل “ برگشت خطي ” توسط يك صفت خروجي كه مقدارش بوسيله :
“ جمع مقادير صفت هاي ورودي × يك وزن مشخص “ مشخص مي شود.
مثلا اگر يك پايگاه داده شامل صفات ورودي A , B, C , D و صفت خروجي E باشد، رابطه زير
مي تواند يك مدل برگشت خطي باشد :
E = 0.5 C – 0.2 B + A + 0.32
ميبينيم كه E صفت خروجي است كه مقدارش توسط تركيب خطي صفات A , B , C تعيين مي گردد.
همانند شبكه عصبي ، در اين روش نيز همه وروديها بايد عددي باشند و در صورتيكه داده ها در پايگاه داده مقوله اي باشند بايد آنها را به داده هاي عددي تبديل كنيم.
3. قوانين وابستگي2 :
به تفصيل در بخشهاي بعد مورد بحث قرار مي گيرد.
قوانین پیوستگی:
یکی از مهمترین بخشهای داده کاوی، کشف قوانین وابستگی در پایگاه داده است.این قوانین، لزوم وقوع برخی صفات(آیتم ها) را در صورت وقوع برخی دیگر از آیتمها، تضمین می کند.
برای روشن شدن مطلب یک فروشگاه خرده فروشی را در نظر بگیرید. مشخصات اجناس خریده شده توسط هر مشتری در یک رکورد پایگاه داده ذخیره می شود.به هر رکورد یک شناسه (TID) نسبت داده می شود.فرض کنید که مجموعه I شامل تمام آیتمها(اجناس) فروشگاه باشد.
اگر I x,y و x∩y=ø آنگاه x=>y یک قانون وابستگی است که بیان میکند اگریک مشتری اجناس مجموعه x را بخرد، اجناس مجموعه y را هم می خرد. این چنین قوانین، تأثیر مهمی در تایین استراتژیهای فروش، بخش بندی مشتریان، تنظیم کاتالوگها و... دارد. همچنین کشف قوانین وابستگی، کاربردهای بسیاری در علوم مختلف نیز دارد.
تعریف مسأله:
مجموعه آیتم: به هر زیر مجموعه از مجموعه آیتمها I)) ' یک مجموعه آیتم ' میگوییم.
در بیشتر الگوریتمها مساله کشف قوانین پیوستگی به دو زیر مساله تقسیم می شود:
1.پیدا کردن تمامی زیر مجموعه های مجموعه I [مجموعه آیتمها] که تکرار (وقوع) آنها در پایگاه بیشتر از یک حد تایین شده است.
به مجموعه آیتمهایی که تعداد وقوع آنها در پایگاه بزرگتر(یا مساوی)حد تایین شده است
' مجموعه آیتمهای بزرگ'، وبه بقیه' مجموعه آیتمهای کوچک' می گوییم.
2.بکارگیری مجموعه آیتمهای بزرگ برای تولید قوانین مطلوب.
تعریف:
پوشش2: مجموعه I شامل تمام آیتمها و مجموعه آیتم x را در نظر بگیرید ، می گوییم پوشش x در پایگاه داده برابر است با ℓ اگر و فقط اگر تعداد وقوع مجموعه آیتم x در پایگاه داده برابر با ℓ باشد.
Support(x)=ℓ
درجه اطمینان:3 مجموعه I شامل تمامی اقلام و مجموعه آیتمهای x و y مفروضند. درجه اطمینان قانون x=>yبرابر است با : x∩y=ø
Conf(x=>y) = support(xUy) support(x)
الگوریتم : Apriori این الگوریتم(Agrawal & Srikant ,1994) برای تولید مجموعه اقلام بزرگ به این ترتیب عمل می کند:
ابتدا با یک دور خواندن پایگاه داده مجموعه اقلام بزرگ یک عضوی ((1-itemsetرا مشخص می کنیم.[مجموعه اقلام 1 عضوی که تعداد تکرار آنها در DB از حد تایین شده(minsup) بیشتر است.]
سپس با استفاده ازمجموعه اقلام بزرگ یک عضوی، مجموعه اقلام دو عضوی را ایجاد می کنیم و برای تایین پوشش مجموعه اقلام دو عضوی یک بار دیگر کل پایگاه داده را می خوانیم تا مجموعه اقلام بزرگ دو عضوی را تایین کنیم.
به همین ترتیب با استفاده از مجموعه اقلام بزرگ دو عضوی مجموعه اقلام سه عضوی را ایجاد کرده و با خواندن دوباره پایگاه داده پوشش هر مجموعه قلم سه عضوی را مشخص کرده و مجموعه اقلام بزرگ سه عضوی تولید می شوند و این کار را برای مجموعه های 4عضوی و ... انجام میدهیم تا مرحله ای که هیچ مجموعه آیتم بزر الگوریتم:
L1= { larg-1-itemset }
for ( k=2; Lk-1 ≠0;k+1 ) do
begin
C k=apriori – gen(Lk-1 ) //عضوی k عضوی با استفاده از اقلام بزرگ1-k ساخت زیر مجموعه های
for all transaction lεD do
begin
C t=subset(Ck,l); // رخ دادند. عضوی در تراکنش k تست اینکها کدام مجموعه آیتمهای
for all candidate cεCt do
c.count++;
end
Lk={ cεCk l c.count ≥minsup}
end;
Answer=Uk Lk
(تبصره : اگر یک مجموعه آیتم بزرگ باشد[تکرارش درپایگاه داده بیشتر از minsupباشد] تمامی زیرمجموعه های آن نیز بزرگ هستند.)
چون هدف، تولید مجموعه اقلام بزرگ است، در الگوریتم aprioriدر هر مرحله پس از ایجاد مجموعه اقلامk عضوی از مجموعه اقلام بزرگ k-1 عضوی قبل از خواندن پایگاه داده برای تشخیص پوشش مجموعه اقلام k عضوی،
ابتدا باید برای هر مجموعه قلم ببینبم آیا زیر مجموعه k-1 عضوی اش بزرگ هستند یا نه، اگر حتی یک زیر مجموعه k-1 عضوی اش هم بزرگ نباشد، آن مجموعه قلم k عضوی نمی تواند بزرگ باشد.(طبق قضیه) و آن را حذف می کنیم.
برای روشن تر شدن الگوریتم به مثال زیر توجه کنید:
minsup=3 Database:
Items TID
1 3 4 5 100
2 3 5 200
1 2 3 5 300
2 5 400
1 3 4 5 500
گام1:ایجاد مجموعه اقلام 1 عضوی:
L 1مجموعه آیتمهای بزرگ: مجموعه آیتمهای 1 عضوی:
{1}=3 {1}=3
{2}=3 {2}=3
{3}=4 → {3}=4
{5}=5 {4}=2
{5}=4
گام2: ایجاد مجموعه آیتمهای دو عضوی با استفاده از مجموعه آیتمهای بزرگ 1 عضوی:
L2مجموعه آیتمهای بزرگ دو عضوی: مجموعه آیتمهای 2 عضوی:
{1,3}=3 {1,2}=1
{2,5}=3 {1,3}=3
{3,5}=3 → {1,5}=3
{1,5}=3 {2,3}=2
{2,5}=3
{3,5}=4
گام3:ایجاد مجموعه آیتمهای سه عضوی با استفاده از مجموعه آیتمهای بزرگ دو عضوی:
مجموعه آیتمهای بزرگ سه عضوی: مجموعه آیتمهای 3عضوی:L3
{1,3,5}=3 {1,3,5}=3 →
Answer=L1 U L2 U L3={{1} {2} {3} {5} {1,3} {2,5} {3,5} {1,5} {1,3,5}}
الگوریتم : Aprior TID
در این الگوریتم (Agrawal & Srikant ,1994)در ابتدا فضای جستجو پایگاه داده اولیه است که هر تراکنش آن را به عنوان مجموعه ای از مجموعه قلم های تک عضوی می بینیم:
به این معنی که تراکنش ((100 l 1,2,3 به صورت (100 l{1}{2}{3})در نظر گرفته می شود
سپس همانند الگوریتم aprioriمجموعه اقلام 1 عضوی را ایجاد کرده و تعداد تکرار آنها را در پایگاه می شماریم و مجموعه اقلام بزرگ 1 عضوی را مشخص می کنیم.
همانند الگوریتمapriori با استفاده ازعناصر مجموعه آیتمهای 1عضوی بزرگ، مجموعه آیتمهای دو عضوی را ایجاد می کنیم.(چون هر مجموعه آیتم k عضوی از ترکیب دو مجموعه k-1 عضوی تشکیل شده است برای شمردن تعداد تکرار یک مجموعه kعضوی در پایگاه می توان در هر تراکنش به دنبال مجموعه آیتمهایk-1 عضوی تولید کننده آن مجموعه آیتم، گشت. یعنی مثلا برای شمردن تکرار مجموعه آیتم {1,2,3}در هر تراکنش باید ببینیم آیا (1,2)و(1,3)در مجموعه هست یا نه.)
سپس برای هر تراکنش TIDمربوطه را به همراه تمامی مجموعه آیتمهای kعضوی که در تراکنش هست[تولید کننده های k-1عضوی اش در تراکنش هست] به عنوان تراکنش پایگاه جدید اضافه می کنیم.(برای ا ستفاده مجموعه آیتمهای k+1) پایگاه جدید Ĉk →
وتراکنشهایی که هیچ مجموعه آیتم kعضوی را پوشش ندهند به پایگاه جدید راه پیدا نمی کنند.سپس مجموعه اقلام k+1عضوی را با استفاذه از مجموعه اقلام kعضوی بزرگ ایجاد می کنیم ودر پایگاه داده جدید به دنبال تعداد تکرارهای این مجموعه اقلام می گردیم.[در واقع برای هر مجموعه آیتمk+1عضوی در هر تراکنش جستجو می کنیم ببینیم آیا دو مجموعه kعضوی تولید کننده اش در تراکنش است یا نه.]
سپس TIDاین تراکنش به همراه تمامی مجموعه آیتمهای k+1عضوی که پوشش میدهد به پایگاه داده جدید دیگری اضافه می کنیم، پایگاه داده جدید → Ĉk+1
و این کار را به ازای تمامی تراکنشها تکرار می کنیم.
عملیات بالا را زمانی که پایگاه داده جدید ایجاد شده (Ĉk )تهی نباشد ادامه می دهیم.
الگوريتم partition :
اين الگوريتم) Savasere &Navathe & Omiecinski,1995) براي بدست آوردن مجموعه آيتمهاي بزرگ از دو قسمت تشكيل شده است. در قسمت اول اين الگوريتم پايگاه داده را به چندين بخش مجزا از نظر منطقي تقسيم مي كند وهمهً مجموعه آيتمهاي بزرگ محلي (مجموعه آيتمهايي كه تعداد تكرار آنها از minsupp محلي كه براي هر بخش در نظر گرفته شده بيشتر است) براي هر بخش بطور مجزا توليد مي شود .
سپس در انتهاي مرحله يك ، همه مجموعه اقلام بزرگ در هر بخش باهم مجموعه اقلام بزرگ بالقوه در سطح كل پايگاه داده را تشكيل مي دهند (مجموعه Σ). درقسمت دوم، پوشش (تعداد تكرار ) هر مجموعه آيتم در مجموعه اقلام بالقوه (Σ) در كل پايگاه داده شمارش مي شود و مجموعه اقلام بزرگ واقعي محاسبه مي شوند .
توجه: براي هر بخش يك minsupp محلي در نظر گرفته مي شود و يك minsupp كلي براي كل پايگاه داده نيز داريم.
نحوه توليد مجموعه اقلام بزرگ در هر بخش به صورت زير است:
1- ابتدا به ازاي هر آيتم a در مجموعه I ( آيتم ها ) ، ID تراكنش هايي در بخش مربوطه از DB كه شامل آيتم a مي باشند را مشخص مي كنيم.
بخش2 t(a)={400,500,601} بخش1t(a)={100,300}
سپس همانند الگوريتم apriori ، ابتدا مجموعه اقلام يك عضوي بزرگ را ايجاد مي كنيم . سپس از روي آنها مجموعه اقلام بزرگ دو عضوي را ايجاد ميكنيم و …
با اين تفاوت كه در اين الگوريتم براي محاسبه پوشش (تعداد وقوع ) هر مجموعه آيتم مثل
A={i1,i3,i5} i1,i3,i5 I
تعداد اعضاي مجموعه t(A)=t(i1)t(i3)t(i5)را مي شماريم (به جاي خواندن دوبارهDB )، كه t(x) مجموعه ID تراكنش هاي شامل x است (در همان بخش).
پس از اينكه تمام مجموعه اقلام بزرگ(مجموعه اقلامي كه تعداد تكرار آنها در اين بخش از DB بزرگتر از minsupp محلي است ) را بدست آورديم همين كار را براي بخش هاي ديگر تكرار مي كنيم .
در صورتيكه مجموعه اقلام بزرگ براي بخش i را ، i بناميم، مجموعه به صورت زير ايجاد مي شود:
=12…n
حال مجموعه Σشامل مجموعه اقلام بزرگ بالقوه است .اكنون يك بار ديگر پايگاه داده را مي خوانيم وپوشش هر كدام از مجموعه اقلام كانديد را در كل پايگاه داده مشخص مي كنيم.
در صورتيكه پوشش A ازminsup،عمومي بزرگتر باشد .يك مجموعه اقلام بزرگ است.
تعداد بخش ها در پايگاه به گونه اي تعيين شده كه هر بخش به همراه ساختمان داده هاي مورد نياز در حافظه جاي گيرد .
الگوريتم هاي MaxEclat,Eclat :
در اين الگوريتم ها(Zaki,1997) نيز همانند partition ابتدا مجموعهt(ai) به ازاي هر ai متعلق I (مجموعه اقلام كلي)توليد مي شود.(t(ai) شناسه تراكنشهايي را دارد كه شامل ai هستند.)
ولذا پس از ايجاد هر مجموعه آيتم k عضوي (از مجموعه هاي k-1 عضوي) مثل A={a1,a2,a3} براي محاسبه پوشش A در پايگاه داده تعداد اعضاي مجموعه ∩ t(a2) ∩ t(a3) t(A)=t(a1) را شمارش مي كنيم.
با توجه به اينكه تعداد مقادير مياني با انجام اين كار (اشتراك ها) بسيار زياد مي شود، فضاي حافظه اصلي جوابگو نيست و لذا راه حل زير ارائه شد.
با توجه به تعاريف رياضي، مجموعه تمام زير مجموعه هاي يك مجموعه (مجموعه تواني) ، يك شبكه را تشكيل ميدهند.اين الگوريتم ، اين شبكه را به چندين زير شبكه تقسيم ميكند و براي هر زير شبكه بطور مجزا مجموعه آيتمهاي بزرگ را توليد مي كند. در اين صورت ساختمان داده هاي هر زير شبكه به راحتي در حافظه اصلي جاي مي گيرد .
در شكل زير ، زير شبكه مربوط به آيتم [A] را مشاهده مي كنيم كه شامل اعضايي است كه با A شروع مي شوند. به نودهايي كه مستقيما با [A] در ارتباطند ’اتم’ها مي گوييم.
درهرزيرشبكه با داشتن اتمهاي مربوطه ميتوان استراتژيهاي پايين به بالا (partition,apriori ) ويا بالا به پايين را براي جستجوي مجموعه اقلام بزرگ بكار برد.(در شكل جستجوي پايين به بالا را مشاهده مي كنيم).
S در الگوريتم فوق مجموعه اتمهاي زير شبكه است و F مجموعه اقلام بزرگ نهايي است و Tiمجموعه اقلام بزرگ جديد هستند.(يك سطح بالاتر).
در روش بالا به پايين در هر زير شبكه از بزرگترين مجموعه آيتم در آن زيرشبكه شروع مي كنيم و به سمت اتمها پيش مي رويم. هر گاه يك نود مجموعه قلم بزرگ را مشخص كند ديگر براي آن نود فرزندانش چك نمي شوند زيرا مطابق قضيه قبلي (زير مجموعه هاي بزرگ هم بزرگند)، تمام زير مجموعه هايش مجموعه اتم هاي بزرگ هستند .
بجز روش بالا به پايين و پايين به بالا روش ديگري به نام hybrid كه تركيب دو روش بالا به پايين و پايين به بالا مي باشد نيز وجود دارد كه اين روش را در شكل زير نشان داديم.
