A feature selection algorithm for online multi-label data

Subject Areas : Information Technology in Engineering Design (ITED) Journal

maryam rahmaninia ¹ , sondos bahadori ²

1 - Department of Computer Engineering,, Qasreshirin Branch, Islamic Azad University, Qasreshirin,, Kermanshah Iran
2 - Department of Computer Engineering, Ilam Branch, Islamic Azad University, Ilam, Iran,

Received: 2024-01-15 Accepted : 2024-06-29 Published : 2024-08-14

Keywords: Feature selection, Multi label dataset, data with feature stream, multi variate feature selection,

Abstract :

Currently, we are facing a large volume of multi-label training data, where each training instance has more than one label. One of the main challenges with this type of training data is the sudden increase in its size, which impacts the efficiency of data mining algorithms. Multi-label feature selection methods reduce the dimensions of this data by selecting a subset of important initial features. On the other hand, in today's world, data is gradually being added over time. Therefore, multi-label feature selection algorithms need to be used in an online fashion. Although several online multi-label feature selection algorithms have been proposed recently, none of them have considered the dependency between labels to determine the relationship between features and labels.To address this issue, this paper presents an online multi-label feature selection method that incorporates multiple mutual information measures into the feature selection process. Additionally, several experiments have been conducted on multiple multi-label feature selection algorithms and datasets to demonstrate the effectiveness of the proposed method. The results obtained indicate that the proposed method performs well in terms of various evaluation metrics.

Full-Text:



	دوره هفدهم، شماره بهار و تابستان 1403   مجله فناوری اطلاعات در طراحی مهندسی Information Technology in Engineering Design https://sanad.iau.ir/journal/ited
یک الگوریتم انتخاب ویژگی چند برچسبی برخط با استفاده از اطلاعات متقابل چندگانه مریم رحمانی‌نیا*(1)     سندس بهادری(2)   (1)       گروه مهندسی کامپیوتر، مرکز قصرشیرین، دانشگاه آزاد اسلامی، کرمانشاه، ایران*  (2)       گروه مهندسی کامپیوتر، واحد ایلام، دانشگاه آزاد اسلامی، ایلام، ایران     (تاریخ دریافت: 25/10/1402     تاریخ پذیرش: 09/04/1403)
چکیده  در حال حاضر، با حجم بزرگی از داده‌های آموزشی چندبرچسبی که در آن هر نمونه آموزشی، دارای بیش از یک برچسب است، روبه‌رو هستیم. یکی از مشکلات اصلی این نوع داده‌های آموزشی، افزایش ناگهانی تعداد ویژگی­ها است؛ که کارایی الگوریتم‌های داده‌کاوی را با مشکل مواجه کرده است. روش‌های انتخاب ویژگی چندبرچسبی، با انتخاب یک زیرمجموعه مهم از ویژگی‌های اولیه، ابعاد این داده‌ها را کاهش می‌دهند. از سوی دیگر، در دنیای امروز، داده‌ها به‌ صورت جریانی و به تدریج با گذر زمان، به مجموعه اضافه می‌شوند. بنابراین، الگوریتم‌های انتخاب ویژگی چندبرچسبی باید بتوانند به صورت برخط استفاده شوند. اگرچه اخیرا الگوریتم‌های انتخاب ویژگی چندبرچسبی برخط متعددی ارائه شده است، اما هیچ‌کدام به وابستگی بین برچسب‌ها جهت تعیین ارتباط ویژگی‌ها و برچسب‌ها در جریان داده ها توجه نکرده‌اند. به همین منظور، در این مقاله، یک روش انتخاب ویژگی چندبرچسبی برخط ارائه شده است که با استفاده از اطلاعات متقابل چندگانه و محاسبه وابستگی میان برچسب‌ها، به فرآیند انتخاب ویژگی‌ها می‌پردازد. همچنین، برای نمایش کارایی روش پیشنهادی، چند آزمایش بر روی چندین الگوریتم انتخاب ویژگی و چند داده آموزشی چندبرچسبی انجام شده است. نتایج به‌دست‌آمده نشان می‌دهد به‌طور متوسط الگوریتم پیشنهادی به ازای معیارهای افت همینگ، افت رتبه، پوشش، متوسط دقت و یک خطا به ترتیب 15%، 6%، 19%، 7% و 13% عملکرد بهتری نسبت به سایر الگوریتم­های انتخاب ویژگی چندبرچسبی داشته است.   کلمات کلیدی: روش­های انتخاب ویژگی چند برچسبی، داده های چند برچسبی با جریان ویژگی، اطلاعات متقابل چندگانه *عهده‌دار مکاتبات:                  مریم رحمانی‌نیا         نشانی: گروه مهندسی کامپیوتر، مرکز قصرشیرین، دانشگاه آزاد اسلامی، کرمانشاه، ایران  پست الکترونیکی:  [e-mail]

 

