Propose a Proper Algorithm for Incremental Learning Based on Fuzzy Least Square Twin Support Vector Machines
Subject Areas : electrical and computer engineeringJavad Salimi Sartakhti 1 * , Salman Goli 2
1 -
2 -
Keywords: Incremental learning, SVM, fuzzy classification, FLSTSVM,
Abstract :
Support Vector machine is one of the most popular and efficient algorithms in machine learning. There are several versions of this algorithm, the latest of which is the fuzzy least squares twin support vector machines. On the other hand, in many machine learning applications input data is continuously generated, which has made many traditional algorithms inefficient to deal with them. In this paper, for the first time, an incremental version of the fuzzy least squares twin support vector algorithm is presented. The proposed algorithmis represented in both online and quasi-online modes. To evaluate the accuracy and precision of the proposed algorithmfirst we run our algorithm on 6 datasets of the UCI repository. Results showthe proposed algorithm is more efficient than other algorithms (even non-incremental versions). In the second phase in the experiments, we consider an application of Internet of Things, and in particular in data related to daily activities which inherently are incremental. According to experimental results, the proposed algorithm has the best performance compared to other incremental algorithms.
[1] D. Bhattacharya and M. Mitra, Analytics on Big Fast Data Using Real Time Stream Data Processing Prchitecture, EMC Corporation, 2013.
[2] B. E. Boser, I. M. Guyon, and V. N. Vapnik, "A training algorithm for optimal margin classifiers," in Proc. of the 5th Annual Workshop on Computational Learning Theory, pp. 144-152, Pittsburgh, PA, USA, 27-29 Jul. 1992.
[3] R. T. Rockafellar, "Lagrange multipliers and optimality," SIAM Review, vol. 35, no. 2, pp. 183-238, 1993.
[4] J. A. Suykens and J. Vandewalle, "Least squares support vector machine classifiers," Neural Processing Letters, vol. 9, no. 3, pp. 293-300, Jun. 1999.
[5] J. A. K. Suykens, T. Van. Gestel, J. De Brabanter, B. De Moor, and J, Vandewalle, Least Squares Support Vector Machines, World Scientific, 2002.
[6] R. Khemchandani and S. Chandra, "Twin support vector machines for pattern classification," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 29, no. 5, pp. 905-910, May 2007.
[7] M. A. Kumar and M. Gopal, "Least squares twin support vector machines for pattern classification," Expert Systems with Applications, vol. 36, no. 4, pp. 7535-7543, May 2009.
[8] J. S. Sartakhti, H. Afrabandpey, and N. Ghadiri, "Fuzzy least squares twin support vector machines," Engineering Applications of Artificial Intelligence, vol. 85, pp. 402-409, Oct. 2019.
[9] V. Losing, B. Hammer, and H. Wersing, "Incremental on-line learning: a review and comparison of state of the art algorithms," Neurocomputing, vol. 275, pp. 1261-1274, Jan. 2018.
[10] R. KhemchandaniJayadeva, and S. Chandra, "Incremental twin support vector machines," in Modeling, Computation and Optimization, in S. K. Neogy, A. K. Das, and R. B. Bapat (eds.), pp. 263-272, World Scientific, 2009.
[11] P. Mitra, C. A. Murthy and S. K. Pal, "Data condensation in large databases by incremental learning with support vector machines," in Proc.of 15th Int. Conf. on Pattern Recognition. ICPR'00, vol.2, pp. 708-711, , Barcelona, Spain, 3-7 Sept. 2000,
[12] Y. Hao and H. Zhang, "A fast incremental learning algorithm based on twin support vector machine," in Proc. IEEE 7th Int. Symp. on Computational Intelligence and Design, , vol. 2, pp. 92-95, Hangzhou, China, 13-14 Dec. 2014.
[13] F. Alamdar, S. Ghane, and A. Amiri, "On-line twin independent support vector machines," Neurocomputing, vol. 186, no. C, pp. 8-21, Apr. 2016.
[14] G. Fung and O. L. Mangasarian, "Incremental support vector machine classification," in Proc. of the SIAM Int. Conf. on Data Mining, pp. 247-260, Arlimgton, VA, USA, 11-13 Apr. 2002.
[15] A. Tveit, M. L. Hetland, and H. Engum, "Incremental and decremental proximal support vector classification using decay coefficients," in Proc. of the Int. Conf. on Data Warehousing and Knowledge Discovery, pp. 422-429, Prague, Czech Republic, 3-5 Sept. 2003.
[16] A. R. Mello, M. R. Stemmer, and A. L. Koerich, "Incremental and decremental fuzzy bounded twin support vector machine," Information Sciences, vol. 526, pp. 20-38, Jul. 2020.
[17] J. Xu, C. Xu, B. Zou, Y. Y. Tang, J. Peng, and X. You, "New incremental learning algorithm with support vector machines," IEEE Trans. on Systems, Man, and Cybernetics, Systems, vol. 49, no. 11, pp. 2230-2241, Nov. 2018.
[18] I. A. Lawal, "Incremental SVM learning," Studies in Big Data Learning from Data Streams in Evolving Environments, pp. 279-296, 2019.
[19] W. Xie, S. Uhlmann, S. Kiranyaz, and M. Gabbouj, "Incremental learning with support vector data description," in Proc. IEEE 22nd Int. Conf. on Pattern Recognition, pp. 3904-3909, Stockholm, Sweden, 24-28 Aug. 2014.
[20] Z. Zhu, X. Zhu, Y. F. Guo, and X. Xue, "Transfer incremental learning for pattern classification," in Proc. of the 19th ACM International Conf. on Information and Knowledge Management, pp. 1709-1712, Toronto, Canada, 26-30 Oct. 2010.
[21] G. Cauwenberghs and T. Poggio, "Incremental and decremental support vector machine learning," in Proc. of the 13th Int Conf. on Neural Information Processing Systems, pp. 388-394, Denver, CO, USA, 1-1 Jan. 2000.
[22] H. Duan, X. Shao, W. Hou, G. He, and Q. Zeng, "An incremental learning algorithm for Lagrangian support vector machines," Pattern Recognition Letters, vol. 30, no. 15, pp. 1384-1391, 1 Nov. 2009.
[23] H. Galmeanu, L. M. Sasu, and R. Andonie, "Incremental and decremental SVM for regression," International J. of Computers Communications & Control, vol. 11, no. 6, pp. 755-775, Dec. 2016.
[24] H. Galmeanu and R. Andonie, "A multi-class incremental and decremental SVM approach using adaptive directed acyclic graphs," in Proc. IEEE Int Conf. on Adaptive and Intelligent Systems, pp. 114-119, Klagenfurt, Austria, 24-26 Sept. 2009.
[25] J. Wang, D. Yang, W. Jiang, and J. Zhou, "Semisupervised incremental support vector machine learning based on neighborhood kernel estimation," IEEE Trans. on Systems, Man, and Cybernetics: Systems, vol. 47, no. 10, pp. 2677-2687, Oct. 2017.
[26] M. S. Chen, T. Y. Ho, and D. Y. Huang, "Online transductive support vector machines for classification," in Proc. IEEE Int. Conf. on Information Security and Intelligent Control, pp. 258-261, Yunlin, Taiwan, 14-16 Aug. 2012.
[27] P. Rai, H. Daume, and S. Venkatasubramanian, "Streamed learning: one-pass SVMs," in Proc. 21st Int. Joint Conf. on Artificial Intelligence, pp. 1211-1216, Pasadena, CA, USA, 11-17 Jul. 2009.
[28] N. A. Syed, S. Huan, L. Kah, and K. Sung, "Incremental learning with support vector machines," in ¬ Proc. IEEE Int. Conf. on Data Mining, San Jose, CA, USA, 29 Nov.-2 Dec. 2001.
[29] F. Orabona, C. Castellini, B. Caputo, L. Jie, and G. Sandini, "On-line independent support vector machines," Pattern Recognition, vol. 43, no. 4, pp. 1402-1412, Apr. 2010.
[30] L. Ralaivola and F. d'Alche-Buc, "Incremental support vector machine learning: a local approach," in Proc. Int. Conf. on Artificial Neural Networks, pp. 322-330, Vienna, Austria, 21-25 Aug. 2001.
[31] M. N. Kapp, R. Sabourin, and P. Maupin, "Adaptive incremental learning with an ensemble of support vector machines," in Proc. IEEE 20th Int. Conf. on Pattern Recognition, pp. 4048-4051, Istanbul, Turkey, 23-26 Aug. 2010.
[32] C. Domeniconi and D. Gunopulos, "Incremental support vector machine construction," in Proc. IEEE Int. Conf. on Data Mining, pp. 589-592, San Jose, CA, USA, 29 Nov.-2 Dec. 2001.
[33] A. R. de Mello, M. R. Stemmer, and A. L. Koerich, Incremental and Decremental Fuzzy Bounded Twin Support Vector Machine, arXiv preprint arXiv:1907.09613, 2019.
[34] "Activities of Daily Living (ADLs) Recognition Using Binary Sensors Data Set," ed, 2013.
[35] F. Ordonez, P. De Toledo, and A. Sanchis, "Activity recognition using hybrid generative/discriminative models on home environments using binary sensors," Sensors, vol. 13, no. 5, pp. 5460-5477, 2013.
نشریه مهندسی برق و مهندسی كامپیوتر ایران، ب- مهندسی کامپیوتر، سال 19، شماره 3، پاییز 1400 183
مقاله پژوهشی
ارائه یک الگوریتم مناسب برای یادگیری جریانی بر اساس الگوریتم ماشینهای بردار پشتیبان دوقلوی مربعات حداقلی فازی
جواد سلیمی سرتختی و سلمان گلی بیدگلی
چكیده: الگوریتم ماشین بردار پشتیبان یکی از الگوریتمهای مشهور و با کارایی بالا در یادگیری ماشین و کاربردهای مختلف است. از این الگوریتم تا کنون نسخههای متعددی ارائه شده که آخرین نسخه آن ماشینهای بردار پشتیبان دوقلوی مربعات حداقلی فازی میباشد. اغلب کاربردها در دنیای امروز دارای حجم انبوهی از اطلاعات هستند. از سویی دیگر یکی از جنبههای مهم دادههای حجیم، جریانیبودن آنها میباشد که باعث شده است بسیاری از الگوریتمهای سنتی، کارایی لازم را در مواجهه با آن نداشته باشند. در این مقاله برای نخستین بار نسخه افزایشی الگوریتم ماشینهای بردار پشتیبان دوقلوی مربعات حداقلی فازی، در دو حالت برخط و شبه برخط ارائه شده است. برای بررسی صحت و دقت الگوریتم ارائهشده دو کاربرد آن مورد ارزیابی قرار گرفته است. در یک کاربرد، این الگوریتم بر روی 6 دیتاست مخزن UCI اجرا شده که در مقایسه با سایر الگوریتمها از کارایی بالاتری برخوردار است. حتی این کارایی در مقایسه
با نسخههای غیر افزایشی نیز کاملاً قابل تشخیص است که در آزمایشها به
آن پرداخته شده است. در کاربرد دوم، این الگوریتم در مبحث اینترنت اشیا و
به طور خاص در دادههای مربوط به فعالیت روزانه به کار گرفته شده است.
طبق نتایج آزمایشگاهی، الگوریتم ارائهشده بهترین کارایی را در مقایسه با سایر الگوریتمهای افزایشی دارد.
کلیدواژه: یادگیری جریانی، ماشینهای بردار پشتیبان، دستهبندی فازی، FLSTSVM.
1- مقدمه
امروزه حجم عظیم دادههای تولیدی و نوع آنها باعث شده که الگوریتمهای یادگیری ماشین سنتی کارایی چندانی نداشته باشند. بسیاری از این الگوریتمها در مواجهه با کلان دادهها2 کارایی خوبی ندارند. علاوه بر حجم دادهها، نوع دادهها هم میتواند باعث عدم کارایی الگوریتمهای سنتی شود. دادههای جریانی3 یکی از انواع دادههایی است که با ظهور و بروزش نیاز به تغییرات اساسی در الگوریتمهای یادگیری ماشین به وجود آورده است. دادههای جریانی دادههایی هستند که در طول زمان تولید میشوند و در هر لحظه به همه دادهها دسترسی نداریم [1]. علاوه بر آن در دادههای جریانی عموماً تغییر توزیع دادهها وجود دارد. یعنی دادهها تا یک زمان خاص از یک توزیع مشخص تبعیت میکنند اما به تدریج ممکن است توزیعشان تغییر کند. این ویژگی باعث میشود که الگوریتمهای سنتی به راحتی قادر به مواجهه با این نوع دادهها نباشند.
دادههای جریانی عموماً در حجم و سرعتی بالا تولید میشوند. به عنوان مثالی از دادههای جریانی میتوان به دادههایی که در کاربردهای اینترنت اشیا، لاگهای امنیتی و لاگهای سرورها، تبلیغات بلادرنگ، کلیکهای اپلیکیشنها و وبسایتها تولید میشوند اشاره کرد. در همه این مثالها ابزارهایی وجود دارند که به طور پیوسته دادههایی با ساختار و یا بدون ساختار را تولید میکنند. بنابراین به دلیل عدم وجود دادهها به صورت یکجا و نیز تغییر توزیع آنها در طول زمان، الگوریتمهای سنتی کارایی بالایی در این نوع دادهها ندارند. بیشتر راهکارهای ارائهشده برای مواجهه با این نوع دادهها بر پایه همان الگوریتمهای سنتی استوار هستند و محققین با تغییراتی در نسخههای اصلی، در کاربردهای دادههای جریانی استفاده نمودهاند. این راهکارها بدین گونه عمل میکنند که ابتدا الگوریتم یادگیری بر اساس یک مجموعه داده در دسترس آموزش میبیند و سپس دادههای جدیدی را که وارد میشوند بر اساس فاز یادگیری دستهبندی میکند. اما تغییر توزیع ممکن است این راهکارها را به شکست بکشاند. از سویی دیگر ممکن است برای مقابله با این نقطه ضعف به ازای هر نمونه جدید تصمیم بگیریم مدل آموزش دیده شده را بر روی تمامی دادههایی که تا کنون دریافت کردهایم مجدداً آموزش دهیم. این روش اگرچه تغییرات توزیع دادهها را یاد میگیرد اما به شدت کند است و عملاً در کاربردهای برخط استفاده از آن غیر ممکن میباشد. در راهکارهای دیگر ابتدا اهمیت هر نمونه جدید ورودی بر اساس یک سری از معیارها سنجیده میشود و سپس بر اساس آن تصمیم گرفته میشود که آیا نیاز به آموزش دوباره مدل آموزشدیده وجود دارد یا خیر. در صورت نیاز، فاز آموزش الگوریتم بر روی تمامی دادههایی که تا کنون دریافت شده است مجدداً اجرا میشود.
یکی از الگوریتمهایی که در کاربردهای سنتی کارایی قابل قبولی دارد الگوریتم ماشینهای بردار پشتیبان 4(SVM) است [2]. الگوریتم ماشین بردار پشتیبان یكی از الگوریتمهای معروف در زمینه یادگیری با ناظر است كه برای دستهبندی و رگرسیون استفاده میشود. یكی از خصوصیات مهم ماشین بردار پشتیبان این است كه به طور همزمان خطای تجربی دستهبندی را کمینه نموده و حاشیههای هندسی را از نمونههای دو کلاس بیشینه میكند. تا کنون چندین نسخه از ماشینهای بردار پشتیبان ارائه شده که از آن جمله میتوان به ماشینهای بردار پشتیبان دوقلو، مقدار ویژه و مربعات حداقل و نیز ماشین بردار پشتیبان دوقلوی مربعات حداقلی فازی (FLSTSVM) اشاره کرد. در سالهای اخیر کاربرد مفهوم فازی در این دسته از الگوریتمها به شدت توسعه یافته و بنابراین ماشین بردار پشتیبان دوقلوی مربعات حداقلی فازی کاربردهای فروانی پیدا کرده است.
از سوی دیگر با توجه به آنچه که به آن اشاره شد، این الگوریتم در مواجهه با دادههای حجیم و دادههای جریانی کارایی بالایی ندارد. در
این مقاله برای نخستین بار الگوریتمی افزایشی بر اساس الگوریتم FLSTSVM ارائه میشود که دارای کارایی به مراتب بهتری از سایر نسخههای SVM در مواجهه با دادههای جریانی میباشد. برای اثبات کارایی الگوریتم ارائهشده که آن را Incremental FLSTSVM مینامیم از 6 مجموعه داده متعلق به مخزن UCI استفاده شده که در همه آنها الگوریتم ارائهشده دقت و سرعت بیشتری دارد.
ساختار ادامه مقاله بدین شرح است: در بخش دوم به مفاهیم پایه در مورد نسخههای مختلف SVM و تفاوت آنها با یکدیگر میپردازیم و کارهای پیشین انجامشده در زمینه الگوریتم افزایشی ماشینهای بردار پشتیبان مورد بررسی قرار میگیرد. در بخش سوم الگوریتم پیشنهادی به طور مفصل ارائه شده و در مورد پیچیدگی متوسط الگوریتم ارائهگردیده بحث خواهد شد. در بخش چهارم نتایج پیادهسازی حاصل از اجرای الگوریتم پیشنهادی بر روی مجموعه دادههای گوناگون ارائه میشود و در بخش نهایی جمعبندی و کارهای آینده بیان خواهد گردید.
2- یادگیری ماشین و الگوریتمهای ژنتیک موازی
در این بخش مروری بر انواع نسخههای SVM خواهیم داشت و توانمندی هر یک از آنها را بیان میکنیم. در بخش بعدی نیز به انواع رویکردهایی که برای تبدیل این الگوریتمها به الگوریتمهای جریانی و یا افزایشی (الگوریتمهایی که فرایند یادگیری آنها به تدریج و با توجه به دریافت دادههای جریانی تکمیل میشود) ارائه شده است میپردازیم.
2-1 الگوریتم استاندارد ماشین بردار پشتیبان
ماشین بردار پشتیبان یک دستهبند متعلق به روشهای مبتنی بر کرنل است که برای اولین بار در سال 1992 توسط وپنیک در موسسه AT&T ارائه شد [2]. شهرت ماشین بردار پشتیبان به دلیل موفقیت آن در تشخیص حروف دستنویس است که با شبکههای عصبی که به دقت برای این کار تنظیم شده بودند برابری میکرد. ایده اصلی در ماشین بردار پشتیبان، بیشینهسازی حاشیه بین دو کلاس میباشد. اگر دادههای آموزشی به صورت ، و برچسبگذاری شده باشند ماشین بردار پشتیبان به دنبال ابرصفحهای با معادله است که توانایی ارضای محدودیتهای بیانشده در (1) را داشته باشد
(1)
چنین ابرصفحهای با حل (2) به دست خواهد آمد
(2)
برای حل (2) باید از روش مضربهای لاگرانژ استفاده کرد [2] که برای این کار دو دلیل وجود دارد. اول این که محدودیتهای نشان داده شده در (2) با خود ضرایب لاگرانژ جایگزین خواهند شد که این مسأله کار ما را بسیار راحتتر خواهد نمود. دوم این که در این گونه فرمولهنمودن مسأله، دادههای آموزشی فقط به صورت ضرب نقطهای بردارها پدیدار میشوند [3]. این یک ویژگی حیاتی است که به ما این اجازه را میدهد که فرایند حل مسأله را به حالت غیر خطی تعمیم دهیم.
2-2 الگوریتم ماشین بردار پشتیبان مربعات حداقلی
یکی از معایب الگوریتم ماشین بردار پشتیبان، زمان یادگیری نسبتاً طولانی آن میباشد. دلیل این زمان زیاد هم به دست آوردن مضربهای لاگرانژ با استفاده از برنامهنویسی غیر خطی است که راه حلهای آن دارای چندین تکرار برای به دست آوردن این ضرایب میباشند. از طرفی اگر بتوان محدودیتهای نابرابری را به محدودیتهای برابری تبدیل کرد، آن گاه تنها با یک بار اجرا میتوان مضربهای لاگرانژ را به دست آورد.
ماشینهای بردار پشتیبان مربعات حداقل5 [4] به دنبال تبدیل محدودیتهای نابرابری موجود در ماشین بردار پشتیبان به محدودیتهای برابری هستند. برای این کار باید محدودیتهای نمونههای مثبت و منفی تغییر کنند. به همین منظور در ماشین بردار پشتیبان مربعات حداقل به دنبال معادله ابرصفحهای هستیم که تمام نمونههای مثبت و منفی بر روی لبههای حاشیه این ابرصفحه قرار گیرند. از طرفی پیداکردن چنین ابرصفحهای عملاً امکانپذیر نمیباشد و بنابراین باید ابرصفحهای را یافت که با در نظر گرفتن فاصله هر نمونه از لبه حاشیه آن، علاوه بر این که پهنای حاشیهاش بیشینه باشد، فاصله هر نمونه نیز از لبه حاشیه این ابرصفحه حداقل باشد (یعنی سعی شود تا آنجایی که امکان دارد نمونههای مختلف بر روی لبه حاشیه قرار گیرند) که به این ترتیب محدودیتهای نابرابری به محدودیتهای برابری تبدیل خواهند شد. با تبدیل محدودیتها به تساوی، (2) به (3) تبدیل خواهد شد
(3)
همان گونه که در (3) آمده است برای محاسبه فاصله هر نمونه تا لبه حاشیه از فرمول مربعات حداقل استفاده شده است. بیان دوباره این نکته ضروری است که هنگامی که میزان خطا (فاصله هر نمونه از لبه حاشیه) درون فرمول کمینهسازی وجود دارد دیگر نیازی به محدودیت نابرابری نیست، چون خطای آن محاسبه میشود و بنابراین محدودیت نابرابری به محدودیت برابری تبدیل خواهد شد.
حال برای کمینهسازی (3) باز هم میتوان از مضارب لاگرانژ استفاده کرد، با این تفاوت که این بار احتیاجی به حل یک مسئله برنامهنویسی
غیر خطی نیست و مستقیماً میتوان مقادیر مضارب لاگرانژ، و را به دست آورد. تابع لاگرانژ به دست آمده برای (3) در (4) نمایش داده شده که در صورت حل آن به یک دستگاه معادله و مجهول خواهیم رسید که مجهولات را میتوان با حل (5) به دست آورد
(4)
(5)
پارامتر ، و به ترتیب برداری با طول مورد نیاز و درایههای با مقدار یک، ماتریس همانی به اندازه (تعداد نمونهها) و ماتریسی که درایه و آن بیانگر ضرب داخلی و میباشد را بیان میکنند.
الگوریتم LSSVM در بیشتر کاربردها دارای سرعت و دقت بیشتری از الگوریتم SVM است [5].
2-3 الگوریتم ماشین بردار پشتیبان دوقلو
ماشینهای بردار پشتیبان دوقلو [6] در ذات، شبیه ماشینهای بردار پشتیبان مقدار ویژه میباشند، یعنی در اینجا هم به دنبال به دست آوردن دو ابرصفحه ناموازی هستیم. اما تفاوت آن با رویکرد ماشینهای بردار پشتیبان مقدار ویژه در این است که در اینجا به دنبال بیشینهکردن فاصله از کلاس مقابل نیستیم بلکه نمونههای کلاس مقابل تنها به صورت محدودیت در معادله ابرصفحه جاری ظاهر میشوند (یعنی نمونههای کلاس مقابل باید حداقل حاشیهای را با ابرصفحه کلاس جاری رعایت کنند). محدودیتهای یادشده در معادلات ارائهشده برای هر یک از صفحات به صورت نابرابری ظاهر خواهند شد (همانند ماشین بردار پشتیبان عادی)، اما این محدودیتهای نابرابری برای هر یک از ابرصفحات به اندازه نمونههای موجود در کلاس مقابل میباشد. بنابراین اگر تعداد نمونههای مثبت و منفی برابر باشند، این محدودیتهای نابرابری برای هر یک از معادلات به اندازه نیمی از محدودیتهای نابرابری در ماشین بردار پشتیبان ارائهشده در بخش دو است. بنابراین به صورت کلی میتوان گفت که به جای حل معادله برنامهنویسی غیر خطی با محدودیتهای فراوان، ماشین بردار پشتیبان دوقلو، دو معادله با محدودیتهای بسیار کمتر را حل میکند که علاوه بر افزایش دقت، باعث افزایش سرعت نیز (تا چهار برابر) میگردد.
همان گونه که گفته شد الگوریتم ماشین بردار پشتیبان دوقلو سعی دارد دو ابرصفحه (برای هر یک از کلاسهای مثبت و منفی) را به گونهای بیابد که علاوه بر این که به نمونههای کلاس خود نزدیکترین هستند برای نمونههای کلاس مقابل نیز حداقل حاشیهای را (با در نظر گرفتن خطای ) در نظر بگیرند. برای به دست آوردن چنین ابرصفحاتی الگوریتم مورد نظر باید قادر به حل روابط کمینهسازی (6) و (7) به ترتیب برای کلاس مثبت و کلاس منفی باشد
(6)
(7)
برای حل هر یک از این معادلات میتوان همانند ماشین بردار پشتیبان از مضربهای لاگرانژ و نهایتاً از برنامهنویسی غیر خطی استفاده کرد.
2-4 ماشین بردار پشتیبان دوقلوی مربعات حداقل
ماشین بردار پشتیبان دوقلوی مربعات حداقل [7] سعی در ترکیب ایدههای موجود در ماشین بردار پشتیبان مربعات حداقل و ماشین بردار پشتیبان دوقلو دارد. به بیان دیگر از نقاط قوت هر دو رویکرد استفاده کرده و از نقاط ضعف آنها دوری میگزیند. بنابراین میتوان گفت که ماشین بردار پشتیبان دوقلوی مربعات حداقل به جای حل معادله برنامهنویسی غیر خطی با محدودیتهای نابرابری فراوان، دو معادله با محدودیتهای برابری بسیار کمتر (تقریباً نصف) را حل میکند. به عبارت دیگر ماشین بردار پشتیبان دوقلوی مربعات حداقل، به دنبال معادلات دو ابرصفحه است که هر کدام از آنها علاوه بر این که سعی دارند به نمونههای کلاس خود نزدیکترین باشند، تلاش میکنند که با در نظر گرفتن یک فاصله، تمام نمونههای کلاس مقابل را بر روی لبه حاشیه خود قرار دهند. به این ترتیب علاوه بر این که در ماشین بردار پشتیبان دوقلوی مربعات حداقل، دو ابرصفحه با مشخصات ذکرشده در ماشین بردار پشتیبان دوقلو وجود دارد، هر یک از آنها از ویژگی ماشین بردار پشتیبان مربعات حداقل (یعنی در نظر گرفتن خطا به صورت مربعات حداقل برای قرارگرفتن نمونههای کلاس مقابل در لبه حاشیه ابرصفحه) نیز سود میبرند. این تعریف از دو ابرصفحه منجر به رابطه کمینهسازی (8) و (9) برای به دست آوردن معادله هر دو ابرصفحه میگردد. برای حل این دو معادله کمینهسازی نیز میتوان از مضربهای لاگرانژ استفاده کرد که در این صورت مقادیر و برای هر یک از ابرصفحات (با در نظر گرفتن و که یک بردار با طول مناسب و درایههای با مقدار یک میباشد) طبق (10) و (11) محاسبه میگردد. یادآوری این نکته نیز ضروری است که در این دو مورد احتیاجی به استفاده از راه حلهای برنامهنویسی غیر خطی نمیباشد
(8)
(9)
(10)
(11)
2-5 الگوریتم ماشین بردار پشتیبان دوقلوی مربعات حداقلی فازی
در این بخش میخواهیم راهکار ارائهشده در مورد کاربرد بنیادی مفهوم فازی را در الگوریتم LSTSVM (یعنی بیان فازی دو ابرصفحه مورد استفاده در الگوریتم F-LSTSVM و روند بهینهسازی معادلات آن) بیان کنیم. بنابراین به دنبال بیان مفهوم ابرصفحه فازی و تمایز بین دادههای کلاس هدف و دیگر کلاس به صورت فازی هستیم. تمام پارامترهای مورد استفاده در این مدل فازی هستند، حتی مؤلفههای موجود در بردار به صورت اعداد فازی بیان میشوند. بیان این نکته نیز ضروری است که تمام پارامترهای مورد استفاده در این مدل با تابع عضویت مثلثی بیان شدهاند.
در الگوریتم سلیمی و همکاران [8] تمام مؤلفههای موجود در بردار وزنی و ترم بایاس که در معادله ابرصفحه مورد استفاده قرار میگیرند به صورت عدد فازی مثلثی متقارن بیان شده است (هرچند که میتوان از سایر توابع عضویت نیز استفاده کرد). بردار وزنی فازی و ترم بایاس فازی را در نظر بگیرید. یک بردار وزنی فازی میباشد که هر مؤلفه از آن یک عدد فازی است که به
[1] این مقاله در تاریخ 10 اردیبهشت ماه 1399 دریافت و در تاریخ 7 تیر ماه 1400 بازنگری شد.
جواد سلیمی سرتختی (نویسنده مسئول)، گروه مهندسی کامپیوتر، دانشکده برق و کامپیوتر، دانشگاه کاشان، ایران، (email: salimi@kashanu.ac.ir).
سلمان گلی بیدگلی، گروه مهندسی کامپیوتر، دانشکده برق و کامپیوتر، دانشگاه کاشان، ایران، (email: salmangoli@kashanu.ac.ir).
[2] . Big Data
[3] . Stream Data
[4] . Support Vector Machine
[5] . Least Squares Support Vector Machine
(14)
شکل بیان میشوند. به بیان دیگر برای بردار وزنی ما دو بردار و خواهیم داشت که یکی مراکز و دیگری پهنای اعداد فازی مثلثی را بیان میکنند. در این صورت ابرصفحه فازی توسط تابع عضویت زیر تعریف میگردد [8]
(12)
که است هنگامی که باشد. حال اگر با توجه به تابع عضویت یک ابرصفحه فازی بخواهیم (15) را بازنویسی کنیم خواهیم داشت
(13)
در این رابطه به عنوان حاشیه فازی1 در نظر گرفته شده است (همانند حاشیهای که در شکل یک قرار دارد تنها با این تفاوت که به صورت فازی تعریف میگردد) و در اینجا یک عدد فازی به مرکز صفر و پهنای میباشد. در این رابطه ترم میزان ابهام2 مدل را بیان میکند و این بدان معناست که ابهام بیشتر inexactness پاسخ را افزایش میدهد. در معادله (27)، وظیفه تنظیم ابهام را بر عهده دارد. همچنین بیانگر میزان خطای مربعات حداقل میباشد که در آن بردار درجه عضویت هر نمونه مثبت و بردار ضرایب slack (که میزان انحراف از قیدهای معادله را بیان میکنند) را بیان میکنند. میزان تأثیر خطای مربعات حداقل در معادله ابرصفحه مربوط به کلاس مثبت توسط ضریب 1C تنظیم میگردد.
با حل معادله ابرصفحه (13)، (14) را خواهیم داشت. حال که تمام پارامترها مقادیرشان مشخص شد، تابع عضویت ابرصفحه فازی بهینه برای نمونههای مثبت همانند زیر به دست میآید
(15)
همین روند را میتوان برای ابرصفحه دوم نیز به کار برد.
3- کارهای پیشین انجامشده در زمینه الگوریتم افزایشی ماشینهای بردار پشتیبان
تا کنون الگوریتمهای زیادی در زمینه یادگیری افزایشی ارائه شده است. لوزینگ و همکاران [9] در سال 2018 اغلب الگوریتمهای معروف افزایشی را بر روی طیف وسیع و متنوعی از دیتاستها اجرا کردند و نشان دادند که نسخههای افزایشی الگوریتم ماشین بردار پشتیبان اغلب بیشترین دقت را دارند. نسخههای متعدد یادگیری افزایشی با استفاده از الگوریتم ماشین بردار پشتیبان در سالهای اخیر ارائه شده است. شاید اولین ایده در زمینه تبدیل الگوریتم ماشین بردار پشتیبان به نسخه افزایشی آن، در نظر گرفتن نقاط و دادههای بردار پشتیبان از مراحل قبل در کنار دادههای ورودی جدید باشد که کار یادگیری بر روی آنها انجام میشود [10] و [11]. نسخه افزایشی ماشین بردار پشتیبان ارائهشده در [11] یک راه حل دقیق برای ماشین بردار پشتیبان برخط میباشد که با اضافهکردن یا حذف یک نمونه در هر مرحله، کار را انجام میدهد. گلوگاه الگوریتم ارائهشده پیچیدگی محاسباتی است. تا کنون نسخههای متعددی از الگوریتم ماشین بردار پشتیبان ارائه شده که یکی از این نسخهها ماشین بردار پشتیبان دوقلوست. کمچندانی و همکاران نسخه افزایشی ماشین بردار پشتیبان دوقلو را ارائه کردند که از مفهوم بردار حاشیه و بردار خطا برای انتخاب نمونه بعدی بهره میبردند [10]. در سال 2014 یونه و همکاران یک نسخه سریع از الگوریتم افزایشی ماشین بردار پشتیبان دوقلو ارائه کردند که از استراتژی مبتنی بر فاصله برای انتخاب نمونه بعدی استفاده میکرد [12]. در پژوهشی دیگر در سال 2016 علمدار و همکاران، الگوریتم افزایشی ماشین بردار پشتیبان مستقل دوقلو را ارائه کردند که از متد نیوتن اصلاحیافته برای ساخت یک تابع تصمیم بر اساس دادههای رؤیتشده تا کنون استفاده میکرد [13]. در سالهای بعد، فونگ و همکاران استراتژی به روز رسانی مدل در این الگوریتم را بر اساس یک پنجره زمانی تغییر دادند [14]. همچنین تویت و همکاران در پژوهشی دیگر این استراتژی را بر اساس کاهش ضرایب قرار داده بودند [15]. در سال 2020 الکساندر و همکاران یک نسخه افزایشی فازی از الگوریتم ماشین بردار پشتیبان دوقلو ارائه کردند [16]. آقای ژو و همکاران در سال 2019 نسخه جدیدی از الگوریتم افزایشی مبتنی بر ماشین بردار پشتیبان ارائه کردند که انتخاب نمونهها در آن بر اساس مدل مارکوف انجام میشد [17]. آنها نشان دادند که الگوریتمشان در کاربردهای دستهبندی، کمتر دچار خطا میشود.
بررسیهای انجامشده در ادامه تا حدود زیادی منطبق بر مقاله مروری لاوال [18] است. متدهای ارائهشده برای رویکرد افزایشی در ماشینهای بردار پشتیبان به دو دسته برخط و شبه برخط تقسیم میشوند [19] و [20]. متدهای برخط دادههای جریانی را به صورت تکی در هر لحظه پردازش میکند و مطمئن میشود که شرایط لازم برای بردارهای پشتیبان در مدل تغییری نکرده باشد. در مدل شبه برخط نمونه دادههای جریانی به
Input: : new sample at time , : decision function at Output: : updated decision function at Definitions: : coefficient of the th sample at , : margin support vector set at 1. Begin 2. Compute 3. If then and go to step 10 4. Else 5. Initialize for 6. Compute for all 7. Increment to its largest value while maintaining the KKT optimality conditions on all previously seen samples 8. Check if one of the following conditions occurs: 9. , and I. If then II. Else if then III. Else if any become part of , due to the change in their corresponding , then update and accordingly 10. End |
شکل 1: متد کاونبرگ و همکارش [21].
صورت دستهای3 نمونههای جدید را پردازش میکند. در این متد زمانی که تصمیم به اجرای دوباره الگوریتم SVM شد، این الگوریتم بر روی دادههای جدید به همراه بردارهای پشتیبانی که تا کنون به دست آمدهاند آموزش خواهد دید.
3-1 متدهای برخط SVM افزایشی
اولین الگوریتم افزایشی SVM توسط کاونبرگ و همکارش پیشنهاد شد [21] و در ادامه نسخههای متفاوتی از این کار توسط محققان ارائه گردید که به عنوان نمونه میتوان به [22] و [23] اشاره کرد. در تمامی این کارها زمانی که نمونهای جدید همانند دریافت میشود، ابتدا را محاسبه میکنند تا بر اساس آن تشخیص دهند آیا نمونه جدید میتواند منجر به بهبود دستهبند جاری شود یا خیر. در این رابطه تابع همان دستهبند SVM است. اگر باشد نمونه جدید یک نمونه مفید برای دستهبند خواهد بود. بنابراین ضریب لاگرانژ این نمونه را برابر صفر قرار داده و با افزایش تدریجی آن مقدار بهینه SVM را به دست میآورد. الگوریتم دقیق این روش در شکل 1 آورده شده که در آن مجموعه بردارهای پشتیبان و ضریب لاگرانژ است.
در کاری دیگر، نسخه تککلاسی SVM افزایشی به نسخه چندکلاسی آن تبدیل شد که البته بار محاسباتی آن به مراتب بیشتر شده است [24]. بوخاروبا و همکارانش همین نسخه از SVM افزایشی را برای حالتی که دادههای بدون برچسب فراوانی وجود دارد توسعه دادند [25]. همچنین چن و همکارانش کاری مشابه و با استفاده از اصل انتقال4 ارائه کردند [26]. در کاری دیگر در زمینه متدهای برخط، رای و همکارانش الگوریتمی را با استفاده از اصل حداقل توپ محصور5 به منظور یادگیری و به روز رسانی SVM پیشنهاد دادند [27].
Input : new samples at time , : margin support vector set at , : bounded support vector set at , : decision function at Output: : updated decision function, : margin support vector set at , : bounded support vector set at Definitions: : coefficient of the th sample at , 1. Begin 2. Compute , 3. Using as input, solve for the problem of (11) in [] to obtain for all 4. Compute by solving the problem of (12) in [] 5. Compute 6. Compute 7. Discard all for which 8. Return 9. End |
شکل 2: متد ساید و همکارانش [28].
3-2 متدهای شبه برخط SVM افزایشی
اولین کار در این زمینه توسط ساید و همکارانش ارائه شد [28]. در این الگوریتم، دادهها در دستههایی با اندازههای ثابت پردازش میشوند. اولین دسته از دادهها در زمان که شامل همه نمونهها تا آن لحظه میگردد، به عنوان ورودی الگوریتم SVM استفاده میشود. سپس الگوریتم، همه دادههای مرحله قبل را به جز بردارهای پشتیبان از مجموعه حذف میکند. زمانی که میخواهد الگوریتم را بر روی دادههای موجود در دسته بعدی اعمال کند، این دادهها را با مجموعه بردارهای پشتیبان موجود در دسته قبل ترکیب میکند و بر اساس مجموع آنها کار یادگیری انجام میشود. این کار در هر زمان که دسته جدیدی از دادهها آماده شود تکرار میگردد. شکل 2 این الگوریتم را نمایش میدهد. اما این متد نمیتواند زمانی که توزیع دادهها تغییر میکند به درستی عمل کند. دلیل این امر نیز حضور بردارهای پشتیبان متعلق به مراحل قبلی در مراحل بعدی میباشد. معضل دیگر این الگوریتم، کنارگذاشتن همه دادهها به جز بردارهای ماشین است که ممکن است اقدام درستی نباشد و دادهای که در این مرحله بردار پشتیبان نبوده است با حضور دادههای مراحل بعد یکی از بردارهای پشتیبان باشد. معضل دیگر این الگوریتم، ذخیرهسازی همه بردارهای پشتیبان مراحل قبلی است که ممکن است در مراحل بعد دیگر بردار پشتیبان نباشند. برای حل معضل آخر در برخی روشها، بردارهای پشتیبان به دست آمده در هر مرحله از نظر وابستگی خطی بین خودشان با توجه به مجموعه ویژگیها بررسی میشوند [29] و [30]. اگر این وابستگی وجود داشت بهتر است تنها بردارهایی نگهداری شوند که به عنوان تابعی از سایرین نباشند.
برای حل مشکل دوم از ترکیب SVM با تکنیکهای بهینهسازی همانند PSO استفاده میکنند تا بهترین مقادیر پارامترها در هر مرحله محاسبه شود [31]. همچنین برای حل معضل نخست، دومینکنی و همکارانش الگوریتم ساید [28] را توسعه دادند [32]. آنها بدین گونه عمل میکنند که در هر لحظه که دسته داده جدیدی دریافت میشود، الگوریتم SVM در قالب دستهبند متفاوت با توجه به دسته اخیر به روز رسانی میشود. به عبارت دیگر در لحظه ما مدل ایجادشده از SVM داریم که به ترتیب شامل همه دسته اخیر، دسته اخیر و
Step 1. Calculate initial and TWSVM(A) ,TWSVM(B) Step 2. Calculate distance threshold and
Step 3. Add the new training sample set and , and establish the dynamic training sample set and
Step 4. Incremental Learning
Step 5. If there will be a new training sample set in the future, we repeat Step 2, Step 3 and Step 4. |
شکل 3: متد هو و ژانگ [12].
یک دسته اخیر میباشند. هر ورودی جدید که دریافت میشود یک دستهبند ایجادشده از بین میرود و یک دستهبند جدید ایجاد میگردد.
برای الگوریتم TSVM نیز چندین نسخه افزایشی ارائه شده که در ادامه به مرور برخی از آنها میپردازیم. الساندرو و همکاران یک نسخه افزایشی از TSVM با ترکیب آن با مفاهیم فازی ارائه دادهاند [33].
آنها بدین گونه عمل میکنند که به هر نمونه ورودی یک درجه اهمیت منتسب میکنند و سپس با استفاده از ابرصفحههای فازیای که ارائه دادهاند، این نمونهها را دستهبندی میکنند. میزان اهمیت نمونههای جدید بیشتر و میزان اهمیت نمونههای قدیمی رفتهرفته کمتر میشود. الگوریتم آنها به صورت شبه برخط عمل میکند و آنها الگوریتمشان را برای حالت چندکلاسی نیز گسترش دادند.
در مطالعهای دیگر خمچندانی و همکاران یک مدل ساده از TSVM افزایشی ارائه دادند که بسیار شبیه به الگوریتم ساید [28] در بخش 2-1-2 عمل میکند [10]. آنها در هر مرحله علاوه بر دادههای دسته جدید، دادههای متعلق به بردارهای پشتیبان مراحل قبل و نیز دادههایی که در باند هر ابرصفحه قرار میگیرند را به الگوریتم TSVM در آن مرحله میدهند و سپس بر اساس آن کار دستهبندی را انجام میدهند. همچنین هو و ژانگ در سال 2014 میلادی یک الگوریتم سریع افزایشی مبتنی بر TSVM ارائه دادند [12]. آنها با استفاده از فاصله نمونههای موجود در هر دسته با هر یک از ابرصفحهها، وزندهی به دستههای دادهها را انجام میدهند و سپس بر اساس آن کار یادگیری اتفاق میافتد. شکل 3 متد آنها را نمایش میدهد. با توجه به کارهای ارائهشده در این بخش و با توجه به دانش نویسندگان، هیچ کاری تا کنون برای ارائه نسخه افزایشی الگوریتم FLSTSVM ارائه نشده است. این پژوهش به آن پرداخته و ایده جدیدی حتی نسبت به سایر رویکردهای معرفیشده ارائه میدهد.
4- الگوریتم پیشنهادی FLSTSVM افزایشی
همان گونه که در بخش 2 به طور کامل توضیح داده شد، یک الگوریتم افزایشی باید در خصوص نحوه به روز رسانی دستهبند ایجادشده با توجه به جریان دادهها و نمونههای ورودی جدید تصمیم بگیرد. ممکن است این تصمیم بر اساس هر نمونه باشد (یعنی برخط) و یا بر اساس تعداد ثابتی از نمونههای دریافتی جدید باشد (یعنی شبه برخط). در این پژوهش دو الگوریتم افزایشی برای هر دو نوع برخط و شبه برخط بر اساس الگوریتم جدید FLSTSVM ارائه شده است. در ابتدا الگوریتم مورد نظر برای حالت برخط ارائه میشود.
الگوریتم برخط ارائهشده بر مبنای الگوریتم مربعات حداقلی ماشینهای بردار پشتیبان فازی است که اخیراً ارائه شده است [8]. دلایل انتخاب و بهبود این الگوریتم عبارت است از: 1) الگوریتم SVM از نظر دقت، عملکرد بسیار خوبی دارد. 2) نسخه TSVM از نظر دقت و سرعت از الگوریتم SVM در بسیاری از موارد بهتر عمل میکند. 3) نسخه LSTSVM از نظر سرعت تقریباً سرعتی تا 8 برابر نسخه اصلی الگوریتم ماشین بردار پشتیبان دارد. 4) نسخه FLSTSVM علاوه بر بهبود دقت نسبت به LSTSVM به دلیل استفاده از مفهوم فازی در آن بسیار مناسب یادگیری دنبالهای است که در آن دادهها به صورت جریانی تولید میشوند. به عنوان مثال، در برخی از کاربردها میخواهیم درجه اهمیت نمونههای اخیر بیشتر از نمونههای در گذشته دور باشد. در این موارد ما میتوانیم از یک تابع عضویت فازی که بر اساس زمان طراحی شده است استفاده کنیم که در این صورت این تابع میتواند بر اساس زمان، به هر نمونه یک درجه عضویت اختصاص دهد. در ادامه این الگوریتم توضیح داده میشود.
4-1 نسخه برخط الگوریتم افزایشی FLSTSVM
در الگوریتم برخط ارائهشده سعی بر آن است الگوریتم FLSTSVM به نحوی تغییر یابد که بتوان از دادههای جریانی که یکی از چالشهای موجود در بسیاری از کاربردها همانند اینترنت اشیا است، به طور بهینه برای یادگیری افزایشی استفاده نمود. فرض میکنیم در یادگیری افزایشی تا لحظه ام دادههای را دریافت کردهایم. اگر تنها بخواهیم بر اساس همین دادهها عمل کنیم به راحتی میتوانیم الگوریتم FLSTSVM را بر روی آنها اعمال کرده و مدل مورد نظر را ایجاد کنیم. در ادامه نیز با دریافت هر نمونه میتوانیم از مدل ساختهشده به منظور پیشبینی استفاده نماییم. اما مشکل جایی است که میخواهیم نمونههای بعدی را نیز در ساخت مدل مشارکت دهیم. اما اگر بخواهیم با دریافت هر نمونه، کل الگوریتم را از ابتدا اجرا کنیم از نظر زمانی و توان محاسباتی با مشکل مواجه خواهیم شد. ضمناً همه نمونههایی که در آینده دریافت میکنیم بااهمیت نیستند و شاید در مدل تأثیر چندانی نداشته باشند و بنابراین اهمیت نمونهها متفاوت خواهد بود. حال ما باید به سه نکته توجه کنیم: 1) چگونه میتوانیم اهمیت نمونههای مختلف را به دست آوریم؟ 2) چگونه میتوانیم این اهمیت را در الگوریتم دخالت دهیم؟ 3) چگونه میتوانیم بدون نیاز به این که تمامی نمونههای قبلی را اجرا کنیم مدل جدید را بسازیم؟ در پاسخ به سؤال اول، 3 معیار مهم ارائه کردهایم که ترکیب آنها، میزان اهمیت نمونه جدید را بیان میکند. اگر مدل ساختهشده تا لحظه را با و دادههای تا این لحظه را با نمایش دهیم آن گاه را به عنوان میزان اهمیت نمونه تعریف میکنیم. این میزان اهمیت بر اساس سه عامل محاسبه میشود: فاصله تا ابرصفحهها، تراکم و شباهت نمونه جدید. چگالی نشاندهنده نزدیکی نمونهها است. چگالی بالا نشاندهنده اطلاعات اضافی نمونهها و محتوای اطلاعاتی حاشیهای است و برعکس. میزان اطلاعات مربوط به چگالی در راهکار ارائهشده به صورت (16) محاسبه میشود
(16)
Incremental FLSTSVM Input: Model , Sample , Output: Model , Compute using: • • • compute and If • Else • All support vectors in • • Apply FLSTSVM on and obtain End |
شکل 4: نسخه پیشنهادی برخط الگوریتم افزایشی FLSTSVM.
جدول 1: توصف ویژگیهای شش بانک داده استفادهشده در الگوریتم پیشنهادی.
#Samples | #Classes | #Features | Missing Value | Dataset |
270 | 2 | 13 | No | Heart-Statlog |
303 | 2 | 14 | No | Heart-C |
354 | 2 | 34 | No | Ionosphere |
445 | 2 | 16 | Yes | Votes |
690 | 2 | 14 | Yes | Australian |
653 | 2 | 14 | No | Japanese Credit |
که در آن برچسب پیشبینی شده توسط مدل ، مجموعه بردار پشتیبان با برچسب در و cosdise معیار فاصله cosine است. از شباهت برای اطمینان از تنوع نمونهها استفاده شده است. این نشان میدهد که باید با دیگر نمونهها در متفاوت باشد تا دارای اهمیت باشد. بنابراین اطلاعات مفید را میتوان بر اساس تشابه به صورت (17) محاسبه کرد
(17)
معیار سوم میزان فاصله نمونه جدید با برچسب پیشبینی شده از دو ابرصفحه موجود در مدل است که فاصله آن با ابرصفحه متعلق به کلاس ، و با ابرصفحه متعلق به کلاس مقابل یعنی برابر خواهد بود. نهایتاً این سه قسمت با وزنهای گوناگون برای محاسبه در (18) ترکیب میشوند
(18)
در پاسخ به سؤال دوم که چگونه میزان اهمیت نمونه جدید را در الگوریتم تأثیر دهیم نیز این گونه عمل میکنیم که با انتخاب مناسب ، ،
و یعنی از به
شکل 5: نسخه پیشنهادی شبه برخط الگوریتم افزایشی FLSTSVM.
عنوان یا همان درجه عضویت نمونه جدید در الگوریتم FLSTSVM استفاده میکنیم.
در پاسخ به سؤال سوم نیز بدین گونه عمل میکنیم: برای جلوگیری از تکرار عملیات یادگیری بر روی دادههای قدیمی در صورتی که میزان اهمیت نمونه جدید از یک مقدار کمتر باشد، آن را حذف میکنیم و در غیر این صورت این نمونه در کنار بردارهای پشتیبان به دست آمده از مدل و دادههای قدیمی قرار گرفته و با استفاده از این مجموعه کار یادگیری مجدداً انجام میشود. الگوریتم بهبودیافته به صورت شبهکد شکل 4 ارائه شده است.
4-2 نسخه شبه برخط الگوریتم افزایشی FLSTSVM
در نسخه شبه برخط بر اساس تعداد ثابتی از نمونههای دریافتی جدید ایجاد میشود. یعنی به جای یک نمونه برای یک دسته از نمونهها باید تصمیمگیری کنیم و بر اساس آن، الگوریتم خود را به روز رسانی نماییم. بدین منظور ما در هر بار به روز رسانی از نمونههای موجود در سریهای قبل استفاده میکنیم: 1) تمامی بردارهای پشتیبان مراحل قبل، 2) نمونههایی که در باند هر یک از ابرصفحهها (نمونههای دارای خطا) قرار میگیرند و 3) نمونههایی که بر اساس (18) دارای اطلاعاتی بیش از یک حد آستانه باشند. این حد آستانه با آزمون و خطا تعیین میشود.
الگوریتم شبه برخط ارائهشده برای نسخه افزایشی FLSTSVM در شکل 5 آورده شده است.
5- نتایج آزمایشگاهی
در این بخش ابتدا به معرفی بانکهای داده مورد استفاده در این مطالعه میپردازیم و در ادامه معیارهای ارزیابی دستهبند معرفی و نهایتاً نتایج حاصل از اعمال روش پیشنهادی بر روی بانکهای داده معرفیشده به تفصیل بیان میگردد.
5-1 بانک داده
برای بررسی قدرت و صحت الگوریتم پیشنهادی از 6 بانک داده مربوط به دو نوع متفاوت از بیماریهای قلب، دیابت، نارسایی کبد و سرطان سینه استفاده شده است. جدول 1 مشخصات کلی شش بانک داده را بیان میکند. هر شش بانک داده متعلق به مخزن UCI میباشند.
5-2 نتایج اعمال الگوریتم پیشنهادی بر روی چهار بانک داده
در این بخش نسخه افزایشی FLSTSVM6، نسخه افزایشی TWSVM و نسخه افزایشی SVM، با الگوریتمهای FLSTSVM،
[1] . Fuzzy Margin
[2] . Vagueness
[3] . Batch
[4] . Principle of Transduction
[5] . Minimum Enclosing Ball
[6] . Inc-FLSTSVM
جدول 2: مقایسه صحت الگوریتم پیشنهادی Inc-FLSTSVM با سایر روشها.
Algorithms |
| |||||
Inc-FLSTSVM | FLSTSVM | SVM | Inc-SVM | TWSVM | Inc-TWSVM | Datasets |
42/303/90 | 18/370/88 | 44/470/83 | 02/670/83 | 52/481/84 | 70/407/84 | Heart-Statlog |
15/460/89 | 87/262/87 | 27/544/84 | 62/548/82 | 71/514/84 | 53/580/83 | Heart-C |
61/387/90 | 41/383/89 | 02/674/87 | 62/588/86 | 42/646/87 | 70/705/86 | Ionosphere |
70/295/98 | 62/469/98 | 66/287/95 | 71/240/95 | 93/209/96 | 47/331/96 | Votes |
84/203/93 | 50/491/92 | 67/251/85 | 67/251/85 | 83/294/85 | 67/296/86 | Australian |
33/355/90 | 62/385/88 | 96/237/86 | 04/452/86 | 04/442/86 | 06/468/86 | Japanese Credit |
جدول 3: مقایسه زمان اجرای الگوریتم Inc-FLSTSVM با سایر روشها بر حسب ثانیه.
Algorithms |
| |||||
Inc-FLSTSVM | FLSTSVM | SVM | Inc-SVM | TWSVM | Inc-TWSVM | Datasets |
980/0 | 045/0 | 96/4 | 70/53 | 84/2 | 50/23 | Heart-Statlog |
75/1 | 070/0 | 05/5 | 47/67 | 93/2 | 16/32 | Heart-C |
32/2 | 100/0 | 47/6 | 84/80 | 74/3 | 17/41 | Ionosphere |
51/2 | 110/0 | 52/6 | 65/81 | 76/3 | 92/48 | Votes |
28/4 | 190/0 | 01/9 | 10/105 | 97/5 | 75/73 | Australian |
90/2 | 104/0 | 49/6 | 95/131 | 77/3 | 12/68 | Japanese Credit |
TWSVM و SVM مقایسه میشوند و نشان داده میشود که الگوریتم پیشنهادی دارای دقت بهتری نسبت به سایر الگوریتمها است. نتایج مربوط به الگوریتمهای TWSVM، SVM و نسخههای افزایشی آنها
از [10] اخذ گردیده است. همچنین دو الگوریتم FLSTSVM و Inc-FLSTSVM در این پژوهش با شرایطی مشابه با [10] پیادهسازی شده تا شرایطی عادلانه برای مقایسه وجود داشته باشد. جدول 2 نتایج حاصل از الگوریتمهای مذکور را نشان میدهد. همان گونه که مشاهده میشود الگوریتم پیشنهادی Inc-FLSTSVM در همه مجموعه دادهها نتایج بهتری از نظر صحت1 نسبت به سایر الگوریتمها دارد.
با مقایسه الگوریتمهای افزایشی موجود از نظر زمان اجرا با یکدیگر، به وضوح الگوریتم افزایشی Inc-FLSTSVM زمان اجرای کمتری را به خود اختصاص میدهد. اما باید این نکته را اضافه کنیم که تمامی نسخههای افزایشی الگوریتمها از نسخه غیر افزایشی آنها زمان اجرای به مراتب بیشتری دارند. این امر هم به آن دلیل است که عموماً در یک الگوریتم افزایشی یک مدل ممکن است دهها و بلکه صدها و هزاران بار اجرا شود که قاعدتاً منجر به افزایش زمان خواهد شد. این مقایسهها در جدول 3 آورده شده است. اما نکته قابل توجه این است که نسخههای افزایشی در مقابل حالت بدتری از زمان اجرا مطرح میشوند و آن هم حالتی است که ما بخواهیم به ازای هر نمونه دریافتی جدید مدل را مجدد آموزش دهیم. همچنین شکل 6 روش پیشنهادی را با سایر روشها بر اساس امتیاز 1F مقایسه میکند که طبق آن روش پیشنهادی تقریباً بر روی همه دیتاستها وضعیت بهتری دارد.
در کاربردی دیگر و به منظور بررسی صحت و دقت الگوریتم ارائهشده از مجموعه دادههای مربوط به فعالیتهای روزمره زندگی (ADL) استفاده شده است [34]. مجموعه دادههای موجود شامل 5 دیتاست است که هر کدام از آنها در شرایط متفاوتی تولید شدهاند. این تفاوت مربوط به مکان زندگی، تعداد سنسورها و زمان مانیتورینگ افراد است. طبق [35] اطلاعات سنسورها در یک دوره زمانی مشخص اخذ شده است. برای یکسانسازی زمانها در این پژوهش، ما یک مقطع زمانی تعریف میکنیم که مجموعه داده شامل اطلاعات همه سنسورها در همه مقاطع زمانی هستند. اطلاعات سنسورها در مقطع زمانی را میتوان با بردار نمایش داد. خروجی این سیستم باید تشخیص فعالیت متناسب با اطلاعات سنسورها در لحظه باشد که با نمایش داده میشود. در این سیستم حداکثر 12 فعالیت خواهیم داشت و بنابراین وظیفه الگوریتم دستهبند تشخیص این فعالیت است. جدول 4 تعداد فعالیتها را در هر یک از 6 دیتاست نمایش میدهد.
دادههای جریانی خام تولیدشده با استفاده از سنسورها میتواند به صورت مستقیم و یا با تغییرات و انجام پردازشهایی مورد استفاده قرار گیرد. به منظور تقویت فضای ویژگیها در این پژوهش، سه نوع نمایش برای دادههای سنسورها در نظر گرفته شده که نتایج نیز بر اساس همین سه مورد میباشند: 1) نمایش خام سنسور: در این نوع نمایش وضعیت سنسور زمانی که فعال است برابر یک و در غیر این صورت برابر صفر است. 2) نمایش نقطه تغییر: در این نوع نمایش، زمانی که سنسور تغییر وضعیت میدهد ویژگی برابر یک و در غیر این صورت برابر صفر خواهد بود. 3) نمایش آخرین سنسور: در این نوع نمایش همواره مقدار ویژگی آخرین سنسوری که فعال شده است برابر یک و برای سایرین برابر صفر خواهد بود. با توجه به این نوع نمایشها روش پیشنهادی به همراه چندین روش شناختهشده دیگر بر روی مجموعه دادهها اجرا شدهاند که نتایج آن در جدول 5 آورده شده است. لازم به ذکر است که به دلیل نامتوازنبودن مجموعه دادهها، برای مقایسه نتایج از معیار استفاده شده است.
6- نتیجهگیری
در این مقاله یک الگوریتم افزایشی برای الگوریتم جدید ماشین بردار پشتیبان دوقلوی مربعات حداقلی فازی ارائه شد. الگوریتم پیشنهادی شامل دو نسخه برخط و شبه برخط است. در ارائه الگوریتم جدید به دنبال تعیین میزان اطلاعات هر نمونه جدید بودیم که این امر در این مقاله با استفاده از چندین معیار از جمله میزان چگالی، میزان مشابهت و میزان
[1] . Accuracy
شکل 6: مقایسه الگوریتم پیشنهادی با سایر روشها بر اساس امتیاز 1F.
جدول 4: درصد تعداد فعالیتها در دیتاستهای مربوط.
Activity | KasterenA | KasterenB | KasterenC | OrdonezA | OrdonezB |
Leaving | 74/49 | 36/54 | 27/46 | 32/8 | 41/17 |
Toileting | 65/0 | 27/0 | 62/0 | 76/0 | 55/0 |
Showering | 70/0 | 6/0 | 6/0 | 54/0 | 24/0 |
Sleeping | 42/33 | 53/33 | 46/28 | 1/39 | 58/35 |
Breakfast | 23/0 | 52/0 | 62/0 | 63/0 | 5/0 |
Dinner | 0/1 | 42/0 | 26/1 | 0 | 38/0 |
Drink | 12/14 | 7/0 | 11/0 | 0 | 0 |
Idle/Unlabeled | 0 | 12/10 | 97/21 | 61/5 | 73/11 |
Lunch | 0 | 0 | 0 | 59/1 | 3/1 |
Snack | 0 | 0 | 0 | 5/0 | 33/1 |
Spare time/TV | 0 | 0 | 0 | 7/42 | 98/28 |
Grooming | 0 | 0 | 0 | 73/0 | 42/1 |
جدول 5: مقایسه الگوریتمهای گوناگون بر روی مجموعه دادههای معرفیشده. نتایج بر اساس F-Measure و به صورت درصد بیان شدهاند. نتایج سایر الگوریتمها از [35] آورده شده است.
Inc-FLSTSVM | MLP | k-NN | SVM | نوع نمایش دادهها | مجموعه داده |
587 | 5111 | 5511 | 5410 | خام | KasterenA |
598 | 5011 | 5410 | 5211 | نقطه تغییر | |
629 | 6111 | 6111 | 6111 | آخرین سنسور | |
599 | 5010 | 5411 | 5710 | خام | KasterenB |
607 | 535 | 586 | 566 | نقطه تغییر | |
656 | 6512 | 6512 | 6512 | آخرین سنسور | |
538 | 5010 | 4810 | 499 | خام | KasterenC |
498 | 478 | 467 | 469 | نقطه تغییر | |
7110 | 677 | 677 | 677 | آخرین سنسور | |
828 | 777 | 775 | 787 | خام | OrdonezA |
556 | 527 | 537 | 537 | نقطه تغییر | |
725 | 678 | 658 | 668 | آخرین سنسور | |
738 | 686 | 697 | 697 | خام | OrdonezB |
576 | 507 | 527 | 505 | نقطه تغییر | |
779 | 727 | 737 | 737 | آخرین سنسور |
نزدیکی به ابرصفحهها اندازهگیری شد. الگوریتم ارائهشده بر روی انواع مجموعه دادهها اجرا شد که نتایج آزمایشگاهی از کارایی بالای این الگوریتم نسبت به نمونههای مشابه آن در نسخههای متفاوت الگوریتم SVM و همچنین سایر الگوریتمها حکایت دارد. الگوریتم ارائهشده به دلیل در نظر گرفتن مفاهیم فازی این قدرت را دارد که به نمونههای جدیدتر اهمیت بیشتری بدهد. همچنین به دلیل وجود دو ابرصفحه و نیز معادلات خطی در این الگوریتم، سرعت آن نسبت به الگوریتمهای SVM و TWSVM به مراتب بیشتر است.
مراجع
[1] D. Bhattacharya and M. Mitra, Analytics on Big Fast Data Using Real Time Stream Data Processing Prchitecture, EMC Corporation, 2013.
[2] B. E. Boser, I. M. Guyon, and V. N. Vapnik, "A training algorithm for optimal margin classifiers," in Proc. of the 5th Annual Workshop on Computational Learning Theory, pp. 144-152, Pittsburgh, PA, USA, 27-29 Jul. 1992.
[3] R. T. Rockafellar, "Lagrange multipliers and optimality," SIAM Review, vol. 35, no. 2, pp. 183-238, 1993.
[4] J. A. Suykens and J. Vandewalle, "Least squares support vector machine classifiers," Neural Processing Letters, vol. 9, no. 3, pp. 293-300, Jun. 1999.
[5] J. A. K. Suykens, T. Van. Gestel, J. De Brabanter, B. De Moor, and J, Vandewalle, Least Squares Support Vector Machines, World Scientific, 2002.
[6] R. Khemchandani and S. Chandra, "Twin support vector machines for pattern classification," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 29, no. 5, pp. 905-910, May 2007.
[7] M. A. Kumar and M. Gopal, "Least squares twin support vector machines for pattern classification," Expert Systems with Applications, vol. 36, no. 4, pp. 7535-7543, May 2009.
[8] J. S. Sartakhti, H. Afrabandpey, and N. Ghadiri, "Fuzzy least squares twin support vector machines," Engineering Applications of Artificial Intelligence, vol. 85, pp. 402-409, Oct. 2019.
[9] V. Losing, B. Hammer, and H. Wersing, "Incremental on-line learning: a review and comparison of state of the art algorithms," Neurocomputing, vol. 275, pp. 1261-1274, Jan. 2018.
[10] R. KhemchandaniJayadeva, and S. Chandra, "Incremental twin support vector machines," in Modeling, Computation and Optimization, in S. K. Neogy, A. K. Das, and R. B. Bapat (eds.), pp. 263-272, World Scientific, 2009.
[11] P. Mitra, C. A. Murthy and S. K. Pal, "Data condensation in large databases by incremental learning with support vector machines," in Proc.of 15th Int. Conf. on Pattern Recognition. ICPR'00, vol.2, pp. 708-711, , Barcelona, Spain, 3-7 Sept. 2000,
[12] Y. Hao and H. Zhang, "A fast incremental learning algorithm based on twin support vector machine," in Proc. IEEE 7th Int. Symp. on Computational Intelligence and Design, , vol. 2, pp. 92-95, Hangzhou, China, 13-14 Dec. 2014.
[13] F. Alamdar, S. Ghane, and A. Amiri, "On-line twin independent support vector machines," Neurocomputing, vol. 186, no. C, pp.
8-21, Apr. 2016.
[14] G. Fung and O. L. Mangasarian, "Incremental support vector machine classification," in Proc. of the SIAM Int. Conf. on Data Mining, pp. 247-260, Arlimgton, VA, USA, 11-13 Apr. 2002.
[15] A. Tveit, M. L. Hetland, and H. Engum, "Incremental and decremental proximal support vector classification using decay coefficients," in Proc. of the Int. Conf. on Data Warehousing and Knowledge Discovery, pp. 422-429, Prague, Czech Republic, 3-5 Sept. 2003.
[16] A. R. Mello, M. R. Stemmer, and A. L. Koerich, "Incremental and decremental fuzzy bounded twin support vector machine," Information Sciences, vol. 526, pp. 20-38, Jul. 2020.
[17] J. Xu, C. Xu, B. Zou, Y. Y. Tang, J. Peng, and X. You, "New incremental learning algorithm with support vector machines," IEEE Trans. on Systems, Man, and Cybernetics, Systems, vol. 49, no. 11, pp. 2230-2241, Nov. 2018.
[18] I. A. Lawal, "Incremental SVM learning," Studies in Big Data Learning from Data Streams in Evolving Environments, pp. 279-296, 2019.
[19] W. Xie, S. Uhlmann, S. Kiranyaz, and M. Gabbouj, "Incremental learning with support vector data description," in Proc. IEEE 22nd Int. Conf. on Pattern Recognition, pp. 3904-3909, Stockholm, Sweden, 24-28 Aug. 2014.
[20] Z. Zhu, X. Zhu, Y. F. Guo, and X. Xue, "Transfer incremental learning for pattern classification," in Proc. of the 19th ACM International Conf. on Information and Knowledge Management, pp. 1709-1712, Toronto, Canada, 26-30 Oct. 2010.
[21] G. Cauwenberghs and T. Poggio, "Incremental and decremental support vector machine learning," in Proc. of the 13th Int Conf. on Neural Information Processing Systems, pp. 388-394, Denver, CO, USA, 1-1 Jan. 2000.
[22] H. Duan, X. Shao, W. Hou, G. He, and Q. Zeng, "An incremental learning algorithm for Lagrangian support vector machines," Pattern Recognition Letters, vol. 30, no. 15, pp. 1384-1391, 1 Nov. 2009.
[23] H. Galmeanu, L. M. Sasu, and R. Andonie, "Incremental and decremental SVM for regression," International J. of Computers Communications & Control, vol. 11, no. 6, pp. 755-775, Dec. 2016.
[24] H. Galmeanu and R. Andonie, "A multi-class incremental and decremental SVM approach using adaptive directed acyclic graphs," in Proc. IEEE Int Conf. on Adaptive and Intelligent Systems, pp. 114-119, Klagenfurt, Austria, 24-26 Sept. 2009.
[25] J. Wang, D. Yang, W. Jiang, and J. Zhou, "Semisupervised incremental support vector machine learning based on neighborhood kernel estimation," IEEE Trans. on Systems, Man, and Cybernetics: Systems, vol. 47, no. 10, pp. 2677-2687, Oct. 2017.
[26] M. S. Chen, T. Y. Ho, and D. Y. Huang, "Online transductive support vector machines for classification," in Proc. IEEE Int. Conf. on Information Security and Intelligent Control, pp. 258-261, Yunlin, Taiwan, 14-16 Aug. 2012.
[27] P. Rai, H. Daume, and S. Venkatasubramanian, "Streamed learning: one-pass SVMs," in Proc. 21st Int. Joint Conf. on Artificial Intelligence, pp. 1211-1216, Pasadena, CA, USA, 11-17 Jul. 2009.
[28] N. A. Syed, S. Huan, L. Kah, and K. Sung, "Incremental learning with support vector machines," in Proc. IEEE Int. Conf. on Data Mining, San Jose, CA, USA, 29 Nov.-2 Dec. 2001.
[29] F. Orabona, C. Castellini, B. Caputo, L. Jie, and G. Sandini, "On-line independent support vector machines," Pattern Recognition, vol. 43, no. 4, pp. 1402-1412, Apr. 2010.
[30] L. Ralaivola and F. d'Alche-Buc, "Incremental support vector machine learning: a local approach," in Proc. Int. Conf. on Artificial Neural Networks, pp. 322-330, Vienna, Austria, 21-25 Aug. 2001.
[31] M. N. Kapp, R. Sabourin, and P. Maupin, "Adaptive incremental learning with an ensemble of support vector machines," in Proc. IEEE 20th Int. Conf. on Pattern Recognition, pp. 4048-4051, Istanbul, Turkey, 23-26 Aug. 2010.
[32] C. Domeniconi and D. Gunopulos, "Incremental support vector machine construction," in Proc. IEEE Int. Conf. on Data Mining, pp. 589-592, San Jose, CA, USA, 29 Nov.-2 Dec. 2001.
[33] A. R. de Mello, M. R. Stemmer, and A. L. Koerich, Incremental and Decremental Fuzzy Bounded Twin Support Vector Machine, arXiv preprint arXiv:1907.09613, 2019.
[34] "Activities of Daily Living (ADLs) Recognition Using Binary Sensors Data Set," ed, 2013.
[35] F. Ordonez, P. De Toledo, and A. Sanchis, "Activity recognition using hybrid generative/discriminative models on home environments using binary sensors," Sensors, vol. 13, no. 5, pp. 5460-5477, 2013.
جواد سلیمی سرتختی در سال 1388 مدرك كارشناسي مهندسي کامپیوتر خود را از دانشگاه کاشان و در سال 1390 مدرك كارشناسي ارشد مهندسي نرمافزار خود را از دانشگاه تربیت مدرس دريافت نمود. از سال 1390 الي 1391 نامبرده به عنوان طراح ارشد در شرکت رایان اقتصاد نوین به كار مشغول بود و پس از آن به دوره دكتراي مهندسي کامپیوتر در دانشگاه صنعتی اصفهان وارد گرديد و در سال 1396 موفق به اخذ درجه دكترا در مهندسي كامپيوتر از دانشگاه مذكور گرديد. دكتر سلیمی از سال 1396 در دانشكده مهندسي كامپيوتر دانشگاه کاشان مشغول به فعاليت گرديد و اينك نيز عضو هيأت علمي اين دانشكده ميباشد. زمينههاي علمي مورد علاقه نامبرده متنوع بوده و شامل موضوعاتي مانند یادگیری ماشین، یادگیری عمیق، تئوری بازیها و طراحی مکانیزم و بلاکچین ميباشد.
سلمان گلی بیدگلی تحصيلات خود را در مقطع كارشناسي مهندسی کامپیوتر در سال 1385 در دانشگاه کاشان و كارشناسي ارشد و دكتري مهندسی كامپيوتر- معماری سیستم های کامپیوتری بهترتيب در سالهاي 1389 و 1396 از دانشگاه اصفهان به پايان رسانده است و هماكنون استادیار دانشكده مهندسي برق و كامپيوتر دانشگاه کاشان ميباشد. زمينههاي تحقيقاتي مورد علاقه ايشان عبارتند از: شبکه-های کامپیوتری، قابلیت اطمینان، اینترنت اشیا و بلاکچین میباشد.