Manuscript ID : 14000111272837 Visit : 4613 Page: 164 - 172

Article Type: Original Research

A Novel Method Based on Non-Negative Matrix Factorization for Dimensions Reduction

Subject Areas : electrical and computer engineering

Mehdi Hosseinzadeh Aghdam ¹ , مرتضی آنالویی ² , Jafar Tanha ³

1 - University of Bonab
2 -
3 -

Received: 2021-03-31 Accepted : 2021-12-13 Published : 2022-08-20

Keywords: Dimension reduction, Non-negative matrix factorization, Frobenius norm, Multiplicative update rules, Text clustering,

Abstract :

Machine learning has been widely used over the past decades due to its wide range of applications. In most machine learning applications such as clustering and classification, data dimensions are large and the use of data reduction methods is essential. Non-negative matrix factorization reduces data dimensions by extracting latent features from large dimensional data. Non-negative matrix factorization only considers how to model each feature vector in the decomposed matrices and ignores the relationships between feature vectors. The relationships between feature vectors provide better factorization for machine learning applications. In this paper, a new method based on non-negative matrix factorization is proposed to reduce the dimensions of the data, which sets constraints on each feature vector pair using distance-based criteria. The proposed method uses the Frobenius norm as a cost function to create update rules. The results of experiments on the data sets show that the proposed multiplicative update rules converge rapidly and give better results than other algorithms.

References:

[1] R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification, Wiley-Interscience, Hoboken, NJ, 2nd Edition, 2000.
[2] D. D. Lee and H. S. Seung, "Learning the parts of objects by nonnegative matrix factorization," Nature, vol. 401, no. 6755, pp. 788-791, Jan. 1999.
[3] D. Kuang, J. Choo, and H. Park, "Nonnegative matrix factorization for interactive topic modeling and document clustering," In M. Emre Celebi (Ed.), Partitional Clustering Algorithms, pp. 215-243, Springer Cham, 2015.
[4] S. Z. Li, X. Hou, H. Zhang, and Q. Cheng, "Learning spatially localized, parts-based representation," in Proc. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, CVPR'01, pp. 207-212, Kauai, HI, USA, 8-14. Dec. 2001.
[5] W. Xu, X. Liu, and Y. Gong, "Document clustering based on nonnegative matrix factorization," in Proc. of the 26th Annual Int ACM SIGIR Conf. on Research and Development in Information Retrieval, pp. 267-273, Toronto, Canada, 28 Jul.-1 Aug. 2003.
[6] D. D. Lee and H. S. Seung, "Algorithms for non-negative matrix factorization," in Proc. of the 2001 Conf. Advances in Neural Information Processing Systems, pp. 556-562, Vancouver, Canada, 3-8 Dec. 2001.
[7] R. Sandler and M. Lindenbaum, "Nonnegative matrix factorization with earth mover's distance metric for image analysis," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 33, no. 8, pp. 1590-1602, Aug. 2011.
[8] V. P. Pauca, J. Piper, and R. J. Plemmons, "Nonnegative matrix factorization for spectral data analysis," Linear Algebra and Its Applications, vol. 416, no. 1, pp. 29-47, Jul. 2006.
[9] M. H. Aghdam and M. D. Zanjani, "A novel regularized asymmetric non-negative matrix factorization for text clustering," Information Processing & Management, vol. 58, no. 6, Article ID: 102694, 6 pp., Nov. 2021.
[10] A. J. Mohammed, Y. Yusof, and H. Husni, "Document clustering based on firefly algorithm," J. of Computer Science, vol. 11, no. 3, pp. 453-465, Mar. 2015.
[11] A. J. Mohammed, Y. Yusof, and H. Husni, "Determining number of clusters using firefly algorithm with cluster merging for text clustering," in Proc. Int. Visual Informatics Conf., pp. 14-24, Bangi, Malaysia, 17- 19 Nov. 2015.
[12] A. Abraham, S. Das, and A. Konar, "Document clustering using differential evolution," in Proc. IEEE Int. Conf. on Evolutionary Computation, pp. 1784-1791, Vancouver, Canada, 16-21 Jul. 2006.
[13] A. Kumar and H. Daum´e, "A co-training approach for multi-view spectral clustering," in Proc. 28th Int. Conf. on Machine Learning, ICML’11, pp. 393-400, Bellevue, WA, USA, 28 Jun.-2 Jul. 2011.
[14] A. Y. Ng, M. I. Jordan, and Y. Weiss, "On spectral clustering: analysis and an algorithm," in Proc. of the 2002 Conf. Advances in Neural Information Processing Systems, pp. 849-856, Vancouver, Canada, 9-14 Dec. 2002.
[15] D. Yogatama and K. Tanaka-Ishii, "Multilingual spectral clustering using document similarity propagation," in Proc. of the Conf. on Empirical Methods in Natural Language Processing, Association for Computational Linguistics, vol. 2, pp. 871-879, Singapore, 6-7 Aug. 2009.
[16] D. Toli´c, N. Antulov-Fantulin, and I. Kopriva, "A nonlinear orthogonal non-negative matrix factorization approach to subspace clustering," Pattern Recognition, vol. 82, pp. 40-55, Oct. 2018.
[17] C. C. Aggarwal and C. Zhai, Mining Text Data, Springer Science & Business Media, 2012.
[18] F. Shahnaz, M. W. Berry, V. P. Pauca, and R. J. Plemmons, "Document clustering using nonnegative matrix factorization," Information Processing & Management, vol. 42, no. 2, pp. 373-386, Mar. 2006.
[19] E. F. Gonzalez and Y. Zhang, Accelerating the Lee-Seung Algorithm for Nonnegative Matrix Factorization, Tech. Rep., 2005.
[20] N. Gillis and S. A. Vavasis, "Fast and robust recursive algorithms for separable nonnegative matrix factorization," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 36, no. 4, pp. 698-714, Nov. 2013.
[21] K. Huang, N. D. Sidiropoulos, and A. Swami, "Non-negative matrix factorization revisited: uniqueness and algorithm for symmetric decomposition," IEEE Trans. on Signal Processing, vol. 62, no. 1, pp. 211-224, Oct. 2013.
[22] K. Kimura, M. Kudo, and Y. Tanaka, "A column-wise update algorithm for nonnegative matrix factorization in bregman divergence with an orthogonal constraint," Machine Learning, vol. 103, no. 2, pp. 285-306, May 2016.
[23] F. Shang, L. Jiao, and F. Wang, "Graph dual regularization non-negative matrix factorization for co-clustering," Pattern Recognition, vol. 45, no. 6, pp. 2237-2250, Jun. 2012.
[24] X. Ma, P. Sun, and G. Qin, "Nonnegative matrix factorization algorithms for link prediction in temporal networks using graph communicability," Pattern Recognition, vol. 71, pp. 361-374, Nov. 2017.
[25] A. David and S. Vassilvitskii, "K-means++: The advantages of careful seeding," in Proc. of the 18th annual ACM-SIAM Symp. on Discrete Algorithms, SODA’07, pp. 1027-1035, New Orleans, LA, USA, 7-9 Jan. 2007.
[26] J. N. Myhre, K. Ø. Mikalsen, S. Løkse, and R. Jenssen, "Robust clustering using a knn mode seeking ensemble," Pattern Recognition, vol. 76, pp. 491-505, Apr. 2018.
[27] W. Jiang, W. Liu, and F. L. Chung, "Knowledge transfer for spectral clustering," Pattern Recognition, vol. 81, pp. 484-496, Sept. 2018.
[28] U. Von Luxburg, "A tutorial on spectral clustering," Statistics and Computing, vol. 17, no. 4, pp. 395-416, Aug. 2007.
[29] J. V. Munoz, M. A. Goncalves, Z. Dias, and R. da S. Torres, "Hierarchical clustering-based graphs for large scale approximate nearest neighbor search," Pattern Recognition, vol. 96, Article ID: 106970, Dec. 2019.
[30] L. Rokach and O. Maimon, Clustering Methods, in Data Mining and Knowledge Discovery Handbook. Springer, pp. 321-352, 2005.
[31] H. Xiong and D. Kong, "Elastic nonnegative matrix factorization," Pattern Recognition, vol. 90, pp. 464-475, Jun. 2019.
[32] N. X. Vinh, J. Epps, and J. Bailey, "Information theoretic measures for clusterings comparison: variants, properties, normalization and correction for chance," J. of Machine Learning Research, vol. 11, pp. 2837-2854, Dec. 2010.
[33] Z. Yang, R. Algesheimer, and C. J. Tessone, "A comparative analysis of community detection algorithms on artificial networks," Scientific Reports, vol. 6, no. 1, pp. 1-18, Aug. 2016.
[34] T. M. Mitchell, "Machine learning and data mining," Communications of the ACM, vol. 42, no. 11, pp. 30-36, Nov. 1999.