1-       مقدمه

1-1- بیان مسئله

اخیرا داده­های آموزشی چندبرچسبی در بسیاری از برنامه­های کاربردی دنیای واقعی (مانند دسته­بندی اسناد متنی [1]، دسته­بندی تصاویر [2]، دسته­بندی ژن­ها [1] و تشخیص احساسات در موسیقی [2]) مورد استفاده قرار گرفته است. همین امر باعث شده تا الگوریتم­های یادگیری ماشین، در داده­های آموزشی چندبرچسبی، مورد توجه بسیاری از محققان قرار بگیرند. در داده­های آموزشی چندبرچسبی، هر نمونه آموزشی به‌طور همزمان با بیش از یک برچسب مرتبط است [2]. به عنوان مثال، یک سند می­تواند به چندین موضوع مختلف متعلق باشد، یا یک ژن می­تواند با مجموعه­ایی از اهداف کاربردی مختلف مرتبط باشد و یا یک قطعه موسیقی را می­توان به ژانر­های مختلفی اختصاص داد. چندین چالش اساسی درباره داده‌های آموزشی چندبرچسبی وجود دارد که در ادامه به آن‌ها اشاره می‌کنم.

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

2.       دومین چالش این است که در مقابل داده‌های آموزشی تک‌برچسبی که برچسب‌های آن‌ها دو به دو مستقل هستند، در داده‌های آموزشی چندبرچسبی، برچسب‌ها به یکدیگر وابسته و مرتبط هستند و پیش‌بینی درست تمامی برچسب‌های مرتبط با یک نمونه آموزشی سخت است. از طرف دیگر، وابستگی بین برچسب‌ها باعث می‌شود برچسب‌های ناشناخته‌ای که متعلق به برخی نمونه‌ها هستند نیز شناسایی شوند. 

3.       چالش سوم مربوط به برخط و جریانی بودن داده­های آموزشی می­شود. همانطور که می­دانیم در دنیای امروزه داده­ها به صورت تدریجی و با گذر زمان به مجموعه داده­ها اضافه می­شوند و دسترسی به مجموعه داده­ها در شروع فرایند انتخاب ویژگی معمولا غیر­ممکن است؛ پس الگوریتم­های انتخاب ویژگی باید بدون هیچ دانش پیش زمینه­ای به فرایند انتخاب ویژگی بپردازند.

 

 

1-2- ضرورت انجام تحقیق

تا به امروز، تعداد زیادی روش انتخاب ویژگی چندبرچسبی به منظور رفع این چالش ها ارائه شده است [5-3]. اگرچه بسیاری از این روش‌ها به ‌صورت جزئی برخی از چالش‌ها را حل کرده‌اند، اما هنوز هیچ روشی به‌طور کامل تمامی مسائل مطرح شده را حل نکرده است. در [3]، چندین روش انتخاب ویژگی چندبرچسبی ارائه شده است؛ که برخی از آن‌ها نیازمند محاسبات پیچیده برای استنتاج این وابستگی‌ها هستند و برخی دیگر این وابستگی‌ها را نادیده می‌گیرند. در [5] یک روش انتخاب ویژگی چندبرچسبی با استفاده از الگوریتم بهینه سازی ازدحام ذرات و نظریه اطلاعات متقابل ارائه شده است. همچنین در [6]  یک الگوریتم انتخاب ویژگی چندبرچسبی تکاملی ارائه شده است که با استفاده از چندین جمعیت، به جلوگیری از محدود کردن تعامل هیبریدیزاسیون کمک می‌کند و زیرمجموعه نهایی از ویژگی را جست‌وجو می‌کند. در [7] ، یک روش انتخاب ویژگی چندبرچسبی ارائه شده است که با استفاده از یک دسته‌بند، به ارزیابی زیرمجموعه‌های انتخاب شده از ویژگی‌ها می‌پردازد. اگرچه روش‌های موجود به خوبی به مسئله انتخاب ویژگی در داده‌های آموزشی چندبرچسبی پرداخته‌اند، اما دارای یک سری معایب نیز هستند. به‌عنوان مثال، در همه این الگوریتم‌ها، نیاز است که قبل از شروع الگوریتم، تمام داده‌های آموزشی در دسترس باشند ولی در بسیاری از داده‌های آموزشی در دنیای واقعی، داده‌های آموزشی به صورت آنلاین و به تدریج به مجموعه داده اضافه می‌شوند، به‌طوری‌که انتظار داشتن داده‌های کامل برای آموزش عملاً غیرممکن است [2]. به ‌عنوان مثال در تجزیه و تحلیل تصاویر [6]، توصیفگرهای متعددی به صورت پویا و با گذر زمان، برای توصیف جنبه‌های مختلف تصاویر مانند نمودار گرادیان درونی، نمودار رنگی و انتقال مقیاس ویژگی‌های غیرقابل تغییر، اضافه می‌شوند. همچنین، کشف حفره‌های موجود در تصاویر ماهواره‌ای از مریخ، مثال دیگری از دنیای واقعی است که در آن ویژگی‌ها به تدریج به داده‌های آموزشی اضافه می‌شوند [7].

