یادگیری متریک بر اساس فاصله χ2 سریع برای دسته‌بندی داده‌های هیستوگرامی با دسته‌بندی کننده KNN

نوع مقاله : علمی-پژوهشی

نویسندگان

دانشکده مهندسی برق - دانشگاه صنعتی امیرکبیر

چکیده

مقایسه داده‌ها یک مسأله بنیادی و پرکاربرد در یادگیری ماشین است. در دهه گذشته تحقیقات فراوانی در زمینه یادگیری متریک انجام شده است؛ از کاربردهای یادگیری متریک می‌توان به خوشه‌بندی و دسته‌بندی داده‌ها اشاره کرد. در این مقاله یک روش یادگیری متریک مناسب برای استفاده در مسائل بینایی ماشین ارائه می‌شود. اکثر ویژگی‌هایی که در بینایی ماشین استفاده می‌شوند، هیستوگرامی هستند؛ اما روش‌های یادگیری متریک اغلب بر مبنای فاصله ماهالانوبیس طراحی شده‌اند که در ویژگی‌های هیستوگرامی کارایی مناسبی ندارد. در این تحقیق یک روش جدید یادگیری متریک برای داده‌های هیستوگرامی بر مبنای فاصله مربع کای (χ2) اصلاح شده ارائه می‌شود. فاصله χ2 در دسته‌بندی داده‌های هیستوگرامی دارای دقت بالاتری نسبت به فاصله اقلیدسی است، اما هزینه محاسباتی آن نیز بالاتر است. در این مقاله یک رابطه تقریبی برای فاصله χ2 پیشنهاد می‌شود و بخشی از محاسبات را به مرحله استخراج ویژگی (که به‌صورت غیربرخط قابل محاسبه است) منتقل می‌کند؛ به این ترتیب سرعت مقایسه ویژگی‌ها افزایش می‌یابد. آزمایش‌ها بر روی پایگاه‌های داده مختلف نشان می‌دهد که روش یادگیری متریک پیشنهادی دارای دقت بالایی در دسته‌بندی داده‌های هیستوگرامی مختلف نسبت به روش‌های موجود است. همچنین معیار تقریبی برای فاصله χ2، با حفظ دقت، سرعت مقایسه داده‌ها را 2.5 برابر افزایش می‌دهد.

کلیدواژه‌ها

عنوان مقاله [English]

Metric Learning based on Fast χ2 Distance for Histogram Data Classification via KNN Classifier

نویسندگان [English]

  • H. Sadeghi
  • Abolghasem-A. Raie
Department of Electrical Engineering, Amirkabir University of Technology, Tehran, Iran
چکیده [English]

Data comparison is a fundamental problem in machine learning research. Since, metric learning has various applications in clustering and classification problems, it is attracted much attention in the last decades. In this paper, an appropriate metric learning method is presented to utilize in machine vision problems. Common features in machine vision are often histogram; however, metric learning methods are usually designed based on Mahalanobis distance which is not applicable in histogram features. In this study, a new metric learning method based on modified chi-squared distance (χ2) for histogram data is presented. In histogram data classification, χ2 distance is more accurate than Euclidean one; however, its computational cost is higher than Euclidean distance. In this paper, a χ2 distance approximated formulation where a part of its computations is moved into the feature extraction step in offline phase is proposed. Consequently, computational cost of feature comparison is reduced. Experiments on different datasets show that the proposed metric learning method is more accurate than the existing ones in histogram data classification. Moreover, the approximated χ2 distance increases feature comparison speed about 2.5 times without loss of accuracy.

کلیدواژه‌ها [English]

  • Metric learning
  • fast chi-squared distance
  • histogram classification
  • KNN classifier

مراجع