Full-Text:

معرفي يک روش جديد خوشه‌يابي خودکار

مقاله پژوهشی

ارائه روشی جدید بر مبنای تجزیه ماتریس غیر منفی برای کاهش ابعاد

مهدی حسین‎زاده اقدم، مرتضی آنالویی و جعفر تنها

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

کلیدواژه: کاهش ابعاد، تجزیه ماتریسی غیر منفی، نرم فروبنیوس، قوانین
به روز رسانی، خوشه‎بندی متن.

1- مقدمه

در بسیاری از مسایل مانند بازیابی اطلاعات، بینایی ماشین و شناسایی الگو، داده‎های ورودی ابعاد زیادی دارند که باعث می‌شود فرایند یادگیری با مشکل روبه‌رو شود [1]. برای حل این چالش از روش‌های تجزیه ماتریسی به عنوان یک رویکرد جدید برای نمایش داده‎ها استفاده می‌شود و ایده اصلی در این روش‌ها پیداکردن دو یا چند ماتریس با ابعاد کم است، به طوری که بتوان با استفاده از ضرب آنها ماتریس اصلی را ساخت. روش‌های اولیه ارائه‌شده برای تجزیه ماتریس عبارت هستند از تجزیه- LU، تجزیه- QR و تجزیه مقادیر ویژه ²(SVD).

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

تحقیقات نشان داده که از نظر فیزیولوژیکی و روان‌شناسی، مغز انسان به صورت نمایش مبتنی بر بخش‎بندی است [2]. از این رو محققین برای مدل‌سازی بهتر یادگیری مبتنی بر بخش‌بندی در شناسایی چهره و نمایش متون از روش تجزیه ماتریس غیر منفی ³(NMF) به عنوان یک راهکار استفاده کردند [3]. در روش NMF هدف، پیداکردن دو ماتریس غیر منفی است به طوری که حاصل‌ضرب آنها تقریبی از ماتریس اصلی باشد و از محدودیت غیر منفی بودن ماتریس‌های تجزیه‌شده برای نمایش مبتنی بر بخش‌بندی استفاده می‌شود، زیرا تنها اجازه عملیات جمع را می‌دهد. روش NMF نشان داده که در تشخیص چهره [4] و خوشه‌بندی متن [5] نسبت به SVD برتری دارد.

روش قوانین به روز رسانی ضربی⁴ در NMF، همگرایی الگوریتم و غیر منفی بودن ماتریس‌های تجزیه‌شده را تضمین می‌کند [6]. روش قوانین به روز رسانی ضربی به دلیل به دست آوردن نتایج خوب در مجموعه داد‎های بزرگ، بسیار مورد استقبال قرار گرفته است ولی این روش تنها محدودیت غیر منفی بودن را به ماتریس‌های تجزیه‌شده اعمال می‌کند که در عمل ممکن است در بعضی از مسایل کافی نباشد. به همین دلیل محققین در این زمینه تحقیقاتی را برای پیشنهاد الگوریتم‌های جدید انجام داده‌اند [7].

روش تجزیه ماتریس غیر منفی با محدودیت ⁵(CNMF)، جزء مهم‌ترین روش‌ها در NMF است که محدودیت‌ها را به صورت عبارات قاعده‌مند اعمال می‌کند [8]. در این روش بیشتر از نرم 1L و نرم 2L برای قاعده‌مندکردن استفاده می‌شود. از نرم 1L برای کم‌کردن پراکندگی ماتریس‌های تجزیه‌شده و از نرم 2L برای جلوگیری از بیش‌برازش استفاده می‌گردد. در روش CNMF محدودیت‌ها تنها بر روی سطرها یا ستون‌ها اعمال می‌شوند و روابط بین سطرها یا ستون‌ها در نظر گرفته نمی‌شود؛ در صورتی که این روابط در بسیاری از مسایل وجود دارند، مخصوصاً زمانی که ماتریس‌های تجزیه‌شده ویژگی‌ها را نشان می‌دهند. از این مسایل می‌توان به سیستم‌های توصیه‎گر و خوشه‌بندی تصویر و متن اشاره نمود.

خوشه‌بندی، فرایند تقسیم‌بندی مجموعه‌ای از داده‌ها در خوشه‌های متمایز بر اساس شباهت محتوای آنها است [9] تا [11] که از آن در سازمان‌دهی، استخراج، خلاصه‌سازی و بازیابی متون استفاده می‌شود [12]. خوشه‌بندی متن یک روش برای پیداکردن نزدیک‌ترین همسایگی برای هر متن در یک مجموعه از متون می‌باشد. در ابتدا از خوشه‌بندی متن برای بهبود دقت سامانه‌های بازیابی اطلاعات استفاده می‌شد ولی امروزه از خوشه‌بندی برای جستجوی یک مجموعه از متون و نرمال‌سازی نتایج داده‌شده توسط موتورهای جستجوی استفاده می‌گردد. اگرچه تحقیقات زیادی در زمینه خوشه‌بندی انجام شده است، ولی با این حال بسیاری از این روش‌ها نیاز به بهبود دارند. خوشه‌بندی طیفی یکی از روش‌هایی است که از بخش‌بندی ماتریس گراف استفاده می‌کند [13]. این روش در مقایسه با روش‌های استاندارد خوشه‌بندی، توانایی شناسایی توزیع غیر محدب را دارد [14] و [15]. در این روش با توجه به مجموعه داده‎ها، یک گراف بدون جهت وزن‌دار برای پیداکردن خوشه‌بندی بهینه با در نظر گرفتن مقادیر ویژه و بردارهای ویژه گراف ساخته می‌شود. NMF با نگاشت ماتریس داده به فضای معنای می‌تواند روش مناسبی برای خوشه‌بندی باشد [16].