همچنین روش‌های انتخاب ویژگی مختلفی برای انتخاب ویژگی‌ها به صورت برخط ارائه شده است [8,9]. به عنوان مثال، یکی از این روش‌ها در [10]  براساس نظریه اطلاعات ارائه شده است که به صورت توزیع‌شده، ویژگی‌های مهم در داده های چندبرچسبی را انتخاب می کند. در [11] نیز یک روش جدید بر اساس اطلاعات متقابل فازی، به منظور انتخاب ویژگی ها در این داده‌ها معرفی شده است که به فرایند انتخاب ویژگی به صورت برخط می پردازد. همچنین، [12]  یک روش انتخاب ویژگی چندبرچسبی برخط را با استفاده از نظریه مجموعه‌های سخت ارائه می‌دهد. اگر چه این دسته از روش‌های انتخاب ویژگی برخط تا حدی چالش جریانی بودن داده های آموزشی را برطرف کرده است اما در هیچ کدام وابستگی میان برچسب ها در نظر گرفته نشده است. به منظور حل این مشکلات، در این مقاله، یک روش جدید به نام  MLOSFS¹ به منظور انتخاب ویژگی­های مهم در جریان داده­های چندبرچسبی با استفاده از نظریه اطلاعات متقابل چندگانه ارائه شده است. در روش پیشنهادی، از مفهوم نظریه اطلاعات متقابل چندگانه استفاده می‌شود و تعداد ویژگی‌ها به صورت پیش‌فرض تعیین نمی‌شود؛ بلکه توسط الگوریتم به صورت خودکار تعیین می‌شود. این روش دارای دو فاز است: فاز ارتباط و فاز افزونگی. در فاز ارتباط، میزان وابستگی و ارتباط ویژگی‌های جدید با مجموعه برچسب‌ها محاسبه می‌شود. اگر ویژگی جدید وارد با مجموعه برچسب‌ها وابستگی و ارتباط داشته باشد، آنگاه ویژگی جدید به مجموعه ویژگی‌های انتخاب شده، افزوده می‌شود و الگوریتم وارد فاز افزونگی می‌شود. در غیر این صورت، الگوریتم منتظر ورود ویژگی جدید می‌ماند. در فاز افزونگی، وابستگی میان مجموعه ویژگی‌ها محاسبه می‌شود و ویژگی‌هایی که دارای افزونگی هستند (یعنی هیچ اطلاعات جدیدی در مورد مجموعه برچسب‌ها تولید نمی‌کنند)، حذف می‌شوند. در محاسبه میزان افزونگی، از وابستگی میان مجموعه برچسب‌ها و مجموعه ویژگی‌های قبلاً انتخاب شده با استفاده از اطلاعات متقابل چندمتغیره و اطلاعات متقابل شرطی استفاده می‌شود. ساختار این مقاله به این‌ صورت است که در ابتدا یک پیش زمینه در مورد نظریه اطلاعات متقابل و پیشینه تحقیق در بخش 2 ارائه می­شود. در بخش 3، الگوریتم پیشنهادی معرفی می­شود. در بخش 4، نتایج آزمایشگاهی به همراه تجزیه و تحلیل نتایج آورده شده است. در نهایت نتیجه گیری و کارهای آینده در فصل 5 ارائه می شود.

2-       پیشینه تحقیق و پیش‌زمینه

2-1- پیشینه تحقیق: مروری بر کارهای انجام‌شده

