• صفحه اصلی
  • راهکاری مبتنی بر ساخت درخت دودویی تقریبی برای سرعت‌بخشیدن به جستجوی نزدیک‌ترین همسایگی در داده‌های حجیم

اشتراک گذاری

آدرس مقاله


کد مقاله : 13991029251782 بازدید : 3379 صفحه: 196 - 206

20.1001.1.16823745.1401.20.3.1.9

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

راهکاری مبتنی بر ساخت درخت دودویی تقریبی برای سرعت‌بخشیدن به جستجوی نزدیک‌ترین همسایگی در داده‌های حجیم

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

حسین کلاته 1 , نگین دانشپور 2

1 - دانشگاه تربیت دبیر شهید رجائی،دانشكده مهندسي كامپيوتر
2 - دانشگاه تربیت دبیر شهید رجائی،دانشکده مهندسی کامپیوتر

تاریخ دریافت : 1399/10/29 تاریخ پذیرش : 1401/01/23 تاریخ انتشار : 1401/08/11

کلید واژه: بافر همپوشانی, داده‌های حجیم, درخت تصمیم دودویی, طبقه‌بندی نزدیک‌ترین همسایگی,

چکیده مقاله :

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

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

Due to the increasing speed of information production and the need to convert information into knowledge, old machine learning methods are no longer responsive. When using classifications with the old machine learning methods, especially the use of inherently lazy classifications such as the k-nearest neighbor (KNN) method, the operation of classifying large data sets is very slow. Nearest Neighborhood is a popular method of data classification due to its simplicity and practical accuracy. The proposed method is based on sorting the training data feature vectors in a binary search tree to expedite the classification of big data using the nearest neighbor method. This is done by finding the approximate two farthest local data in each tree node. These two data are used as a criterion for dividing the data in the current node into two groups. The data set in each node is assigned to the left and right child of the current node based on their similarity to the two data. The results of several experiments performed on different data sets from the UCI repository show a good degree of accuracy due to the low execution time of the proposed method.

منابع و مأخذ:

[1] X. Lv, "The big data impact and application study on the like ecosystem construction of open internet of things," Cluster Computing, vol. 22, no. 2, pp. 3563-3572, Mar. 2019.
[2] V. Marx, Biology: the Big Challenges of Big Data, Ed: Nature Publishing Group, 2013.
[3] I. Triguero, J. Maillo, J. Luengo, S. García, and F. Herrera, "From big data to smart data with the k-nearest neighbours algorithm," in Proc. IEEE Int. Conf. on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData), pp. 859-864, Chengdu, China, 15- 18 Dec. 2016.
[4] D. W. Aha, D. Kibler, and M. K. Albert, "Instance-based learning algorithms," Machine Learning, vol. 6, no. 1, pp. 37-66, Jan. 1991.
[5] T. Cover and P. Hart, "Nearest neighbor pattern classification," IEEE Trans. on Information Theory, vol. 13, no. 1, pp. 21-27, Jan. 1967.
[6] D. W. Aha, Lazy Learning, in Lazy learning: Kluwer Academic Publishers, pp. 7-10, 1997.
[7] P. P. Anchalia and K. Roy, "The k-nearest neighbor algorithm using mapreduce paradigm," in Proc. 5th IEEE Int. Conf. on Intelligent Systems, Modelling and Simulation, pp. 513-518, Langkawi, Malaysia, 27- 9 Jan. 2014.
[8] H. Saadatfar, S. Khosravi, J. H. Joloudari, A. Mosavi, and S. Shamshirband, "A new k-nearest neighbors classifier for big data based on efficient data pruning," Mathematics, vol. 8, no. 2, p. 286, Feb. 2020.
[9] A. Hassanat, "Norm-based binary search trees for speeding up knn big data classification," Computers, vol. 7, no. 4, pp. 5, Oct. 2018. [10] D. Zhu, "Humor robot and humor generation method based on big data search through IOT," Cluster Computing, vol. 22, no. 4, pp. 9169-9175, Jul. 2019.
[11] J. Calvo-Zaragoza, J. J. Valero-Mas, and J. R. Rico-Juan, "Improving kNN multi-label classification in prototype selection scenarios using class proposals," Pattern Recognition, vol. 48, no. 5, pp. 1608-1622, May 2015.
[12] X. Wu, X. Zhu, G. Q. Wu, and W. Ding, "Data mining with big data," IEEE Trans. on Knowledge and Data Engineering, vol. 26, no. 1, pp. 97-107, Jun. 2013.
[13] S. García, J. Luengo, and F. Herrera, Data Preprocessing in Data Mining, Springer, 2015.
[14] L. Micó and J. Oncina, "A constant average time algorithm to allow insertions in the LAESA fast nearest neighbour search index," in Proc. 20th IEEE Int. Conf. on Pattern Recognition, pp. 3911-3914, Istanbul, Turkey, 23- 26 Aug. 2010.
[15] A. Bifet, et al., "Extremely fast decision tree mining for evolving data streams," in Proc. of the 23rd ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 1733-1742, Halifax, Canada, 13-17 Aug. 2017.
[16] A. B. Hassanat, "Furthest-pair-based binary search tree for speeding big data classification using k-nearest neighbors," Big Data, vol. 6, no. 3, pp. 225-235, Sept 2018.
[17] X. Wu, et al., "Top 10 algorithms in data mining," Knowledge and Information Systems, vol. 14, no. 1, pp. 1-37, Jan. 2008.
[18] E. Plaku and L. E. Kavraki, "Distributed computation of the kNN graph for large high-dimensional point sets," J. of Parallel and Distributed Computing, vol. 67, no. 3, pp. 346-359, Mar. 2007.
[19] C. Zhang, F. Li, and J. Jestes, "Efficient parallel kNN joins for large data in mapreduce," in Proc. of the 15th Int. Conf. on Extending Database Technology, pp. 38-49, Berlin, Germany, 27-30 Mar. 2012.
[20] K. Sun, H. Kang, and H. H. Park, "Tagging and classifying facial images in cloud environments based on KNN using mapreduce," Optik, vol. 126, no. 21, pp. 3227-3233, Nov. 2015.
[21] J. Maillo, S. Ramírez, I. Triguero, and F. Herrera, "kNN-IS: an iterative spark-based design of the k-nearest neighbors classifier for big data," Knowledge-Based Systems, vol. 117, no. 1, pp. 3-15, Feb. 2017.
[22] S. Ramírez-Gallego, B. Krawczyk, S. García, M. Woźniak, J. M. Benítez, and F. Herrera, "Nearest neighbor classification for high-speed big data streams using spark," IEEE Trans. on Systems, Man, and Cybernetics: Systems, vol. 47, no. 10, pp. 2727-2739, Jul. 2017.
[23] G. Chatzigeorgakidis, S. Karagiorgou, S. Athanasiou, and S. Skiadopoulos, "FML-kNN: scalable machine learning on big data using k-nearest neighbor joins," J. of Big Data, vol. 5, no. 1, pp. 1-27, Feb. 2018.
[24] S. Bagui, A. K. Mondal, and S. Bagui, "Improving the performance of kNN in the mapreduce framework using locality sensitive hashing," International J. of Distributed Systems and Technologies, vol. 10, no. 4, pp. 1-16, Oct. 2019.
[25] Z. Yong, L. Youwen, and X. Shixiong, "An improved KNN text classification algorithm based on clustering," J. of Computers, vol. 4, no. 3, pp. 230-237, Mar. 2009.
[26] H. Neeb and C. Kurrus, Distributed k-Nearest Neighbors, Ed: Stanford University Publishing: Stanford, CA, USA, 2016.
[27] Y. Ben-Haim and E. Tom-Tov, "A streaming parallel decision tree algorithm," J. of Machine Learning Research, vol. 11, no. 2, pp. 849-872, Feb. 2010.
[28] D. Xia, H. Li, B. Wang, Y. Li, and Z. Zhang, "A map reduce-based nearest neighbor approach for big-data-driven traffic flow prediction," IEEE Access, vol. 4, pp. 2920-2934, Jun. 2016.
[29] F. Angiulli, "Fast condensed nearest neighbor rule," in Proc. of the 22nd Int. Conf. on Machine learning, pp. 25-32, New York, NY, USA, 7-11Aug. 2005.
[30] Z. Deng, X. Zhu, D. Cheng, M. Zong, and S. Zhang, "Efficient kNN classification algorithm for big data," Neurocomputing, vol. 195, no. 100, pp. 143-148, Jun. 2016.
[31] T. Seidl and H. P. Kriegel, "Optimal multi-step k-nearest neighbor search," SIGMOD Rec., vol. 27, no. 2, pp. 154-165, Jun. 1998.
[32] L. R. Lu and H. Y. Fa, "A density-based method for reducing the amount of training data in kNN text classification," J. of Computer Research and Development, vol. 45, no. 4, pp. 539–544, Aug. 2004.
[33] A. J. Gallego, J. Calvo-Zaragoza, J. J. Valero-Mas, and J. R. Rico-Juan, "Clustering-based k-nearest neighbor classification for large-scale data with neural codes representation," Pattern Recognition, vol. 74, no. 1, pp. 531-543, Feb. 2018.
[34] A. J. Gallego, J. R. Rico-Juan, and J. J. Valero-Mas, "Efficient k-nearest neighbor search based on clustering and adaptive k values," Pattern Recognition, vol. 122, Article ID: 108356, Feb. 2022.
[35] S. Ougiaroglou and G. Evangelidis, "RHC: a non-parametric cluster-based data reduction for efficient k kNN classification," Pattern Analysis and Applications, vol. 19, no. 1, pp. 93-109, Feb. 2016.
[36] F. Wang, Q. Wang, F. Nie, W. Yu, and R. Wang, "Efficient tree classifiers for large scale datasets," Neurocomputing, vol. 284, no. 2, pp. 70-79, Apr. 2018.
[37] A. Hassanat, "Greedy algorithms for approximating the diameter of machine learning datasets in multidimensional euclidean space: experimental results," 2018.
[38] A. B. Hassanat, "Two-point-based binary search trees for accelerating big data classification using KNN," PloS One, vol. 13, no. 11, Article ID: e0207772, Nov. 2018.
[39] T. Liu, A. W. Moore, K. Yang, and A. G. Gray, "An investigation of practical approximate nearest neighbor algorithms," in Proc. 17th Int. Conf. on Information Processing Systems, pp. 825-832, Vancouver, Canada,13-18 Dec. 2004.
متن کامل:
معرفي يک روش جديد خوشه‌يابي خودکار

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

