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

اشتراک گذاری

آدرس مقاله


کد مقاله : 14000111272837 بازدید : 4837 صفحه: 164 - 172

20.1001.1.16823745.1401.20.2.4.0

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

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

محورهای موضوعی : مهندسی برق و کامپیوتر

مهدی حسین زاده اقدم 1 * , مرتضی آنالویی 2 , جعفر تنها 3

1 - دانشگاه بناب،دانشکده فنی و مهندسی
2 - دانشگاه علم و صنعت ایران،دانشكده مهندسي كامپيوتر
3 - دانشگاه تبریز،دانشكده مهندسي برق و كامپيوتر

تاریخ دریافت : 1400/01/11 تاریخ پذیرش : 1400/09/22 تاریخ انتشار : 1401/05/29

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

چکیده مقاله :

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

چکیده انگلیسی:

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.

منابع و مأخذ:

[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.
متن کامل:
معرفي يک روش جديد خوشه‌يابي خودکار

164                                                                                         نشریه مهندسی برق و مهندسی كامپیوتر ایران، ب- مهندسی کامپیوتر، سال 20، شماره 2، تابستان 1401

مقاله پژوهشی

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

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

 

 

1 

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

 

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

1-       مقدمه

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

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

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

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

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

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

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

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

2-       پیش‌زمینه

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

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

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

img0        (1)

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

img0        (2)

img0        (3)

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

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

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

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

img0        (4)

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

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

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

img0        (5)

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

img0        (6)

img0        (7)

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

img0        (8)

img0        (9)

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

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

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

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

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

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

img0        (10)

اثبات: img0

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

img0 

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

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

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

 

لم 2: تابع

img0        (11)

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

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

img0        (12)

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

img0        (13)

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

img0        (14)

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

لم 3: تابع

img0        (15)

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

img0        (16)

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

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

img0        (17)

img0        (18)

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

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

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

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

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

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

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

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

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

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

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

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

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

img0        (19)

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

img0        (20)

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

img0        (21)

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

4-3 نتایج

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

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

شکل 2:  مقدار NMI و سیلوته روش پیشنهادی در مقایسه با تغییرات img0 بر روی مجموعه داده رویترز- 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].

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

img0        (22)

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

img0        (23)

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

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

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

همان طور که در شکل 2 دیده می‌شود، روش پیشنهادی وقتی img0 برابر با 05/0 باشد، بیشترین img0 را دارد و به همین ترتیب وقتی img0 برابر با 2 است، بیشترین سیلوته را دارد. در این آزمایش‌ها تعداد ویژگی‌های معنایی برابر با تعداد خوشه‌ها در نظر گرفته شده است. در روش پیشنهادی با در نظر گرفتن معیار img0 به عنوان معیار اصلی، مقدار img0 برابر 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

 

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

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

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

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

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

 

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

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

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

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

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

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

[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

 

 

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

مراجع

[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 موفق به اخذ درجه دكترا در علوم كامپيوتر از دانشگاه مذكور گرديد. دكتر تنها اينك عضو هيأت علمي دانشكده مهندسی برق و کامپیوتر دانشگاه تبریز مي‎باشد. زمينه‎هاي علمي مورد علاقه نام­برده متنوع بوده و شامل موضوعاتي مانند یادگیری ماشین، شناسایی الگو و تحلیل متن مي‎باشد.

 

 

 

 

 

 

 

 

 


مقالات مرتبط

حقوق این وب‌سایت متعلق به سامانه مدیریت نشریات رایمگ است.
حق نشر © 1403-1396

صفحه اصلی| عضویت/ ورود| درباره رایمگ| تماس با ما|
[English] [العربية] [en] [ar]