به طور کلی، دو نوع از الگوریتم ها برای کاهش ابعاد داده‌های آموزشی حجیم چندبرچسبی وجود دارند. این الگوریتم‌ها را می‌توان در دو دسته استخراج ویژگی و انتخاب ویژگی قرار داد. روش‌های استخراج ویژگی چندبرچسبی، با استفاده از روش‌های نگاشت فضای ویژگی یا روش‌های انتقال فضا، ابعاد داده‌های آموزشی را کاهش می‌دهند [13,14]. در این دسته از روش‌ها، معنای اولیه ویژگی‌ها و برچسب‌ها از بین می‌رود. به همین دلیل است که در محیط‌هایی که معنای اصلی و اولیه ویژگی‌ها لازم است، به خوبی عمل نمی‌کنند. در مقابل، در روش‌های انتخاب ویژگی چندبرچسبی، الگوریتم‌ها تنها سعی می‌کنند با انتخاب زیرمجموعه‌ای مهم و کارا از میان مجموعه ویژگی‌های اولیه، اندازه داده‌های آموزشی را کاهش دهند. در این روش‌ها، معنا و شکل اولیه ویژگی‌ها حفظ می‌شود و هیچ‌گونه تغییری در ویژگی‌ها به وجود نمی‌آید و تنها تعدادی از ویژگی‌های اضافی و نامربوط حذف می‌شوند. در ادامه، تعدادی از روش‌های استخراج ویژگی و انتخاب ویژگی را بیان می‌کنیم.

·       روش‌های استخراج ویژگی چندبرچسبی

 یکی از روش‌های معروف کاهش بعد بر مبنای استخراج ویژگی، روش تجزیه و تحلیل تبعیض‌آمیز خطی است [13]. هدف این روش، یافتن یک تابع نگاشت خطی است که شباهت درون کلاسی را بیشینه کرده و در عین حال شباهت میان کلاس‌ها را کمینه کند. این روش اخیرا به چندین شکل در داده‌های آموزشی چندبرچسبی گسترش یافته است [15, 16]. تفاوت اصلی این روش‌ها به نحوه وزن‌دهی برچسب‌ها برمی‌گردد. به این ترتیب، روش [4] از وزن‌دهی دودویی، روش [3] از وزن‌دهی براساس آنتروپی، روش [15] از وزن‌دهی براساس همبستگی، روش [17] از وزن‌دهی براساس منطق فازی و روش [16] از وزن‌دهی براساس وابستگی استفاده کرده است. در [18]، یک روش استخراج ویژگی تحت نظارت، برای کاهش ابعاد داده‌های آموزشی مطرح شده است. این روش با استفاده از معیار استقلال هیلبرت-اشمیت [19]، وابستگی بین ویژگی‌ها و برچسب‌ها را بیشینه می‌کند. این راهکار به دو صورت MDDMp و MDDMf معرفی شده است. روش MDDMp با استفاده از جهت‌های نگاشت متعامد عمل می‌کند، در حالی که روش MDDMf ویژگی‌های نگاشت‌شده را به صورت متعامد کاهش می‌دهد. در  [20]، نویسندگان نشان دادند که روش MDDMp را می‌توان به عنوان یک مسئله کمترین مربعات خطا فرموله کرد. آنها همچنین با ادغام روش تحلیل مولفه اصلی و تابع هدف روش MDDMp، یک روش جدید به نام MVMD را ارائه کردند. در [21]، یک روش انتخاب ویژگی با استفاده از ابرگراف بر مبنای داده‌ها و برچسب‌ها معرفی شده است؛ که وابستگی بین برچسب‌های مختلف را بررسی می‌کند. در این روش، از فرمول یادگیری طیفی ابرگراف برای دسته‌بندی چندبرچسبی استفاده می‌شود. همچنین در [22]  با در نظر گرفتن ماتریس معکوس مور-پنروز²، هسته خطی³ برای فضای ویژگی و هسته دلتا⁴ برای فضای برچسب، مجموعه داده های آموزشی به مجموعه با اندازه کوچکتر نگاشت شده است.

·       روش‌های انتخاب ویژگی چندبرچسبی