مقاله پژوهشی

راهکاری مبتنی بر ساخت درخت دودویی تقریبی برای سرعت‌بخشیدن به جستجوی نزدیک‌ترین همسایگی در داده‌های حجیم

حسین کلاته و نگین دانشپور

 

 

1 

چكیده: با توجه به سرعت روزافزون تولید اطلاعات و نیاز تبدیل اطلاعات به دانش، روش‌های یادگیری ماشین قدیمی دیگر پاسخگو نیستند. هنگام استفاده از طبقه‌بندی‌ها با روش‌های یادگیری ماشین قدیمی، به ویژه استفاده از طبقه‌بندی‌های ذاتاً تنبل مانند روش k- نزدیک‌ترین همسایگی (KNN)، عملیات طبقه‌بندی داده‌های حجیم بسیار کند است.

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

 

کلیدواژه: بافر همپوشانی، داده‌های حجیم، درخت تصمیم دودویی، طبقه‌بندی نزدیک‌ترین همسایگی.

1-       مقدمه

در طی دهه گذشته، تقاضاهای روزافزون جهانی برای انواع ارتباطات و اطلاعات، منجر به پیشرفت‌های چشم‌گیری در زمینه فناوری اطلاعات شده است که اشتراک داده‌ها و ارتباطات جهان را تسهیل می‌کند [1]. این تعاملات تکنولوژیکی جهانی در بین انسان‌ها، حجم زیادی از داده‌ها را ایجاد می‌کند. مدیریت این داده‌ها مزایای رقابتی برای شرکت‌ها دارد و یا به صورت اکتشافات مهم در زمینه‌های مختلف علمی منعکس می‌شود [2]. شرکت‌ها و محققان برای ذخیره، تجزیه و تحلیل این مقدار زیاد از داده‌ها با مشکلات اساسی روبه‌رو هستند. این مقدار از داده‌ها تحت عنوان داده‌های حجیم2 معرفی می‌شوند [3].

معمولاً داده‌های حجیم به 2 دسته داده‌های جریانی3 و داده‌های ایستا4 یا دسته‌ای5 تقسیم می‌شوند. در مورد داده‌های جریانی، داده‌ها به طور مداوم در حال تولیدشدن هستند، در حالی که در مورد داده‌های دسته‌ای تمام داده‌های مورد استفاده از قبل موجود هستند؛ مثل تشخیص تخصیص وام به مشتری جدید که با توجه به مجموعه داده‌ای که از قبل جمع‌آوری شده است، این تصمیم‌گیری انجام می‌شود. کار ارائه‌شده در این مقاله بر روی داده‌های دسته‌ای تمرکز دارد.

KNN (نزدیک‌ترین همسایگی) [4] به صورت گسترده در مسائل طبقه‌بندی6 استفاده می‌شود و از معروف‌ترین تکنیک‌های داده‌کاوی است [5]. این روش بر اساس مفهوم شباهت کار می‌کند و اساس و ایده آن به این صورت است که نمونه‌هایی که مشابه هستند باید به کلاس یکسانی مربوط باشند. شباهت بر اساس معیار فاصله سنجیده می‌شود.

روش نزدیک‌ترین همسایگی، یک روش بر اساس یادگیری تنبل7 است [6]. در این نوع یادگیری، مجموعه آموزش ذخیره شده و فرایند یادگیری تا زمان ورود نمونه آزمایش جدید به تأخیر می‌افتد. با توجه به حجم زیاد داده در مجموعه آموزش، این کار برای داده‌های حجیم مناسب نیست. دقیقاً بر خلاف این روش، نوع دیگری از یادگیری، یادگیری مشتاق8 است که به محض ورود نمونه آزمایش شروع به ساخت مدل می‌کند.

در مورد داده‌های حجیم، یافتن نزدیک‌ترین همسایگی به مقدار زیادی هزینه محاسباتی نیاز دارد. برخی از محققان از چارچوب‌های9 توزیع‌شده مانند آپاچی هدوپ10 برای نمونه‌های آموزش استفاده می‌کنند [7]. این رویکردها معمولاً به یافتن دقیق‌ترین همسایگی نزدیک می‌شوند، اما برای این کار نیاز به استفاده از یک سیستم توزیع‌شده بزرگ است [8].

بیشتر روش‌های شناخته‌شده یادگیری ماشین برای مرحله آموزش پرونده11های حجیم به زمان زیادی نیاز دارند. برای مثال، طبقه‌بندی K نزدیک‌ترین همسایگی (KNN) بیش از 6 هفته طول کشید تا مجموعه داده HIGGS را با استفاده از ماشین‌های محاسباتی قدرتمند طبقه‌بندی کند [9]. بنابراین در مورد پرونده‌های داده‌های حجیم برای تأمین وسیله‌ای برای غلبه بر مشکل اندازه داده‌ها، تسهیل روند تجزیه و تحلیل و به دست آوردن اطلاعات حیاتی که برای برنامه‌های جدید مهم است، نیاز به تفکری مبتکرانه می‌باشد [10].

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

در راستای طبقه‌بندی داده‌های حجیم، کار ارائه‌شده توسط حسنات [16] که جزو گروه سوم طبقه‌بندی بالا می‌باشد، از انتخاب داده تصادفی و روش تپه‌نوردی12 برای یافتن دو دورترین نقطه و ساخت درخت تصمیم استفاده می‌کند و هدف آن سرعت‌بخشیدن به فرایند یافتن نزدیک‌ترین همسایه برای پیداکردن طبقه داده آزمایش می‌باشد. این کار در بخش بعد به طور کامل شرح داده شده است.

این مقاله با ارائه روشی برای انتخاب نقطه اول به صورت هوشمندانه و همچنین استفاده از بافر همپوشانی، از منظر دقت باعث بهبود نتایج کار مذکور گردیده است. روش ارائه‌شده با روش‌هاي معروف موجود، بر روي مجموعه داده‌هاي UCI مقایسه مي‌شود. ارزيابي دقيق نتايج بر روي چند مجموعه داده طبيعي نشان مي‌دهد كه اين الگوريتم، با توجه به زمان کم اجرا و با دقت بالا می‌تواند بر روی مجموعه داده‌های بزرگ مورد استفاده قرار گیرد.

روش ارائه‌شده در اين مقاله به طور خلاصه داراي مزاياي زير است:

1)        انتخاب نقطه اول به صورت هوشمندانه که باعث می‌شود با تعداد پیمایش کمتر، دو دورترین نقطه را یافت که نتیجه کار باعث افزایش سرعت مرحله آموزش می‌شود.

2)        با انتخاب نقطه اول به صورت هوشمندانه، همچنین می‌توان موازنه‌بودن فاصله دو دورترین نقطه را سنجید و از انتخاب 
مقادیر پرت13 به عنوان دورترین نقاط جلوگیری کرد. این کار باعث 
می‌شود درخت بهتر شکل بگیرد و از تشکیل درختان مورب یا با عمق زیاد جلوگیری شود.

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

4)        در اجراهای متفاوت بر روی مجموعه داده یکسان، دقت روش تغییر نکرده و این باعث می‌شود که کار قابل اتکا بوده و بتوان آن را قضاوت کرد.

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

2-       کارهای پیشین

در این بخش، کارهای پیشین انجام‌گردیده برای سرعت‌بخشیدن و افزایش دقت روش k- نزدیک‌ترین همسایگی در محیط داده‌های حجیم بررسی می‌شوند.

استفاده از طبقه‌بندی KNN روی داده‌های حجیم به قدرت محاسباتی بالایی نیاز دارد. در این روش طبقه‌بندی، برچسب کلاس یک نمونه آزمایش بر اساس k تا از نزدیک‌ترین نمونه‌های موجود در مجموعه آموزش تعیین می‌شود [17].

به طور کلی کارهای انجام‌شده در این رابطه به 2 دسته تقسیم می‌شود: کارهایی که از چارچوب موازی و توزیع‌شده مانند آپاچی هدوپ و آپاچی اسپارک14 برای سرعت‌بخشیدن به یافتن نزدیک‌ترین همسایگی استفاده می‌کنند [18] تا [24] و دسته دیگر که از روش‌های تقسیم و غلبه و خوشه‌بندی برای کاهش حجم نمونه‌های آموزش استفاده می‌کنند [25] و [26]. کار این مقاله به دسته دوم مرتبط است.

به عنوان نمونه‌ای از گروه اول، بن هَیم و اِلَد تامتو [27] یک روش سریع ساخت درخت تصمیم پیشنهاد می‌دهند و از روش ارباب- برده15 استفاده می‌کنند. ابتدا داده‌های ورودی به سیستم‌های برده وارد شده و این سیستم‌های برده از این داده‌ها هیستوگرام‌ می‌سازند و یک خلاصه آماری از داده‌ها را در اختیار پردازنده مرکزی قرار می‌دهند. این روش، داده‌ها را در مقدار معینی از حافظه فشرده می‌کند. پردازنده اصلی از این نقاط برای پیداکردن نقاط بهینه تقریبی برای شکستن گره‌های نهایی درخت تصمیم و به روز نگه داشتن درخت استفاده می‌کند. در این گروه کار، ژیا و همکاران [28] برای تعیین ترافیک شهری در ساعات مختلف روشی ارائه کردند که بر اساس آن برای تعیین ترافیک در هر لحظه، علاوه بر استفاده از نزدیک‌ترین همسایگان زمانی برای حدس ترافیک از نزدیک‌ترین همسایگان مکانی نیز استفاده کردند که موجب بهبود دقت کار آنها شده بود و برای پیاده‌سازی کارشان نیز از روش نگاشت- کاهش16 بهره بردند. در کار دیگری، گالگو و بنیتز [22] روشی ارائه کردند که بر اساس آن 
ابتدا از میان داده‌های آموزشی، تعدادی داده با استفاده از نمونه‌برداری هوشمندانه انتخاب می‌شود و از این داده‌ها برای ساخت درخت در رایانه مرکزی استفاده می‌گردد. باقی داده‌ها بر اساس این درخت به برگ‌ها منتسب می‌شوند. به ازای هر برگ، یک رایانه قرار دارد که در آن داده‌های موجود با استفاده از الگوریتم RNGE یک گراف را تشکیل می‌دهند. در مرحله به روز رسانی و طبقه‌بندی داده‌های جدید در ابتدا با پیمایش درخت، داده جدید به یک رایانه می‌رسد. در اطراف داده جدید که برای طبقه‌بندی وارد می‌شود، گراف RNGE به روز رسانی می‌گردد. بر اساس همسایه‌های داده موجود که با یال به آن متصل هستند، تصمیم گرفته می‌شود که داده واردشده مورد قبول است و یا این که به عنوان داده پرت با آن برخورد شده و از مجموعه داده‌ها حذف گردد. همچنین به ازای تمام داده‌های موجود که با یال به داده جدید متصل هستند، بررسی می‌شود که آیا این داده‌ها به داده قدیمی تبدیل شده‌اند؟ در صورت مثبت‌بودن پاسخ، داده قدیمی حذف شده و گراف به روز رسانی می‌شود. معایب این کار عبارتند از پیچیدگی زمانی بالای الگوریتم RNGE و همچنین وابستگی سرعت انجام الگوریتم به تعداد مراحل نگاشت که در نظر گرفته شده است. از مزایای این کار هم می‌توان به پیداکردن نزدیک‌ترین همسایگان به صورت موازی اشاره کرد.

به عنوان نمونه‌ای از گروه دوم، آنجیولی و همکاران [29] یک روش افزایشی جدید برای محاسبه یک زیرمجموعه سازگار از داده‌های آموزشی ارائه کردند. رویکرد پیشنهادی ایشان، نادیده‌گرفتن داده‌هایی بود که به داده‌های موجود شباهت داشتند و اطلاعات جدیدی اضافه نمی‌کردند. راه حل ارائه‌شده در این مقاله در حالی که هنوز دقت قابل قبولی داشت، سرعت یادگیری بهتر و پیچیدگی فضایی پایین‌تری را نسبت به روش نزدیک‌ترین همسایگی نشان می‌داد. در نتیجه برای زمانی که مسئله کمبود حافظه مطرح است، این روش مناسب می‌باشد. از سوی دیگر این روش پیچیدگی محاسباتی بیشتری نسبت به روش نزدیک‌ترین همسایگی دارد. در تحقیق انجام‌شده توسط دنگ و همکاران [30] از روش خوشه‌بندی k-means برای تقسیم فضای نمونه به k تا خوشه استفاده شده است. پس از ساخت خوشه‌ها با توجه به مشخص‌بودن مراکز خوشه‌ها با ورود داده آزمایش، فاصله آن تا مراکز خوشه‌ها سنجیده شده 
و خوشه‌ای که مرکز آن کمترین فاصله را تا داده آزمایش دارد انتخاب می‌گردد. سپس از داده‌های آن به عنوان مجموعه داده آموزشی استفاده شده و با استفاده از روش نزدیک‌ترین همسایگی، برچسب طبقه داده آزمایش را حدس می‌زند. این روش به دو پارامتر برای تعیین تعداد خوشه‌ها و همچنین برای مشخص‌کردن تعداد همسایه‌ها برای روش نزدیک‌ترین همسایگی نیاز دارد که از مشکلات آن هستند. همچنین روش بیان‌شده به دلیل کم‌کردن فضای جستجو، از روش نزدیک‌ترین همسایگی سریع‌تر است اما نسبت به آن روش دقت کمتری دارد. سیدل و کریگل [31] روش جدید چندمرحله‌ای ارائه دادند که از مکانیزم فیلتر برای کاهش تعداد نامزدها و در نتیجه کمترشدن اندازه‌گیری فاصله، در زمان ورود نمونه آزمایش جدید استفاده می‌کند. در نتیجه روش ارائه‌شده در این مقاله سرعت بهتری نسبت به روش نزدیک‌ترین همسایگی دارد. لی و همکاران [32] بر اساس یک رویکرد مبتنی بر تراکم، مقدار داده‌های آموزشی را کاهش دادند و سپس از مجموعه آموزش جدید برای طبقه‌بندی استفاده کردند. در نتیجه سرعت یافتن طبقه داده آزمایش جدید افزایش یافت. در کار انجام‌شده توسط سعادت‌فر و همکاران [8] برای بهبود کار تحقیقاتی دنگ، عنوان شده که معیار فاصله تا مرکز خوشه به تنهایی کفایت نمی‌کند. بنابراین پس از خوشه‌بندی مجموعه داده به وسیله روش k-means، از معیارهای چگالی و همچنین نحوه گسترش داده‌ها در خوشه‌ها استفاده کردند که باعث افزایش دقت کار شده است. همچنین در کار ارائه‌شده توسط گالگو و همکاران [33] از دو روش خوشه‌بندی برای سرعت‌بخشیدن به روش نزدیک‌ترین همسایگی با نام‌های cKNN و +cKNN استفاده شده است. روش دوم از رویکردی فازی17 برای تقویت فرایند خوشه‌بندی استفاده می‌کند. دقت کار آنها به تعداد خوشه‌هایی که انتخاب می‌کنند، بستگی دارد اما با این حال زمانی که از روش شبکه عصبی عمیق18 برای یادگیری و حدس بهتر تعداد خوشه‌ها استفاده می‌کنند، کارشان دقت خوبی را ارائه می‌دهد. همچنین در کار دیگری که توسط ایشان منتشر شد [34]، در بهبود کار قبلی خود روشی به نام caKD+ ارائه کردند که در آن ابتدا با استفاده از شبکه عصبی عمیق سعی نمودند که ویژگی‌های نامرتبط مجموعه داده را نادیده بگیرند و در نتیجه، سرعت یافتن نزدیک‌ترین همسایگی را افزایش دهند. سپس با استفاده 
از خوشه‌بندی، فضای جستجو را با فرض این که تمام نزدیک‌ترین همسایگان در همان خوشه هستند، محدود کردند. برای این منظور در هر خوشه ابتدا تمام نزدیک‌ترین همسایگان هر عضو خوشه نیز به آن خوشه اضافه شدند. علاوه بر این به جای استفاده از یک مقدار k ثابت برای تمام مجموعه داده، با استفاده از یک فرایند پیش‌پردازش، مقدار k مناسب برای هر خوشه مشخص می‌شود. همچنین از یک ساختار داده درخت KD19 برای تسریع در یافتن خوشه مناسب و همچنین جستجو در هر خوشه استفاده کردند. این کار باعث شد که دقت کار آنها بسیار بالا اما 
سرعت کارشان پایین باشد. در کار دیگری که توسط اوگیاروگلو، استفانو، اونگلیدیس و جرجیوس [35] ارائه گردیده است، دو روش برای طبقه‌بندی داده‌های حجیم مطرح شده است. روش اول برای داده‌های ایستا مناسب می‌باشد و ابتدا مراکز هر طبقه را پیدا می‌کند و از این مراکز به عنوان نقطه شروع برای الگوریتم k-means استفاده می‌نماید. پس از پایان خوشه‌بندی، اگر در خوشه‌ای داده ناهمگن وجود داشته باشد این مراحل را تکرار می‌کند. پس از پایان مرحله آموزش با ورود داده آزمایش، طبقه نزدیک‌ترین خوشه به عنوان طبقه داده آزمایش انتخاب می‌شود. با این کار سرعت پیداکردن طبقه نسبت به روش نزدیک‌ترین همسایگی افزایش اما دقت کاهش پیدا می‌کند. در روش دوم پیشنهادی در مقاله ایشان از وزن برای داده‌ها و همچنین از بافر استفاده می‌کنند که برای داده‌های جریانی مناسب است.

