برق. قدرت. کنترل. الکترونیک. مخابرات. تاسیسات.

دایره المعارف تاسیسات برق (اطلاعات عمومی برق)

الگوریتم Apriori

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

بنابراین در هر مرحله باید کل فضا جستجو شود اما این الگوریتم از یک خصوصیت به نام خصوصیت Apriori استفاده میکند، به این صورتکه اگر یک مجموعهای از عناصر مکرر باشد، تمام زیر مجموعههای غیر تهی آن نیز مکرر خواهند بود. مثلا" اگر مجموعه A نامبرده شده در زیر مکرر باشد، آنگاه مجموعههای زیر نیز مکرر هستند.

A= {Milk, Bread, Cigarettes} {Milk, Bread}, {Milk, Cigarettes}, {Bread, Cigarettes} {Milk},{Bread},{Cigarettes}

این خصوصیت را اینگونه نیز میتوان توصیف کرد، که اگر مجموعهی I به یک تعداد مرتبه تکرار شده باشد، اگر A را نیز به آن اضافه کنیم تعداد تکرار مجموعهی جدید از تعداد تکرار مجموعهی قبلی بیشتر نخواهد بود. پس اگر اولی مکرر نباشد دومی هم مکرر نخواهد بود. اما این الگوریتم چگونه از این خصوصیت استفاده میکند؟ در اینجا عملکرد آنرا شرح میدهیم:

میدانیم که از LK-1 یعنی یک زیرمجموعه K-1 عضوی برای بدست آوردن LK ، یعنی مجموعههای K عضوی استفاده میشود. این کار در دو مرحله صورت میگیرد، ابتدا باید مجموعهای از اعضا پیدا شود، که با LK-1 برای به دست آوردن LK ترکیب شود. این مجموعه از عناصر را CK نامیده و مرحله به دست آوردن آن را پیوست مینامیم. مرحله بعد اضافه کردن این عناصر به مجموعههای قبلی است که آن را مرحله هرس مینامیم.

· مرحله پیوست

ابتدا باید مطمئن شویم که عناصر بر مبنای ترتیب حروف الفبا مرتب شده باشند. LK-1 را با li و اعضای آنها را به صورت li[j] نشان میدهیم. اگر K-2 عنصر اول آنها با یکدیگر برابر باشند، آنگاه دو مجموعه LK-1 با یکدیگر قابل پیوست هستند، یعنی داشته باشیم:

) l1[1] = l2[1] ) ^ (l1[2] = l2[2]) ^ … (l1[k-2] = l2[k-2]) ^ (l1[k-1] < l2[k-1])

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

با این روش ترکیب، مجموعه حاصل K عضو خواهد داشت، که البته عنصر آخر از نظر ترتیبی از مجموعه دوم خواهد بود.

P in Lk-1 =(1 2 3)

|| ||

Join: Result in CK = (1 2 3 4)

|| ||

Q in LK-1 = (1 2 4)

مرحله هرس

CK مجموعهای از LKها است، که هر عنصر آن یا مکرر است یا نیست، اما تمام عناصر مکرر در آن قرار دارند حال تمام عناصر این مجموعه باید بررسی شوند تا مشخص شود، که آیا مکرر هستند یا خیر؟ اما چون ممکن است تعداد آنها زیاد باشد لذا برای کاهش حجم محاسبات از اصل Apriori استفاده میشود. به این صورت که اگر یکی از زیر مجموعهها مکرر نباشد، آن مجموعه نیز مکرر نخواهد بود. حال برای پیدا کردن مجموعههای مکرر کافی است مجموعههای غیر مکرر را از آنها جدا کنیم، به این صورت که اگر عضوی از CK دارای زیرمجموعههای k-1 عضویی باشد که در LK-1 عضو نباشند، آن عضو CK مکرر نخواهد بود.

تفاوت اساسی این الگوریتم با دو الگوریتم قبلی در روش محاسبه اقلام پر تکرار CK و گزینش آنها برای مراحل بعدی است. در الگوریتمهای قبلی اقلام پر تکرار بزرگ با گسترش به هر یک از اقلام پر تکرار مجزا (که ممکن بود خودشان بزرگ نباشند) در هر یک از تراکنشها ایجاد میشدند، تا CK­­ها را تولید کنند و به این ترتیب CK­های زیادی تولید میشدند، که بایستی در مراحل بعدی کوچک میشدند و پایگاه داده چندین بار (برای هر یک از تراکنشها) پیموده میشد، در حالیکه این الگوریتم پایگاه داده را فقط یکبار میپیماید و اقلام پر تکرار بزرگ را پیدا میکند.