در مقابل، روش‌های انتخاب ویژگی چندبرچسبی ایستا، که در آنها اندازه داده های آموزشی ثابت است، تنها با انتخاب زیرمجموعه‌ای از ویژگی‌های موجود و با حفظ ساختار داده‌ها، کاهش ابعاد داده‌های آموزشی را انجام می‌دهند [23-27]. اگرچه این روش‌ها به خوبی در داده‌های آموزشی چندبرچسبی مشکل ازدحام ابعاد را حل می‌کنند، اما وابستگی بین برچسب‌ها را در نظر نمی‌گیرند. از طرف دیگر، بیشتر این روش‌ها برای محاسبه بردارهای ویژه در ماتریس‌های بزرگ و چگال استفاده می‌کنند که محاسباتی بسیار زمان‌بر و هزینه‌بر در داده‌های با ابعاد بالا می‌باشد. به علاوه، می‌توان گفت که این روش‌ها یک مشکل مشترک دارند و آن این است که برای شروع الگوریتم، نیاز به دسترسی به کل مجموعه داده‌ها است. در بسیاری از برنامه‌های کاربردی واقعی، داده‌ها به طور پیوسته با گذر زمان به مجموعه اضافه می‌شوند و انتظار نمی‌رود که مجموعه داده‌ها به طور کامل در دسترس باشد. به عنوان مثال، در شبکه‌های اجتماعی، عناوین داغ و مورد توجه به صورت پیوسته اضافه می‌شوند و هنگام به‌روزرسانی عنوان جدید، کلمات کلیدی جدیدی نیز به داده‌ها اضافه می‌شود [28].

برخلاف روش‌های انتخاب ویژگی ایستا، روش‌های انتخاب ویژگی برخط، ویژگی‌ها را در یک حالت برخط انتخاب می‌کنند [29,30]. اما همه این روش‌ها فرض می‌کنند که هر نمونه تنها به یک برچسب تعلق دارد. همان‌طور که قبلاً گفته شد، در دنیای واقعی، هر نمونه می‌تواند به چندین برچسب تعلق داشته باشد. روش‌های آنلاین انتخاب ویژگی چندبرچسبی، فرض می‌کنند که با گذر زمان ویژگی‌ها به داده‌های آموزشی با بیش از یک برچسب اضافه می‌شوند. در [12] یک روش چندبرچسبی آنلاین انتخاب ویژگی گروهی ارائه شده است. این روش شامل دو فاز است: فاز انتخاب گروهی و فاز انتخاب داخل گروهی. در فاز اول، گروه‌های موثر از میان گروه‌های اضافه شده تا آن لحظه، شناسایی می‌شوند و سپس در فاز دوم، ویژگی‌های مهم از هر گروه انتخاب شده و ویژگی‌های اضافی حذف می‌شوند. در این روش، میزان اهمیت یک گروه از ویژگی‌ها در فاز انتخاب گروهی و همچنین میزان ارتباط ویژگی‌ها در فاز انتخاب داخل گروهی محاسبه می‌شود. همچنین، در [11]، دو روش برخط انتخاب ویژگی چندبرچسبی با استفاده از اطلاعات متقابل فازی ارائه شده است. در [31]، نویسندگان یک روش آنلاین انتخاب ویژگی چندبرچسبی با استفاده از نظریه همسایگی مجموعه‌های سخت ارائه داده‌اند. این نظریه تنها برای داده‌های گسسته در داده‌های آموزشی استفاده می‌شود و استفاده از آن در داده‌های پیوسته با هزینه محاسباتی بالا همراه است. اخیراً، در [26] یک روش برخط انتخاب ویژگی چندبرچسبی ارائه شده است که با استفاده از یک استراتژی جست‌وجوی چند هدفه و بهره‌گیری از نظریه مجموعه‌های پارتو و نظریه اطلاعات متقابل، به انتخاب ویژگی‌های موثر پرداخته می‌شود. در [32] یک روش انتخاب ویژگی چندبرچسبی در جریان داده‌های برخط با استفاده از نظریه همسایگی مجموعه­های سخت ارائه شده؛ که در آن اهمیت ویژگی، تکرار ویژگی و یکپارچگی فضای برچسب به طور همزمان مورد توجه قرار گرفته شده است. در [33] نیز با استفاده از ارزیابی ارتباط قابل مقیاس، ارتباط مشروط ویژگی‌ها با مجموعه برچسب‌ها را به طور دقیق محاسبه می‌کند. در [34]، یک روش سریع برای انتخاب ویژگی‌های چندبرچسبی بر اساس رتبه‌بندی ویژگی‌های اطلاعاتی معرفی شده است که از یک استراتژی جدید به منظور انتخاب برچسب‌های مهم و در نتیجه کاهش میزان محاسبات استفاده کرده است. در [35] نیز یک روش انتخاب ویژگی با استفاده از نظریه اطلاعات متقابل تقریبی بر مبنای نظریه نامساوی شیرر [36] ارائه شده است که بدون انتقال مجموعه ویژگی‌ها و به صورت مستقیم ارتباط میان برچسب‌ها و ویژگی‌ها را محاسبه می‌کند. در [37] یک روش انتخاب ویژگی چندبرچسبی دیگر با استفاده از نظریه اطلاعات متقابل شرطی ارائه شده است که تمرکز اصلی آن روی کاهش تعداد محاسبات اصلی است.

 