در این مقاله یک روش جدید تجزیه ماتریس غیر منفی مبتنی بر نرم فروبنیوس ⁶(FNMF) برای کاهش ابعاد و خوشه‌بندی ارائه ‌شده است. در روش پیشنهادی، نرم فروبنیوس به عنوان تابع هزینه در نظر گرفته ‌شده و قوانین به روز رسانی ضربی جدیدی برای تجزیه‌کردن ماتریس‎ها پیشنهاد گردیده است. در روش پیشنهادی، ویژگی‌های معنایی با استفاده از قوانین به هنگام‎سازی یاد گرفته می‎شوند و با استفاده از روابط بین بردارهای ویژگی، کاهش بهتری با حفظ محدودیت‌های اعمال‌‌شده انجام می‌گردد. برخلاف روش‌های دیگر، روش پیشنهادی بعد از تجزیه ماتریس اصلی، روابط موجود را حفظ می‌کند. اثبات همگرایی قوانین به روز رسانی پیشنهادشده و تحلیل پیچیدگی زمانی روش پیشنهادی در مقایسه با روش اولیه NMF نشان می‌دهد که اعمال محدودیت‌های جدید باعث افزایش پیچیدگی زمانی نمی‌شود و الگوریتم پیشنهادی سریع همگرا می‌گردد. نتایج پیاده‌سازی‌ها نشان‌دهنده برتری روش پیشنهادی در کاهش ابعاد و خوشه‌بندی نسبت به روش‌های دیگر است.

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

2- پیش‌زمینه

خوشه‌بندی، دسته‌بندی داده‌ها با ساختارهای معنایی یکسان در خوشه‌های مشابه است که هم می‌تواند به صورت سلسله‌مراتبی و هم
به صورت بخش‌بندی باشد [3]. روش NMF می‌تواند داده‌ها را بر اساس شباهت ویژگی‌های معنایی استخراج‌شده دسته‌بندی کند [17]. ترکیب خطی بردارهای ویژگی استخراج‌شده در روش NMF غیر منفی است که نشان می‌دهد فقط می‌توان از عملگر جمع در ترکیب استفاده کرد؛ بنابراین هر داده می‌تواند به صورت ترکیب جمعی ویژگی‌های معنایی نشان داده شود و خوشه‌بندی می‌تواند در فضای ترکیب خطی بردارهای ویژگی انجام گردد. هر نمونه داده در ابتدا به صورت ویژگی‌ها نشان داده می‌شود. بعد از عملیات پیش‌پردازش در مجموعه داده‌ها، یک سری ویژگی‌ها می‌مانند که با استفاده از آنها بردار ویژگی‌ها ساخته می‌شود. همان طور که گفته شد، روش NMF، ماتریس اصلی را به دو ماتریس و ماتریس تجزیه می‌کند که هر دوی آنها غیر منفی هستند .

NMF می‌تواند داده‌ها را در یک سیستم برداری جدید که بر اساس تحلیل ماتریس اولیه است نمایش دهد. در ماتریس اولیه، سطرها داده‌ها را نمایش می‌دهند و ستون‌ها معادل با ویژگی‌ها هستند. این ماتریس، تبدیل به دو ماتریس می‌شود که ماتریس‌های تجزیه‌شده، معمولاً کوچک‌تر از ماتریس اصلی هستند و از این طریق یک نمایش فشرده از ماتریس اصلی ایجاد می‌گردد. اگر سطرهای ماتریس اصلی، داده‌ها باشند آن گاه می‌توان ستون‌های ماتریس تجزیه‌شده دوم را به عنوان بردارهای پایه برای تشکیل داده‌ها در نظر گرفت که در این حالت هر سطر ماتریس تجزیه‌شده اول، میزان مشارکت هر پایه را در تشکیل یک نمونه داده نشان می‌دهد. در این روش بردارها، برچسب‌های خوشه‌ها را نشان می‌دهند و از این رو می‌توان عضویت هر نمونه داده در هر خوشه را به وسیله تعیین بزرگ‌ترین مؤلفه بردار معادل در ماتریس تجزیه‌شده اول تعیین کرد. مختصات هر نمونه داده در هر بردار همیشه غیر منفی است. نمایش داده‌ها به صورت ترکیب تجمعی از مفاهیم معنایی، درک بهتری را برای خوشه‌بندی فراهم می‌کند و به همین دلیل نگاشت NMF برای خوشه‌بندی بسیار مناسب است [18]. قوانین به روز رسانی ضربی در روش اولیه NMF، غیر منفی بودن ماتریس‌های تجزیه‌شده و همگراشدن آنها به ماتریس داده اصلی را تضمین می‎کنند [6]. همگراشدن این قوانین به کمینه محلی اثبات شده و این قوانین نتایج خوبی را در مجموعه داده‌های بزرگ تولید می‌کنند [19]. با وجود این، روش اولیه NMF تنها محدودیت غیر منفی بودن را در تجزیه اعمال می‌کند که در بعضی کاربردها کافی نیست. به همین خاطر الگوریتم‌های جدیدی بر مبنای قوانین به روز رسانی ضربی برای افزایش کارایی ارائه شده است [20] تا [22]. تجزیه ماتریس غیر منفی منظم ⁷(RNMF) از روش‌هایی است که محدودیت‌هایی را به صورت متغیرهای منظم در فرایند تجزیه اعمال می‌کند [23]. در این روش، این محدودیت‌ها تنها بر روی هر کدام از بردارهای ویژگی اعمال می‌شود و روابط بین آنها را در نظر نمی‌گیرد. این روابط در بسیاری از کاربردها مانند خوشه‌بندی متن وجود دارند.

نرم فروبنیوس تابع هزینه‎ای است که اکثراً برای ارزیابی تقریب ماتریس‌های تجزیه‌شده به کار می‌رود. نرم فروبنیوس مربع فاصله اقلیدسی بین دو ماتریس است

(1)

این تابع نسبت به تک‌تک ماتریس‌های و محدب⁸ است ولی نسبت به هر دو محدب نیست [24]، پس پیداکردن کمینه سراسری برای این تابع عملی نیست. با این حال روش‌های زیادی برای پیداکردن کمینه محلی ارائه شده است. لی و سیونگ الگوریتمی را برای کمینه‌کردن این تابع ارائه کردند [6] که قوانین به روز رسانی آنها برای کمینه‌کردن به صورت زیر است

(2)

(3)

