Manuscript ID : 13991029251782 Visit : 3460 Page: 196 - 206

Article Type: Original Research

An Approximate Binary Tree-Based Solution to Speed Up the Search for the Nearest Neighbor in Big Data

Subject Areas : electrical and computer engineering

1 -
2 - Shahid Rajaee Teacher Training University

Received: 2021-01-18 Accepted : 2022-04-12 Published : 2022-11-02

Keywords: Overlap buffer, big data, binary decision tree, nearest neighbor classification,

Abstract :

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.

References:

[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.

Full-Text:

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

مقاله پژوهشی

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

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

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

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

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

1- مقدمه

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

به عنوان نمونه‌ای از گروه دوم، آنجیولی و همکاران [29] یک روش افزایشی جدید برای محاسبه یک زیرمجموعه سازگار از داده‌های آموزشی ارائه کردند. رویکرد پیشنهادی ایشان، نادیده‌گرفتن داده‌هایی بود که به داده‌های موجود شباهت داشتند و اطلاعات جدیدی اضافه نمی‌کردند. راه حل ارائه‌شده در این مقاله در حالی که هنوز دقت قابل قبولی داشت، سرعت یادگیری بهتر و پیچیدگی فضایی پایین‌تری را نسبت به روش نزدیک‌ترین همسایگی نشان می‌داد. در نتیجه برای زمانی که مسئله کمبود حافظه مطرح است، این روش مناسب می‌باشد. از سوی دیگر این روش پیچیدگی محاسباتی بیشتری نسبت به روش نزدیک‌ترین همسایگی دارد. در تحقیق انجام‌شده توسط دنگ و همکاران [30] از روش خوشه‌بندی k-means برای تقسیم فضای نمونه به k تا خوشه استفاده شده است. پس از ساخت خوشه‌ها با توجه به مشخص‌بودن مراکز خوشه‌ها با ورود داده آزمایش، فاصله آن تا مراکز خوشه‌ها سنجیده شده
و خوشه‌ای که مرکز آن کمترین فاصله را تا داده آزمایش دارد انتخاب می‌گردد. سپس از داده‌های آن به عنوان مجموعه داده آموزشی استفاده شده و با استفاده از روش نزدیک‌ترین همسایگی، برچسب طبقه داده آزمایش را حدس می‌زند. این روش به دو پارامتر برای تعیین تعداد خوشه‌ها و همچنین برای مشخص‌کردن تعداد همسایه‌ها برای روش نزدیک‌ترین همسایگی نیاز دارد که از مشکلات آن هستند. همچنین روش بیان‌شده به دلیل کم‌کردن فضای جستجو، از روش نزدیک‌ترین همسایگی سریع‌تر است اما نسبت به آن روش دقت کمتری دارد. سیدل و کریگل [31] روش جدید چندمرحله‌ای ارائه دادند که از مکانیزم فیلتر برای کاهش تعداد نامزدها و در نتیجه کمترشدن اندازه‌گیری فاصله، در زمان ورود نمونه آزمایش جدید استفاده می‌کند. در نتیجه روش ارائه‌شده در این مقاله سرعت بهتری نسبت به روش نزدیک‌ترین همسایگی دارد. لی و همکاران [32] بر اساس یک رویکرد مبتنی بر تراکم، مقدار داده‌های آموزشی را کاهش دادند و سپس از مجموعه آموزش جدید برای طبقه‌بندی استفاده کردند. در نتیجه سرعت یافتن طبقه داده آزمایش جدید افزایش یافت. در کار انجام‌شده توسط سعادت‌فر و همکاران [8] برای بهبود کار تحقیقاتی دنگ، عنوان شده که معیار فاصله تا مرکز خوشه به تنهایی کفایت نمی‌کند. بنابراین پس از خوشه‌بندی مجموعه داده به وسیله روش k-means، از معیارهای چگالی و همچنین نحوه گسترش داده‌ها در خوشه‌ها استفاده کردند که باعث افزایش دقت کار شده است. همچنین در کار ارائه‌شده توسط گالگو و همکاران [33] از دو روش خوشه‌بندی برای سرعت‌بخشیدن به روش نزدیک‌ترین همسایگی با نام‌های cKNN و +cKNN استفاده شده است. روش دوم از رویکردی فازی¹⁷ برای تقویت فرایند خوشه‌بندی استفاده می‌کند. دقت کار آنها به تعداد خوشه‌هایی که انتخاب می‌کنند، بستگی دارد اما با این حال زمانی که از روش شبکه عصبی عمیق¹⁸ برای یادگیری و حدس بهتر تعداد خوشه‌ها استفاده می‌کنند، کارشان دقت خوبی را ارائه می‌دهد. همچنین در کار دیگری که توسط ایشان منتشر شد [34]، در بهبود کار قبلی خود روشی به نام caKD+ ارائه کردند که در آن ابتدا با استفاده از شبکه عصبی عمیق سعی نمودند که ویژگی‌های نامرتبط مجموعه داده را نادیده بگیرند و در نتیجه، سرعت یافتن نزدیک‌ترین همسایگی را افزایش دهند. سپس با استفاده
از خوشه‌بندی، فضای جستجو را با فرض این که تمام نزدیک‌ترین همسایگان در همان خوشه هستند، محدود کردند. برای این منظور در هر خوشه ابتدا تمام نزدیک‌ترین همسایگان هر عضو خوشه نیز به آن خوشه اضافه شدند. علاوه بر این به جای استفاده از یک مقدار k ثابت برای تمام مجموعه داده، با استفاده از یک فرایند پیش‌پردازش، مقدار k مناسب برای هر خوشه مشخص می‌شود. همچنین از یک ساختار داده درخت KD¹⁹ برای تسریع در یافتن خوشه مناسب و همچنین جستجو در هر خوشه استفاده کردند. این کار باعث شد که دقت کار آنها بسیار بالا اما
سرعت کارشان پایین باشد. در کار دیگری که توسط اوگیاروگلو، استفانو، اونگلیدیس و جرجیوس [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- رویکرد پیشنهادی

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

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

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

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

از فاصله اقلیدسی که یکی از شناخته‌شده‌ترین معیارهای اندازه‌گیری موجود می‌باشد، برای اندازه‌گیری میزان شباهت استفاده شده است. فاصله بین دو نقطه با استفاده از (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 استفاده می‌کند و برخلاف روش‌های گذشته که برای پیش‌بینی فقط جاده مد نظر را در زمان‌های مختلف در نظر می‌گرفتند، وابستگی مکانی (یعنی جاده‌های مجاور) را نیز برای پیش‌بینی در نظر می‌گیرد و به همسایگی‌های نزدیک‌تر وزن بیشتر می‌دهد تا اثر انتخاب کمرنگ‌تر شود.	2016	[28]
	با استفاده از ویژگی وزن‌دهی به رأی‌ها بر اساس نزدیکی به محل مورد نظر، اثر را کم‌رنگ می‌کند.
پیچیدگی زمانی بالا	انجام نزدیک‌ترین همسایه که روشی بر پایه یادگیری تنبل است به صورت موازی برای داده‌های جریانی.	الگوریتم ارائه‌شده از درخت m-tree استفاده می‌کند و kNN را که روشی بر اساس یادگیری تنبل است، برای جریان داده‌ها مناسب می‌کند و به صورت موازی از آن استفاده می‌نماید.	2017	[22]
سرعت وابسته به تعداد مراحل نگاشت
پیچیدگی زیاد	دقت قابل قبول	با نادیده‌گرفتن داده‌هایی که اطلاعات جدید به سیستم اضافه نمی‌کنند، باعث کم‌شدن حجم داده می‌شود.	2005	[29]	گروه دوم (کارهای ارائه‌شده برای داده‌های ایستا و با استفاده از یک رایانه)
سرعت کم
به انتخاب و (تعداد خوشه‌ها) حساس است.	فضای آموزش را کاهش می‌دهد، در نتیجه زمان کمتری نسبت به 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 را ارائه کردند که در آن، ابتدا با استفاده از شبکه عصبی عمیق ویژگی‌های مناسب را انتخاب نمودند. سپس با استفاده از روش خوشه‌بندی، فضای جستجو برای نزدیک‌ترین همسایگی را محدود کردند. برای جلوگیری از خوشه‌های همپوشان در هر خوشه نزدیک‌ترین همسایگان اعضای خوشه نیز به خوشه اضافه شدند. علاوه بر این به جای استفاده از مقدار ثابت برای هر خوشه، از مناسب استفاده شد. همچنین از روش KD-Tree برای انتخاب خوشه مناسب و یافتن نزدیک‌ترین همسایگان داخل خوشه استفاده شد.	2022	[34]
پیچیدگی زیاد و سرعت کم	دقت بالا و قابل قبول	ابتدا داده‌ها را بر روی بردار تصادفی و PCA نگاشت و سپس آنها را نصف می‌کند. اگر خلوص هر گروه کافی بود که ادامه نمی‌دهد و در غیر این صورت دو گره جدید ایجاد می‌کند.	2018	[36]
احتیاج به زمان بیشتری دارد.	بهبود دقت کار آقای دنگ	در بهبود کار آقای دنگ ذکر کردند که فاصله به تنهایی کفایت نمی‌کند و پس از خوشه‌بندی با k-means از معیارهای چگالی و نحوه گسترش داده‌ها نیز استفاده کردند.	2020	[8]
وابستگی به معیارهای و

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

(1)

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

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

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

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

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

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

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

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

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

نام مجموعه داده		نام مجموعه داده
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 در شاخه راست گره فعلی ذخیره می‌شوند. این کار باعث ایجاد داده‌های تکراری و اضافی در درخت می‌شود و در سرعت اجرای روش تأثیر می‌گذارد، اما باعث افزایش دقت و از بین رفتن مشکل عنوان‌شده می‌شود. برای تعیین مقدار بافر همپوشانی دو راه وجود دارد: راهکار اول آن است که این مقدار را یک مقدار ثابت در نظر گرفت. برای مثال را 2/0 در نظر گرفت و این کار را تا زمانی که مقدار بزرگ‌تر از نصف فاصله دو دورترین نقطه شود در هر مرحله تکرار کرد، چون در غیر این صورت درخت به سمت بی‌نهایت کشیده می‌شود. راهکار دوم این است که مقدار در هر مرحله برابر درصدی از فاصله دو دورترین نقطه باشد که با این کار می‌توان تا آخرین مرحله ساخت درخت از بافر همپوشانی استفاده کرد. در این مقاله از روش دوم استفاده شده و مقدار در هر مجموعه داده با توجه به آزمایش‌های مختلف بر اساس موازنه بین سرعت و دقت تعیین شده است. زیرا با افزایش ، دقت کار افزایش اما سرعت کاهش می‌یابد. برای تعیین حد بالای به این نحو عمل شده که در هر مرحله، مقدار در الگوریتم به مقدار 01/0 افزایش داده می‌شود و زمان آن به نسبت اجرای قبل محاسبه می‌گردد. اگر زمان انجام مرحله آموزش نسبت به مرحله قبل دو برابر یا بیشتر شده باشد، اجرا به پایان می‌رسد. در این میان با توجه به داده‌های test و train موجود، مقدار برای الگوریتم به گونه‌ای انتخاب می‌شود که مقدار دقت را بیشینه کند. همچنین مقدار انتخابی باید کمتر از 5/0 باشد، در غیر این صورت درخت به سمت بی‌نهایت میل خواهد کرد. مثلاً در شکل 4 برای مجموعه داده Normalized covtype مشاهده می‌شود که با تغییر مقدار از مقدار 01/0 به مقدار 02/0، زمان اجرا از 8490 میلی‌ثانیه به 17010 میلی‌ثانیه افزایش می‌یابد. در نتیجه اجرا پایان یافته و مقدار مناسب برای این کار با توجه به دقت به دست آمده برابر 02/0 خواهد بود. به همین طریق برای مجموعه داده‌های استفاده‌شده، مقدار به دست آمده که در جدول 2 قابل مشاهده است.

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

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

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

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

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

4- آزمایش‌ها

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

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

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

عملکرد روش پیشنهادی با جدیدترین روش‌های ارائه‌شده برای طبقه‌بندی داده‌های بزرگ که شامل 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 اخذ نموده است. در حال حاضر، ایشان عضو هیأت علمی و دانشیار دانشکده مهندسی کامپیوتر دانشگاه تربیت دبیر شهید رجایی است. زمینههای پژوهشی مورد علاقه ایشان عبارتند از: تحلیل و مدیریت داده، پایگاه داده تحلیلی ، داده کاوی و پیشپردازش داده.

Automatic Change Detection by Intelligent Backgrounding Method
Print Date : 2003-03-21
Speed Estimation and Sensorless Torque Optimization of Single Phase Induction Motor
Print Date : 2003-06-21
Optimal Design of Three-Phase Squirrel-Cage Induction Motor for Electric Vehicle
Print Date : 2003-06-21
A New Method in Design and Implementation of Electronic Synchronizer Based on Phase Locked Loop for Fast Paralleling of Diesel–Generators
Print Date : 2003-06-21
A New Circuit for Protecting of Series Connected Power Thyristors
Print Date : 2003-06-21
Cooperation in Multi-Agent Systems Using Learning Automata
Print Date : 2003-06-21

Share To

Article Url

An Approximate Binary Tree-Based Solution to Speed Up the Search for the Nearest Neighbor in Big Data