در کار دیگری، ونگ و همکاران [36] روشی مبتنی بر ساخت درخت دودویی متوازن برای طبقه‌بند چندمتغیره ارائه کردند که دقت بالایی دارد. در این مقاله از دو روش برای محاسبه وزن برای تشکیل درخت استفاده شده است: یکی به صورت تصادفی که با MDT RND و دیگری با استفاده از روش PCA که با MDT PCA نمایش داده شده است. از 
این درخت‌ها برای سرعت‌بخشیدن به مرحله آزمایش استفاده می‌شود و همچنین در هر برگ این درخت‌ها تنها یک داده وجود دارد که در نتیجه برای پیداکردن همسایگی نیاز به پیچیدگی بالا ندارد. در این مقاله در بخش آزمایش‌ها از این دو روش برای مقایسه کار استفاده شده است.

همچنین حسنات [16] روشی را برای ساخت درخت دودویی ارائه کرده که مبتنی بر پیداکردن دو دورترین نقطه با استفاده از روش تپه‌نوردی محلی است. در این کار در هر لحظه فقط دو نقطه اصلی داریم. ابتدا یک نقطه به صورت تصادفی انتخاب شده و بعد دورترین نقطه از این داده را پیدا کرده و به عنوان نقطه اصلی در نظر می‌گیرد. در جستجوی بعدی به دنبال یافتن دورترین نقطه از نقطه اول می‌گردد و با یافتن این نقطه، آن را نقطه اصلی دوم قرار می‌دهد. در این مرحله از روش بازگشتی استفاده کرده و دومین نقطه اصلی را معیار قرار داده و به دنبال دورترین نقطه از این نقطه می‌گردد. اگر نقطه‌ای پیدا کند که فاصله آن تا نقطه اصلی دوم از دورترین نقاط یافته‌شده فعلی بیشتر باشد، نقاط یافته‌شده فعلی را به عنوان دورترین نقاط موجود، جایگزین نقاط قبلی می‌کند و این فرایند را تکرار می‌کند تا دورترین نقاط را پیدا کند. حال این دو نقطه را فرزندان گره فعلی در نظر می‌گیرد. سپس داده‌های موجود در گره فعلی را با توجه به شباهتشان به این دو داده به دو گروه تقسیم می‌کند. برای هر کدام از فرزندان همین کار را تکرار می‌کند تا درخت تصمیمی ایجاد شود که در هر گره آن یک داده قرار داشته باشد. در این کار چون نقطه اول به صورت هدفمند انتخاب نمی‌شود و به صورت تصادفی این کار انجام می‌گردد، در هر اجرا ممکن است در دام قله محلی گرفتار شده و جواب متفاوتی ارائه دهد که این برای کار طبقه‌بندی مناسب نیست. همچنین برای پیداکردن دو دورترین نقطه نیاز است به تعداد دفعات زیاد داده‌های موجود در گره فعلی پیمایش گردند. از ایده این کار برای روش ارائه‌شده در این مقاله استفاده گردیده است. این کار نیز در بخش آزمایش‌ها برای مقایسه با روش ارائه‌شده با نام FPBST آمده است.

در دیگر کار ارائه‌شده توسط حسنات [9]، ابتدا نرم دوم تمام داده‌های موجود در گره محاسبه می‌شود. در مرحله بعد با استفاده از دو روش ذکرشده در مقاله، کمترین و بیشترین نرم داده‌های موجود محاسبه شده و از آنها برای تقسیم فضای داده به دو زیردرخت استفاده می‌کند. این گام‌ها را برای هر دو زیردرخت تا رسیدن به گره برگ نیز تکرار می‌کند. این روش سرعت بیشتر اما در عین حال دقت به مراتب کمتری نسبت به روش FPBST دارد. در دیگر کار ارائه‌شده توسط حسنات [37]، روش‌های مختلف که توسط ایشان ارائه شده است مورد آزمایش قرار گرفته‌اند. این روش‌ها عبارت هستند از Tabu، Beam و EPBST که همگی دارای پیچیدگی زمانی بیشتر و نیز دقت کمتری نسبت به FPBST هستند. همچنین در کار دیگری که توسط ایشان منتشر شد [38]، برای ساخت درخت از دو روش RPBST و EPBST استفاده می‌کند. در روش RPBST از روش تصادفی برای انتخاب دو نقطه برای ساخت درخت استفاده می‌کند و داده‌ها را بر اساس شباهتشان به این دو داده به دو گروه تقسیم می‌نماید و این کار را ادامه می‌دهد. در روش EPBST ابتدا بیشینه و کمینه نرم داده‌ها را در گره ریشه پیدا می‌کند و به این داده‌ها بیشینه و کمینه سراسری می‌گوید، سپس داده‌ها را بر اساس شباهتشان به این دو داده به دو گروه تقسیم می‌کند. در هر کدام از فرزندان نیز دو داده که بیشترین شباهت را به کمینه و بیشینه سراسری دارند، انتخاب می‌کند و تقسیم‌بندی داده‌ها را بر اساس شباهتشان به این دو نقطه به دو گروه تقسیم می‌کند. این کار به صورت بازگشتی تا رسیدن به گره برگ انجام می‌شود. این روش‌ها از روش FPBST که توسط آقای حسنات ارائه شد سرعت بیشتر و دقت کمتری دارند.