لی و سیونگ اثبات کردند که این الگوریتم به روز رسانی تکراری می‌تواند کمینه محلی را برای تابع هزینه در (1) پیدا کند [6]. در روش NMF ستون ام ماتریس به وسیله ترکیب خطی بردارهای سطری ماتریس که با ستون ام ماتریس وزن‌دهی شده‌اند ساخته می‌شود . ماتریس W را می‌توان به عنوان پایه‌ای برای بهینه‌سازی ترکیب خطی ماتریس در نظر گرفت. از آنجایی که تعداد محدودی از بردارهای پایه برای نمایش تعداد زیادی بردار به کار برده می‌شوند، از این رو پیش‌بینی قابل قبول وقتی به دست می‌آید که بردارهای پایه بتوانند ساختار معنایی داده‌ها را نشان دهند. معمولاً تعداد ویژگی‌های معنایی، کمتر از تعداد داده‌ها و ویژگی‌های اولیه در نظر گرفته می‌شوند. در واقع روش NMF، ماتریس اولیه با ابعاد زیاد را با بردارهایی در ابعاد کم نشان می‌دهد. برخلاف روش‌های دیگر تجزیه ماتریسی، محدودیت غیر منفی بودن، تنها اجازه عملیات جمع‌کردن در ماتریس‌های تجزیه‌شده را می‌دهد و عملیات منها در این روش مجاز نیست.

چندین روش بر مبنای NMF برای خوشه‌بندی ارائه شده است. در [5] از روش اولیه NMF برای خوشه‌بندی متن استفاده گردیده و در این مقاله نشان داده شده که نتایج NMF از تجزیه مقدار ویژه (SVD) بهتر است. در [18] یک الگوریتم برای یادگیری ویژگی‌های معنایی با استفاده از قوانین به روز رسانی آمده است. بیشتر روش‌های ارائه‌شده در مقالات، مشکل پیچیدگی زمان اجرا و مصرف حافظه زیاد را دارند.

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

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

(4)

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

3-1 قوانین به روز رسانی پیشنهادی برای کمینه‌کردن تابع هزینه

برای کمینه‌کردن تابع هزینه در (4)، نیاز به قوانین به روز رسانی برای ماتریس‌های و می‌باشد. در این مقاله برای پیداکردن این قوانین از تابع لاگرانژ استفاده شده است

(5)

به طوری که و ضرایب لاگرانژ برای محدودیت‌های و هستند. مشتق جزئی لاگرانژ نسبت به و برابر است با

(6)

(7)

با استفاده از شرایط KKT، و است و قوانین به روز رسانی زیر به دست می‌آید

(8)

(9)

3-2 اثبات همگرایی قوانین به روز رسانی پیشنهادی

اثبات همگرایی در این مقاله شبیه اثبات همگرایی در مقاله لی و سیونگ است [6]. با توجه به قوانین به روز رسانی (8) و (9) می‌توان قضیه زیر را در نظر گرفت.

قضیه: تابع هزینه در (4) نسبت به قوانین به روز رسانی (8) و (9) غیر افزایشی است.

اگر باشد، آن گاه قوانین به روز رسانی (8) و (9) شبیه قوانین اولیه NMF خواهند بود. در این مقاله برای اثبات همگرایی از یک تابع کمکی استفاده شده است.

تعریف: اگر و باشد، یک تابع کمکی برای است.

لم 1: اگر یک تابع کمکی برای باشد، آن گاه تحت قانون به روز رسانی (10) غیر افزایشی است

(10)

اثبات:

اگر یک کمینه محلی برای باشد، آن گاه برقرار است. پس یک سری تقریب‌ها را می‌توان
با تکرار قانون به روز رسانی (10) برای همگراشدن تابع هزینه به دست آورد:

با در نظر گرفتن یک تابع کمکی مناسب می‌توان نشان داد که قانون به روز رسانی در (8) یک تابع به روز رسانی در (10) است.

$C:\Users\Mehdi\Desktop\Text clustering NMF\farsi\fig1.png$

شکل 1: روند روش پیشنهادی برای خوشه‎بندی.

لم 2: تابع

(11)

یک تابع کمکی برای در (4) است که اشاره به قسمت تابع دارد.

اثبات: واضح است. برای پیداکردن ، (11) با سری تیلور بسط داده‌شده روی مقایسه شده است

(12)

برای اثبات نیاز به اثبات نامعادله زیر است

(13)

برای اثبات این نامعادله می‌توان از نامعادله زیر استفاده کرد

(14)

پس نامعادله برقرار است و به این ترتیب می‌توان یک تابع کمکی برای قانون به روز رسانی (9) تعیین کرد.

لم 3: تابع

(15)

یک تابع کمکی برای در (4) است که اشاره به قسمت تابع دارد

(16)

لم 3 اثباتی شبیه لم 2 دارد و از تکرار آن صرف نظر شده است. با در نظر گرفتن این لم‎ها همگرایی قضیه اثبات می‌شود.

اثبات قضیه: جایگذاری در (10) با (11) و (15) منجر به ایجاد قوانین به روز رسانی زیر می‌شود

(17)

(18)

از آنجایی که (11) و (15) توابع کمکی هستند، پس می‌توان نتیجه گرفت که و تحت این قوانین به روز رسانی، غیر افزایشی هستند و در کل تابع هزینه در (4) غیر افزایشی است. شکل 1 روش پیشنهادی برای خوشه‌بندی را نشان می‌دهد.

3-3 تحلیل پیچیدگی زمانی روش پیشنهادی

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

4- نتایج آزمایش‌ها

در این بخش آزمایش‌های انجام‌شده جهت نشان‌دادن کارایی روش پیشنهادی در کاهش ابعاد و خوشه‌بندی ارائه گردیده است. در ابتدا روش‌های مقایسه‌شده توضیح داده می‌شوند و سپس معیارهای ارزیابی بیان می‎گردند و نهایتاً نتایج آمده است.

4-1 روش‌های مقایسه‌شده

چندین روش خوشه‌بندی برای مقایسه با روش پیشنهادی بررسی شده که این روش‌ها به شرح زیر هستند:

K-means: در این روش، داده‌ها در خوشه‌هایی که واریانس برابر دارند گروه‌بندی می‌شوند و هدف، کمینه‌کردن جمع مربعات فواصل نقاط داده‌ها در داخل هر خوشه است. در این روش، تعداد خوشه‌ها باید از قبل مشخص باشد. این الگوریتم مقیاس‌پذیر است و در مجموعه داده‌های بزرگ می‌توان از آن استفاده کرد و هم‌اکنون در کاربردهای زیادی از این روش استفاده می‌شود [25] و [26].

خوشه‌بندی طیفی⁹: این روش در ابتدا با استفاده از مقادیر ویژه ماتریس شباهت، کاهش ابعاد انجام می‌دهد و سپس خوشه‌بندی می‎کند. روش کلی خوشه‌بندی طیفی به کارگیری یک خوشه‌بندی استاندارد بر روی بردارهای ویژه ماتریس لاپلاسین ماتریس شباهت است [27] و [28].

خوشه‌بندی Agglomerative: الگوریتم‌های خوشه‌بندی سلسله‌مراتبی، خوشه‌های تودرتو را به وسیله ادغام یا تقسیم‌کردن پی‌درپی ایجاد می‌کنند [29] و سلسله‌مراتب خوشه‌ها به صورت درخت یا دندروگرام¹⁰ نشان
داده می‌شود. ریشه درخت یک خوشه تنها است که هم نمونه‌ها را در بر می‌گیرد و برگ‌های آن خوشه‌هایی است که تنها یک نمونه دارند [30]. خوشه‌بندی agglomerative یک خوشه‌بندی سلسله‌مراتبی است که از روش بالا به پایین استفاده می‌کند. این الگوریتم در ابتدا هر نمونه را یک خوشه در نظر می‌گیرد و به صورت پی‌درپی آنها را با هم ادغام می‌کند و از معیار پیوند¹¹ برای ادغام خوشه‌ها استفاده می‌کند.