[1] B. Kulis, “Metric learning: a survey,” Foundations and Trends® in Machine Learning, vol. 5, no. 4, pp. 287-364, 2013.
[2] A. Bellet, A. Habrard and M. Sebban, “A survey on metric learning for feature vectors and structured data,” ArXiv Preprint ArXiv, pp. 1306.6709, 2013.
[3] C. Jin and S. W. Jin, “Image distance metric learning based on neighborhood sets for automatic image annotation,” Journal of Visual Communication and Image Representation, vol. 34, pp. 167-175, 2016.
[4] J. Hu, J. Lu and Y. Tan, “Sharable and individual multi-view metric learning,” IEEE Transactions on Pattern Analysis and Machine Intelligence, no. 99, 2017 (In Press).
[5] H. Yan, “Kinship verification using neighborhood repulsed correlation metric learning,” Image and Vision Computing, vol. 60, no. 1, pp. 91-97, 2017.
[6] H. Yan, and J. Hu, “Video-based kinship verification using distance metric learning,” Pattern Recognition, vol. 75, pp.15-24, 2018.
[7] E. P. Xing, M. I. Jordan, S. J. Russell and A. Y. Ng, “Distance metric learning with application to clustering with side-information,” In Advances in Neural Information Processing Systems (NIPS), vol. 15, pp. 521-528, 2003.
[8] M. Schultz and T. Joachims, “Learning a distance metric from relative comparisons,” in Advances in Neural Information Processing Systems (NIPS), vol. 16, pp. 41-48, 2004.
[9] J. V. Davis, B. Kulis, P. Jain, S. Sra and I. S. Dhillon, “Information theoretic metric learning,” In Proceedings of the 24th International Conference on Machine Learning (ICML), pp. 209–216, 2007.
[10] G. Kunapuli and J. Shavlik, “Mirror descent for metric learning: a unified approach,” In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Database (ECML/PKDD), pp. 859–874, 2012.
[11] Q. Qian, R. Jin, J. Yi, L. Zhang and S. Zhu, “Efficient distance metric learning by adaptive sampling and mini-batch stochastic gradient descent (SGD),” Machine Learning, vol. 99, no. 3, pp. 353-372, 2015.
[12] M. T. Law, N. Thome and M. Cord, “Learning a distance metric from relative comparisons between quadruplets of images,” International Journal of Computer Vision, vol. 121, no. 1, pp. 65-94, 2017.
[13] B. Nguyen, C. Morell and B. D. Baets, “Supervised distance metric learning through maximization of the Jeffrey divergence,” Pattern Recognition, vol. 64, pp. 215-225, 2017.
[14] K. Q. Weinberger and K. S. Lawrence, “Distance metric learning for large margin nearest neighbor classification,” Journal of Machine Learning Research, vol. 10, pp. 207-244, 2009.
[15] Y. Ying and P. Li, “Distance metric learning with eigenvalue optimization,” Journal of Machine Learning Research, vol. 13, no. 1, pp. 1–26, Jan. 2012.
[16] W. Zuo, F. Wang, D Zhang, L. Lin, Y. Huang, D. Meng and L. Zhang, “Distance metric learning via iterated support vector machines,” IEEE Transactions on Image Processing, vol. 26, no. 10, pp. 4937-4950, 2017.
[17] Z. Hao, Y. Ruan, Y. Xiao and B. Liu, “A multi-task-based classification framework for multi-instance distance metric learning,” Neurocomputing, vol. 275, pp. 418-429, 2018.
[18] وحیده منعمی‌زاده و جواد حمیدزاده، «جستجوی k نزدیک‌ترین همسایه تقریبی با روش ترکیب خطی»، مجله مهندسی برق دانشگاه تبریز، جلد 47، شماره 3، صفحات 1249-1237، پاییز 1396.
[19] مهرداد حیدری ارجلو، سید قدرت‌اله سیف‌السادات و مرتضی رزاز، «یک روش هوشمند تشخیص جزیره در شبکه‌ی توزیع دارای تولیدات پراکنده مبتنی بر تبدیل موجک و نزدیک‌ترین K-همسایگی (KNN)»، مجله مهندسی برق دانشگاه تبریز، جلد 19، شماره 1، صفحات 15-26، 1392.
[20] D. Kedem, S. Tyree, F. Sha, G. R. Lanckriet and K. Q. Weinberger, “Non-linear metric learning,” In Advances in Neural Information Processing Systems (NIPS), vol. 25, pp. 2573-2581, 2012.
[21] نصیبه اسدی‌پرور ماسوله و اسدالله شاه‌بهرامی، «تخمین خودکار سن از روی تصویر چهره با تلفیق ویژگی‌های آماری و بافت»، مجله مهندسی برق دانشگاه تبریز، جلد 47، شماره 3، صفحات 842-829، پاییز 1396.
[22] T. Ahonen, A. Hadid and M. Pietikäinen, “Face recognition with local binary patterns,” In European Conference on Computer Vision (ECCV-2004), pp. 469-481, Springer, Berlin, Heidelberg, 2004.
[23] G. Zhang, X. Huang, S. Z. Li, Y. Wang and X. Wu, “Boosting local binary pattern (LBP)-based face recognition,” In Advances in Biometric Person Authentication, pp. 179-186, Springer Berlin Heidelberg, 2004.
[24] G. E. Hinton, N. Srivastava, A. Krizhevsky, I. Sutskever and R. Salakhutdinov, “Improving neural networks by preventing co-adaptation of feature detectors,” Arxiv Preprint Arxiv, pp. 1207-0580, 2012.
[25] L. V. D. Maaten, M. Chen, S. Tyree and K. Q. Weinberger, “Learning with marginalized corrupted features,” In International Conference on Machine Learning (ICML), pp. 410-418, 2013.
[26] S. Wager, S. Wang and P. Liang, “Dropout training as adaptive regularization,” In Advances in Neural Information Processing Systems (NIPS), vol. 26, pp. 351-359, 2013.
[27] Q. Qian, J. Hu, R. Jin, J. Pei and S. Zhu, “Distance metric learning using dropout: a structured regularization approach,” In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 323-332, 2014.
[28] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.
[29] B. Shaw, B. C. Huang and T. Jebara, “Learning a distance metric from a network,” In Advances in Neural Information Processing Systems (NIPS), vol. 24, pp. 1899-1907, 2011.
[30] Q. Qian, R. Jin, S. Zhu and Y. Lin, “Fine-grained visual categorization via multi-stage metric learning,” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3716-3724, 2015.
[31] G. Chechik, V. Sharma, U. Shalit and S. Bengio, “Large scale online learning of image similarity through ranking,” Journal of Machine Learning Research, vol. 11, pp. 1109-1135, 2010.
[32] K. Saenko, B. Kulis,M. Fritz and T. Darrell, “Adapting visual category models to new domains,” In European Conference on Computer Vision (ECCV-2010), pp. 213–226, 2010.
[33] O. Pele and M. Werman, “The quadratic-chi histogram distance family,” In European Conference on Computer Vision (ECCV-2010), pp. 749-762. Springer, Berlin, Heidelberg, 2010.
[34] J. Alcalá-Fdez, L. Sánchez, S. García, M. D. Jesus, S. Ventura, J. Garrell, J. Otero, C. Romero, J. Bacardit, V. Rivas, J. Fernández and F. Herrera, “KEEL: a software tool to assess evolutionary algorithms for data mining problems,” Soft Computing, vol. 13, no. 3, pp. 307–318, 2009.
[35] P. Lucey, J. F. Cohn, T. Kanade, J. Saragih, Z. Ambadar and I. Matthews, “The extended cohn-kanade dataset (ck+): a complete dataset for action unit and emotion-specified expression,” IEEE Computer Society Conf. Computer Vision and Pattern Recognition-Workshops, pp. 94-101, June 2010,
[36] M. J. Lyons, J. Budynek and S. Akamatsu, “Automatic classification of single facial images,” IEEETransactions on Pattern Analysis and Machine Intelligence, vol. 21, no. 12, pp. 1357-1362, 1999.
[37] P. Belhumeur, J. Hespanha and D. Kriegman, “Eigenfaces vs. fisherfaces: Recognition Using Class Specific Linear Projection,” IEEETransactions on Pattern Analysis and Machine Intelligence, vol. 19, no. 7, pp. 711-720, 1997.
[38] W. Yang, L. Xu, X. Chen, F. Zheng and Y. Liu, “Chi-squared distance metric learning for histogram data,” Mathematical Problems in Engineering, vol. 2015, 2015.
[39] T. Ojala, M. Pietikäinen and D. Harwood, “A comparative study of texture measures with classification based on featured distributions,” Pattern Recognition., vol. 29, no. 1, pp. 51-59., 1996.
[40] N. S. Vu and A. Caplier, “Enhanced patterns of oriented edge magnitudes for face recognition and image matching,” IEEETransactions on Image Processing, vol. 21, no. 3, pp. 1352-1365, 2012.
[41] N. Dalal and B. Triggs, “Histograms of oriented gradients for human detection,” In 2005 IEEE Computer Society Conf. Computer Vision and Pattern Recognition (CVPR'05), vol. 1, pp. 886-893, June 2005.

فایل ها

هم رسانی

ارجاع به این مقاله

آمار