بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
دسته بندي دادههاي چند برچسبی با استفاده از وابستگی بین کلاسها و تخمین تعداد برچسبها
چکیده - با افزایش حجم دادهها نیاز به دستهبندي و تحلیل دادهها به صورت خودکار، از جایگاه ویژهاي بر خوردار شده است. در این مقاله به دسته بندي دادههاي چندبرچسبی خواهیم پرداخت . دادههاي چند برچسبی دادههایی هستند که در آنها نمونهها میتوانند بیش از یک برچسب داشته باشند. به عبارت دیگر هر نمونه توسط یک بردار از برچسبها نمایش داده میشود.
در این مقاله یک روش مبتنی بر نزدیک ترین همسایگی براي دستهبندي دادههاي چندبرچسبی پیشنهاد شده است. در روش ارائه شده نخست تعداد برچسبها براي هر نمونه جدید تخمین زده میشود و سپس براي هر نمونه جدید، با استفاده از ارتباط و وابستگی بین برچسبها، برچسبهاي آن را پیشبینی میگردد. در این مقاله از دستهبند نزدیک ترین همسایگی به عنوان دسته بند پایه استفاده شده است اما با این تفاوت که براي محاسبه فاصله بین نمونهها از معیار فاصله اقلیدسی استفاده نمیشود. با ارزیابی روش پشنهادي بر روي مجموعهدادههاي موجود در حوزه دادههاي چندبرچسبی و مقایسه آن با دیگر روشهاي مطرح در این زمینه، نشان داده میشود که روش پیشنهادي در مقایسه با روشهاي دیگر در پیشبینی برچسبهاي نمونههاي جدید، از لحاظ پیچیدگی زمانی و دقت از کارایی بهتري برخوردار است.
کلید واژه-دادههاي چندبرچسبی ، دستهبندي دادهها، الگوریتمهاي دستهبندي
-1مقدمه
در دسته بندي تک برچسبی هر نمونه با یک برچسب در ارتباط میباشد که این برچسب ویژگیهاي آن نمونه را مشخص میکند. در دسته بندي چند برچسبی هر نمونه ممکن است با چندین برچسب در ارتباط باشد و اجتماع این برچسبها ویژگیهاي نمونهها را مشخص میکنند به عبارت دیگر در دستهبندي چندبرچسبی هر نمونه توسط برداري از برچسبها مشخص میشود. در بساري از کاربردهاي واقعی نیز دادهها چند برچسبی میباشند. به عنوان مثال یک فیلم سینمایی ممکن است مربوط به چندین ژانر مختلف باشد. و یا یک خبر مربوط به چندین حوزه مختلف باشد. معمولا براي حل این مسائل از راهکارهاي تک برچسبی استفاده می شود که اغلب، این راهکارها،باعث افزایش هزنیههاي نگه داري و بازیابی میشود و داراي پیچیدگی زمانی زیادي نیز هستند. با افزایش تعداد برچسب ها یادگیري دادههاي چند برچسبی دچار چالش می شود زیرا با این افزایش،
تعداد حالتهاي ممکن براي مجموعه برچسبهاي متفاوت به صورت نمایی افزایش می یابد و نمیتوان از الگوریتمهاي موجود در دادههاي تک برچسبی براي حل این مسائل استفاده کرد. زیرا استفاده از دستهبندهاي دادههاي تک برچسبی باعث پیچیدگی زمانی زیادي می شود.روشهاي یادگیري چند برچسبی سعی در کاهش این هزینهها دارند.از طرفی برخی از کاربردها همانند توابع تاثیر ژنها، ذاتا چند برچسبی هستند و حتی با هزنیه هاي بالا هم نمیتوان آنها را به مسئله تک برچسبی تبدیلn کردونیاز به یادگیري چند برچسبی براي این مسائل ضروري است. در یادگیري چند برچسبی هدف یافتن تابع نگاشتی است که فضاي ویژگیهاي را به فضاي مجموعه برچسبها نگاشت کند.[1]
یک رویکرد مناسب براي حل این مشکل استفاده از ارتباط و وابستگی بین برچسب میباشد.
در ادامه این مقاله در بخش 2 مروري بر پژوهشهاي پیشین در حوزه یادگیري چند برچسبی خواهیم داشت در بخش 3 روش پیشنهادي ارائه میشود در بخش 4 به ارزیابی و مقایسه نتایج حاصل از پیاده سازي روش پیشنهادي میپردازیم و در بخش 5 نتایج و جمع بندي ارائه می شود.
-2مروري بر پژوهشهاي پیشین
انواع پژوهش هاي انجام شـده در حـوزه یـادگیري داده هـاي چند برچسبی به سـه دسـته کلـی روشهـاي تطبیـق الگـوریتم ، روش هاي تغییر مسئلهو روش هاي جمعـی تقسـیم بنـدي شـده است.[2]
-1 -2 روشهاي تغییر مسئله
این روشها تلاش می کنند که داده هاي چند برچسـبی را بـه گونــهاي تغییــر دهنــد کــه ایــن دادههــا تبــدیل بــه داده هــاي تک برچسبی شوند. سپس با استفاده از روش هـا و الگـوریتم هـاي موجود در حوزه یادگیري تک برچسبی کار یادگیري و پیش بینـی برچسب هـا را بـراي ایـن دادههـا انجـام مـیشـود. کـه برخـی از مهمترین روش ها در این حوزه عبارتند از:
روش ارتبــاط دودویــی(:(BRدر ایــن روش بــه ازاي تعــداد برچسب ها، دسته بند ساخته می شود. و یـادگیري و پـیش بینـی براي هـر کـدام از ایـن دسـتهبنـدها بـه صـورت جداگانـه انجـام می شود.یعنـی بـه ازاي هـر برچسـب یـک دسـتهبنـد جداگانـه خواهیم داشت.
روش مجموعــه تــوانی(:(LPدر ایــن روش بــه ازاي هــر زیــر مجموعه اي از مجموعه توانی برچسب هاي موجود، یـک برچسـب جداگانه در نظر گرفته می شود. براي نمونه اگر L برچسب داشته باشیم2L مجموعه برچسب خواهیم داشت که هر کدام بـه عنـوان یک برچسـب مجـزا در نظـر گرفتـه مـیشـود و بـه ایـن ترتیـب داده هاي چند برچسبی به داده هاي تک برچسبی تبدیل میشـوند .[3]
روش فاصله جفتی:در این روش به ازاي هـر جفـت برچسـب یک دسته بند ساخته می شود. یعنی اگر L برچسب داشته باشـیم L*(L-1)/2 دسته بند ساخته می شود. هر دستهبند بـراي مقایسـه دو برچسب به کار میرود. براي دادههاي آزمایشی هر کدام از این
دسـته بنـدهـا یکـی از دو برچســب را بـه عنـوان برچسـب آنهــا پیش بینی می کند در پایان براي ترکیب این دسـتهبنـدها از روش رايگیري و رتبهبندي استفاده می شـود. یـک روش جدیـد مـوثر براي رايگیري بـر اسـاس روش وزن دهـی Qweighted بـه نـام QWML براي روش فاصله جفتی ارائه شده است]۴.[
-2 -2 روشهاي تطبیق الگوریتم
در این دسته از روش ها تلاش مـی شـود کـه الگـوریتم هـاي موجود در دسته بندي دادههاي تک برچسـبی بـه گونـهاي تغییـر داده شوند که توانایی دستهبندي داده هاي چند برچسبی را داشته باشند.
روش درخت تصمیم: در این روش سعی شده الگوریتم C4.5 به گونه تغییر داده شود تا این الگوریتم براي دستهبندي دادههاي چند برچسبی هم مناسـب باشـد. در الگـوریتم C4.5ML- رابطـه موجود در الگوریتم C4.5 براي محاسبه اینتروپی تغییـر یافتـه و به صورت رابطه (1) محاسبه میشود.[5]
منظور از E مجموعه نمونههاي آموزشی و منظـور از نسـبت تکرار هاي برچسب i ام به مجموع تکرارهاي کل برچسبهـا مـی باشد و است.
روش نزدیک ترین همسایگی:در این روش ابتدا با اسـتفاده از فاصله اقلیدسی نزدیکترین همسایه هاي نمونه جدید پیدا می شود سپس در بین این همسایهها احتمال ایـن کـه نمونـه جدیـد هـر کـدام از برچســبهــا را بگیــرد محاســبه مــی شــود. ســپس ایــن احتمالات را به عنوان احتمال اولیه اینکه یک نمونه جدید با چـه کلاسهایی در ارتباط است به یک دسته بند بیز داده می شـود و برچسبهاي خروجی دسته بند بیزین که احتمال بیش 0.5 دارنـد به عنوان برچسب هاي نمونه جدید درنظر گرفته می شوند.[6]
روش :HOMERاینروش یک سلسله مراتب از دسـتهبنـدهـا می سازد؛که هر کدام از این دستهبندها با یک مجموعه کوچـک از برچسب ها (نسبت به کل برچسـب هـا) در ارتبـاط هسـتند. ایـده اصلی این است که الگوریتم دسته بندي داده هاي چند برچسـبی، در مجموعه داده هاي با برچسب هاي زیاد، بـه شـکل یـک درخـت سلســله مراتبــی تبــدیل شــوند. در ایــن درخــت هــر گرهشــامل
مجموعه اي از برچسب ها می باشد. این درخت |L| بـرگ دارد کـه هر کدام از این برگ ها شامل یک مجموعه مولفه با برچسب جـدا می باشد{ j}و هر گره داخلی شامل مجموعه برچسب هایی اسـت که از اجتماع برچسب هاي فرزندانش بدست میآید و ریشه شامل همه برچسب ها می باشد. هر گـره داخلـی از سلسـله مراتـب نیـز شامل یک دسته بند چند برچسبی((hn می باشد. کار این دستهبند این است که یک یا چند ابر برچسب براي فرزنـدانش پـیشبینـی کند.[7]
-3 -2 روشهاي جمعی
در دسته بنـدي داده هـا بـه کمـک روشهـاي جمعـی، ابتـدا نمونــههــا را توســط چنــدین دســتهبنــد جداگانــه، دســتهبنــدي می کنند. سپس براي مشخص کـردن برچسـب نهـایی نمونـههـا، براي هر نمونه، بین دستهبندها رايگیري انجام میدهند.
روشK مجموعه برچسب تصـادفی(:(RAKELدر ایـن روش ابتدا به صورت تصادفی مجموعه برچسب هاي اولیه به K مجموعه برچسب مساوي افـراز مـی شـود. سـپس بـراي هـر کـدام از ایـن مجموعه برچسب هاي ایجاد شده، به صورت جداگانه دسته بنـدي انجام می شود. یعنی براي هر کدام از ایـن مجموعـه برچسـبهـا، تمام مجموعه توانی آن هـا را سـاخته و کـار دسـتهبنـدي انجـام می شود. در پایان براي مشخص کردن خروجی نهایی یـک نمونـه جدید، بـین خروجـی هـاي ایـن K دسـتهبنـد راي گیـري انجـام میشود.[8]
مــدل دســتهبنــدي زنجیــرهاي(:(CCدر مــدل دســتهبنــدي زنجیره اي L دستهبند دودویـی وجـود دارد. کـه هـر دسـتهبنـد دودویی براي یک برچسب است و این دسته بنـد هـا بـا هـم یـک زنجیر را می سازنند. در این زنجیر هر دسته بند مربوط به یکـی از برچسبهاي موجود در مجموعه برچسبها است.[9]
-3روش پیشنهادي
هدف نهایی در دسته بندي داده هـاي چندبرچسـبی ارائه الگوریتم هایی اسـت کـه توانـایی پـیشبینـی برچسـبهـاي نمونه هاي جدید را داشته باشند. بنابراین لازم است الگوریتمهـاي ارائه شده در این راستا سه مسئله مهم زیر را در نظر بگیرند:
.1 مشخص کردن احتمال حضور هر برچسب براي هر نمونه
2. تعیین کردن تعداد برچسبهاي هر نمونه
3. هزینه محاسباتی پایین
روش هاي تغییر مسئله ( همانند روش ارتباط دودویی، روش مجموعه توانی و روش فاصله جفتی ) نسبت به روش هـاي دیگـر در محاسبه احتمال حضور هر برچسب بـراي نمونـه هـاي جدیـد موفق تر هستند اما کاستی بزرگ این روش ها هزینه زمانی بسـیار بـالاي آنهاسـت و زمــانی کـه حجــم مجموعـه دادههــا یـا تعــداد برچسب ها زیاد شود، استفاده از این روشها در عمل غیـر ممکـن مـیشــود. از طرفـی ایــن روشهـا بــراي مشـخص کــردن تعــداد برچسب هاي نمونه هاي جدیـد هـیچ راهحلـی ارائـه نمـیدهنـد و معمولا تعداد برچسب هاي نمونه هاي جدید را به اشتباه تشخیص میدهند.
روش هاي تطبیق الگوریتم ها ( همانند روش درخت تصـمیم، روش نزدیکترین همسایگی، روش HOMERو..) نسبت بـه دیگـر روش ها اغلب داراي پچیدگی زمانی پایین تري هستند و با بـزرگ شدن حجم مجموعه داده ها یا تعـداد برچسـب هـا دچـار چـالش جدي نمی شوند. اما این روش ها نسـبت بـه دیگـر روشهـا داراي دقت پایین تري در پیشبینی برچسبها هستند این روشهـا نیـز همانند روش هاي تغییر مسئله هیچ راهکاري براي مشخص کردن تعداد برچسب هاي نمونه هاي جدید ارائه نمیدهند. ایـن روشهـا معمولادر تشخیص تعداد برچسب هاي نمونـه هـاي جدیـد دچـار مشکل میشوند.
روش هاي جمعی رفتارهاي متفاوتی دارند، برخـی روشهـاي جمعی (همانند روش ( RAKEL با وجود اینکه داراي پیچیـدگی زمانی پایینی هستند اما در تشخیص احتمـال برچسـبهـاي هـر نمونه، دقـت کـافی ندارنـد و بسـیار حسـاس بـه پارامترهایشـان هســتند. برخــی دیگــر از روشهــاي جمعــی (هماننــد روش دسـتهبنـدي زنجیـرهاي ) ماننـد روشهـاي تغییـر مســئله داراي پیچیدگی زمانی زیادي هستند و زمانی که حجم مجموعه داده ها یا تعداد برچسب ها زیاد شود استفاده از این روشها در عمل غیـر ممکن می شود.در راستاي حل مسئله دسته بندي داده هـاي چنـد برچسبی، ساختار شکل((1 براي حل مساله بیان می شـود کـه در ادامه هر کدام از زیر بخشها با جزیئات بیشتر بیان میشود.
شکل :1 ساختار روش پیشنهادي
-1 -3 تخمین تعداد برچسبهاي هر نمونه
بسیاري از الگوریتم هاي ارائه شده براي دسته بندي داده هاي چند برچسبی، اغلب پس از مشخص کـردن احتمـال حضـور هـر برچسب در هر نمونه جدید i، از یک تابع آسـتانگی بـراي تعیـین برچسب هاي نهایی استفاده می نمایند. این تابع آسـتانگی معمـولا به صورت رابطه (2) تعریف میشود.
که منظور از حتمال حضور برچسبiام براي نمونه جدید j ام و منظور از برچسب iام براي نمونه jام است.
میزان دقت و کارایی الگوریتم هایی که از رابطه (1- 3) بـراي تعیین تعـداد برچسـب هـاي نهـایی نمونـه هـاي جدیـد اسـتفاده می کنند، به میزان زیـادي بـه نحـوه انتخـاب متغیـر آسـتانگی a وابسته است. به عنوان نمونه در الگـوریتم نزدیکتـرین همسـایگی a=0.5 در نظر گرفته می شود.
بـه منظــور مــدیریت چــالش مـذکور بــراي تخمــین تعــداد برچسب هاي نمونه هاي جدید، تخمین تعداد برچسـب هـاي یـک نمونه جدید قبل از دسته بندي به عنوان یـک فـاز اولیـه در نظـر گرفته میشود و در آن تخمین تعداد برچسبها انجام میپذیرد.
-2 -3 استفاده از احتمال شرطی برچسبها
براي اینکه درپـیش بینـی برچسـب هـاي نمونـه هـاي جدیـد کارایی بهتري حاصل شود مـی تـوان از ارتبـاط و وابسـتگی بـین برچسب ها استفاده کرد. اگر بـدانیم کـه یـک نمونـه حتمـا یـک برچسب خاص را می گیرد می توان از وابستگی بین این برچسب و دیگر برچسب ها براي دسته بندي دادهها استفاده کرد. بـه عنـوان نمونه، فرض کنید برچسب L1 جزء برچسب هاي واقعی یک نمونه است. اکنون اگر بدانیم که برچسب L2 در هیچ یک از مثـالهـاي آموزشی به همراه برچسب L1 نیامده است و برچسب L3 همـواره با برچسب L1 رخ داده است می توان گفت، اگر نمونه اي برچسب L1 را داشته باشد به احتمال بالایی برچسب L3 را دارد و برچسب L2 را ندارد. رابطه (3) احتمال شرطی مربوط به برچسب هـاي L1 و L2 را نشان میدهد.
رابطه (4) احتمال شـرطی مربـوط بـه برچسـبهـاي L1 و L3را نشان میدهد.
نکته اصلی بـراي اسـتفاده از وابسـتگی بـین برچسـبهـا در دسته بندي داده هاي چندبرچسبی این است که ابتـدا بـراي یـک نمونه جدید برچسبی یافته شود که با احتمال زیادي مربـوط بـه آن نمونه باشد. سپس براي بقیه برچسبها کـه احتمـال کمتـري دارند از احتمال شرطی استفاده شود و در پایان کار دسـته بنـدي انجام شود. براي یافتن احتمال هر برچسب براي هر نمونه جدیـد از روش نزدیکترین همسایگی استفاده خواهد شد.
براي هر نمونه جدیـد ابتـدا بـا اسـتفاده از روش نزدیکتـرین همسایگی، K نزدیکترین همسایه آن پیدا شـده سـپس در بـین برچسب هاي این K همسایه، احتمال وقوع هر برچسـب محاسـبه می شود. یعنی براي هر برچسب تعداد رخداد آن برچسب در بـین K همسایه، بر مجموع رخدادهاي کل برچسب ها در K همسایه تقسیم می شود. سپس براي هر نمونه، برچسـبی کـه بـیش تـرین تکرار را داشته باشد به عنوان برچسب اصلی ایـن نمونـه در نظـر گرفته شده و احتمالات بدست آمده براي برچسـبهـاي دیگـر از روش نزدیکترین همسایگی بـا اسـتفاده از احتمـال شـرطی ایـن برچسب و دیگر برچسبها به روز رسانی میشود.