NMF: در پیاده‌سازی‌ها از روش اولیه NMF برای مقایسه استفاده شده است [6] و [31].

4-2 معیارهای ارزیابی

اکثراً از دو معیار برای ارزیابی کارایی الگوریتم‌های خوشه‌بندی استفاده می‌شود. اولین معیار، اطلاعات متقابل ¹² بین دو خوشه‌بندی است. این معیار شباهت بین دو نوع خوشه‌بندی بر روی یک داده را نشان می‌دهد [32]. برای دو خوشه‌بندی و اطلاعات متقابل به صورت زیر محاسبه می‌شود

(19)

در این فرمول تعداد نمونه‌ها را در خوشه نشان می‌دهد و تعداد نمونه‌ها در خوشه است. این معیار مستقل از برچسب نمونه‌ها می‌باشد و یک معیار برای ارزیابی دو خوشه‌بندی است. دو نسخه برای نرمال‌کردن وجود دارد: اطلاعات متقابل تنظیم‌شده ¹³ و اطلاعات متقابل نرمال‌شده ¹⁴ [33]. اکثراً از در مقالات استفاده می‌شود و معیار ، نرمال‌شده در مقیاس صفر (بدون اطلاعات متقابل) و یک (وابستگی کامل) است و به صورت رابطه زیر تعریف می‌شود

(20)

که و آنتروپی یا میزان عدم قطعیت خوشه‌بندی و را نشان می‌دهد و احتمال این را که یک متن، متعلق به خوشه باشد بیان می‌کند. در این معیار ترتیب برچسب‌گذاری خوشه‌ها، امتیاز را تغییر نمی‌دهد. امتیاز نزدیک به یک نشان می‌دهد که دو خوشه‌بندی بسیار شبیه به هم هستند و امتیاز نزدیک به صفر نشان می‌دهد که دو خوشه‌بندی از همدیگر مستقل می‌باشند. معیارهای که بر پایه هستند برای ارزیابی نیاز دارند که برچسب‌گذاری دستی خوشه‌ها موجود باشد که این در عمل همیشه امکان‌پذیر نیست. اگر برچسب‌های دستی در دسترس نباشند، می‌توان ارزیابی را توسط خود مدل انجام داد. ضریب سیلوته ¹⁵، معیاری است که در آن امتیاز زیاد نشان می‌دهد که خوشه‌بندی به صورت مناسب توزیع شده است. این ضریب برای هر نمونه از داده به صورت زیر محاسبه می‌شود

(21)

در این فرمول میانگین فاصله نمونه داده با نمونه‌های دیگر در خوشه خودش است و میانگین فاصله با نمونه‌های نزدیک‌ترین خوشه را نشان می‌دهد. این معیار برای یک مجموعه از داده‌ها به صورت میانگین ضریب سیلوته همه داده‌ها بیان می‌شود. بازه این ضریب بین و است؛ یک خوشه‌بندی با چگالی زیاد را نشان می‌دهد و برای خوشه‌بندی نامناسب است. مقادیر نزدیک صفر نیز خوشه‌بندی با همپوشانی را نشان می‌دهند.

4-3 نتایج

در این پژوهش از مجموعه داده‎های رویترز- 21578 و WebKB برای ارزیابی روش پیشنهادی در مقایسه با روش‌های دیگر استفاده شده است. تمامی پیاده‌سازی‌ها با زبان پایتون بر روی کامپیوتری هشت‌هسته‌ای با حافظه 8 گیگابایت و سیستم عامل ویندوز 7 انجام شده است. قبل از انجام خوشه‌بندی متن نیاز است که بر روی مجموعه داده، پیش‌پردازش انجام شود. پیش‌پردازش متن یکی از مراحل مهم در خوشه‌بندی متن است. در این مقاله از روش‌هایی مانند توکن‎سازی¹⁶، حذف کلمات متناوب و ریشه‌یابی کلمات استفاده شده است. توکن‎سازی روشی است که در آن محتوای یک متن به عبارات و کلمات تقسیم می‌شود. خیلی از کلمات در

$C:\Users\Mehdi\Desktop\Text clustering NMF\farsi\fig2.png$

شکل 2: مقدار NMI و سیلوته روش پیشنهادی در مقایسه با تغییرات بر روی مجموعه داده رویترز- 21578.

جدول 1: توزیع متون در مجموعه داده رویترز- 21578.

نام خوشه	تعداد متون
Earn	3964
Acq	2369
money-fx	717
Grain	582
crude	578
Trade	485
interest	478
Ship	286
wheat	283
Corn	237

[1] این مقاله در تاریخ 11 فروردین ماه 1400 دریافت و در تاریخ 4 آذر ماه 1400 بازنگری شد.

مهدی حسین‎زاده اقدم (نویسنده مسئول)، دانشکده فنی و مهندسی، گروه مهندسی کامپیوتر، دانشگاه بناب، بناب، ایران، (email: mhaghdam@ubonab.ac.ir).

مرتضی آنالویی، دانشكده مهندسي كامپيوتر، دانشگاه علم و صنعت ايران، تهران، ایران، (email: analoui@iust.ac.ir).

جعفر تنها، دانشكده مهندسي برق و كامپيوتر، دانشگاه تبریز، تبریز، ایران،
(email: jafar.tanha.pnu@gmail.com).

[2] . Singular Value Decomposition

[3] . Non-Negative Matrix Factorization

[4] . Multiplicative Updating Rules

[5] . Constrained Non-Negative Matrix Factorization

[6] . Frobenius-Norm Non-Negative Matrix Factorization

[7] . Regularized Non-Negative Matrix Factorization

[8] . Convex

[9] . Spectral Clustering

[10] . Dendrogram

[11] . Linkage

[12] . Mutual Information

[13] . Adjusted Mutual Information

[14] . Normalized Mutual Information

[15] . Silhouette Coefficient

[16] . Tokenization

جدول 2: کارایی روش‌های مقایسه‌شده در مجموعه داده رویترز- 21578.

	NMI					سیلوته
تعداد ویژگی‌ها انتخابی	500	1000	2000	همه ویژگی‌ها	میانگین	500	1000	2000	همه ویژگی‌ها	میانگین
K-means	435/0	466/0	461/0	491/0	463/0	088/0	060/0	043/0	025/0	054/0
طیفی	414/0	416/0	419/0	414/0	416/0	088/0	063/0	043/0	019/0	053/0
Agglomerative	410/0	482/0	477/0	467/0	459/0	091/0	043/0	037/0	018/0	047/0
NMF	434/0	464/0	441/0	472/0	453/0	047/0	037/0	014/0	019/0	029/0
FNMF	484/0	487/0	494/0	512/0	494/0	098/0	065/0	055/0	029/0	062/0