در روش ارائه‌شده در این مقاله از بافر همپوشانی برای افزایش دقت استفاده گردیده که در واقع شکل ساده و تغییریافته از spill-tree که در کار [39] ارائه شده است، می‌باشد. در بخش بعد به طور مفصل در رابطه با روش ارائه‌گردیده صحبت می‌شود.

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

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

معمولاً در یادگیری ماشین20 مجموعه‌ای تحت عنوان مجموعه آموزش شامل تعدادی نمونه21 که هر نمونه با برچسب طبقه‌ا‌ش مشخص شده است، در دسترس می‌باشد. یک نمونه داده با بردار ویژگی نمایش داده می‌شود. پیچیدگی زمانی برای پیداکردن نزدیک‌ترین همسایگی یک نمونه ورودی از مرتبه img0 است که img0 تعداد رکوردهای موجود در مجموعه داده و img0 نشان‌دهنده ابعاد آن می‌باشد و به این دلیل که در محیط داده‌های حجیم img0 مقدار بزرگی دارد، روش پیداکردن نزدیک‌ترین همسایگی غیر بهینه است.

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

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

از فاصله اقلیدسی که یکی از شناخته‌شده‌ترین معیارهای اندازه‌گیری موجود می‌باشد، برای اندازه‌گیری میزان شباهت استفاده شده است. فاصله بین دو نقطه img0 با استفاده از (1) تعریف می‌شود

 

[1] این مقاله در تاریخ 23 آبان ماه 1400 دریافت و در تاریخ 10 اسفند ماه 1400 بازنگری شد.

حسین کلاته، دانشكده مهندسي كامپيوتر، دانشگاه تربیت دبیر شهید رجائی، تهران، ایران، (email: h.kalateh@sru.ac.ir).

نگین دانشپور (نویسنده مسئول)، دانشکده مهندسی کامپیوتر، دانشگاه تربیت دبیر شهید رجائی، تهران، ایران، (email: ndaneshpour@sru.ac.ir).

[2] . Big Data

[3] . Stream Data

[4] . Static Data

[5] . Batch Data

[6] . Classification

[7] . Lazy Learning

[8] . Eager Learning

[9] . Framework

[10] . Apache Hadoop

[11] . File

[12] . Hill Climbing

[13] . Outlier

[14] . Apache Spark

[15] . Master-Slave

[16] . Map-Reduce

[17] . Fuzzy

[18] . Deep Neural Network

[19] . KD Tree

[20] . Machine Learning

[21] . Instance

جدول 1: خلاصه روش‌های ارائه‌شده در کارهای پیشین. 

 

معایب

مزایا

توضیح مختصر

سال ارائه

نام مقاله

 

افت دقت (کم)

پیداکردن نقاط split 
به صورت موازی

کار این الگوریتم، ساخت سریع درخت تصمیم از هیستوگرام‌های ساخته‌شده در پردازنده‌های slave است که داده‌ها را به مقدار معینی فشرده می‌کند و یک دید آماری از داده‌ها ارائه می‌دهد. یک پردازنده اصلی نیز از این نقاط برای پیداکردن نقاط بهینه تقریبی برای شکستن گره‌های نهایی درخت استفاده می‌کند.

2010

[27]

گروه اول (کارهای ارائه‌شده برای داده‌های جریانی و با استفاده از سیستم‌های توزیع‌شده)

نرخ خطا (کم)

نیاز به یک بار رصد داده‌ها دارد.

 

قوانین قابل فهم برای 
انسان (ویژگی DT)

داده تست را به همه گره‌ها می‌فرستد و گامی برای پیش‌بینی گره مناسب ندارد.

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

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

2016

[28]

با استفاده از ویژگی وزن‌دهی به رأی‌ها بر اساس نزدیکی به محل مورد نظر، اثر img0 را کم‌رنگ می‌کند.

پیچیدگی زمانی بالا

انجام img0 نزدیک‌ترین همسایه که روشی بر پایه یادگیری تنبل است به صورت موازی برای داده‌های جریانی.

الگوریتم ارائه‌شده از درخت m-tree استفاده می‌کند و kNN را که روشی بر اساس یادگیری تنبل است، برای جریان داده‌ها مناسب می‌کند و به صورت موازی از آن استفاده می‌نماید.

2017

[22]

سرعت وابسته به تعداد مراحل نگاشت

پیچیدگی زیاد

دقت قابل قبول

با نادیده‌گرفتن داده‌هایی که اطلاعات جدید به سیستم اضافه نمی‌کنند، باعث کم‌شدن حجم داده می‌شود.

2005

[29]

گروه دوم (کارهای ارائه‌شده برای داده‌های ایستا و با استفاده از یک رایانه)

سرعت کم

به انتخاب img0 و img0 (تعداد خوشه‌ها) حساس است.

فضای آموزش را کاهش می‌دهد، در نتیجه زمان کمتری نسبت به kNN دارد.

ابتدا با استفاده از k-means خوشه می‌سازد و سپس در قسمت آزمایش، ابتدا نزدیک‌ترین خوشه را برای داده ورودی پیدا می‌کند و سپس درون نزدیک‌ترین خوشه، روش kNN را برای پیداکردن برچسب داده‌های ورودی جدید اعمال می‌نماید.

2016

[30]

در مقایسه با kNN 
کمی افت دقت دارد.

دقت کمتر نسبت 
به FPBST

سرعت بیشتر نسبت به FPBST

در این کار ابتدا نرم دوم تمام داده‌ها محاسبه شده و سپس با توجه به دو راه حل برای کمینه و بیشینه نرم، شروع به ساخت درخت دودویی می‌کند.

2018

[9]

پیچیدگی زمانی زیاد

مناسب برای داده‌های بزرگ

روش‌هایی از قبیل تپه‌نوردی، BEAM و TABU را ارائه می‌کند که همگی بر اساس ساخت درخت دودویی هستند.

2018

[37]

دقت کمتر نسبت به FPBST

دقت پایین‌تر نسبت 
به FPBST

سرعت بهتر نسبت به FPBST

ابتدا کوچک‌ترین و بزرگ‌ترین نرم داده‌ها را پیدا می‌کند و از این داده‌ها برای تقسیم‌کردن داده‌ها در تمام مراحل استفاده می‌نماید.

2018

[38]

کاهش دقت به خاطر محاسبه نزدیک‌ترین همسایگی به صورت تقریبی

افزایش سرعت نسبت به kNN

ابتدا مرکز هر کلاس را برای نقطه شروع k-means انتخاب می‌نماید. پس از اتمام خوشه‌بندی، این کار را برای خوشه‌های ناهمگن تکرار می‌کند. در روش بعدی هم برای داده‌های جریانی مناسب بوده و از وزن و بافر استفاده می‌کند.

2014

[35]

دقت قابل قبول

پیچیدگی بالا

دقت خوب کار

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

2018

[33]

زمان زیاد اجرا

سرعت پایین

دقت بالاتر نسبت به روش‌های cKNN و +cKNN

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

2022

[34]

پیچیدگی زیاد و سرعت کم

دقت بالا و قابل قبول

ابتدا داده‌ها را بر روی بردار تصادفی و PCA نگاشت و سپس آنها را نصف می‌کند. اگر خلوص هر گروه کافی بود که ادامه نمی‌دهد و در غیر این صورت دو گره جدید ایجاد می‌کند.

2018

[36]

احتیاج به زمان بیشتری دارد.

بهبود دقت کار آقای دنگ

در بهبود کار آقای دنگ ذکر کردند که فاصله به تنهایی کفایت نمی‌کند و پس از خوشه‌بندی با k-means از معیارهای چگالی و نحوه گسترش داده‌ها نیز استفاده کردند.

2020

[8]

وابستگی به معیارهای 
img0 و img0

 

 

img0 

شکل 1:  مرحله آموزش.

 

img0        (1)

در (1)، img0 و img0 دو نمونه داده می‌باشند که با استفاده از بردار ویژگی img0 توصیف می‌گردند که img0 نشان‌دهنده img0امین ویژگی نمونه img0 است.

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

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

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

حال با فرض این که دو دورترین نقطه یافته‌شده به ترتیب نقاط 1P و 2P باشند، با توجه به شکل 2 برای پیداکردن برچسب طبقه داده‌های موجود در گره از وسط فاصله دو دورترین نقطه یعنی خط M داده‌ها به دو گروه تقسیم می‌شوند. با استفاده از روش مذکور، نقطه‌ای که با علامت سؤال مشخص شده است، به زیردرخت راست و نقطه‌ای که از لحاظ فاصله با نقطه مورد نظر کمترین فاصله را دارد به زیردرخت سمت چپ تعلق می‌گیرد. این برخلاف خواسته ما که استفاده از روش نزدیک‌ترین همسایگی می‌باشد است.

