Semi-Supervised Self-Training Classification Based on Neighborhood Construction
Subject Areas : electrical and computer engineeringmona emadi 1 , jafar tanha 2 , Mohammadebrahim Shiri 3 , Mehdi Hosseinzadeh Aghdam 4
1 - Islamic Azad University, Borujerd, Iran
2 -
3 - Borujerd Branch, Islamic Azad University, Borujerd, Iran
4 - University of Bonab
Keywords: Epsilon- neighborhood Algorithm (DBSCAN), Self-training Algorithm, Semi-supervised classification, Support vector machine,
Abstract :
Using the unlabeled data in the semi-supervised learning can significantly improve the accuracy of supervised classification. But in some cases, it may dramatically reduce the accuracy of the classification. The reason of such degradation is incorrect labeling of unlabeled data. In this article, we propose the method for high confidence labeling of unlabeled data. The base classifier in the proposed algorithm is the support vector machine. In this method, the labeling is performed only on the set of the unlabeled data that is closer to the decision boundary from the threshold. This data is called informative data. the adding informative data to the training set has a great effect to achieve the optimal decision boundary if the predicted label is correctly. The Epsilon- neighborhood Algorithm (DBSCAN) is used to discover the labeling structure in the data space. The comparative experiments on the UCI dataset show that the proposed method outperforms than some of the previous work to achieve greater accuracy of the self-training semi-supervised classification.
[1] D. Wu, et al., "Self-training semi-supervised classification based on density peaks of data," Neurocomputing, vol. 275, pp. 180-191, Jan. 2018.
[2] N. Zeng, Z. Wang, H. Zhang, W. Liu, and F. E. Alsaadi, "Deep belief networks for quantitative analysis of a gold immunochromatographic strip," Cognitive Computation, vol. 8, no. 4, pp. 684-692, 2016.
[3] N. Zeng, Z. Wang, and H. Zhang, "Inferring nonlinear lateral flow immunoassay state-space models via an unscented Kalman filter," Science China Information Sciences, vol. 59, no. 11, Article ID: 112204, 10 pp., 2016.
[4] N. Zeng, H. Zhang, W. Liu, J. Liang, and F. E. Alsaadi, "A switching delayed PSO optimized extreme learning machine for short-term load forecasting," Neurocomputing, vol. 240, pp. 175-182, May 2017.
[5] Y. Cao, H. He, and H. H. Huang, "LIFT: a new framework of learning from testing data for face recognition," Neurocomputing, vol. 74, no. 6, pp. 916-929, May 2011.
[6] F. Pan, J. Wang, and X. Lin, "Local margin based semi-supervised discriminant embedding for visual recognition," Neurocomputing, vol. 74, no. 5, pp. 812-819, Feb. 2011.
[7] D. Mallis, E. Sanchez, M. Bell, and G. Tzimiropoulos, "Unsupervised learning of object landmarks via self-training correspondence," Advances in Neural Information Processing Systems, vol. 33, pp. 4709-4720, 2020.
[8] G. Zhang, J. Wang, G. Shi, J. Zhang, and W. Dou, "A semi-supervised classification method for hyperspectral images by triple classifiers with data editing and deep learning," in Proc. EIA Int. Conf. Cloud Computing, Smart Grid and Innovative Frontiers in Telecommunications, pp. 171-183, Beiging, China, 4-5 Dec. 2019.
[9] J. Tanha, M. Van Someren, and H. Afsarmanesh, "Boosting for multiclass semi-supervised learning," Pattern Recognition Letters, vol. 37, pp. 63-77, Feb. 2014.
[10] D. Zhang, L. Jiao, X. Bai, S. Wang, and B. Hou, "A robust semi-supervised SVM via ensemble learning," Applied Soft Computing, vol. 65, pp. 632-643, Apr. 2018.
[11] J. Tanha, "MSSBoost: a new multiclass boosting to semi-supervised learning," Neurocomputing, vol. 314, pp. 251-266, Nov. 2018.
[12] C. Blake and C. Merz, UCI Repository of Machine Learning Databases, http://www.ics.uci.edu/?mlearn/MLRepository.html, University of California. Department of Information and Computer Science, Irvine, CA, p. 55, 1998.
[13] Z. H. Zhou and M. Li, "Semi-supervised learning by disagreement," Knowledge and Information Systems, vol. 24, no. 3, pp. 415-439, 2010.
[14] A. Blum and T. Mitchell, "Combining labeled and unlabeled data with co-training," in Proc. of the 11th Annual Conf. on Computational Learning Theory, pp. 92-100, Madison, WN, USA, 24 – 26 Jul. 1998.
[15] C. X. Ling, J. Du, and Z. H. Zhou, "When does co-training work in real data?" in ¬Proc. Pacific-Asia Conf. on Knowledge Discovery and Data Mining, pp. 596-603, Bangkok, Thailand, 27-30 Apr. 2009.
[16] Z. Jiang, S. Zhang, and J. Zeng, "A hybrid generative/discriminative method for semi-supervised classification," Knowledge-Based Systems, vol. 37, pp. 137-145, Jan. 2013.
[17] S. Sun, "A survey of multi-view machine learning," Neural Computing and Applications, vol. 23, no. 7-8, pp. 2031-2038, Feb. 2013.
[18] M. Li and Z. H. Zhou, "SETRED: self-training with editing," in Proc. Pacific-Asia Conf. on Knowledge Discovery and Data Mining, pp. 611-621, Hanoi, Vietnam, 18-20 May 2005.
[19] R. Chen, et al., "Semi-supervised anatomical landmark detection via shape-regulated self-training," Neurocomputing, vol. 471, pp. 335-345, Jan. 2022.
[20] Z. Yang and Y. Xu, "Laplacian twin parametric-margin support vector machine for semi-supervised classification," Neurocomputing, vol. 171, pp. 325-334, Jan. 2016.
[21] ش. پوربهرامی، ا. خالدی و ل. خانعلی، "الگوریتم جدید خوشهبندی ارسال داده در شبکههای حسگر بیسیم با استفاده از دایره آپولونیوس،" نشریه مهندسی برق و مهندسی کامپيوتر ايران، ب- مهندسی کامپیوتر، سال 17، شماره 3، صص. 226-219، پاییز 1398.
[22] ع. زاده بابایی، ع. باقری و خ. افشار، "ارائه یک الگوریتم خوشهبندی مبتنی بر چگالی با قابلیت کشف خوشههای با چگالی متفاوت در پایگاه دادههای مکانی،" نشریه مهندسی برق و مهندسی کامپيوتر ايران، ب- مهندسی کامپیوتر، سال 15، شماره 3، صص. 186-171، پاییز 1396.
[23] M. Ester, H. P. Kriegel, J. Sander, and X. Xu, "A density-based algorithm for discovering clusters in large spatial databases with noise," in Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining, KDD’96, pp. 226-231, Portland, ON, USA, 2-4 Aug. 1996.
[24] A. Lotfi, P. Moradi, and H. Beigy, "Density peaks clustering based on density backbone and fuzzy neighborhood," Pattern Recognition, vol. 107, Article ID: 107449, Nov. 2020.
[25] S. A. Seyedi, A. Lotfi, P. Moradi, and N. N. Qader, "Dynamic graph-based label propagation for density peaks clustering," Expert Systems with Applications, vol. 115, pp. 314-328, Jan. 2019.
[26] Y. Qin, Z. L. Yu, C. D. Wang, Z. Gu, and Y. Li, "A novel clustering method based on hybrid K-nearest-neighbor graph," Pattern Recognition, vol. 74, pp. 1-14, Feb. 2018.
[27] M. Emadi, J. Tanha, M. E. Shiri, and M. H. Aghdam, "A selection metric for semi-supervised learning based on neighborhood construction," Information Processing & Management, vol. 58, no. 2, Article ID: 102444, Mar. 2021.
[28] S. Pourbahrami and L. M. Khanli, A Survey of Neighbourhood Construction Models for Categorizing Data Points, arXiv preprint arXiv:1810.03083, 2018.
[29] S. Khezri, J. Tanha, A. Ahmadi, and A. Sharifi, "STDS: self-training data streams for mining limited labeled data in non-stationary environment," Applied Intelligence, vol. 50, no. 5, pp. 1-20, 2020.
[30] X. Gu, "A self-training hierarchical prototype-based approach for semi-supervised classification," Information Sciences, vol. 535, pp. 204-224, Oct. 2020.
[31] M. M. Adankon and M. Cheriet, "Help-training for semi-supervised support vector machines," Pattern Recognition, vol. 44, no. 9, pp. 2220-2230, Sept. 2011.
[32] M. Emadi and J. Tanha, "Margin-based semi-supervised learning using apollonius circle," in Proc. Int Conf. on Topics in Theoretical Computer Science, pp. 48-60, Tehran, Iran, 26-28 Aug. 2020.
[33] S. Pourbahrami, L. M. Khanli, and S. Azimpour, "A novel and efficient data point neighborhood construction algorithm based on Apollonius circle," Expert Systems with Applications, vol. 115, pp. 57-67, Jan. 2019.
[34] S. Pourbahrami, M. A. Balafar, L. M. Khanli, and Z. A. Kakarash, "A survey of neighborhood construction algorithms for clustering and classifying data points," Computer Science Review, vol. 38, Article ID: 100315, Nov. 2020.
[35] J. Tanha, M. van Someren, and H. Afsarmanesh, "Semi-supervised self-training for decision tree classifiers," International J. of Machine Learning and Cybernetics, vol. 8, no. 1, pp. 355-370, 2017.
[36] T. Joachims, "Transductive inference for text classification using support vector machines," in Proc. of The 26th Int. Conf. on Machine Learning, ICML'99, pp. 200-209, 1999.
[37] M. Belkin, P. Niyogi, and V. Sindhwani, "Manifold regularization: a geometric framework for learning from labeled and unlabeled examples," J. of Machine Learning Research, vol. 7, no. 85, pp. 2399-2434, 2006.
نشریه مهندسی برق و مهندسی کامپیوتر ایران، ب- مهندسی کامپیوتر، سال 20، شماره 3، پاییز 1401 217
مقاله پژوهشی
طبقهبندی خودآموز نیمهنظارتی مبتنی بر ساخت همسایگی
منا عمادی، جعفر تنها، محمدابراهیم شیری و مهدی حسینزاده اقدم
چکیده: بهکارگیری دادههای بدون برچسب در خودآموزی نیمهنظارتی میتواند به طور قابل توجهی دقت طبقهبند نظارتشده را بهبود بخشد، اما در برخی موارد ممکن است دقت طبقهبندی را به مقدار چشمگیری کاهش دهد. یکی از دلایل چنین تنزلی، برچسبگذاری اشتباه به دادههای بدون برچسب میباشد. در این مقاله، روشی را برای برچسبگذاری با قابلیت اطمینان بالا به دادههای بدون برچسب پیشنهاد میکنیم. طبقهبند پایه در الگوریتم پیشنهادی، ماشین بردار پشتیبان است. در این روش، برچسبگذاری فقط به مجموعهای از دادههای بدون برچسب که از مقدار مشخصی به مرز تصمیم نزدیکتر هستند انجام میشود. به این دادهها، دادههای دارای اطلاعات میگویند. اضافهشدن دادههای دارای اطلاعات به مجموعه آموزشی در صورتی که برچسب آنها به درستی پیشبینی شود در دستیابی به مرز تصمیم بهینه تأثیر بهسزایی دارد. برای کشف ساختار برچسبزنی در فضای داده از الگوریتم اپسیلون- همسایگی (DBSCAN) استفاده شده است. آزمایشهای مقایسهای روی مجموعه دادههای UCI نشان میدهند که روش پیشنهادی برای دستیابی به دقت بیشتر طبقهبند نیمهنظارتی خودآموز به نسبت برخی از کارهای قبلی عملکرد بهتری دارد.
کلیدواژه: الگوریتم اپسیلون- همسایگی (DBSCAN)، الگوریتم خودآموزی، طبقهبندی نیمهنظارتی، ماشین بردار پشتیبان.
1- مقدمه
الگوریتمهای یادگیری ماشین به سه دسته الگوریتمهای نظارتی، بدون نظارت و نیمهنظارتی تقسیم میشوند. در یادگیری نظارتی، مجموعهای از جفتهای ورودی و خروجی به ماشین داده میشود و ماشین تلاش میکند تا تابعی از ورودی به خروجی را یاد بگیرد. یادگیری نظارتشده یک مسئله تحقیقاتی فعال در زمینه دادهکاوی و یادگیری ماشین است
و تا کنون به طور گستردهای در حفاظت از سیستمهای قدرت، داروهای بیولوژیکی، تشخیص چهره، پردازش تصویر و تشخیص شیء مورد استفاده قرار گرفته است [1] تا [6]. یادگیری نظارتی برای آموزش طبقهبندی کارآمد به نمونههای با برچسب متکی است اما محدودیت آن در دستیابی به دادههای برچسبدار است، زیرا در دنیای واقعی اکثر دادهها بدون برچسب هستند و تنها درصد کمی از آنها برچسب دارند. از طرفی در عمل به دست آوردن دادههای برچسبدار، فرایندی بسیار پرهزینه، زمانبر و دشوار است.
یادگیری بدون نظارت، سعی بر یافتن الگوها و ساختار خاص در دادههای بدون برچسب دارد و آموزش واقعی در آن رخ نمیدهد. از آنجایی که دادههای بدون برچسب به وفور در دنیای واقعی یافت میشوند، دستهبندیای به نام طبقهبندی نیمهنظارتی مطرح میشود که نمونهای از یادگیری به همراه یافتن راهی جهت بهبودبخشیدن به یادگیری نظارتی با استفاده از دادههای بدون برچسب است. در یادگیری نیمهنظارتی، حجم عظیمی از دادههای بدون برچسب وجود دارد و فقط مقدار اندکی از دادهها برچسبدار هستند، از این رو برچسبدارکردن دادههای بدون برچسب یکی از مسائل حائز اهمیت در یادگیری ماشین به شمار میرود [7]. یادگیری نیمهنظارتی از روشهای یادگیری ماشین است و در آن میتوان از دادههای بدون برچسب و برچسبدار به صورت همزمان برای بهبود دقت یادگیری استفاده کرد. از این رو در این نوع یادگیری لزومی به برچسبداربودن تمام دادههای جمعآوریشده برای آموزش طبقهبند نیست و بسیار منطبق با نیازهای دنیای کنونی است.
رویکردهای متنوعی از یادگیری نیمهنظارتی در سراسر دنیا در حال مطالعه و بررسی است که اغلب آنها طبقهبندی را بر اساس فرضیات متفاوتی که وابسته به ارتباط میان توزیع دادههای برچسبدار و بدون برچسب میباشند، انجام میدهند. برای کنارگذاشتن این فرضیات، تکنیکهای خودبرچسبزن2 مطرح شدند که شامل دو روش باهمآموز3 و خودآموز4 میباشند [8].
باهمآموز تکنیکی است که فضای ویژگی را به صورت دو دیدگاه مستقل شرطی در نظر میگیرد که هر دیدگاه قادر به آموزش یک طبقهبند است. همچنین دو طبقهبند قادر به آموزش یکدیگر هستند تا بتوانند کلاسها را به طور کامل پیشبینی کنند [4]. روش خودآموز یک متد مبتنی بر غلاف5 است که از پیشبینیهای یادگیر پایه برای بهبود کارایی خودش استفاده میکند. در هر مرحله، مجموعه دادههای برچسبدار
با نمونههای بدون برچسبی که انتخاب شدهاند تا بر اساس پیشبینی طبقهبند پایه به آنها برچسب اختصاص داده شود به روز رسانی میشود [9]. با این حال عملکرد این الگوریتم تا حد زیادی بستگی به نمونههای بدون برچسب انتخابشده دارد. پیشبینی درست برچسب برای دادههای بدون برچسب، نقش قابل توجهی در بهبود عملکرد مدل ایفا میکند. اگر نمونههای بدون برچسبی که به اشتباه طبقهبندی شدهاند به مجموعه آموزشی اضافه گردند، منجر به انتشار خطا در روند آموزش میشوند. به طور کلی برای طبقهبندی نیمهنظارتی با استفاده از چارچوب خودآموز، دو چالش مهم وجود دارد: 1) انتخاب مجموعه کاندیدای مناسب از دادههای بدون برچسب در هر دور از فرایند آموزش میباشد. این مجموعه نقاط را نقاط دادهای دارای اطلاعات6 مینامیم. 2) پیشبینی برچسبهای درست برای زیرمجموعههای انتخابشده است. مطالعات اخیر در این زمینه تمایل به انتخاب نمونههایی را دارند که در هر دور از نظر تخمین برچسب توسط طبقهبند پایه، بالاترین قابلیت اطمینان را دارند [1]، [9] و [10]. اینها دادههایی هستند که معمولاً از مرز تصمیم دور میباشند. از این رو، این الگوریتمها نمیتوانند به طور قابل توجهی اطلاعات را از دادههای بدون برچسب استخراج نمایند و مرز تصمیمی که نهایتاً به دست خواهد آمد بسیار نزدیک به مرز تصمیم طبقهبند اولیه خواهد بود [11].
مسئله دیگر، در ارتباط با تخمین برچسب طبقهبندهای پایه است که
در اکثر مواقع ممکن است تخمینی با احتمال مطمئن به پیشبینیهای آنها اختصاص داده نشود [9]. در [10]، زیرمجموعهای از دادههای بدون برچسب بر مبنای فاصله آنها از مرز تصمیم انتخاب شده است. اگرچه
نقاط دادهای انتخابشده با توجه به معیار برآورد احتمال طبقهبند پایه استفادهشده قابلیت اطمینان بالایی دارند، اما آنها نقاط دادهای دارای اطلاعات یا به بیان دیگر نقاط آموزندهای نیستند که بتوانند قادر به بهبود مرز تصمیم باشند؛ زیرا تأثیر کمی بر روی موقعیت ابرصفحه7 میگذارند. علاوه بر این، اضافهکردن همه نقاط بدون برچسب به مجموعه برچسبدار زمانبر است و ممکن است مرز تصمیم را تغییر ندهد.
برای غلبه بر مشکلات ذکرشده در بالا، این مقاله یک الگوریتم خودآموز نیمهنظارتی جدید را بر مبنای الگوریتم ساخت همسایگی مطرح میکند. روش پیشنهادی، زیرمجموعهای از نقاط بدون برچسب نزدیک
به مرز تصمیم را به عنوان نقاط دارای اطلاعات در طی فرایند آموزش انتخاب میکند. این انتخاب اگرچه برای رسیدن به مرز تصمیمی بهینه، واقعبینانه است اما احتمال این را دارد که نقاط دادهای به اشتباه برچسب زده شوند. برای حل این مشکل و برچسبگذاری صحیح نمونههای بدون برچسب، یک الگوریتم مبتنی بر ساخت همسایگی ارائه شده است. این الگوریتم با استفاده از DBSCAN همسایه نمونهها را پیدا میکند. الگوریتم DBSCAN در دسته روشهای خوشهبندی مبتنی بر چگالی قرار دارد. این روش خوشهبندی بر این فرض استوار است که خوشهها شامل ناحیهای از فضای داده با تراکم بالا میباشند که از نواحی با چگالی کمتر جدا شدهاند. مزیت روش پیشنهادی این است که به شکل دادهها حساس نیست و بنابراین قادر به شناسایی خوشههایی با اشکال مختلف غیر کروی میباشد. تعداد خوشهها به طور همزمان و خودکار تعیین میشود و همچنین در شناسایی نویز کارآمد است. بخشهای اصلی این مطالعه شامل موارد زیر است:
- این مقاله تأثیر نقاط نزدیک به مرز تصمیم را برای بهبود کارایی طبقهبندی بررسی میکند.
- معیاری جدید برای اندازهگیری شباهت بین نقاط داده برچسبدار و بدون برچسب معرفی کرده است.
- روش پیشنهادی یک روش مبتنی بر توافق بین پیشبینیهای طبقهبند پایه و الگوریتم مبتنی بر ساخت همسایگی به منظور اختصاصدادن برچسب به دادههای بدون برچسب میباشد.
- راهکاری کارآمد جهت اطمینان از درستی برچسب پیشبینی شده ارائه داده است.
نتایج آزمایشگاهی بر روی بعضی از مجموعههای دادهها UCI [12] نشان میدهند که الگوریتم پیشنهادی بهتر از دیگر الگوریتمهای مطرحشده در این حوزه است.
باقی مقاله به شرح زیر سازماندهی میشود: بخش 2 کارهای مرتبط با یادگیری نیمهنظارتی را مورد مطالعه قرار میدهد. بخش 3 هدف تحقیق و الگوریتم پیشنهادی را بیان میکند. بخش 4 آزمایشها و نتایج آنها را بر روی برخی از مجموعه دادهها ارائه میدهد و آنها را با بعضی از الگوریتمهای مطرح در این حوزه مقایسه میکند. در نهایت بخش 5 به نتیجهگیری میپردازد.
2- تحقیقهای پیشین انجامشده
یک روش برای مقابله با مشکلات یادگیری نیمهنظارتی، الگوریتمهای خودبرچسبگذار هستند که از طبقهبند نظارتشده برای نشاندادن نمونههای برچسبدار با کلاس ناشناخته و بدون هیچ فرضیه خاصی درباره داده ورودی، استفاده میکنند [13]. تکنیکهای خودبرچسبگذاری شامل دو روش شناختهشده به نامهای باهمآموز و خودآموز میباشند. آموزش باهمآموز، فضای ویژه را در دو دیدگاه مستقل از نظر شرطی بررسی میکند [14]. هر دیدگاه قادر است یک طبقهبند را آموزش دهد و سپس به دیگران آموزش دهد که کلاسها را کاملاً پیشبینی کنند [15] و [16]. علاوه بر این، رویکردهای پیشرفتهای برای آموزش همزمان چندین یادگیری وجود دارد که نیازی به تقسیم ویژگیها به صورت آشکار و یا روش آموزش تکرار متقابل ندارند [13] و [17]. همان طور که از نام خودآموز مشخص است، خودآموزی تلاش میکند تا به صورت مکرر دادههای برچسبدار مجموعه آموزشی را بیشتر و بیشتر کند [18]. برای شروع، یک طبقهبند با دادههای دارای برچسب اولیه آموزش داده میشود و سپس دادههای بدون برچسب با بیشترین اطلاعات و اطمینان
انتخاب میگردند. آن گاه به تدریج دادههای کاندیدا به همراه برچسبهای پیشبینیشده آنها به مجموعه آموزشی اضافه میشوند و این روش تا رسیدن به همگرایی تکرار میگردد. خودآموز با موفقیت در بسیاری از دادههای واقعی اعمال شده است [19]. محدودیت این روش در تعداد دادههای برچسبدار و توزیع آنهاست، زیرا اگر این دادهها نتوانند ساختار فضای داده را به خوبی نشان دهند، فرایند آموزش به فضای واقعی دادهها نزدیک نشده و طبقهبند به درستی آموزش نمیبیند. روشهایی برای بهبود روش خودآموز ارائه شدهاند که از جمله آنها، روش کمک یادگیری8 است که سعی بر آموزش یک طبقهبند متمایزکننده9 استفاده از مدل تولیدی دارد [6]. ولی این روش نتوانست به طور ریشهای محدودیت روش خودآموز را برطرف کند، زیرا مدل تولیدی تنها با دادههای برچسبدار آموزش میبیند. سپس الگوریتم نیمهنظارتی فازی c-means ارائه شد، از هر دو نوع داده برچسبدار و بدون برچسب برای نشان دادن ساختار واقعی داده استفاده میکرد، اما محدودیتهای این الگوریتم باعث ناکارآمدی آن در توزیعهای غیر کروی بود10 [14].
گروهی از الگوریتمهای یادگیری نیمهنظارتی، مبتنی بر حاشیهها میباشند که به دلیل داشتن پایه ریاضی از اهمیت زیادی برخوردار هستند (مانند بوستینگ، ماشین بردار پشتیبان و 11TSVM). الگوریتمهای ماشین
[1] این مقاله در تاریخ 17 مهر ماه 1400 دریافت و در تاریخ 17 بهمن ماه 1400 بازنگری شد.
منا عمادی، گروه مهندسی کامپیوتر، واحد بروجرد، دانشگاه آزاد اسلامی، بروجرد، ایران، (email: emadi.mona@pnu.ac.ir).
جعفر تنها (نویسنده مسئول)، گروه مهندسی برق و الکترونیک، دانشگاه تبریز، تبریز، ایران، (email: tanha@tabrizu.ac.ir).
محمدابراهیم شیری، گروه علوم کامپیوتر، دانشگاه امیرکبیر، تهران، ایران،
(email: shiri@aut.ac.ir).
مهدی حسینزاده اقدم، گروه مهندسی کامپیوتر، دانشگاه بناب، بناب، ایران، (email: mhaghdam@ubonab.ac.ir).
[2] . Self-Labeled
[3] . Co-Training
[4] . Self-Training
[5] . Wrapper
[6] . Informative Data Points
[7] . Hyperplane
[8] . Help-Training
[9] . Discriminative
[10] . Non-Spherical
[11] . Transductive Support Vector Machine
جدول 1: مزایا و معایب سه روش ساخت همسایگی.
مزایا | معایب | |
k-NN | - سادگی روش - ناپارامتریک است. - رویکردی شهودی دارد. - در تشخیص نقاط پرت قوی است. - در برخورد با ویژگیهای عددی و پیوسته خوب است. | - تعيين همسايگي فقط براساس فاصله است. - حساسيت به ويژگيهاي نامربوط دارد. - در مديريت دادهها با انواع مختلط بسيار مشکل دارد. - فقدان مباني نظري - بر روي مقادير عددي/ دودويي نامشخص است. |
DBSCAN | - خوشههایی از اشکال دلخواه را کشف ميکند. - پيچيدگي متوسط دارد. - پردازش آن سريع است. - توانايي تشخيص نقاط پرت - نيازي به تعريف تعداد خوشهها ندارد. | - نميتواند خوشههايي با چگالي متفاوت را به طور مؤثر پيدا کند. - نميتواند با چندين نقطه پرت کار کند. - براي مجموعه دادههای بزرگ، هزینه محاسباتی بالایی دارد. - عدم قطعیت در تنظیم پارامترهای ورودی - برای دادههای با ابعاد بالا مناسب نیست. |
DPC | - عدم وجود فاز تکرار - مراکز از ویژگیهای اساسی نقاط داده استخراج میشوند. | - هزینه محاسباتی بالا - فقط برای مجموعه دادههای کوچک مناسب است. - نیاز به تعریف پارامتر دارد. - تعداد خوشههای مناسب به دست آمده از گراف تصمیم ممکن است برابر نباشند و با تعداد خوشههای ایدهآل قابل مقایسه نباشند. |
بردار پشتیبان در بسیاری از برنامههای کاربردی واقعی موفق به کسب موفقیتهایی شدهاند [20]. در روش پیشنهادی، طبقهبند پایه مورد استفاده ماشین بردار پشتیبان میباشد.
الگوریتمهای خوشهبندی مبتنی بر چگالی، یکی از روشهای اصلی در دادهکاوی هستند که نسبت به روشهای قبلی، پایه ریاضی قویتری دارند [21]. الگوریتم DBSCAN پایه روشهای خوشهبندی مبتنی بر چگالی است. در این الگوریتم برای تعریف اپسیلون همسایگی، شعاع اپسیلونی با دایره تعیین میشود [22]. در دایرهای به شعاع اپسیلون، اگر نقاط درون دایره در حداقل فاصله نقطه مورد نظر قرار گرفته باشند، آن گاه به آن نقاط، نقاط همسایگی نمونه بدون برچسب گفته میشود.
اما اگر نقاط، خارج از آستانه مورد نظر باشد به آن نقاط، نقاط پرت یا حاشیهای گفته میشود [23].
یکی دیگر از الگوریتمهای مبتنی بر چگالی، الگوریتم DPC میباشد که در مجله معتبر علوم آمریکا به چاپ رسیده است. در این الگوریتم برای تشخیص خوشههای غیر کروی و یافتن تعداد خوشهها به طور خودکار برای تمام نقاط داده، دو کمیت چگالی محلی و دلتا به کمک ماتریس فاصله محاسبه میشوند [15]. پس از محاسبه این دو کمیت، نقاط مطمئن با استفاده از گراف تصمیم به دست میآیند. نقاط مطمئن، نقاطی در گراف تصمیم هستند که چگالی بالا و فاصله بیشتری از نقاط پرتراکم دیگر دارند. این الگوریتم وابسته به پارامتری به نام فاصله قطع1 است که برای تعیین درصد همسایگی در محاسبه چگالی محلی نقاط به کار میرود و باعث میشود که دقت الگوریتم همواره به یک پارامتر اولیه وابسته باشد. مرجع [3] از این الگوریتم برای مشخصکردن ساختار فضای داده استفاده کرده است، به طوری که پس از محاسبه دو کمیت چگالی محلی و دلتا برای تمامی نقاط، ساختار واقعی داده با اشارهکردن هر
نقطه به نزدیکترین نقطهای که چگالی آن بیشتر از خودش میباشد به دست آمده است. سپس از روش نیمهنظارتی خودآموز برای برچسبزنی به دادههای بدون برچسب استفاده کرده است، به طوری که ابتدا طبقهبند با مجموعه دادههای برچسبدار آموزش دیده و سپس برای نقاط بدون برچسبی که مابعد دادههای پرچگال برچسبدار هستند، برچسبی پیشبینی کرده و آنها را به مجموعه آموزشی برچسبدار اضافه و از مجموعه دادههای بدون برچسب کم کرده و بار دیگر با مجموعه دادههای برچسبدار جدید آموزش دیده است. سپس همین کار را برای نقاط بدون برچسب که ماقبل دادههای پرچگالش هستند، انجام داده و بدین ترتیب تمام نقاط بدون برچسب را برچسب زده است. در [24] الگوریتمی برای بهبود عملکرد DPC ارائه گردیده که از هسته فازی برای انتخاب خوشه مناسب استفاده شده است. این الگوریتم مبتنی بر گراف KNN میباشد و راهکاری را برای برچسبگذاری دادههای مرزی و همچنین دادههایی با اشکال و چگالیهای متفاوت ارائه میدهد. در [25] یک روش خوشهبندی با استفاده از DPC ارائه شده است. در این روش با ایده K نزدیکترین همسایه، پارامتر قطع و چگالی محلی هر نمونه محاسبه شده است و برچسبگذاری با استفاده از انتشار برچسب انجام میشود.
یکی دیگر از الگوریتمهایی که برای خوشهبندی و تعریف همسایگی دادهها استفاده میشود، k نزدیکترین همسایه (k-NN) است که از فاصله اقلیدسی استفاده میکند. این الگوریتم با مجموعه دادههایی که مشابه یکدیگر هستند، شروع میشود و سپس خوشهها را مشخص میکند. k نزدیکترین همسایه، الگوریتمی بسیار ساده است و در تعیین همسایگی مفید میباشد. تنها معیار استفادهشده برای تعیین همسایگی در این الگوریتم، فاصله و مکان نقاط است [26]. یکی از الگوریتمهای مورد مقایسه در این مطالعه SSApollo میباشد [27] که برای حل مسائل طبقهبندی نیمهنظارتی از DPC و دایره آپولونیوس استفاده کرده است.
اکثر الگوریتمهای طبقهبندی خودآموز جهت برچسبزدن به نمونههای بدون برچسب از پیشبینی طبقهبند پایه استفاده نموده و همچنین اقدام به برچسبزدن به تمامی مجموعه نقاط بدون برچسب کردهاند که این عمل نهتنها زمانبر است، بلکه در بعضی مواقع منجر به کاهش دقت نیز میشود. در الگوریتم پیشنهادی، علاوه بر انتخاب مجموعه داده بدون برچسب به عنوان کاندیدایی برای برچسبزدن، از الگوریتم ساخت همسایگی استفاده شده تا برچسب مطمئن را به نمونه بدون برچسب اختصاص دهد. در الگوریتم پیشنهادی برای پیداکردن نقاط همسایه نمونه بدون برچسب در فرایند خودآموز از الگوریتم DBSCAN استفاده شده است. در جدول 1 مقایسه تحلیلی سه الگوریتم ساخت همسایگی آمده است [28].
شکل 1: نحوه تخصیص برچسب به دادههای بدون برچسب با استفاده از الگوریتم همسایگی DBSCAN.
3- یادگیری نیمهنظارتی
در این بخش، ابتدا مسائل طبقهبندی نیمهنظارتی و اهداف تحقیق را بیان و سپس الگوریتم پیشنهادی را مطرح میکنیم.
3-1 اهداف تحقیق و تعریف مسئله
در الگوریتم نیمهنظارتی هم دادههای برچسبدار با برچسبهای و هم دادههای بدون برچسب با برچسبهای ناشناخته وجود دارند، به طوری که تعداد دادههای برچسبدار خیلی کمتر از دادههای بدون برچسب میباشد. هر دو گروه از دادهها (برچسبدار و بدون برچسب) در توزیع دادههایی یکسان به طور مستقل هستند. همان طور که قبلاً بیان شد، در چارچوب خودآموز دو چالش اصلی وجود دارد: 1) انتخاب مجموعه مناسب از نمونههای بدون برچسب در هر تکرار فرایند خودآموز و
2) پیشبینی درست برچسب نمونههای موجود در زیرمجموعههای انتخابشده. برای غلبه بر این مسائل، بیشتر الگوریتمهای یادگیری نیمهنظارتی، تخمینهای احتمالی طبقهبندهای پایه را به منظور اختصاص برچسب به دادههای بدون برچسب به کار میگیرند. این الگوریتمها از همین ابزار به عنوان معیار انتخاب استفاده میکنند [1]، [9] و [29] تا [31]. استفاده از چنین معیاری ممکن است منجر به انتخاب نمونههای مطمئنی شود که به اشتباه طبقهبندی شدهاند و نتیجه آن انتشار خطا و همچنین عدم بهبود مرز تصمیم میباشد [27] و [32]. هدف ما در این مطالعه، تمرکز بر روی نقاطی است که نزدیک به مرز تصمیم هستند. این نمونههای بدون برچسب به طور کلی از نظر پیشبینی احتمال طبقهبند پایه، اطمینان بالایی ندارند. بعد از انتخاب این نمونهها باید به دنبال ابزاری بود تا برچسب درستی به این نمونههای دارای اطلاعات اختصاص داد و سپس آنها را به مجموعه دادههای برچسبدار اصلی در هر تکرار فرایند آموزش اضافه کرد. بر اساس این ایده در الگوریتم پیشنهادی از الگوریتمهای نیمهنظارتی مبتنی بر حاشیه استفاده میکنیم.
3-2 الگوریتم پیشنهادی
روش ساده اپسیلون همسایگی (DBSCAN)، همسایگی را بر اساس شعاعی کوچک و بر اساس پارامتر فاصله اپسیلون تعیین مینماید و در این ناحیه از شعاع همسایگی، دادهها برچسبگذاری میشوند [23] و [33].
در دایرهای با شعاع اپسیلون، اگر نقاط داخل دایره با فاصله حداقل MINPTS از نقطه مورد نظر تعریف شوند، به عنوان نقاط همسایه اصلی برای آن نقطه انتخاب میگردند. اما اگر نقاط، خارج از نقاط تعریفشده قرار داشته باشند، به عنوان نقاط مرزی یا نویز نشان داده میشوند. منطقه تصمیمگیری و تراکم در بین این نقاط در فضای همسایگی، آنها را در برچسبگذاری مرتبط میکند [34].
در الگوریتم پیشنهادی قرار است که برچسبگذاری دادههای بدون برچسب به روشی انجام گردد که باعث افزایش دقت طبقهبند پایه شود. اگر تمامی دادههای بدون برچسب را اضافه کنیم، علاوه بر این که سایز فضای فرضیه خیلی بزرگ میشود، باعث ایجاد نویز نیز میگردد. بنابراین در این الگوریتم، دادههای بدون برچسبی انتخاب شدهاند که حاوی اطلاعات مهمی باشند و این دادهها از حد مشخصی به حاشیه نزدیکتر هستند. برای تشخیص درستی یا نادرستی برچسب پیشبینی شده و همچنین تأثیرگذاری مجموعه بدون برچسب انتخابشده به روش زیر عمل میشود:
ابتدا با استفاده از الگوریتم ماشین بردار پشتیبان استاندارد و فقط
با مجموعه آموزشی اولیه، برچسبگذاری نمونههای بدون برچسب انجام میگردد. سپس نمونههای بدون برچسبی که در مرحله قبل برچسب خوردهاند به مجموعه آموزشی اضافه میشوند و مجدداً با الگوریتم ماشین بردار پشتیبان عمل آموزش تکرار میگردد و دقت، محاسبه میشود. اضافهکردن همه دادههای بدون برچسب کار درستی نیست. در الگوریتم پیشنهادی، نمونههای بدون برچسبی اضافه میشوند که از فاصله مشخصی به حاشیه نزدیکتر هستند
و بنابراین بعد از محاسبه فاصله دادهها از مرز تصمیم، آنهایی را
که فاصلهشان از مقدار معینی کمتر باشد در مجموعهای جداگانه ریخته و در مرحله بعدی، قبل از اضافهکردن آنها به مجموعه آموزشی، برچسب آنها را پیشبینی مینماید. برچسبگذاری نمونههای بدون برچسب بر اساس همسایگان آنها با الگوریتم اپسیلون همسایگی انجام میشود. نحوه اختصاص برچسب به نمونههای بدون برچسب با الگوریتم DBSCAN در شکل 1 نشان داده شده است.
سه گروه همسایگی را در شکل 1 میتوان مشاهده کرد. در الگوریتم پیشنهادی با استفاده از الگوریتم همسایگی DBSCAN، نمونههای همسایه داده بدون برچسب مورد نظر را که از بین مجموعه برچسبدار انتخاب شدهاند پیدا کرده و سپس برچسب کلاس اکثریت را به نمونه بدون برچسب اختصاص میدهد. به عنوان مثال در شکل 1 به نمونه بدون برچسبی که در گروه همسایگی 1 قرار دارد، برچسب کلاس 2 اختصاص مییابد و به نمونههای بدون برچسب گروههای همسایگی 2 و 3، برچسب کلاس 1 اختصاص مییابد.
الگوریتم پیشنهادی در فرایند خودآموزی، تمام دادههای بدون برچسب را برچسبگذاری نمیکند و فقط نمونههایی که از مقدار تعیینشدهای
به مرز تصمیم نزدیکتر هستند، انتخاب میگردند. این دادهها به دلیل نزدیکی به مرز تصمیم، تأثیرگذاری فراوانی در دستیابی ابرصفحه بهینه دارند و واقعاً آموزنده هستند. تأثیر مثبت اضافهشدن این نمونهها در صورتی است که برچسب آنها به درستی پیشبینی شود، زیرا این دادهها به دلیل نزدیکی به مرز تصمیم، عدم قطعیت دارند و احتمال این که برچسب تخمین زده شده برای آنها اشتباه باشد، زیاد است. در الگوریتم پیشنهادی در هر بار تکرار از میان دادههای بدون برچسب نزدیک به مرز، N زیرمجموعه به صورت تصادفی انتخاب میشوند. ؟؟؟ مشکل عدم قطعیت برچسب تخمین زده شده توسط طبقهبند پایه را با استفاده از الگوریتم ساخت همسایگی DBSCAN و همچنین با روش ردکردن معکوس همان زیرمجموعه حل کرده است. طبقهبند استفادهشده در این الگوریتم ماشین بردار پشتیبان میباشد.
[1] . Cut of Distance
شکل 2: نمایی از الگوریتم پیشنهادی.
روش کار چنین است که ابتدا طبقهبند را بر روی مجموعه آموزش میدهد و سپس برای هر یک از زیرمجموعه از دادههای بدون برچسبی که انتخاب میشوند ، زیرمجموعه معکوس آن ایجاد میگردد. از معکوسکردن برچسب نقاط دادهای در به دست میآید. برچسب دادههای با استفاده از همسایگانی که عضو مجموعه آموزشی برچسبدار میباشند، بر اساس الگوریتم ساخت همسایگی DBSCAN پیشبینی میشود. نحوه تشخیص برچسب دادهها توسط این الگوریتم در شکل 1 نشان داده شده است. بعد از معکوسکردن برچسب دادههای پیشبینی شده، طبقهبند را بر روی مجموعه آموزش میدهد. در نهایت زیرمجموعهای انتخاب میشود که باعث ایجاد ماکسیمم اختلاف دقت برای دو طبقهبند و گردد. در واقع زیرمجموعهای که با معکوسشدن برچسبهای آن، دقت طبقهبند به شدت کاهش یابد انتخاب میشود و به مجموعه برچسبدار اضافه میگردد. با این روش نقاطی برچسبگذاری شدهاند
که بالاترین اطمینان را در پیشبینی برچسب داشتهاند. شکل 2 نمایی از الگوریتم پیشنهادی را نشان میدهد.
در این الگوریتم در ابتدای کار به تمام دادههای بدون برچسب، وزن یکسانی اختصاص داده میشود. سپس در هر دور از الگوریتم خودآموز، دادههای بدون برچسبی که برای اضافهشدن به مجموعه برچسبدار انتخاب شدهاند، وزنشان کاهش مییابد. با کاهش وزن، شانس انتخاب مجدد آنها در دورهای بعدی اجرای الگوریتم کاهش مییابد؛ زیرا فرایند انتخاب دادههای بدون برچسب به صورت تصادفی و با جایگشت است. در پایان هر دور، شرط بررسی میشود و اگر شرط برقرار نباشد الگوریتم پایان مییابد. یک ثابت مثبت و دستگیرهای است که زمان خاتمه الگوریتم را مشخص میکند. هرچه مقدار بزرگتر باشد، الگوریتم زودتر خاتمه مییابد. نرخ کاهش وزن نمونههای بدون برچسب را نشان میدهد. یکی دیگر از ثابتهایی که در الگوریتم استفاده شده است، میباشد که مقدار آن با میانگین فاصله دادههای بدون برچسب تا مرز تصمیم تنظیم شده است. الگوریتم ۱ چهارچوب را با جزئیات بیشتری نشان داده است.
الگوریتم 1: الگوریتم پیشنهادی خودآموز مبتنی بر ساخت همسایگی
دادههای ورودی: مجموعه برچسبدار ، مجموعه بدون برچسب ، نرخ کاهش وزن و مقدار مثبت ثابت که این مقدار کنترل میکند الگوریتم چه زمانی خاتمه یابد.
دادههای خروجی: دقت مدل طبقهبندی
1) فاصله دادههای بدون برچسب را از مرز تصمیم پیدا کن .
2) میانگین فاصله را پیدا کن و حد فاصله تعیینشده برای انتخاب دادههای بدون برچسب انتخابی را برابر آن قرار بده .
3) وزن اولیه تمامی نمونههای بدون برچسب را برابر یک قرار بده .
4) میانگین وزن همه نمونههای بدون برچسب را با نشان بده.
5) طبقهبند را بر روی مجموعهای که از اجتماع دادههای برچسبدار و بدون برچسب ایجاد شده است آموزش داده و دقت را محاسبه کن.
6) تا زمانی که مقدار برقرار است، مراحل زیر را تکرار کن:
7) برای تمامی نمونههای بدون برچسب مراحل زیر را انجام بده:
8) دادههای بدون برچسبی را که فاصله آنها از مرز تصمیم، کمتر یا مساوی است در مجموعهای به نام قرار بده. این مجموعه در ابتدا تهی است.
9) به طور تصادفی زیرمجموعه از انتخاب کن و مراحل 10 تا 14 را انجام بده.
10) وزن نمونه انتخابشده را کاهش بده تا شانس انتخاب آن در دورهای بعدی فرایند خودآموز کاهش یابد.
11) با استفاده از الگوریتم DBSCAN نزدیکترین همسایههای نمونه بدون برچسب را انتخاب کن. نمونههای همسایه انتخابشده عضو مجموعه برچسبدار میباشند.
12) برچسب کلاس اکثریت همسایگان را به نمونه بدون برچسب انتخابشده اختصاص بده.
13) طبقهبند را روی آموزش داده و دقت را محاسبه کن.
14) مجموعهای که بیشترین اختلاف را برای دو طبقهبند و ایجاد میکنند، انتخاب کرده و به مجموعه دادههای برچسبدار اضافه کن.
15) مراحل 6 تا 14 را تکرار کن تا الگوریتم خودآموز پایان پذیرد.
16) دقت مدل طبقهبند نهایی را محاسبه کن.
جدول 2: مشخصات مجموعه دادهها.
تعداد کلاس | تعداد صفات | تعداد نمونه | نام مجموعه داده |
2 | 13 | 270 | Heart |
2 | 4 | 748 | Blood |
2 | 18 | 155 | Hepatitis |
2 | 16 | 435 | Vote |
2 | 22 | 8124 | Mushroom |
2 | 6 | 345 | Liver |
2 | 10 | 699 | Breast |
2 | 60 | 208 | Sonar |
2 | 24 | 1000 | German |
2 | 27 | 300 | Colic |
3 | 4 | 150 | Iris |
3 | 13 | 178 | wine |
3-3 پیچیدگی محاسباتی الگوریتم پیشنهادی
پیچیدگی محاسباتی الگوریتم ساخت همسایگی است که در آن، برابر با سایز مجموعه داده میباشد. الگوریتم به ازای نمونههای عضو زیرمجموعه بدون برچسب، اعمال برچسبزدن و تخصیص وزن را انجام میدهد. از آنجایی که میباشد، پیچیدگی کلی الگوریتم است.
4- نتایج آزمایشها
در این بخش، آزمایشهایی تنظیم شده که متد پیشنهادی را با چندین الگوریتم دیگر بررسی میکند. الگوریتم پیشنهادی میتواند برای هر نوعی از یادگیری مبتنی بر حاشیه استفاده گردد. در این مطالعه از یادگیر پایه ماشین بردار پشتیبان استفاده شده است. در آزمایش اول، کارایی ماشین بردار پشتیبان، فقط با استفاده از دادههای برچسبدار گزارش شده است. در آزمایش دوم با ماشین بردار پشتیبان استاندارد که در غلاف الگوریتم خودآموز قرار گرفته است و همچنین روش خودآموز مبتنی بر فاصله که 1ST-DB [35] نام دارد، عمل مقایسه انجام شده است. همچنین الگوریتم پیشنهادی به ترتیب با الگوریتمهای این حوزه مانند 2TSVM [36] و خودآموز استاندارد (ST) [37] و SSApollo [27] مقایسه شده است. در آزمایشها، از مجموعه داده واقعی برای آزمایش عملکرد الگوریتم استفاده شده و جزئیات این مجموعه دادهها در جدول 1 آمده است.
4-1 مجموعه دادهها
چندین مجموعه داده UCI در این آزمایشها استفاده گردیده است.
در جدول 2 به طور خلاصه مشخصات 12 مجموعه داده از مخزن داده UCI مورد استفاده در این آزمایشها نشان داده شده است. ما مجموعه دادههای واقعی را انتخاب کردهایم تا در صورتی که در واقعیت، مجموعه دادهها از نظر پراکندگی و توزیع شبیه اینها بودند، الگوریتم بتواند برچسبگذاری نمونهها را انجام دهد (مانند مجموعه دادههای پزشکی و صنعتی). الگوریتم پیشنهادی برای مجموعه دادههای باینری و چندکلاسه کارایی دارد.
4-2 تنظیمات آزمایشی
برای هر مجموعه داده، 30% از دادهها به طور تصادفی برای مجموعه تست کنار گذاشته میشوند. در ابتدا دادههای مجموعه آموزشی به 90% دادههای بدون برچسب و 10% دادههای برچسبدار تقسیم میشوند. کلاسها برای همه مجموعهها به نسبت برابر با مجموعه داده اصلی انتخاب میشوند و هر آزمایش با زیرمجموعههای متفاوتی از تست و آموزش، 10 بار تکرار شده است. برای بررسی کارایی روش پیشنهادی، نرخ میانگین دقت (MAR) برای هر 10 آزمایش تکرار شده که برای محاسبه آن از یک مجموعه تست متشکل از تعداد نمونههای با شناختهشده برای مرحله آزمون استفاده میگردد. دو مقدار از نرخ دقت (AR) و میانگین نرخ دقت 3(MAR) به ترتیب زیر محاسبه میشوند
(1)
(2)
برچسب محاسبهشده برای و تعداد دفعات تکرار برای محاسبه AR است. MAR بیانکننده توانایی الگوریتم پیشنهادی است.
برای اجرای شبیهسازیها از نرمافزار بر روی سیستمی با پردازنده با حافظه 16 گیگابایت و سیستم عامل استفاده شده است.
4-3 بحث پیرامون نتایج
جداول 3 و 4 کارایی طبقهبندی الگوریتم پیشنهادی و سایر الگوریتمها را در شرایطی که فقط 10% و 20% از دادههای آموزشی برچسبدار هستند، نشان میدهد. در این جدولها، ستون اول کارایی طبقهبند SVM نظارتشده را نشان میدهد. ستون دوم، سوم، چهارم و پنجم به ترتیب بیانکننده کارایی طبقهبندهای خودآموز استاندارد (ST)، خودآموز مبتنی بر فاصله (ST-DB)، TSVM و SSApollo میباشند. نهایتاً ستون آخر کارایی طبقهبند الگوریتم پیشنهادی است. برای همه متدها SVM به کار گرفته شده است. بهترین کارایی طبقهبندی برای هر مجموعه داده در جدولها با فونت ضخیم نشان داده شده است.
جدول 3، نتایج آزمایشها را برای زمانی که فقط 10% دادهها برچسبدار هستند، نشان میدهد. همان طور که مشاهده میشود الگوریتم پیشنهادی به طور چشمگیری دقت طبقهبندی ماشین بردار پشتیبان نظارتشده را برای اکثر مجموعه دادهها بهبود میدهد.
جدول 4 نتایج آزمایشها را برای زمانی که فقط 20% دادهها برچسبدار هستند، نشان میدهد. همان طور که مشاهده میشود الگوریتم پیشنهادی به طور چشمگیری دقت طبقهبندی ماشین بردار پشتیبان نظارتشده را برای اکثر مجموعه دادهها بهبود میدهد.
با محاسبه نرخ میانگین دقت مشاهده میشود که در جدول 3 الگوریتم پیشنهادی، کارایی الگوریتم طبقهبندی نظارتشده ماشین بردار پشتیبان را برای 6 مجموعه داده از بین 12 مجموعه داده به طور قابل توجهی بهبود میدهد. همچنین در جدول 4 نیز مشاهده میشود که کارایی الگوریتم پیشنهادی در بین 6 تا از 12 مجموعه داده بهتر از سایر الگوریتمها است.
[1] . Distance-Based Self-Training
[2] . Transductive SVM
[3] . Mean Accuracy Rate
جدول 3: دقت طبقهبندی با 10% دادههای برچسبدار.
الگوریتم پیشنهادی | SSApollo | TSVM | ST-DB | ST | Supervised SVM | مجموعه داده |
37/70 | 31/70 | 98/63 | 70/63 | 87/64 | 96/62 | Heart |
05/62 | 62 | 32/55 | 78/50 | 40/50 | 32/49 | Blood |
81/46 | 67/46 | 02/46 | 78/44 | 11/44 | 68/44 | Hepatits |
79/87 | 88/86 | 05/85 | 19/82 | 76/84 | 26/82 | Vote |
86/65 | 72 | 46/61 | 23/59 | 45/59 | 96/56 | Mushroom |
15/71 | 90/61 | 88/71 | 10/72 | 40/71 | 12/72 | Liver |
57/88 | 57/88 | 90 | 33/89 | 04/88 | 43/91 | Breast |
23/53 | 70/66 | 01/57 | 02/55 | 23/55 | 45/56 | Sonar |
67/71 | 89/70 | 50/67 | 68 | 89/67 | 67/67 | German |
00/60 | 89/60 | 43/54 | 20/53 | 45/55 | 33/53 | Colic |
80/93 | 76/93 | 12/89 | 8/92 | 86 | 40/91 | iris |
09/90 | 40/90 | 91/89 | 50/84 | 81/89 | 30/85 | wine |
جدول 4: دقت طبقهبندی با 20% دادههای برچسبدار.
SSApollo | TSVM | ST-DB | ST | Supervised SVM | مجموعه داده | |
27/82 | 97/82 | 91/80 | 70/80 | 60/81 | 25/80 | Heart |
61/61 | 45/61 | 87/56 | 40/56 | 87/55 | 52/54 | Blood |
57/59 | 43/59 | 03/57 | 23/56 | 45/56 | 32/55 | Hepatits |
50/85 | 98/84 | 02/85 | 57/84 | 11/83 | 21/83 | Vote |
87/64 | 00/65 | 23/61 | 56/56 | 89/55 | 79/56 | Mushroom |
31/67 | 00/68 | 90/68 | 20/68 | 08/67 | 27/68 | Liver |
00/90 | 59/90 | 00/93 | 55/92 | 43/92 | 33/93 | Breast |
00/60 | 32/66 | 50/66 | 20/66 | 05/66 | 40/66 | Sonar |
67/70 | 42/70 | 03/69 | 23/68 | 70/68 | 67/68 | German |
33/73 | 34/74 | 98/70 | 45/71 | 02/71 | 00/70 | Colic |
00/95 | 76/94 | 00/91 | 90/93 | 00/88 | 60/92 | Iris |
43/90 | 40/91 | 91/90 | 50/89 | 81/90 | 48/88 | wine |
4-4 نسبتهای مختلف اعداد بدون برچسب
به منظور ارزیابی تأثیر تعداد دادههای برچسبدار بر دقت طبقهبندی، مجموعهای از آزمایشها با نرخهای مختلف دادههای برچسبدار (از 10% تا 50%) انجام شده و سپس کارایی الگوریتم پیشنهادی با الگوریتم ماشین بردار پشتیبان نظارتشده مقایسه گردیده است. مجموعه تست به صورت جداگانه برای ارزیابی کارایی به کار گرفته شده است. شکل 3 کارایی الگوریتمها را با نرخهای مختلف روی چهار مجموعه داده نشان میدهد. همان طور که در شکل آمده است، وقتی مقدار دادههای برچسبدار
در دسترس افزایش مییابد، اختلاف بین الگوریتم SVM و الگوریتم پیشنهادی کاهش مییابد. حتی در بعضی از مجموعه دادهها الگوریتم ماشین بردار پشتیبان نظارتشده بهتر از الگوریتم پیشنهادی عمل میکند. همان طور که نشان داده شده است، الگوریتم پیشنهادی به طور قابل توجهی کارایی SVM را در حالتی که دادههای برچسبدار فقط 10 یا 20% است بهبود میدهد.
4-5 تأثیر انتخاب دادههای نزدیک به مرز تصمیم
در بیشتر مجموعه دادهها، برچسبزدن تمامی دادههای بدون برچسب نهتنها به بهبود کارایی طبقهبند پایه منجر نمیشود، بلکه میتواند دقت طبقهبندی را کاهش دهد که این کار همچنین زمان اجرای الگوریتم را افزایش میدهد. اگرچه نمونههای بدون برچسب دورتر از مرز تصمیم قابل اعتمادتر هستند، اما دارای اطلاعات نمیباشند. آنها نقش مهمی در بهبود مرز تصمیم ایفا نمیکنند و در نتیجه به جای اضافهکردن تمامی دادههای بدون برچسب به مجموعه آموزشی، فقط مجموعهای از دادههای بدون برچسب را اضافه میکنیم که از مقدار معینی به مرز تصمیم نزدیکتر باشند. در آزمایشها، میانگین فاصله دادههای بدون برچسب تا مرز تصمیم به عنوان مقدار آستانه در نظر گرفته شده است. به عبارت دیگر، دادههای بدون برچسبی که فاصله آنها تا مرز تصمیم کمتر یا مساوی میانگین فاصله باشند، به مجموعه آموزشی اضافه میگردند. چندین آزمایش برای نشاندادن این مسئله انجام شده است.
جدول 5 عملکرد طبقهبندی الگوریتم پیشنهادی را بر روی چندین مجموعه داده نشان میدهد. ستون 2 نشاندهنده دقت طبقهبند پیشنهادی در حالتی است که تمام دادههای بدون برچسب اضافه شدهاند. ستون 3، دقت طبقهبند الگوریتم پیشنهادی را در حالتی که فقط نمونههای بدون برچسب نزدیک به مرز تصمیم اضافه شدهاند نشان میدهد. همان طور که مشاهده میشود، الگوریتم پیشنهادی با انتخاب نمونههای نزدیک به مرز تصمیم در 6 تا از 10 مجموعه داده عملکرد بهتری را نشان میدهد. در این آزمایشها نرخ دادههای برچسبدار 10% در نظر گرفته شده است.
4-6 بحث و بررسی
همان طور که در جداول 3 و 4 مشاهده میشود، الگوریتم پیشنهادی با استفاده از نمونههای بدون برچسب، عملکرد طبقهبندی الگوریتم ماشین
(الف)
(ب)
(ج)
(د)
شکل 3: دقت الگوریتم پیشنهادی و SVM نظارتشده با نرخ دادههای برچسبدار از 10% تا 50% بر روی مجموعه دادههای مختلف.
شکل 4: مجموعه داده liver.
بردار پشتیبان نظارتشده را برای اکثر مجموعه دادهها بهبود داده
است. با این حال، با توجه به نتایج گزارششده برای مجموعه دادههای mushroom، liver و breast نشان داده میشود که الگوریتم پیشنهادی برای تعدادی از مجموعه دادهها به خوبی کار نمیکند. به طور نمونه مجموعه داده liver رسم شده و همان طور که در شکل 4 میتوان مشاهده کرد، توزیع دادههای هر دو کلاس همپوشانی زیادی دارند. از این رو پیداکردن نمونههای نزدیک به مرز تصمیم کار آسانی نیست. در نتیجه الگوریتم پیشنهادی در مقایسه با سایر الگوریتمها به خوبی کار نمیکند. در مقابل، برای مجموعه دادههایی که دارای توزیعی کاملاً مجزا هستند، الگوریتم پیشنهادی دارای عملکرد بهتری نسبت به سایر الگوریتمها میباشد. همچنین الگوریتم پیشنهادی در مجموعه دادههای با ابعاد بالا به علت استفاده از DBSCAN معمولاً کارایی خوبی ندارد.
جدول 5: ميانگين نرخ دقت الگوريتم پيشنهادي با انتخاب همه دادههاي
بدون برچسب و انتخاب نمونههاي نزديك به مرز تصميم.
دادههاي بدون برچسب انتخابي | همه دادههاي بدون برچسب | مجموعه داده |
37/70 | 37/70 | Heart |
05/62 | 62 | Blood |
81/46 | 79/46 | Hepatits |
79/87 | 80/87 | Vote |
86/65 | 66 | Mushroom |
15/71 | 07/70 | Liver |
57/88 | 03/83 | Breast |
23/53 | 54 | Sonar |
67/71 | 45/69 | German |
00/60 | 76/59 | Colic |
96/95 | 40/95 | iris |
40/89 | 22/89 | wine |
5- جمعبندی
در این مقاله، یک الگوریتم نیمهنظارتی خودآموز مطرح شد. در فرایند خودآموز به مجموعهای از نقاط بدون برچسب، برچسب اختصاص داده میشود. طبقهبند پایه مورد استفاده SVM است که الگوریتمی مبتنی بر حاشیه میباشد. مجموعهای از آزمایشها بر روی تعدادی مجموعه داده انجام شد و کارایی الگوریتم پیشنهادی مورد ارزیابی قرار گرفت. بر طبق نتایج آزمایشها نتیجه گرفته شد که الگوریتم پیشنهادی بهتر از دیگر الگوریتمها عمل میکند. نقاط بدون برچسبی که نسبتاً به مرز تصمیم نزدیکتر هستند در فرایند خودآموز برچسبدار شدند. اضافهشدن این نقاط به مجموعه برچسبدار تأثیر مثبتی بر روی پیداکردن مرز تصمیم بهینه داشت؛ زیرا این نقاط اگرچه نقاط مطمئنی نیستند و به علت نزدیکی به مرز تصمیم خطر تعلقداشتن به کلاس دیگر را دارند، اما نقاطی با اطلاعات بیشتر هستند. در نتیجه، این نقاط نسبت به نقاط دورتر، در رسیدن به بهبود کارایی طبقهبند مؤثرتر میباشند و اضافهکردن این نقاط به مجموعه دادههای برچسبدار در فرایند خودآموز در به دست آمدن مرز تصمیم بهینه کمک زیادی میکنند. جهت اطمینان از تشخیص درست برچسب علاوه بر استفاده از الگوریتم همسایگی DBSCAN، از مکانیزم انتخاب نمونهها از طریق ردکردن برچسب اشتباه استفاده شد. از معایب الگوریتم پیشنهادی، وابستگی آن به انتخاب مناسب چندین پارامتر است. همچنین به دلیل ساختار هندسی دایرهای DBSCAN، الگوریتم برای مجموعه دادههایی که نمونههای کلاسها همپوشانی زیادی دارند به خوبی کار نمیکند. کارهای آینده میتوانند در زمینه مجموعه طبقهبندی نیمهنظارتی دادههای نامتوازن و کلاندادهها باشند.
مراجع
[1] D. Wu, et al., "Self-training semi-supervised classification based on density peaks of data," Neurocomputing, vol. 275, pp. 180-191, Jan. 2018.
[2] N. Zeng, Z. Wang, H. Zhang, W. Liu, and F. E. Alsaadi,
"Deep belief networks for quantitative analysis of a gold immunochromatographic strip," Cognitive Computation, vol. 8,
no. 4, pp. 684-692, 2016.
[3] N. Zeng, Z. Wang, and H. Zhang, "Inferring nonlinear lateral flow immunoassay state-space models via an unscented Kalman filter," Science China Information Sciences, vol. 59, no. 11, Article ID: 112204, 10 pp., 2016.
[4] N. Zeng, H. Zhang, W. Liu, J. Liang, and F. E. Alsaadi, "A switching delayed PSO optimized extreme learning machine for short-term load forecasting," Neurocomputing, vol. 240, pp. 175-182, May 2017.
[5] Y. Cao, H. He, and H. H. Huang, "LIFT: a new framework of learning from testing data for face recognition," Neurocomputing, vol. 74, no. 6, pp. 916-929, May 2011.
[6] F. Pan, J. Wang, and X. Lin, "Local margin based semi-supervised discriminant embedding for visual recognition," Neurocomputing, vol. 74, no. 5, pp. 812-819, Feb. 2011.
[7] D. Mallis, E. Sanchez, M. Bell, and G. Tzimiropoulos, "Unsupervised learning of object landmarks via self-training correspondence," Advances in Neural Information Processing Systems, vol. 33, pp. 4709-4720, 2020.
[8] G. Zhang, J. Wang, G. Shi, J. Zhang, and W. Dou, "A semi-supervised classification method for hyperspectral images by triple classifiers with data editing and deep learning," in Proc. EIA Int. Conf. Cloud Computing, Smart Grid and Innovative Frontiers in Telecommunications, pp. 171-183, Beiging, China, 4-5 Dec. 2019.
[9] J. Tanha, M. Van Someren, and H. Afsarmanesh, "Boosting for multiclass semi-supervised learning," Pattern Recognition Letters, vol. 37, pp. 63-77, Feb. 2014.
[10] D. Zhang, L. Jiao, X. Bai, S. Wang, and B. Hou, "A robust semi-supervised SVM via ensemble learning," Applied Soft Computing, vol. 65, pp. 632-643, Apr. 2018.
[11] J. Tanha, "MSSBoost: a new multiclass boosting to semi-supervised learning," Neurocomputing, vol. 314, pp. 251-266, Nov. 2018.
[12] C. Blake and C. Merz, UCI Repository of Machine Learning Databases, http://www.ics.uci.edu/?mlearn/MLRepository.html, University of California. Department of Information and Computer Science, Irvine, CA, p. 55, 1998.
[13] Z. H. Zhou and M. Li, "Semi-supervised learning by disagreement," Knowledge and Information Systems, vol. 24, no. 3, pp. 415-439, 2010.
[14] A. Blum and T. Mitchell, "Combining labeled and unlabeled data with co-training," in Proc. of the 11th Annual Conf. on Computational Learning Theory, pp. 92-100, Madison, WN, USA, 24 – 26 Jul. 1998.
[15] C. X. Ling, J. Du, and Z. H. Zhou, "When does co-training work in real data?" in Proc. Pacific-Asia Conf. on Knowledge Discovery and Data Mining, pp. 596-603, Bangkok, Thailand, 27-30 Apr. 2009.
[16] Z. Jiang, S. Zhang, and J. Zeng, "A hybrid generative/discriminative method for semi-supervised classification," Knowledge-Based Systems, vol. 37, pp. 137-145, Jan. 2013.
[17] S. Sun, "A survey of multi-view machine learning," Neural Computing and Applications, vol. 23, no. 7-8, pp. 2031-2038, Feb. 2013.
[18] M. Li and Z. H. Zhou, "SETRED: self-training with editing," in Proc. Pacific-Asia Conf. on Knowledge Discovery and Data Mining, pp. 611-621, Hanoi, Vietnam, 18-20 May 2005.
[19] R. Chen, et al., "Semi-supervised anatomical landmark detection via shape-regulated self-training," Neurocomputing, vol. 471, pp. 335-345, Jan. 2022.
[20] Z. Yang and Y. Xu, "Laplacian twin parametric-margin support vector machine for semi-supervised classification," Neurocomputing, vol. 171, pp. 325-334, Jan. 2016.
[21] ش. پوربهرامی، ا. خالدی و ل. خانعلی، "الگوریتم جدید خوشهبندی ارسال داده در شبکههای حسگر بیسیم با استفاده از دایره آپولونیوس،" نشریه مهندسی برق و مهندسی کامپيوتر ايران، ب- مهندسی کامپیوتر، سال 17، شماره 3، صص. 226-219، پاییز 1398.
[22] ع. زاده بابایی، ع. باقری و خ. افشار، "ارائه یک الگوریتم خوشهبندی مبتنی بر چگالی با قابلیت کشف خوشههای با چگالی متفاوت در پایگاه دادههای مکانی،" نشریه مهندسی برق و مهندسی کامپيوتر ايران، ب- مهندسی کامپیوتر، سال 15، شماره 3، صص. 186-171، پاییز 1396.
[23] M. Ester, H. P. Kriegel, J. Sander, and X. Xu, "A density-based algorithm for discovering clusters in large spatial databases with noise," in Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining, KDD’96, pp. 226-231, Portland, ON, USA, 2-4 Aug. 1996.
[24] A. Lotfi, P. Moradi, and H. Beigy, "Density peaks clustering based on density backbone and fuzzy neighborhood," Pattern Recognition, vol. 107, Article ID: 107449, Nov. 2020.
[25] S. A. Seyedi, A. Lotfi, P. Moradi, and N. N. Qader, "Dynamic graph-based label propagation for density peaks clustering," Expert Systems with Applications, vol. 115, pp. 314-328, Jan. 2019.
[26] Y. Qin, Z. L. Yu, C. D. Wang, Z. Gu, and Y. Li, "A novel clustering method based on hybrid K-nearest-neighbor graph," Pattern Recognition, vol. 74, pp. 1-14, Feb. 2018.
[27] M. Emadi, J. Tanha, M. E. Shiri, and M. H. Aghdam, "A selection metric for semi-supervised learning based on neighborhood construction," Information Processing & Management, vol. 58,
no. 2, Article ID: 102444, Mar. 2021.
[28] S. Pourbahrami and L. M. Khanli, A Survey of Neighbourhood Construction Models for Categorizing Data Points, arXiv preprint arXiv:1810.03083, 2018.
[29] S. Khezri, J. Tanha, A. Ahmadi, and A. Sharifi, "STDS: self-training data streams for mining limited labeled data in non-stationary environment," Applied Intelligence, vol. 50, no. 5, pp. 1-20, 2020.
[30] X. Gu, "A self-training hierarchical prototype-based approach for semi-supervised classification," Information Sciences, vol. 535, pp. 204-224, Oct. 2020.
[31] M. M. Adankon and M. Cheriet, "Help-training for semi-supervised support vector machines," Pattern Recognition, vol. 44, no. 9, pp. 2220-2230, Sept. 2011.
[32] M. Emadi and J. Tanha, "Margin-based semi-supervised learning using apollonius circle," in Proc. Int Conf. on Topics in Theoretical Computer Science, pp. 48-60, Tehran, Iran, 26-28 Aug. 2020.
[33] S. Pourbahrami, L. M. Khanli, and S. Azimpour, "A novel and efficient data point neighborhood construction algorithm based on Apollonius circle," Expert Systems with Applications, vol. 115, pp. 57-67, Jan. 2019.
[34] S. Pourbahrami, M. A. Balafar, L. M. Khanli, and Z. A. Kakarash, "A survey of neighborhood construction algorithms for clustering and classifying data points," Computer Science Review, vol. 38, Article ID: 100315, Nov. 2020.
[35] J. Tanha, M. van Someren, and H. Afsarmanesh, "Semi-supervised self-training for decision tree classifiers," International J. of Machine Learning and Cybernetics, vol. 8, no. 1, pp. 355-370, 2017.
[36] T. Joachims, "Transductive inference for text classification using support vector machines," in Proc. of The 26th Int. Conf. on Machine Learning, ICML'99, pp. 200-209, 1999.
[37] M. Belkin, P. Niyogi, and V. Sindhwani, "Manifold regularization: a geometric framework for learning from labeled and unlabeled examples," J. of Machine Learning Research, vol. 7, no. 85, pp. 2399-2434, 2006.
منا عمادی تحصيلات خود را در مقاطع كارشناسي و كارشناسي ارشد مهندسی کامپیوتر در سالهاي 1388 و 1390 از دانشگاه آزاد اسلامی واحد اراک و در مقطع دكتري مهندسی کامپیوتر- سیستمهای نرم افزاری در سال 1400 از دانشگاه آزاد اسلامی واحد بروجرد به پايان رسانده است و هماكنون استادیار دانشكده مهندسي كامپيوتر دانشگاه پیام نور ميباشد. زمينه تحقیقاتی مورد علاقه ایشان در زمینه یادگیری ماشین و دادهکاوی میباشد.
جعفر تنها تحصيلات خود را در مقاطع كارشناسي و كارشناسي ارشد علوم کامپیوتر از دانشگاه امیرکبیر و در مقطع دكتري هوش مصنوعی دانشگاه آمستردام هلند به پایان رسانده است. و هماکنون دانشیار دانشگاه تبریز میباشد. زمینههای تحقیقاتی مورد علاقه ایشان داده کاوی یادگیری ماشین میباشد.
محمد ابراهیم شیری دکترای علوم کامپیوتر. استادیار دانشگاه صنعتی امیرکبیر زمینههای تحقیقاتی ایشان داده کاوی و هوش مصنوعی میباشد.
مهدی حسینزاده اقدم دکترای تخصصی مهندسی کامپیوتر- هوش مصنوعی، دانشگاه علم و صنعت ایران را در سال 1395 اخذ نموده انست. در حال حاضر استادیار دانشگاه بناب میباشد. زمینههای تحقیقاتی مورد علاقه ایشان داده کاوی ، یادگیری ماشین، بازیابی اطلاعات و سیستمهای توصیهگر می باشد.