بیشتر متن‌ها تکرار می‌شوند و اهمیت زیادی ندارند، زیرا اکثراً برای اتصال کلمات به یکدیگر به کار می‌روند. آنها معمولاً به عنوان کلمات متناوب در نظر گرفته می‌شوند و حذف می‌گردند چون به محتوای متن ربطی ندارند. ریشه‌یابی کلمات روشی است که در آن فرم‌های مختلف یک کلمه به صورت یک فرم کلی به نام ریشه کلمه نشان داده می‌شود [17].

بعد از پیش‌پردازش متون با استفاده از روش ¹، میزان اهمیت یک عبارت نسبت به یک متن در مجموعه‌ای از متون نشان داده می‌شود. در واقع هدف این سیستمِ وزن‎دهی، نشان‌دادن اهمیت عبارت در متن است. مقدار متناسب با تعداد تکرار عبارت در متن افزایش می‌یابد و توسط تعداد متونی که شامل عبارت می‌باشند متعادل می‌شود. به این معنی که اگر کلمه‌ای در بسیاری از متون ظاهر شود، احتمالاً کلمه‌ای متداول است و ارزش چندانی در ارزیابی متن ندارد

(22)

که تعداد متونی است که در آن عبارت تکرار شده و تعداد تکرار عبارت در متن است. انتخاب ویژگی، یک روش کاهش تعداد ویژگی‎ها است که در آن، تعداد کلمات یا عبارت‌ها در ماتریس متن- عبارت کاهش پیدا می‌کند. این روش با کاهش تعداد ویژگی‌ها، هم باعث کاهش پیچیدگی زمانی روش‌های خوشه‌بندی و هم باعث افزایش دقت خوشه‌بندی می‌گردد. در این پژوهش از بهره اطلاعات ² برای ارزیابی ویژگی‌ها استفاده شده که کاربرد وسیعی در یادگیری ماشین دارد [34]. بهره اطلاعات به صورت میزان اطلاعات فراهم‌شده توسط کلمات برای خوشه‌بندی متن تعریف می‌شود. فرمول این روش برای اندازه‌گیری میزان اهمیت کلمات در خوشه‌بندی به صورت زیر است

(23)

در این فرمول آنتروپی شرطی را نشان می‌دهد.

مجموعه داده رویترز- 21578 از سال 1987 توسط رویترز در دسترس است که شامل 21578 متن و 135 خوشه می‌باشد که به صورت دستی تعیین شده‌اند. هر متن در این مجموعه بر اساس محتوایش به یک یا چند خوشه به صورت دستی منتسب شده و متونی که چند برچسب دارند در این پژوهش به هر کدام از خوشه‌ها منتسب شده‌اند. اندازه خوشه‌های یعنی تعداد متون در آنها در بازه 10 تا 4000 هستند. در این مقاله فقط از 10 خوشه بزرگ استفاده گردیده که کلاً 9979 متن دارند. توزیع اندازه خوشه‌ها بالانس نیست؛ بزرگ‌ترین خوشه 3964 متن دارد که 72/39% مجموعه داده و کوچک‌ترین خوشه 237 متن دارد که 37/2% مجموعه داده می‌شود. جدول 1 تعداد متون داخل خوشه‌ها را نشان می‌دهد.

در روش پیشنهادی باید پارامتر و تعداد ویژگی‌های معنایی در ابتدا تعیین شوند. شکل 2 نشان می‌دهد که و سیلوته روش پیشنهادی چگونه با استفاده از پارامتر بر روی مجموعه داده رویترز تغییر می‌کند. این شکل نشان می‌دهد که کارایی روش پیشنهادی با 500 ویژگی و 200 تکرار، وقتی از صفر تا پنج تغییر می‌کند، چه تغییراتی دارد.

همان طور که در شکل 2 دیده می‌شود، روش پیشنهادی وقتی برابر با 05/0 باشد، بیشترین را دارد و به همین ترتیب وقتی برابر با 2 است، بیشترین سیلوته را دارد. در این آزمایش‌ها تعداد ویژگی‌های معنایی برابر با تعداد خوشه‌ها در نظر گرفته شده است. در روش پیشنهادی با در نظر گرفتن معیار به عنوان معیار اصلی، مقدار برابر 05/0 در نظر گرفته شده است.

جدول 2 جزئیات نتایج خوشه‌بندی روش پیشنهادی و روش‌های

$C:\Users\Mehdi\Desktop\Text clustering NMF\farsi\fig3.png$

شکل 3: میزان همگرایی NMF بر روی مجموعه داده رویترز- 21578.

جدول 3: توزیع متون در مجموعه داده WEBKB.

نام خوشه	تعداد متون
Student	1641
Faculty	1124
Course	930
Project	504

مقایسه‌شده را بر روی مجموعه داده رویترز نشان می‌دهد. در این جدول با استفاده از روش ابتدا 500 ویژگی برای ارزیابی در نظر گرفته شده و سپس از 1000، 2000 و همچنین تمام ویژگی‌ها یعنی بدون انتخاب ویژگی و با 21687 ویژگی برای ارزیابی روش پیشنهادی استفاده گردیده است. به ازای هر مقدار ثبت‌شده، 3 اجرا انجام شده و مقدار نهایی بر اساس میانگین 3 اجرا تعیین گردیده است. روش پیشنهادی کارایی خوبی در هر تعداد ویژگی انتخاب‌شده نسبت به روش‌های دیگر دارد و به صورت میانگین آن برابر با 512/0 و سیلوته‎اش برابر با 062/0 است. نتایج نشان می‌دهند که محدودیت شباهت اضافه‌شده در روش پیشنهادی باعث افزایش کارایی خوشه‌بندی گردیده است. روش اولیه بعد از 100 تکرار، توانایی افزایش را نداشت و در حالت کلی بدتر از روش
K-means عمل کرد. NMF به خاطر در نظر نگرفتن محدودیت شباهت، نمی‌تواند شباهت بین بردارها را بعد از نگاشت داده‎ها به فضای جدید حفظ کند.

دلیل کم‌بودن مقدار سیلوته برای روش پیشنهادی و روش‌های دیگر، توزیع برچسب خوشه‌ها در مجموعه داده رویترز بود. زیرا وقتی تنها با روش مجموعه داده به بردارهای ویژگی تبدیل می‌شود و بدون انتخاب ویژگی و با برچسب‌های خود مجموعه داده رویترز سیلوته محاسبه می‌گردد، مقدار سیلوته برابر 027/0 می‌شود. این نشان می‌دهد که افزایش در راستای افزایش سیلوته نمی‌باشد، یعنی برچسب‌گذاری دستی خوشه‌ها در مجموعه داده با معیار فاصله متناسب نیست و به همین دلیل با افزایش مقدار سیلوته کاهش می‎یابد. با این حال همان طور که در شکل 2 دیده می‌شود، می‌توان برای به دست آوردن مقدار سیلوته بالا در روش پیشنهادی، مقدار را تا عدد 2 بالا برد و به مقدار سیلوته 221/0 رسید. در این پیاده‎سازی‎ها هدف، افزایش معیار بود.