این الگوریتم این موضوع مهم را مدنظر قرار میدهد و CK­ها را با اتصال اقلام پر تکرار بزرگ حاصل از فاز قبلی و حذف آنهایی که در فاز قبلی بودهاند بدون توجه به هر یک از تراکنشها بهطور مجزا تولید میکند. بدینترتیب تعداد CK­های اضافی بهطو چشم­گیری کاهش مییابند.

تذکر: CKها در این الگوریتم مطابق شبه كد زیر محاسبه میگردد.

Apriori-gen (Lk-1)

Join step

insert into Ck

select p.item1, p.item2 ,… , p.itemk-1, q.itemk-1

from Lk-1 p, Lk-1 q

where p.item1=q.item1, …,p.itemk-2 = q.itemk-2,

Prune step

p.itemk-1 < q.itemk-1

for all itemsets c in Ck do

for all (k-1)-subsets s of c do

if ( s in Lk-1 ) then

delete c from Ck;

مثال: فرض کنیم L3 به صورت زیر باشد:

{{1 3 5}{2 3 4} {1 3 4} {1 2 4} {1 2 3}} L3 =



پس از مرحله اتصال خواهیم داشت:

{{1 3 4 5} {1 2 3 4}}

و پس از مرحله هرس کردن خواهیم داشت :

{1 2 3 4} C4 =

پس از محاسبه CK­ها، میزان پشتیبان هر یک از اعضای آنها را محاسبه میکنیم، و فقط آنهایی را که از حداقل میزان پشتیبانی برخوردارند را در LK قرار میدهیم. الگوریتم زیر مراحل کار را به صورت کلی نشان میدهد.

The Apriori Algorithm

L1 = {large 1–itemsets}

