الگوریتم PSO چند هدفه برای استخراج قوانین انجمنی عددی بدون گسسته‌سازی اولیه
در حوزه کشف استخراج قوانین انجمنی (ARM)، قوانین برای ویژگی‌های عددی هنوز یک مسئله بحث برانگیز است. بیشتر روش‌های محبوب برای ARM عددی نیاز به یک گسسته‌سازی داده ای اولیه برای رسیدگی به ویژگی‌های عددی دارد. علاوه بر این در فرآیند کشف روابط بین داده‌ها اغلب بیشتر از یک هدف ( اندازه‌گیری کیفیت ) مورد نیاز می‌باشد و در اکثر موارد این اهداف شامل اندازه‌گیری‌های متضاد می‌شود. در چنین شرایطی توصیه برای بدست آوردن تعادل بهینه بین اهداف می‌شود. این مقاله به مسئله ی ARM عددی با استفاده از یک دیدگاده چند هدفه با پیشنهاد یک الگوریتم بهینه‌سازی ازدحام ذرات چند هدفه (به عنوان مثال MOPAR) برای ARM عددی که قوانین انجمنی عددی (ARs) را در فقط یک مرحله منفرد کشف می‌کند می‌پردازد.برای شناسایی ARs کارآمد‌تر چندین هدف در رویکرد بهینه‌سازی چند هدفه پیشنهاد شده تعریف می‌شوند. شامل اعتماد به نفس، قابلیت درک و جالب توجه بودن. در نهایت با استفاده از بهینه‌سازی Pareto بهترین ARsها استخراج می‌شوند. برای مقابله با ویژگی‌های عددی ما مقادیر ناهمگون شامل کران‌های بالاتر و پائین‌تر را برای نشان دادن باز ه‌های ویژگی‌ها، استفاده می‌کنیم. در بخش تجربی از مقاله ما اثر اپراتورهای استفاده شده در این مقاله را تجزیه و تحلیل می‌کنیم برای مقایسه روش مان با محبوب ترین پیشنهادات بر مبنای تکاملی برای ARM راو یک تجزیه و تحلیل از ARs استخراج شده را نشان می‌دهیم. نتایج نشان می‌دهد که MOPAR مقادیر قابل اعتمادی ) با مقادیر مطمئن نزدیک ۹۵%(، قابل درک و جالب توجهی از ARs عددی را استخراج می‌کند بهنگام رسیدن به تعادل بهینه بین اعتماد به نفس، قابل درک بودن و جالب توجه بودن.
۱- معرفی
دادهکاوی مجموعه ای از تکنیک‌ها برای کشف دانش می‌باشد که شامل استخراج با دقت بالا، به طور بالقوه مفید ، قابل درک بودن و دانش قابل درک از مجموعه داده‌های بزرگ می‌باشد. (۲۰۰۶,pia Kamber,han) یک مسئله ای تحقیق مهم در زمینه‌ی تحقیق داده کاوی استخراج قوانین انجمن ARM می‌باشد که در آن هدف، از همبستگی چند ویژگی میان پایگاه هاي داده مشتق می‌شود. از آنجاییکه الگوریتم‌های استخراج متعارف معمولاً تعداد زیادی از قوانین را می‌دهد که رسیدگی به آنها مشکل می‌باشد، ARM هنوز یک مسئله‌ی در حال بررسی می‌باشد.
یک علامت گذاری از B → A یک قانون انجمنی (AR) نامیده می‌شود که در آن A و B هر دو مجموعه‌هایی از اقلام (itemsets) می‌باشند. طرف چپ این اصطلاح مقدمه نامیده می‌شود در حالیکه طرف راست نتیجه می‌باشد. به منظور بررسی اثر بخشی قوانین تعدادی اندازه‌گیری‌های آماری خاص مثل حمایت یا اعتماد به نفس ( در میان دیگران) استفاده می‌شود. ARs شامل فقط ویژگی‌های دسته‌بندی (به عنوان مثال نام تجاری، شامل ماشین، جنس) به عنوان ARs دسته‌بندی شناخته می‌شوند، در حالیکه در ویژگی‌های ARs عددی (کمّی) می‌توان هر دو دسته‌بندی و کمی بودن را داشت ( به عنوان مثال حرارت، سن، درآمد). اکثریت محققان برروی پایگاه داده‌های شامل ویژگی‌های دسته‌بندی متمرکز شده اند با این حال هر دو ویژگی دسته‌بندی و کمی اغلب در پایگاه داده‌ی دنیای واقعی وجود دارند. علاوه بر این بسیاری از ابزارهای برخورد با مسائل ARM عددی فقط ویژگی‌های کمی با استفاده از یک استراتژی خاص را گسسته می‌کند و پس از آن آنها با آنها به عنوان ویژگی‌های دسته‌بندی رفتار می‌کنند (Mata Vazquez & pachm Alvarez 2012). ARs عددی از شکل c2 c1 → بیان می‌شود، در هر دو c2 و c1 به عنوان قسمتهایی مقدمه و نتیجه از قانون ویژگی‌هایی از مجموعه‌ها هستند در فرم‌هایی A= {v1,v2,………..,vn} ( اگر A یک ویژگی دسته‌بندی باشد) یا Aϵ [v1,v2] ( اگر A یک ویژگی کمی باشد). با توجه به چالش‌های زیر ARs کمی کمتر مورد مطالعه قرار گرفته است .(۱) ویژگی‌های کمی معمولاً طیف گسترده ای از مقادیر پیوسته دارد که نیاز به یک فرآیند پیچیده برای گسسته‌سازی تمام ویژگی‌ها دارد که یک روند مستمر برای خطا محسوب می‌شود؛ (۲) ARs کمی یک گستره‌ی ساده از ARs های دسته‌بندی نمی‌باشند در عوض آنها یک قسمت از یک فرآیند پیچیده‌تر را تشکیل می‌دهند : (۳) مشکل بررسی کردن مقادیر زیادی از داده ها. بنابراین در این مقاله ما برروی استخراج ARs های عددی متمرکز می‌شویم. اکثریت الگوریتم‌های مرسوم نماینده برای ARM الگوریتم Aprior می‌باشد. (Agrawal and Srikabt 1994) AIS (Agrawal, Imielinskiandx) و الگوریتم مجموعه محور (Houtswa and Swam; 1995) . این الگوریتم‌ها با پیشنهاد بسیاری از الگوریتم‌های تغییر یافته به خوبی تحقیق شدهاند که متمرکز شده اند برروی بهبود کارآمدی و دقت. با این حال دو پارامتر حمایت و اعتماد به نفس حداقل همیشه توسط خود تصمیم گیرنده یا از طریق آزمون و خطا تعیین می‌شوند و به این ترتیب الگوریتم‌های مرسوم هم هدف مندی و هم کارایی را کم دارند. علاوه براین فرآیند ARM در روش‌های مرسوم بیش از حد منابع را مصرف می‌کنند به ویژه هنگامی که حافظه در دسترس فیزیکی برای کل مجموعه داده‌ها کافی نمی‌باشد. این روش‌ها اغلب دقیق می‌باشند اما از عملیات شکننده ای رنج می‌برند.
از سوی دیگر محاسبات تکاملی یک رویکرد کارآمد و قوی فراهم می‌کند برای کشف یک فضای تحقیق عظیم. در سالهای اخیر بعنوان یک راه حل برای محدودیت‌های روش‌های مرسوم برخی از تلاش‌های تحقیقاتی توسط محاسبات تکاملی الهام گرفته شد. (Freitas,2002 , deljesas, Gamez and Puerta 2011). محاسبات تکاملی یک رویکرد جایگزین برای کشف راه حل‌های بهینه جهانی درغیر پیوستگی و گسستگی ،غیر محدب بودن، فضاهایی راه حل غیر خطی بالا فراهم می‌نماید. آن شامل رویکردهای بهینه‌سازی مبتنی بر تصادفی بودن که یک روش کارآمد برای کشف یک فضای تحقیق بزرگ فراهم می‌کند، می‌باشد. (Dehuri, Jagude , GAosh and Mull, 2006). محبوب ترین روش‌های محاسبات تکاملی به کار رفته در مسئله ARM اینها می‌باشند: الگوریتم‌های ژنتیک (Alatas and Akin 2006, Salleb – Aouissi, Vrain and norlet 2007, yon ,zhang and zhang,2009) .الگوریتم‌های تکاملی (Deepa shenay Srinivasa , Venugopol , and Patnaik 2003 b , Pschon Alvarez and MataVazquez,2012, Yang Mabu, Shimada and Hirasawa 2011 , Ykhlef 2011 )، الگوریتم‌های کلونی مورچگان (Klexin , and Shih 2007 ,Kuo and shih 2007 ; Ozbakir , Baykasoglu, Kullukand , Yapici ,2009 ( ،الگوریتم‌های ازدحام ذرات (Kua, Cha,and Chiu 2011) .
بیشتر این روش‌ها مسئله ARM را بعنوان یک مسئله با یک هدف بررسی می‌کند. با این حال روند ARM عملی به طور طبیعی یک مسئله چند هدفه شامل بهینه‌سازی همزمان چندین جامعه هدف می‌باشد که شامل چنین معیارهایی بعنوان جالب توجه بودن، دقت پیش بینی و قابل درک بودن می‌شود. (Dehurf , Patnaik, Ghosh and Mall , 2008)
به تازگی برخی تحقیقات برای بررسی مسئله ARM از یک دیدگاه چند هدفه انجام شده است. با این حال در اکثر این روش‌های بر مبنای تکاملی یک روش جمع وزن یافته برای رسیدگی به ماهیت چند هدفه بودن فرآیند ARM دنبال می‌شود. اما این رویکرد به اندازه کافی کارآمد نیست، باتوجه به رفتار شرایط بهینه‌سازی برای اهداف چندگانه، که معمولاً غیر متناسب، متناقص و اهداف در حال رقابت می‌باشد.
بر این اساس با توجه به مسائل مرتبط به ARM کمی تحقیقات ذکر شده در بالا ما یک روش چند هدفه بر اساس عقیده بهینه‌سازی Pareto برای استخراج ARs جالب توجه از پایگاه‌های داده پیشنهاد می‌کنیم. یک الگوریتم بهینه‌سازی ازدحام ذرات چند هدفه تطبیق می‌یابد برای متعادل کردن اهداف در حال تناقض به منظرو پیدا کردن ARs متعجب کننده‌تر و یک روش ساده‌تر و مستقیم‌تر برای استخراج ARs عددی فراهم می‌کند.
Multi-objective PSO algorithm for mining numerical association rules without a priori discretization
Abstract
In the domain of association rules mining (ARM) discovering the rules for numerical attributes is still a challenging issue. Most of the popular approaches for numerical ARM require a priori data discretization to handle the numerical attributes. Moreover, in the process of discovering relations among data, often more than one objective (quality measure) is required, and in most cases, such objectives include conflicting measures. In such a situation, it is recommended to obtain the optimal trade-off between objectives. This paper deals with the numerical ARM problem using a multi-objective perspective by proposing a multi-objective particle swarm optimization algorithm (i.e., MOPAR) for numerical ARM that discovers numerical association rules (ARs) in only one single step. To identify more efficient ARs, several objectives are defined in the proposed multi-objective optimization approach, including confidence, comprehensibility, and interestingness. Finally, by using the Pareto optimality the best ARs are extracted. To deal with numerical attributes, we use rough values containing lower and upper bounds to show the intervals of attributes. In the experimental section of the paper, we analyze the effect of operators used in this study, compare our method to the most popular evolutionary-based proposals for ARM and present an analysis of the mined ARs. The results show that MOPAR extracts reliable (with confidence values close to 95%), comprehensible, and interesting numerical ARs when attaining the optimal trade-off between confidence, comprehensibility and interestingness.
لینک مقاله اصلی:
https://www.sciencedirect.com/science/article/pii/S0957417414000025
لطفاً براي ارسال دیدگاه، ابتدا وارد حساب كاربري خود بشويد