در این مقاله برای بررسی بهتر روش پیشنهادی، علاوه بر مجموعه داده رویترز- 21578 از مجموعه داده WebKB نیز استفاده شده است. صفحات وب در این مجموعه داده متعلق به گروه‎های علمی دانشگاه‎های مختلف می‌باشد که توسط دانشگاه کارنگی ملون جمع‎آوری شده است. صفحات وب این مجموعه داده به صورت دستی به هفت خوشه تقسیم

$C:\Users\Mehdi\Desktop\Text clustering NMF\farsi\fig4.png$

شکل 4: میزان همگرایی FNMF بر روی مجموعه داده رویترز- 21578.

شده است. در این مقاله، سه خوشه از هفت خوشه به خاطر وجود تعداد کم داده‎ها در آنها حذف گردیده است. جدول 3 تعداد داده‎ها در هر خوشه را نشان می‎دهد.

جدول 4 نتایج خوشه‎بندی بر روی مجموعه داده WebKB را نشان می‎دهد. همانند نتایج رویترز- 21578، در این جدول نیز با استفاده از روش ابتدا 500 ویژگی برای ارزیابی در نظر گرفته شده و سپس از 1000، 2000 و تمام ویژگی‌ها با 7647 ویژگی برای ارزیابی روش پیشنهادی استفاده گردیده است. همان طور که در جدول دیده می‎شود روش پیشنهادی نتایج بهتری نسبت به روش‎های دیگر دارد.

همان طور که قبلاً ذکر شد، قوانین به روز رسانی برای پیداکردن بهینه محلی به کار برده می‌شوند و در بخش 3، همگرایی این قوانین اثبات شد و پیچیدگی زمانی روش پیشنهادی مورد تحلیل قرار گرفت. در این بخش میزان همگرایی روش پیشنهادی در مقایسه با در پیاده‌سازی‌ها نشان داده می‌شود. شکل‌های 3 و 4 سرعت همگرایی و روش پیشنهادی را بر روی مجموعه داده رویترز نشان می‌دهند. همان طور که در شکل 4 دیده می‌شود، روش پیشنهادی خیلی سریع همگرا می‌شود و در کمتر از 10 تکرار کارایی خوبی را نشان می‌دهد، ولی روش اولیه بعد از 100 تکرار همگرا می‌شود (شکل 3). این آزمایش مطالب گفته‌شده در بخش 3-3 را تأیید می‌کند که اگرچه روش پیشنهادی محاسبات زیادی نسبت به روش اولیه دارد ولی در تعداد تکرار کمتری همگرا می‌شود و در کل فرایند به روز رسانی، روش پیشنهادی خیلی سریع‎تر عمل می‌کند.

5- نتیجه‌گیری

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

با تنظیم صحیح مقدار ، روش پیشنهادی می‌تواند نتایج بهتری نسبت به روش‌های دیگر به دست آورد. همچنین روش پیشنهادی را

[1] . Term Frequency - Inverse Document Frequency

[2] . Information Gain

جدول 4: کارایی روش‌های مقایسه‌شده در مجموعه داده WEBKB.

	NMI					سیلوته
تعداد ویژگی‌ها انتخابی	500	1000	2000	همه ویژگی‌ها	میانگین	500	1000	2000	همه ویژگی‌ها	میانگین
K-means	341/0	326/0	325/0	358/0	338/0	013/0	013/0	005/0	012/0	011/0
طیفی	315/0	310/0	295/0	298/0	305/0	017/0	015/0	045/0	014/0	023/0
Agglomerative	256/0	241/0	262/0	001/0	190/0	057/0	065/0	040/0	015/0	044/0
NMF	304/0	327/0	330/0	333/0	324/0	002/0-	001/0	007/0	010/0	004/0
FNMF	356/0	362/0	377/0	360/0	364/0	053/0	050/0	041/0	024/0	042/0

می‌توان در مسایل دیگری به کار برد و به عنوان کارهای آتی در نظر داریم که این روش را بر روی خلاصه‌سازی متن اعمال کنیم و نیز انتخاب مقدار بهینه برای یک چالش در روش پیشنهادی است که در نظر داریم در تحقیقات آتی، انتخاب خودکار مقدار را بررسی نماییم.

مراجع

[1] R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification, Wiley-Interscience, Hoboken, NJ, 2nd Edition, 2000.

[2] D. D. Lee and H. S. Seung, "Learning the parts of objects by nonnegative matrix factorization," Nature, vol. 401, no. 6755, pp. 788-791, Jan. 1999.

[3] D. Kuang, J. Choo, and H. Park, "Nonnegative matrix factorization for interactive topic modeling and document clustering," In M. Emre Celebi (Ed.), Partitional Clustering Algorithms, pp. 215-243, Springer Cham, 2015.

[4] S. Z. Li, X. Hou, H. Zhang, and Q. Cheng, "Learning spatially localized, parts-based representation," in Proc. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, CVPR'01, pp. 207-212, Kauai, HI, USA, 8-14. Dec. 2001.

[5] W. Xu, X. Liu, and Y. Gong, "Document clustering based on nonnegative matrix factorization," in Proc. of the 26th Annual Int ACM SIGIR Conf. on Research and Development in Information Retrieval, pp. 267-273, Toronto, Canada, 28 Jul.-1 Aug. 2003.

[6] D. D. Lee and H. S. Seung, "Algorithms for non-negative matrix factorization," in Proc. of the 2001 Conf. Advances in Neural Information Processing Systems, pp. 556-562, Vancouver, Canada, 3-8 Dec. 2001.

[7] R. Sandler and M. Lindenbaum, "Nonnegative matrix factorization with earth mover's distance metric for image analysis," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 33, no. 8, pp. 1590-1602, Aug. 2011.

[8] V. P. Pauca, J. Piper, and R. J. Plemmons, "Nonnegative matrix factorization for spectral data analysis," Linear Algebra and Its Applications, vol. 416, no. 1, pp. 29-47, Jul. 2006.

[9] M. H. Aghdam and M. D. Zanjani, "A novel regularized asymmetric non-negative matrix factorization for text clustering," Information Processing & Management, vol. 58, no. 6, Article ID: 102694, 6 pp., Nov. 2021.

[10] A. J. Mohammed, Y. Yusof, and H. Husni, "Document clustering based on firefly algorithm," J. of Computer Science, vol. 11, no. 3, pp. 453-465, Mar. 2015.

[11] A. J. Mohammed, Y. Yusof, and H. Husni, "Determining number
of clusters using firefly algorithm with cluster merging for text clustering," in Proc. Int. Visual Informatics Conf., pp. 14-24, Bangi, Malaysia, 17- 19 Nov. 2015.

[12] A. Abraham, S. Das, and A. Konar, "Document clustering using differential evolution," in Proc. IEEE Int. Conf. on Evolutionary Computation, pp. 1784-1791, Vancouver, Canada, 16-21 Jul. 2006.

[13] A. Kumar and H. Daum´e, "A co-training approach for multi-view spectral clustering," in Proc. 28th Int. Conf. on Machine Learning, ICML’11, pp. 393-400, Bellevue, WA, USA, 28 Jun.-2 Jul. 2011.

[14] A. Y. Ng, M. I. Jordan, and Y. Weiss, "On spectral clustering: analysis and an algorithm," in Proc. of the 2002 Conf. Advances in Neural Information Processing Systems, pp. 849-856, Vancouver, Canada, 9-14 Dec. 2002.