img0 

شکل 2:  مشکل ساخت درخت تقریبی.

 

img0 

شکل 3:  استفاده از بافر همپوشانی برای مقابله با مشکل ساخت درخت تقریبی.

 

 

img0 

شکل 4:  نحوه تغییرات دقت و زمان آموزش با تغییر مقدار img0.

 

 

جدول 2: مقادیر مختلف img0 به ازای مجموعه داده‌های مختلف.

 

نام مجموعه داده

img0 

نام مجموعه داده

img0 

covtype

12%

Normalized Covtype

2%

HIGGS

1%

Normalized HIGGS

1%

letter

11%

Normalized letter

11%

SUSY

4%

Normalized SUSY

4%

waveform

10%

Normalized waveform

7%

satimage

16%

Normalized satimage

17%

Mnist

4%

Physical Unclonable Functions

6%

 

برای مقابله با این مشکل طبق شکل 3 به جای این که از خط M داده‌ها به دو قسمت تقسیم شوند از بافر همپوشانی استفاده می‌شود. بافر همپوشانی یک حاشیه امن است که در اطراف خط M ایجاد می‌گردد و داده‌های درون آن در هر 2 فرزند گره موجود نگهداری می‌شود. به عبارت دیگر، داده‌های موجود در سمت چپ MR در زیردرخت چپ گره فعلی و داده‌های موجود در سمت راست ML در شاخه راست گره فعلی ذخیره می‌شوند. این کار باعث ایجاد داده‌های تکراری و اضافی در درخت می‌شود و در سرعت اجرای روش تأثیر می‌گذارد، اما باعث افزایش دقت و از بین رفتن مشکل عنوان‌شده می‌شود. برای تعیین مقدار بافر همپوشانی دو راه وجود دارد: راهکار اول آن است که این مقدار را یک مقدار ثابت در نظر گرفت. برای مثال img0 را 2/0 در نظر گرفت و این کار را تا زمانی که مقدار img0 بزرگ‌تر از نصف فاصله دو دورترین نقطه شود در هر مرحله تکرار کرد، چون در غیر این صورت درخت به سمت بی‌نهایت کشیده می‌شود. راهکار دوم این است که مقدار img0 در هر مرحله برابر درصدی از فاصله دو دورترین نقطه باشد که با این کار می‌توان تا آخرین مرحله ساخت درخت از بافر همپوشانی استفاده کرد. در این مقاله از روش دوم استفاده شده و مقدار img0 در هر مجموعه داده با توجه به آزمایش‌های مختلف بر اساس موازنه بین سرعت و دقت تعیین شده است. زیرا با افزایش img0، دقت کار افزایش اما سرعت کاهش می‌یابد. برای تعیین حد بالای img0 به این نحو عمل شده که در هر مرحله، مقدار img0 در الگوریتم به مقدار 01/0 افزایش داده می‌شود و زمان آن به نسبت اجرای قبل محاسبه می‌گردد. اگر زمان انجام مرحله آموزش نسبت به مرحله قبل دو برابر یا بیشتر شده باشد، اجرا به پایان می‌رسد. در این میان با توجه به داده‌های test و train موجود، مقدار img0 برای الگوریتم به گونه‌ای انتخاب می‌شود که مقدار دقت را بیشینه کند. همچنین مقدار img0 انتخابی باید کمتر از 5/0 باشد، در غیر این صورت درخت به سمت بی‌نهایت میل خواهد کرد. مثلاً در شکل 4 برای مجموعه داده Normalized covtype مشاهده می‌شود که با تغییر مقدار img0 از مقدار 01/0 به مقدار 02/0، زمان اجرا از 8490 میلی‌ثانیه به 17010 میلی‌ثانیه افزایش می‌یابد. در نتیجه اجرا پایان یافته و مقدار مناسب img0 برای این کار با توجه به دقت به دست آمده برابر 02/0 خواهد بود. به همین طریق برای مجموعه داده‌های استفاده‌شده، مقدار img0 به دست آمده که در جدول 2 قابل مشاهده است.

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

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

img0 

شکل 5:  مرحله آزمایش. 

 

اگر در گره برگ فقط یک داده وجود داشته باشد، نیاز به استفاده از روش نزدیک‌ترین همسایگی نیست چون نزدیک‌ترین همسایه مشخص است. اما در کار ارائه‌شده در هر صورت از روش نزدیک‌ترین همسایگی برای یافتن برچسب مناسب استفاده شده است. روش توضیح داده­شده برای مرحله آزمایش، در شکل 5 نشان داده شده است.

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

4-       آزمایش‌ها

برای انجام آزمایش‌ها و ارزیابی کار ارائه‌شده از سیستمی با پردازنده G3400 5 AMD Ryzen به همراه 16 گیگابایت حافظه استفاده گردیده و برنامه شرح داده شده به زبان جاوا نوشته شده است. البته به این دلیل که باقی روش‌ها هم برای مجموعه داده HIGGS با این مقدار حافظه قابل پیاده‌سازی نبودند، برای این مجموعه داده خاص، برای تمام روش‌های مقایسه‌شده از 32 گیگابایت حافظه استفاده گردیده است. همچنین برای اجرا از حالت تک‌نخی استفاده شده که راهکار ارائه‌شده هم در زمان محاسبه میانگین و به دست آوردن دورترین نقاط و تخصیص داده‌های محلی به فرزندان و هم در زمان ورود و آزمایش داده جدید، قابلیت اجرا به صورت چندنخی را دارد که باعث بهبود سرعت می‌شود.

 

 

 

در این مقاله از مجموعه داده‌های مختلف استفاده شده که اندازه آنها از 5000 تا 11 میلیون رکورد و ابعاد آنها از 18 تا 784 ویژگی1 متغیر بوده که مشخصات آنها در جدول 3 آمده است. همچنین در آزمایش‌ها به جز مجموعه داده‌های MNIST و Physical Unclonable Functions که به صورت مجموعه آموزش و آزمایش از پیش مشخص شده در مخزن UCI قرار داده شده‌اند، برای باقی مجموعه داده‌ها از اعتبارسنجی متقابل 5تایی2 برای آزمایش روش‌ها استفاده شده و از نتایج، میانگین گرفته شده است. همچنین به دلیل این که این دو مجموعه داده به صورت نرمال‌شده در دسترس هستند، تنها یک بار مورد آزمایش قرار گرفته‌اند. نیز در روش MDT PCA و MDT RND طبق پیشنهاد نویسندگان مقاله ارائه‌شده برای هر قسمت از img0 استفاده گردیده و میانگین گرفته شده است. برای مجموعه داده‌های بزرگ‌تر مانند HIGGS از مقدار img0 و SUSY و Physical Unclonable Functions از میانگین نتایج حاصل از img0 استفاده شده است.

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

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

 

[1] . Attribute

[2] . 5-Fold-Cross-Validation

جدول 3: مشخصات مجموعه داده‌های استفاده‌شده در آزمایش‌ها.

 

تعداد کلاس

تعداد ویژگی

اندازه مجموعه آموزش

اندازه مجموعه تست

نوع داده

تعداد رکورد

نام مجموعه داده

2

28

8800000

2200000

حقیقی

11000000

HIGGS

2

128

5000000

1000000

صحیح

6000000

Physical Unclonable Functions

2

18

4000000

1000000

حقیقی

5000000

SUSY

7

54

464809

116203

صحیح

581012

covtype

10

784

60000

10000

صحیح

70000

mnist

26

16

16000

4000

حقیقی

20000

letter

6

86

5144

1286

صحیح

6430

satimage

3

21

4000

1000

حقیقی

5000

waveform

 

جدول 4: متوسط زمان اجرا برای مرحله آموزش بر حسب میلی‌ثانیه (مقادیر توپر نشان‌دهنده بهترین نتایج به ازای هر مجموعه داده است).

 

روش ارائه‌شده 
بدون بافر همپوشانی

روش ارائه‌شده همراه با بافر همپوشانی

FPBST [16]

MDT PCA [36]

MDT RND [36]

نام مجموعه داده

5648

15099

6308

23735

28253

covtype

8059

17010

8975

445618

673655

Normalized Covtype

373746

434868

398054

4319711