for ( k = 2; Lk-1 # Ø ; k ++ ) do begin

Ck = apriori – gen (Lk-1);

for all transactions t in D do begin

Ct = subset (Ck ,t)

for all candidates c in Ct do

c.count ++;

end

end

Lk = { c in Ck | c.count ≥ minsup}

end

Answer = U Lk

k

پس از آنکه مجموعههای قوی با (تکرار قابل قبول) استخراج شد حال نوبت به استخراج قوانین میرسد.

support_count ( A U B )

confidence ( A => B ) = P(B |A) = --------------------------------

support_count( A)



برای هر مجموعه مکرر L تمام زیر مجموعههای غیر تهی را مینویسیم. برای هر زیر مجموعه حاصل s قوانین زیر مینویسیم.

" s => ( L - s) "

سپس اطمینان را حساب میکنیم و اگر بیشتر از حد قابل قبول بود آنرا میپذیریم.


http://www.dataminer.blogfa.com/8808.aspx

چگونه پای رقابت های استعماری به دنیای ریاضی باز شد؟ – مصاحبه با پدید آورنده این الگوریتم

متن مصاحبه روزنامه هفت 7 صبح در مورد الگوریتم رقابت استعماری، اسماعیل آتش پز گرگری

متلب سایت - مرجع هوش مصنوعی ایران: الگوریتم رقابت استعماری، به عنوان یک روش جدید و با قدرت عمل بالا، به خوبی، جای خود را در میان روشهای بهینه سازی تکاملی باز کرده است و روند رشد و توسعه آن هنوز هم ادامه دارد. اخیراً روزنامه هفت صبح در بخش سرویس علمی خود، مصاحبه ای را با پدید آورنده این الگوریتم منتشر کرده است که باز نشر آن برای مخاطبین وبسایت محاسبات تکاملی نیز خالی از لطف به نظر نیامد. در این مصاحبه، می توانید با چگونگی ایجاد، رشد و توسعه الگوریتم رقابت استعماری آشنا شوید و از زبان مبتکر آن، نقاط قوت و ضعف کار و موانع راه توسعه یک کار علمی را بشنوید. در ادامه مطلب می توانید باز نشر بخشهای برداشت شده ای از این مصاحبه مفصل را بخوانید.


گزارش از علی موحد – روزنامه هفت صبح:
—————————————————————–
پژوهشگر ایرانی با الهام از روند تکامل اجتماعی انسان، موفق به طراحی الگوریتم فرهنگی جدیدی شده است. این الگوریتم به عنوان نخستین الگوریتم بهینه سازی مبتنی بر یک فرآیند اجتماعی-سیاسی، از سرعت همگرایی بالایی در مقایسه با الگوریتم های موجود برخوردار است.

اسماعیل آتش پز گرگری، دانش آموخته کارشناسی ارشد مهندسی برق (کنترل) دانشگاه تهران و دانشجوی دکتری مهندسی برق دانشگاه تگزاس اِی اَند اِم، در دوران تحصیلات کارشناسی ارشد خود موفق به ارائه این الگوریتم جدید شده بود. او در توضیح طرح خود گفت: این الگوریتم در سال ۲۰۰۷ میلادی، طی مقاله ای با نویسندگی بنده و زنده یاد دکتر کارو لوکس، چهره ماندگار مهندسی برق کشور، به جامعه علمی محاسبات تکاملی معرفی شد. الگوریتم رقابت استعماری (Imperialist Competitive Algorithm – ICA) روش جدیدی در بهینه سازی تکاملی است که قابلیت اعمال به بسیاری از مسائل بهینه سازی در زمینه های مختلف علوم و مهندسی را دارد.

بیشتر جذبه علمی این الگوریتم به ابتکار آن در ارائه مدلی جدید از روند بهینه سازی است که الهام گرفته از فرایند توسعه و تکامل اجتماعی، سیاسی و فرهنگی است. وی خاطر نشان کرد: الگوریتم ارائه شده، با داشتن یک دیدگاه نو به مبحث بهینه سازی، پیوندی جدید میان علوم انسانی و اجتماعی از یک سو و علوم فنی و ریاضی از سوی دیگر برقرار می کند.

روش کار الگوریتم رقابت استعماری
آتش پز گرگری در تشریح ساختار الگوریتم توسعه داده شده تصریح کرد: پایه‌های اصلی این الگوریتم را سیاست همسان سازی (Assimilation)، رقابت استعماری (Imperialistic Competition) و انقلاب (Revolution) تشکیل می‌دهند. این الگوریتم با تقلید از روند تکامل اجتماعی، اقتصادی و سیاسی کشورها و با مدلسازی ریاضی بخشهایی از این فرایند، عملگرهایی را در قالب منظم به صورت الگوریتم ارائه می‌دهد که می‌توانند به حل مسائل پیچیده بهینه سازی کمک کنند. در واقع این الگوریتم جوابهای مسئله بهینه سازی را در قالب کشورها نگریسته و سعی می‌کند در طی فرایندی تکرار شونده این جواب‌ها را رفته رفته بهبود داده و در نهایت به جواب بهینه مسئله برساند.

آتش پز گرگری خاطر نشان کرد: همانند دیگر الگوریتم‌های تکاملی، این الگوریتم، نیز با تعدادی جمعیت اولیه تصادفی که هر کدام از آنها یک «کشور» نامیده می‌شوند؛ شروع می‌شود. تعدادی از بهترین عناصر جمعیت (معادل نخبه‌ها در الگوریتم ژنتیک) به عنوان امپریالیست انتخاب می‌شوند. باقیمانده جمعیت نیز به عنوان مستعمره، در نظر گرفته می‌شوند. استعمارگران بسته به قدرتشان، این مستعمرات را با یک روند خاص که در ادامه می‌آید؛ به سمت خود می‌کشند. قدرت کل هر امپراطوری، به هر دو بخش تشکیل دهنده آن یعنی کشور امپریالیست (به عنوان هسته مرکزی) و مستعمرات آن، بستگی دارد. در حالت ریاضی، این وابستگی با تعریف قدرت امپراطوری به صورت مجوع قدرت کشور امپریالیست، به اضافه در صدی از میانگین قدرت مستعمرات آن، مدل شده‌است. با شکل‌گیری امپراطوری‌های اولیه، رقابت امپریالیستی میان آن‌ها شروع می‌شود. هر امپراطوری‌ای که نتواند در رقابت استعماری، موفق عمل کرده و بر قدرت خود بیفزاید (و یا حداقل از کاهش نفوذش جلوگیری کند)، از صحنه رقابت استعماری، حذف خواهد شد. بنابراین بقای یک امپراطوری، وابسته به قدرت آن در جذب مستعمرات امپراطوری‌های رقیب، و به سیطره در آوردن آنها خواهد بود. در نتیجه، در جریان رقابت‌های امپریالیستی، به تدریج بر قدرت امپراطوری‌های بزرگتر افزوده شده و امپراطوری‌های ضعیف‌تر، حذف خواهند شد.

تصویر: شمایی از چرخه رقابت استعماری در الگوریتم رقابت استعماری
تصویر: شمایی از چرخه رقابت استعماری در الگوریتم رقابت استعماری

اقبال گسترده به الگوریتم رقابت استعماری
وی خاطر نشان کرد: از همان روزهای ابتدای معرفی، این الگوریتم به سرعت مورد استقبال پژوهشگران داخل و خارج کشور قرار گرفت. پایان نامه های مختلف در مقاطع کارشناسی ارشد و دکتری در حل مسائل بهینه سازی خود در زمینه مهندسی برق، کامپیوتر، مهندسی صنایع، رباتیک، مهندسی شیمی و مهدسی مکانیک و غیره، به سرعت شروع به استفاده از این الگوریتم کردند. در عرض کمتر از ۴ سال، بدون در نظر کردن مقالاتی که به کار ارجاع داده اند و نیز دهها مقاله منتشر شده به فارسی در داخل کشور، بیش از یکصد مقاله معتبر به زبان انگلیسی منتشر شده در مجلات و کنفرانسهای معتبر بین المللی از این الگوریتم به صورت مستقیم در عنوان کار خود استفاده کرده اند. همچنین نگارش دهها پایان نامه در داخل و خارج کشور به محوریت این الگوریتم، نشان اقبال عمومی و اعتماد علمی جامعه محاسبات تکاملی و نیز اساتید و دانشجویان، به این الگوریتم جدید دارد. روند رشد این الگوریتم بصورت تصاعدی ادامه دارد. بطوری که بیش از ۷۰ دردصد رشد آن و استفاده از آن در پروژه های علمی و صنعتی در سال گذشته میلادی صورت گرفته است.

وی در عین حال اظهار کرد: در حالی که استفاده از این الگوریتم، روز به روز در حال گسترش است، اما به دلیل عدم وجود حمایت های لازم امکان پاسخ گویی به همه نیاز واقعی استفاده از این الگوریتم میسر نمی شود. رشد و شناخته شدن هر چه بیشتر این طرح، در عرصه بین المللی، به حمایت همه جانبه از آن از طریق تهیه و در اختیار گذاشتن مستندات آموزشی کافی برای آن به زبان های مختلف و نیز استفاده سیستماتیک از پتانسیل بالای محققین متخصص مربوطه در داخل کشور نیاز دارد. امری تا کنون امکان پذیر نبوده است و همین رشد قابل توجه نیز تنها با پیگیری های شخصی و تحمیل هزینه های زمانی و تحصیلی از طرف بنده حاصل شده است که متاسفانه به دلیل گستردگی بیش از حد آن در حال حاضر ادامه چنین حمایت شخصی از آن برای بنده ممکن به سختی امکان پذیر است.

آتش پز تصریح کرد: تا کنون کوچکترین حمایتی توسط مسئولین امر در داخل کشور، از این ایده پر پتانسیل علمی داخلی، صورت نگرفته است و تا کنون تمام طرح با انرژی زمانی و هزینه شخصی از طرف بنده و سایر دانشجویان علاقه مند، پیش رفته است. به گونه ای که حتی وبیناری (کنفرانس تحت وب) که در تابستان سال ۱۳۸۹ با حضور پرشکوه ۳۰۰ نفر از دانشجویان ایرانی سراسر دنیا در بستر اینترنت درباره این الگوریتم، برگزار شد و به نوعی اولین تجربه کنفرانس رسمی تحت وب در ایران بود، بدون کوچکترین حمایتی از طرف هیچ سازمان خصوصی و دولتی خاصی، تنها با انرژی شخصی یک گروه کوچک دانشجویی با موفقیت برگزار شد.

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


صفحات جانبی

نظرسنجی

    لطفاً نظرات خود را درمورد وبلاگ با اینجانب در میان بگذارید.(iman.sariri@yahoo.com)نتایج تاکنون15000مفید و 125غیرمفید. با سپاس


  • آخرین پستها

آمار وبلاگ

  • کل بازدید :
  • تعداد نویسندگان :
  • تعداد کل پست ها :
  • آخرین بازدید :
  • آخرین بروز رسانی :