[15] D. Yogatama and K. Tanaka-Ishii, "Multilingual spectral clustering using document similarity propagation," in Proc. of the Conf. on Empirical Methods in Natural Language Processing, Association for Computational Linguistics, vol. 2, pp. 871-879, Singapore, 6-7 Aug. 2009.

[16] D. Toli´c, N. Antulov-Fantulin, and I. Kopriva, "A nonlinear orthogonal non-negative matrix factorization approach to subspace clustering," Pattern Recognition, vol. 82, pp. 40-55, Oct. 2018.

[17] C. C. Aggarwal and C. Zhai, Mining Text Data, Springer Science & Business Media, 2012.

[18] F. Shahnaz, M. W. Berry, V. P. Pauca, and R. J. Plemmons, "Document clustering using nonnegative matrix factorization," Information Processing & Management, vol. 42, no. 2, pp. 373-386, Mar. 2006.

[19] E. F. Gonzalez and Y. Zhang, Accelerating the Lee-Seung Algorithm for Nonnegative Matrix Factorization, Tech. Rep., 2005.

[20] N. Gillis and S. A. Vavasis, "Fast and robust recursive algorithms for separable nonnegative matrix factorization," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 36, no. 4, pp. 698-714, Nov. 2013.

[21] K. Huang, N. D. Sidiropoulos, and A. Swami, "Non-negative matrix factorization revisited: uniqueness and algorithm for symmetric decomposition," IEEE Trans. on Signal Processing, vol. 62, no. 1, pp. 211-224, Oct. 2013.

[22] K. Kimura, M. Kudo, and Y. Tanaka, "A column-wise update algorithm for nonnegative matrix factorization in bregman divergence with an orthogonal constraint," Machine Learning, vol. 103, no. 2, pp. 285-306, May 2016.

[23] F. Shang, L. Jiao, and F. Wang, "Graph dual regularization non-negative matrix factorization for co-clustering," Pattern Recognition, vol. 45, no. 6, pp. 2237-2250, Jun. 2012.

[24] X. Ma, P. Sun, and G. Qin, "Nonnegative matrix factorization algorithms for link prediction in temporal networks using graph communicability," Pattern Recognition, vol. 71, pp. 361-374, Nov. 2017.

[25] A. David and S. Vassilvitskii, "K-means++: The advantages of careful seeding," in Proc. of the 18th annual ACM-SIAM Symp. on Discrete Algorithms, SODA’07, pp. 1027-1035, New Orleans, LA, USA, 7-9 Jan. 2007.

[26] J. N. Myhre, K. Ø. Mikalsen, S. Løkse, and R. Jenssen, "Robust clustering using a knn mode seeking ensemble," Pattern Recognition, vol. 76, pp. 491-505, Apr. 2018.

[27] W. Jiang, W. Liu, and F. L. Chung, "Knowledge transfer for spectral clustering," Pattern Recognition, vol. 81, pp. 484-496, Sept. 2018.

[28] U. Von Luxburg, "A tutorial on spectral clustering," Statistics and Computing, vol. 17, no. 4, pp. 395-416, Aug. 2007.

[29] J. V. Munoz, M. A. Goncalves, Z. Dias, and R. da S. Torres, "Hierarchical clustering-based graphs for large scale approximate nearest neighbor search," Pattern Recognition, vol. 96, Article ID: 106970, Dec. 2019.

[30] L. Rokach and O. Maimon, Clustering Methods, in Data Mining and Knowledge Discovery Handbook. Springer, pp. 321-352, 2005.

[31] H. Xiong and D. Kong, "Elastic nonnegative matrix factorization," Pattern Recognition, vol. 90, pp. 464-475, Jun. 2019.

[32] N. X. Vinh, J. Epps, and J. Bailey, "Information theoretic measures for clusterings comparison: variants, properties, normalization and correction for chance," J. of Machine Learning Research, vol. 11, pp. 2837-2854, Dec. 2010.

[33] Z. Yang, R. Algesheimer, and C. J. Tessone, "A comparative analysis of community detection algorithms on artificial networks," Scientific Reports, vol. 6, no. 1, pp. 1-18, Aug. 2016.

[34] T. M. Mitchell, "Machine learning and data mining," Communications of the ACM, vol. 42, no. 11, pp. 30-36, Nov. 1999.

مهدی حسین‎زاده اقدم در سال 1385 مدرك كارشناسي مهندسي کامپیوتر خود را از دانشگاه آزاد اسلامی واحد قزوین و در سال 1387 مدرك كارشناسي ارشد مهندسي کامپیوتر خود را از دانشگاه اصفهان دريافت نمود. دكتر حسین‎زاده اقدم دوره دكتراي مهندسي كامپيوتر را در دانشگاه علم و صنعت ایران در سال 1395 به پایان رساند و از سال 1396 در دانشكده فنی و مهندسي دانشگاه بناب مشغول به فعاليت گرديد و اينك نيز عضو هيأت علمي اين دانشكده مي‎باشد. زمينه‎هاي علمي مورد علاقه نامبرده متنوع بوده و شامل موضوعاتي مانند یادگیری ماشین، هوش محاسباتی، سيستم‎هاي توصیه‎گر و پردازش متن مي‎باشد.

مرتضی آنالویی تحصيلات خود را در مقطع كارشناسي مهندسی برق در سال 1363 از دانشگاه علم و صنعت ایران و در مقطع دكتري مهندسی برق و الکترونیک در سال 1369 از دانشگاه اکایاما ژاپن به پايان رسانده است و هماكنون عضو هیأت علمی دانشكده مهندسي كامپيوتر دانشگاه علم و صنعت ایران مي‎باشد. نامبرده قبل از پيوستنش به دانشگاه علم و صنعت ایران در سالهاي 1370 الي 1373 عضو هیأت علمی دانشكده مهندسي دانشگاه اکایاما ژاپن و در سال 1374 عضو هیأت علمی دانشكده مهندسي دانشگاه تربیت مدرس بوده است. زمينه‎هاي تحقيقاتي مورد علاقه ايشان عبارتند از: هوش مصنوعی، بهینه‎سازی و شبكههاي كامپيوتري.

جعفر تنها تحصیلات خود را در مقاطع کارشناسی و کارشناسی ارشد علوم کامپیوتر
بهترتیب در سالهای 1378 و 1381 از دانشگاه صنعتی اميرکبير به پايان رسانده است و پس از آن به دوره دكتراي مهندسي كامپيوتر در دانشگاه آمستردام در هلند وارد گرديد و در سال 1392 موفق به اخذ درجه دكترا در علوم كامپيوتر از دانشگاه مذكور گرديد. دكتر تنها اينك عضو هيأت علمي دانشكده مهندسی برق و کامپیوتر دانشگاه تبریز مي‎باشد. زمينه‎هاي علمي مورد علاقه نامبرده متنوع بوده و شامل موضوعاتي مانند یادگیری ماشین، شناسایی الگو و تحلیل متن مي‎باشد.

Share To

Article Url

A Novel Method Based on Non-Negative Matrix Factorization for Dimensions Reduction

Rimag

Links

Related Centers

Technical Support

Official pages