9822844

HIGGS

358041

400486

386421

7365151

13489007

Normalized HIGGS

294

706

344

3616

3836

letter

325

612

331

3702

3916

Normalized letter

68555

120121

74499

249358

384764

SUSY

77765

133374

80458

2429040

2656200

Normalized SUSY

175

46

208

429

322

waveform

256

62

291

510

358

Normalized waveform

8580

21657

8752

119568

556251

Mnist

266

665

269

547

394

satimage

244

540

276

564

397

Normalized satimage

123662

156783

124085

34559288

31162527

Physical Unclonable Functions

 

 

میانگین به 4 تا 7 بار پیمایش نیاز دارد و این مقدار حتی می‌تواند بیشتر هم باشد. بنابراین در روش ارائه‌شده، اغلب اوقات هم زمان مرحله آموزش و هم تعداد سطوح درخت کاهش می‌یابد که نتیجه آن، اجرای سریع‌تر و دقیق‌تر مرحله آزمایش است. همچنین از آنجا که مؤلفان در [16] روش FPBST را بیان کرده‌اند و برای مقایسه کارشان کارهای MDT RND و MDT PCA را انتخاب کرده‌اند و دلایل برتری کارشان نسبت به این کارها توضیح داده شده است، در این کار نیز برای مقایسه، این کارها انتخاب شده‌اند.

در ادامه و در جدول 4، متوسط زمان اجرای مرحله آموزش بر حسب میلی‌ثانیه برای روش‌های مورد مقایسه نمایش داده شده است. نتایج نشان می‌دهند که روش ارائه‌شده در این مقاله که در ستون‌های 5 و 6 جدول مذکور قرار دارد به نسبت روش‌های MDT PCA و MDT RND سرعت خیلی بیشتری دارد. همچنین بر اساس توضیحات داده‌شده در همین بخش، روش ارائه‌شده نسبت به روش FPBST نیز سریع‌تر است. در این جدول به عنوان مثال در مورد مجموعه داده HIGGS که با 11 میلیون رکورد بیشترین داده را دارا می‌باشد، همان طور که مشخص است روش ارائه‌شده بدون بافر همپوشانی بهترین نتیجه را دارد. همچنین در مورد مجموعه داده Mnist که بیشترین تعداد ویژگی را دارا است، طبق نتایج حاصل‌شده، روش ارائه‌گردیده بدون بافر همپوشانی به دلایل توضیح داده شده بهترین زمان را ثبت کرده است. در جدول 5 نیز متوسط زمان اجرای مرحله آزمایش بر حسب میلی‌ثانیه نمایش داده شده است. همان طور که در جدول مشخص است در بیشتر آزمایش‌ها با مجموعه داده‌های مختلف، روش ارائه‌شده بدون بافر همپوشانی بهترین زمان را ثبت کرده است. در بعضی از مجموعه داده‌ها روش ارائه‌شده با بافر همپوشانی بهترین زمان را داشته و این زمان خوب با وجود دقت بسیار بالای این روش می‌باشد. به عنوان نمونه در حالت نرمال، کار ارائه‌شده بدون بافر همپوشانی هم در مورد مجموعه داده HIGGS و Mnist که به ترتیب دارای بیشترین نمونه و بیشترین ویژگی هستند، بهترین زمان را ثبت کرده است. در جدول 6 متوسط دقت به ازای هر مجموعه داده نمایش داده شده است. همان طور که در جدول آمده است، در همه مجموعه داده‌ها به جز SUSY و Physical Unclonable Functions روش ارائه‌شده همراه با بافر همپوشانی، بهترین دقت را دارد. در این دو مجموعه داده نیز زمان بسیار کمتر بوده و البته میزان دقت، بسیار نزدیک به بهترین دقت به دست آمده می‌باشد. این دقت‌ها برای هر مجموعه داده از میانگین 5 اجرای انجام‌شده محاسبه گردیده است. برای آن که این کارها به صورت کلی قابل قیاس باشند، در ردیف آخر جدول 6 میانگین دقت به ازای هر روش محاسبه شده است.

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

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

جدول 5: متوسط زمان اجرا برای مرحله آزمایش بر حسب میلی‌ثانیه (مقادیر توپر نشان‌دهنده بهترین نتایج به ازای هر مجموعه داده است).

 

روش ارائه‌شده 
بدون بافر همپوشانی

روش ارائه‌شده همراه با بافر همپوشانی

FPBST [16]

MDT PCA [36]

MDT RND [36]

نام مجموعه داده

1182

1700

1360

24788

25456

Covtype

1715

2000

1699

5472

7385

Normalized Covtype

355637

130063

342714

158029

175008

HIGGS

118511

131193

191630

161229

195593

Normalized HIGGS

31

45

31

112

188

Letter

31

40

31

109

191

Normalized letter

18021

33766

18510

150580

158972

SUSY

21024

37723

22116

172747

204119

Normalized SUSY

15

5

16

85

79

Waveform

15

15

28

74

112

Normalized waveform

985

1718

985

7083

9015

Mnist

20

18

25

136

139

Satimage

15

12

27

131

142

Normalized satimage

73794

79977

62047

155712

157473

Physical Unclonable Functions

 

جدول 6: متوسط دقت آزمایش‌های انجام‌شده به صورت درصد (مقادیر توپر نشان‌دهنده بهترین نتایج به ازای هر مجموعه داده است).

 

روش ارائه‌شده بدون بافر همپوشانی

روش ارائه‌شده همراه با بافر همپوشانی

FPBST [16]

MDT PCA [36]

MDT RND [36]

نام مجموعه داده

5403/58%

34/64%

8301/57%

264/44%

702/45%

Covtype

368/62%

07/67%

855/61%

598/58%

56/62%

Normalized Covtype

2078/58%

89242/60%

18/58%

704/59%

262/58%

HIGGS

6183/58%

8988/58%

2332/57%

832/58%

398/57%

Normalized HIGGS

52/78%

27/95%

34/77%

41/75%

95/59%

Letter

52/78%

27/95%

39/77%

406/75%

968/59%

Normalized letter

9688/70%

7865/71%

92946/70%

476/72%

738/68%

SUSY

8812/66%

8772/68%

7591/66%

208/67%

33/66%

Normalized SUSY

36/77%

98/78%

24/76%

76/75%

308/66%

Waveform

42/75%

54/78%

06/75%

74/75%

66/65%

Normalized waveform

92/84%

53/95%

86/84%

3/83%

34/52%

Mnist

554/85%

86/90%

316/85%

69/81%

306/76%

Satimage

88/85%

41/90%

6/85%

454/80%

816/75%

Normalized satimage

9697/49%

9973/49%

9341/49%

0/50%

93/49%

Physical Unclonable Functions

8378/70%

1945/76%

3234/70%

4887/68%

3806/61%

میانگین

 

 

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

مراجع

[1]       X. Lv, "The big data impact and application study on the like ecosystem construction of open internet of things," Cluster Computing, vol. 22, no. 2, pp. 3563-3572, Mar. 2019.

[2]       V. Marx, Biology: the Big Challenges of Big Data, Ed: Nature Publishing Group, 2013.

[3]       I. Triguero, J. Maillo, J. Luengo, S. García, and F. Herrera, "From big data to smart data with the k-nearest neighbours algorithm," in Proc. IEEE Int. Conf. on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData), pp. 859-864, Chengdu, China, 15- 18 Dec. 2016.

[4]       D. W. Aha, D. Kibler, and M. K. Albert, "Instance-based learning algorithms," Machine Learning, vol. 6, no. 1, pp. 37-66, Jan. 1991.

[5]       T. Cover and P. Hart, "Nearest neighbor pattern classification," IEEE Trans. on Information Theory, vol. 13, no. 1, pp. 21-27, Jan. 1967.

[6]       D. W. Aha, Lazy Learning, in Lazy learning: Kluwer Academic Publishers, pp. 7-10, 1997.

[7]       P. P. Anchalia and K. Roy, "The k-nearest neighbor algorithm using mapreduce paradigm," in Proc. 5th IEEE Int. Conf. on Intelligent Systems, Modelling and Simulation, pp. 513-518, Langkawi, Malaysia, 27- 9 Jan. 2014.

[8]       H. Saadatfar, S. Khosravi, J. H. Joloudari, A. Mosavi, and S. Shamshirband, "A new k-nearest neighbors classifier for big data based on efficient data pruning," Mathematics, vol. 8, no. 2, p. 286, Feb. 2020.