2-2- پیش‌زمینه: نظریه اطلاعات مقابل

تلاش­های زیادی به منظور به‌دست آوردن مقدار اطلاعات متقابل [38] میان مجموعه­ای از متغیرها صورت گرفته است. این تلاش­ها با نگرانی­های زیادی روبه‌رو بوده است. از جمله آن که تعاملات میان بسیاری از متغیرها قابل درک نیست. از طرف دیگر، محاسبه همه تعاملات کار دشواری است. بر اساس [38] اطلاعات متقابل میان زیرمجموعه­ای از ویژگی­ها مانند  و مجموعه برچسب­های  عبارت است از:

 

به‌طوری‌که هر کدام از معیارهای H(.) به آنتروپی مشترک میان مجموعه­ای از متغیرها اشاره می­کند که طبق رابطه زیر به‌دست می­آید:

(1)

همچنین  به تابع جرم احتمالی به ازای مجموعه متغیرهای  اشاره می­کند. آنتروپی معیاری است که مقدار اطلاعات درون یک متغیر را نشان می­دهد. به منظور سادگی کار می­توان گفت اطلاعات متقابل به میزان اطلاعات مشترک یک ویژگی با ویژگی­های دیگر اشاره می­کند. به‌طورکلی با استفاده از تعریف آورده شده در [39] می­توان اطلاعات متقابل چندگانه را به صورت حاصل­جمع آنتروپی­ها همانند زیر نوشت:

(2)

به‌طوری‌که  مجموع تمام عناصر مشتق شده از  و  به مجموعه توانی اعضای T اشاره می­کند. به عنوان مثال فرض کنید  ، پس مجموعه توانی آن عبارت است از . درحالیکه اطلاعات متقابل دوتایی، وابستگی میان دو ویژگی را محاسبه می­کند، اطلاعات متقابل چندگانه، میزان وابستگی میان چندین ویژگی را محاسبه می­کند؛ اما چون محاسبه میزان آنتروپی مشترک مجموعه­ای از ویژگی­ها بسیار پرهزینه است، تلاش­های زیادی به منظور ارائه یک تخمین مناسب از اطلاعات متقابل انجام شده است  فرض کنید S به مجموعه­ای از ویژگی­ها با n ویژگی و f  به یک عضو از مجموعه  اشاره کند. حال مجموع آنتروپی همه زیرمجموعه­های k عضوی از مجموعه Sk با استفاده از نماد  به صورت زیر نشان داده می­شود:

(3)

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

(4)

 

حال اگر به مجموعه تمام زیرمجموعه­های  عضوی از مجموعه توانی  همانند زیر اشاره ­کند:

(5)

  در این صورت، با در نظر گرفتن  Yبه عنوان یک عضو از مجموعه ، رابطه شماره (2) را می­توان به صورت زیر بازنویسی کرد:

(6)

حال به منظور تخمین آنتروپی توام چندین متغیر با استفاده از آنتروپی­های  عضوی، می­توان حاصل جمع بالا را به صورت زیر نوشت:

(7)

از طرف دیگر همانند فرمول رابطه (4)، می­توان مجموع اطلاعات متقابل با زیرمجموعه­هایی با سایز  را به صورت زیر نوشت:

(8)

در نتیجه فرمول رابطه (7) را به صورت زیر می توان بازنویسی کرد:

(9)

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

(10)

   با استفاده از رابطه شماره (11) می­توان آنتروپی توام دو مجموعه S و L را به صورت آنتروپی توام روی مجموعه های  عضوی از مجموعه  همانند زیر تعریف کرد:

(11)

   به‌طوری‌که  به مجموعه توانی حاصل‌ضرب دکارتی مجموعه­های  و  اشاره می­کند. مجموعه توانی  در طرف راست رابطه (5-12) را می­توان به صورت سه عبارت نوشت. به این صورت که عبارت اول از حاصل‌ضرب دکارتی ، عبارت دوم از حاصل‌ضرب مجموعه­های  و عبارت سوم از حاصل‌ضرب اعضای باقی‌مانده مجموعه­ها به‌دست می­آید. همان‌طور که قبلاً گفته شد،  و  به عضوهای صفر عضوی از مجموعه توانی  و  اشاره می­کند. به عنوان مثال،  را می­توان به صورت حاصل‌جمع سه عبارت نوشت: عبارت اول ، عبارت دوم  و عبارت سوم . می­توان گفت  عبارت است از:

(12)

عبارت بالا نشان می­دهد که هر زیرمجموعه  عضوی از مجموعه  را می­توان به صورت اعضای

 ،  و  نوشت. از آنجا که عبارت سوم اطلاعات متقابل چندگانه بین متغیرهای انتخاب شده از ترکیب  و  را شامل می­شود، پس شامل اعضای با اندازه بیشتر یا مساوی دو است. در نتیجه با استفاده از رابطه (13) می­توان رابطه (12) را به صورت زیر نوشت:

(13)

به‌طوری‌که n و t به ترتیب به اندازه مجموعه L و S اشاره می­کند. در نتیجه با استفاده از رابطه (14) اطلاعات متقابل میان دو مجموعه را می­توان به صورت زیر خلاصه کرد:

(14)

 

3-       راهکار پیشنهادی

برای انتخاب ویژگی در الگوریتم‌های انتخاب ویژگی چندبرچسبی، مجموعه داده‌های آموزشی را با نماد  نشان می‌دهیم. در اینجا، n تعداد نمونه‌های آموزشی و d تعداد ویژگی‌ها را نشان می‌دهد. همچنین، فرض کنید    به مجموعه فضای برچسب‌ها با |L|  حالت مختلف اشاره کند. فضای ویژگی‌ها نیز یک بردار با جریان پویا F={f1,f2,…,ft,..} است که به تدریج به مجموعه داده‌ها اضافه می‌شود. در این قسمت، یک راهکار برای انتخاب ویژگی مبتنی بر نظریه اطلاعات متقابل چندگانه در داده‌های آموزشی چندبرچسبی ارائه می‌دهیم. این راهکار قادر است با وجود جریان ویژگی، از میان ویژگی‌هایی که تا آن لحظه وارد شده‌اند، یک زیرمجموعه بهینه از ویژگی‌ها را انتخاب کند.

3-1- چهارچوب روش پیشنهادی

در این بخش، الگوریتم پیشنهادی به نام MLOSFS (Multi Label Online Stream Feature Selection) که برای انتخاب ویژگی در داده‌های چندبرچسبی با جریان آنلاین طراحی شده است را معرفی می‌کنیم. تعداد ویژگی‌ها در این الگوریتم به طور خودکار توسط خود الگوریتم محاسبه می‌شود. همان‌طور که در شکل 1، چهارچوب روش پیشنهادی هنگامی که یک ویژگی وارد می‌شود، MLOSFS ابتدا ارتباط آن با برچسب‌ها را بررسی می‌کند. اگر ویژگی با برچسب‌ها مرتبط باشد، آن را به مجموعه ویژگی‌های انتخاب شده S اضافه می‌کند؛ در غیر این‌صورت، آن را نادیده می‌گیرد. اگر ویژگی به مجموعه S اضافه شود، MLOSFS تعدادی از ویژگی‌هایی که هیچ تأثیری در پیش‌بینی برچسب‌ها ندارند را حذف می‌کند. این فرایند تا زمانی ادامه می‌یابد که ویژگی جدیدی به داده‌ها اضافه نشود. به طور کلی، می‌توان گفت که این الگوریتم دارای دو فاز اصلی به نام ارتباط و افزونگی است. در شکل 1، چهارچوب کلی روش پیشنهادی پیشنهادی آورده شده است.

 

شکل 1: فلوچارت الگوریتم پیشنهادی

فاز اول: در مرحله اول، یعنی فاز ارتباط، ما بررسی می‌کنیم که آیا ویژگی جدید با برچسب‌های کلاس مرتبط است یا خیر؟ در یادگیری چندبرچسبی، میزان ارتباط یک ویژگی جدید  fiبا برچسب‌های کلاس  (L) با استفاده از محاسبه مقدار  به صورت زیر تعیین می‌شود.

(15)

 

به منظور جلوگیری از احتمال تخمین نادرست ناشی از مجموعه داده­های چند برچسبی با ابعاد بزرگ، با در نظر گرفتن ، رابطه بالا را می­توان به صورت زیر تخمین زد:

(16)

 

به‌طوری‌که × به حاصل‌ضرب دکارتی و  به مجموع تعاملات با درجه  میان متغیرها اشاره دارد که طبق رابطه (9) عبارت است از:

(17)

 به مجموعه توانی از ، بدون در نظر گرفتن ،  به تمام زیرمجموعه­های عضوی از مجموعه توانی  و X به یک عضو دلخواه از مجموعه توانی   با اندازه  اشاره می­کند. همچنین مقدار  عبارت است از:

(18)

به منظور محاسبه دقیق این عبارت تمام حالات ممکن از زیر مجموعه­های مجموعه توانی  به منظور محاسبه اطلاعات متقابل میان ویژگی  و مجموعه برچسب­های  باید در نظر گرفته شود. از آنجا که  پس می­توان رابطه زیر را به‌دست آورد:

(19)

به همین ترتیب یک تخمین ساده از رابطه بالا عبارت است از:

(20)

  طبق این الگوریتم اگر ویژگی تازه‌وارد با مجموعه برچسب­ها بر اساس رابطه (21) مرتبط بود، ویژگی تازه‌وارد به مجموعه ویژگی­های انتخابی اضافه و الگوریتم وارد فاز دوم می­شود (خط 4 تا 7 الگوریتم پیشنهادی در شکل2 ). در غیر این‌صورت الگوریتم منتظر ورود ویژگی جدید می­ماند.

 

شکل 2: شبه کد الگوریتم پیشنهادی

فاز دوم، افزونگی: در این فاز قدرت تاثیر ویژگی­ها بر اساس خطوط 8 تا 21 الگوریتم پیشنهادی در شکل 2 محاسبه می­شود. هدف اصلی در این فاز، انتخاب حداقل تعداد ویژگی است به‌طوری‌که میزان ارتباط ویژگی­ها همچنان حفظ شود. در این فاز در هر مرحله ویژگی­هایی با قدرت تاثیر بالا انتخاب می­شوند. میزان تاثیر یک ویژگی را می‌توان با در نظر گرفتن ارتباط آن ویژگی، با برچسب کلاس و در نظر گرفتن سایر ویژگی­های انتخاب شده قبلی محاسبه کرد. هر چه میزان ارتباط یک ویژگی با مجموعه برچسب­ها بیشتر و افزونگی کمتری داشته باشد، پس قدرت تاثیر ویژگی بیشتر است. انتخاب ویژگی­ با قدرت تاثیر بالا از میان مجموعه ویژگی­های انتخاب شده تا زمانی ادامه می­یابد، که میزان ارتباط مجموعه ویژگی­های انتخاب شده جدید () با برچسب کلاس نزدیک به مقدار ارتباط مجموعه ویژگی­های انتخابی اولیه () با مجموعه برچسب­های  باشد. بر اساس الگوریتم (1)­، در فاز افزونگی ابتدا قدرت تاثیر هر ویژگی محاسبه می­شود. طبق رابطه زیر، قدرت تاثیر ویژگی fi  که با نشان داده می­شود عبارت است از: 

(21)

به‌طوری‌که اصطلاح اول به مقدار ارتباط ویژگی با برچسب کلاس و اصطلاح دوم به مقدار افزونگی ویژگی fi  با سایر ویژگی­های قبلاً انتخاب‌ شده اشاره می­کند. همان‌طور که پیش­تر نیز گفته شد، مقدار ارتباط ویژگی عبارت است از:  

(22)

از طرف دیگر افزونگی ویژگی fi ، شامل دو قسمت است. قسمت اول، عبارت است از افزونگی ویژگی fi  با سایر ویژگی­های قبلاً انتخاب شده، با در نظر گرفتن برچسب­های کلاس و قسمت دوم شامل افزونگی برچسب­ها نسبت به یکدیگر با در نظر گرفتن ویژگی fi  است. با در نظر گرفتن ، می­توان گفت افزونگی ویژگی fi  از رابطه زیر به‌دست می­آید:

(23)

و

(24)
(25)

حال با جای‌گذرای روابط (24)، (25) و (26) در رابطه شماره (22) می­توان قدرت تاثیر ویژگی fi  را از رابطه زیر به‌دست آورد:

(26)

---

[1]  Mutual Information-based Online Feature Selection

[2] 1 Moore-Penrose

[3] 2 Linear kernel

[4] 3 Delta kernel

---