[9]       A. Hassanat, "Norm-based binary search trees for speeding up knn big data classification," Computers, vol. 7, no. 4, pp. 5, Oct. 2018.

[10]       D. Zhu, "Humor robot and humor generation method based on big data search through IOT," Cluster Computing, vol. 22, no. 4, pp. 9169-9175, Jul. 2019.

[11]       J. Calvo-Zaragoza, J. J. Valero-Mas, and J. R. Rico-Juan, "Improving kNN multi-label classification in prototype selection scenarios using class proposals," Pattern Recognition, vol. 48, no. 5, pp. 1608-1622, May 2015.

[12]       X. Wu, X. Zhu, G. Q. Wu, and W. Ding, "Data mining with big data," IEEE Trans. on Knowledge and Data Engineering, vol. 26, no. 1, pp. 97-107, Jun. 2013.

[13]       S. García, J. Luengo, and F. Herrera, Data Preprocessing in Data Mining, Springer, 2015.

[14]       L. Micó and J. Oncina, "A constant average time algorithm to allow insertions in the LAESA fast nearest neighbour search index," in Proc. 20th IEEE Int. Conf. on Pattern Recognition, pp. 3911-3914, Istanbul, Turkey, 23- 26 Aug. 2010.

[15]       A. Bifet, et al., "Extremely fast decision tree mining for evolving data streams," in Proc. of the 23rd ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 1733-1742, Halifax, Canada, 13-17 Aug. 2017.

[16]       A. B. Hassanat, "Furthest-pair-based binary search tree for speeding big data classification using k-nearest neighbors," Big Data, vol. 6, no. 3, pp. 225-235, Sept 2018.

[17]       X. Wu, et al., "Top 10 algorithms in data mining," Knowledge and Information Systems, vol. 14, no. 1, pp. 1-37, Jan. 2008.

[18]       E. Plaku and L. E. Kavraki, "Distributed computation of the kNN graph for large high-dimensional point sets," J. of Parallel and Distributed Computing, vol. 67, no. 3, pp. 346-359, Mar. 2007.

[19]       C. Zhang, F. Li, and J. Jestes, "Efficient parallel kNN joins for large data in mapreduce," in Proc. of the 15th Int. Conf. on Extending Database Technology, pp. 38-49, Berlin, Germany, 27-30 Mar. 2012.

[20]       K. Sun, H. Kang, and H. H. Park, "Tagging and classifying facial images in cloud environments based on KNN using mapreduce," Optik, vol. 126, no. 21, pp. 3227-3233, Nov. 2015.

[21]       J. Maillo, S. Ramírez, I. Triguero, and F. Herrera, "kNN-IS: an iterative spark-based design of the k-nearest neighbors classifier for big data," Knowledge-Based Systems, vol. 117, no. 1, pp. 3-15, Feb. 2017.

[22]       S. Ramírez-Gallego, B. Krawczyk, S. García, M. Woźniak, J. M. Benítez, and F. Herrera, "Nearest neighbor classification for high-speed big data streams using spark," IEEE Trans. on Systems, Man, and Cybernetics: Systems, vol. 47, no. 10, pp. 2727-2739, Jul. 2017.

[23]       G. Chatzigeorgakidis, S. Karagiorgou, S. Athanasiou, and S. Skiadopoulos, "FML-kNN: scalable machine learning on big data using k-nearest neighbor joins," J. of Big Data, vol. 5, no. 1, pp. 1-27, Feb. 2018.

[24]       S. Bagui, A. K. Mondal, and S. Bagui, "Improving the performance of kNN in the mapreduce framework using locality sensitive hashing," International J. of Distributed Systems and Technologies, vol. 10, no. 4, pp. 1-16, Oct. 2019.

[25]       Z. Yong, L. Youwen, and X. Shixiong, "An improved KNN text classification algorithm based on clustering," J. of Computers, vol. 4, no. 3, pp. 230-237, Mar. 2009.

[26]       H. Neeb and C. Kurrus, Distributed k-Nearest Neighbors, Ed: Stanford University Publishing: Stanford, CA, USA, 2016.

[27]       Y. Ben-Haim and E. Tom-Tov, "A streaming parallel decision tree algorithm," J. of Machine Learning Research, vol. 11, no. 2, pp. 849-872, Feb.  2010.

[28]       D. Xia, H. Li, B. Wang, Y. Li, and Z. Zhang, "A map reduce-based nearest neighbor approach for big-data-driven traffic flow prediction," IEEE Access, vol. 4, pp. 2920-2934, Jun. 2016.

[29]       F. Angiulli, "Fast condensed nearest neighbor rule," in Proc. of the 22nd Int. Conf. on Machine learning, pp. 25-32, New York, NY, USA, 7-11Aug. 2005.

[30]       Z. Deng, X. Zhu, D. Cheng, M. Zong, and S. Zhang, "Efficient kNN classification algorithm for big data," Neurocomputing, vol. 195,
no. 100, pp. 143-148, Jun. 2016.

[31]       T. Seidl and H. P. Kriegel, "Optimal multi-step k-nearest neighbor search," SIGMOD Rec., vol. 27, no. 2, pp. 154-165, Jun. 1998.

[32]       L. R. Lu and H. Y. Fa, "A density-based method for reducing the amount of training data in kNN text classification," J. of Computer Research and Development, vol. 45, no. 4, pp. 539–544, Aug. 2004.

[33]       A. J. Gallego, J. Calvo-Zaragoza, J. J. Valero-Mas, and J. R. Rico-Juan, "Clustering-based k-nearest neighbor classification for large-scale data with neural codes representation," Pattern Recognition, vol. 74, no. 1, pp. 531-543, Feb. 2018.

[34]       A. J. Gallego, J. R. Rico-Juan, and J. J. Valero-Mas, "Efficient k-nearest neighbor search based on clustering and adaptive k values," Pattern Recognition, vol. 122, Article ID: 108356, Feb. 2022.

[35]       S. Ougiaroglou and G. Evangelidis, "RHC: a non-parametric cluster-based data reduction for efficient k kNN classification," Pattern Analysis and Applications, vol. 19, no. 1, pp. 93-109, Feb. 2016.

[36]       F. Wang, Q. Wang, F. Nie, W. Yu, and R. Wang, "Efficient tree classifiers for large scale datasets," Neurocomputing, vol. 284, no. 2, pp. 70-79, Apr. 2018.

[37]       A. Hassanat, "Greedy algorithms for approximating the diameter of machine learning datasets in multidimensional euclidean space: experimental results," 2018.

[38]       A. B. Hassanat, "Two-point-based binary search trees for accelerating big data classification using KNN," PloS One, vol. 13, no. 11, Article ID: e0207772, Nov. 2018.

[39]       T. Liu, A. W. Moore, K. Yang, and A. G. Gray, "An investigation of practical approximate nearest neighbor algorithms," in Proc. 17th Int. Conf. on Information Processing Systems, pp. 825-832, Vancouver, Canada,13-18 Dec. 2004.

 

حسین کلاته مدرک کارشناسی خود را در سال 1395 از دانشگاه سمنان اخذ نموده است. نام­برده همچنین مدرک کارشناسی ارشد خود را در سال 1399 از دانشگاه تربیت دبیر شهید رجایی تهران دریافت نموده است. زمینه­های پژوهشی مورد علاقه ایشان عبارتند از: داده ­کاوی و طبقه‌بندی داده‌های حجیم.

 

نگین دانشپور مدرک کارشناسی خود را در سال 1377 از دانشگاه شهید بهشتی اخذ نموده است. همچنین نام­برده درجة کارشناسی ارشد و دکتری خود را از دانشگاه صنعتی امیرکبیر در سال­های 1380 و 1389 اخذ نموده است. در حال حاضر، ایشان عضو هیأت علمی و دانشیار دانشکده مهندسی کامپیوتر دانشگاه تربیت دبیر شهید رجایی است. زمینه­های پژوهشی مورد علاقه ایشان عبارتند از: تحلیل و مدیریت داده، پایگاه داده تحلیلی ، داده کاوی و پیش­پردازش داده.

 

 

 


رایمگ

سامانه رایمگ تمامی فرآیندهای دریافت، ارزیابی و داوری، ویراستاری، صفحه‌آرایی و انتشار الکترونیکی نشریات علمی را به انجام می‌رساند

پیوندهای سایت

مراکز مرتبط

پشتیبانی

صفحات رسمی

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

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