{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T07:55:50Z","timestamp":1782978950918,"version":"3.54.5"},"reference-count":34,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T00:00:00Z","timestamp":1641513600000},"content-version":"vor","delay-in-days":6,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100018532","name":"Major Scientific and Technological Innovation Project of Shandong Province","doi-asserted-by":"publisher","award":["2019JZZY010716"],"award-info":[{"award-number":["2019JZZY010716"]}],"id":[{"id":"10.13039\/501100018532","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Wireless Communications and Mobile Computing"],"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:p>Owing to the absence of hypotheses of the underlying distributions of the data and the strong generation ability, the <jats:italic>k<\/jats:italic>\u2010nearest neighbor (kNN) classification algorithm is widely used to face recognition, text classification, emotional analysis, and other fields. However, kNN needs to compute the similarity between the unlabeled instance and all the training instances during the prediction process; it is difficult to deal with large\u2010scale data. To overcome this difficulty, an increasing number of acceleration algorithms based on data partition are proposed. However, they lack theoretical analysis about the effect of data partition on classification performance. This paper has made a theoretical analysis of the effect using empirical risk minimization and proposed a large\u2010scale <jats:italic>k<\/jats:italic>\u2010nearest neighbor classification algorithm based on neighbor relationship preservation. The process of searching the nearest neighbors is converted to a constrained optimization problem. Then, it gives the estimation of the difference on the objective function value under the optimal solution with data partition and without data partition. According to the obtained estimation, minimizing the similarity of the instances in the different divided subsets can largely reduce the effect of data partition. The minibatch <jats:italic>k<\/jats:italic>\u2010means clustering algorithm is chosen to perform data partition for its effectiveness and efficiency. Finally, the nearest neighbors of the test instance are continuously searched from the set generated by successively merging the candidate subsets until they do not change anymore, where the candidate subsets are selected based on the similarity between the test instance and cluster centers. Experiment results on public datasets show that the proposed algorithm can largely keep the same nearest neighbors and no significant difference in classification accuracy as the original kNN classification algorithm and better results than two state\u2010of\u2010the\u2010art algorithms.<\/jats:p>","DOI":"10.1155\/2022\/7409171","type":"journal-article","created":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T16:35:22Z","timestamp":1641573322000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["A Large\u2010Scale <i>k<\/i>\u2010Nearest Neighbor Classification Algorithm Based on Neighbor Relationship Preservation"],"prefix":"10.1155","volume":"2022","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3697-7134","authenticated-orcid":false,"given":"Yunsheng","family":"Song","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaohan","family":"Kong","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chao","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2022,1,7]]},"reference":[{"key":"e_1_2_9_1_2","volume-title":"Foundations of Machine Learning","author":"Mohri M.","year":"2018"},{"key":"e_1_2_9_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2017.09.038"},{"key":"e_1_2_9_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2019.01.016"},{"key":"e_1_2_9_4_2","doi-asserted-by":"publisher","DOI":"10.22266\/ijies2020.0630.02"},{"key":"e_1_2_9_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2020.01.015"},{"key":"e_1_2_9_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.2986245"},{"key":"e_1_2_9_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-007-0114-2"},{"key":"e_1_2_9_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2009.164"},{"key":"e_1_2_9_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.188"},{"key":"e_1_2_9_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2014.2321376"},{"key":"e_1_2_9_11_2","first-page":"825","volume-title":"Advances in Neural Information Processing Systems","author":"Liu T.","year":"2004"},{"key":"e_1_2_9_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2011.142"},{"key":"e_1_2_9_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355745"},{"key":"e_1_2_9_14_2","unstructured":"VermaN. KpotufeS. andDasguptaS. Which Spatial Partition Trees Are Adaptive to Intrinsic Dimension? Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence 2009 Montreal Canada 565\u2013574."},{"key":"e_1_2_9_15_2","unstructured":"McFeeB.andLanckrietG. R. G. Large-scale music similarity search with spatial trees Proceedings of the 12th International Society for Music Information Retrieval Conference 2011 Miami USA 55\u201360."},{"key":"e_1_2_9_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2007.914237"},{"key":"e_1_2_9_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.01.001"},{"key":"e_1_2_9_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2012.03.002"},{"key":"e_1_2_9_19_2","unstructured":"HsiehC.-J. SiS. andDhillonI. A divide-and-conquer solver for kernel support vector machines Proceedings of the 31st International Conference on Machine Learning 2014 Beijing China 566\u2013574."},{"key":"e_1_2_9_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054155"},{"key":"e_1_2_9_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190645"},{"key":"e_1_2_9_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190665"},{"key":"e_1_2_9_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2010.08.014"},{"key":"e_1_2_9_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(01)00137-6"},{"key":"e_1_2_9_25_2","doi-asserted-by":"crossref","unstructured":"SculleyD. Web-scale k-means clustering Proceedings of the 19th international conference on world wide web 2010 Raleigh USA 1177\u20131178.","DOI":"10.1145\/1772690.1772862"},{"key":"e_1_2_9_26_2","first-page":"4149","article-title":"Data analytics for effectiveness evaluation of islamic higher educationusing k-means algorithm","volume":"29","author":"Hidayat A.","year":"2020","journal-title":"International Journal of Advanced Science and Technology"},{"key":"e_1_2_9_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.2964763"},{"key":"e_1_2_9_28_2","doi-asserted-by":"publisher","DOI":"10.1111\/1467-9868.00293"},{"key":"e_1_2_9_29_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1008625"},{"key":"e_1_2_9_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961199"},{"key":"e_1_2_9_31_2","unstructured":"BacheK.andLichmanM. Uci machine learning repository 2021 http:\/\/archive.ics.uci.edu\/ml\/index.php."},{"key":"e_1_2_9_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4380-9_16"},{"key":"e_1_2_9_33_2","first-page":"1","article-title":"Statistical comparisons of classifiers over multiple data sets","volume":"7","author":"Dem\u0161ar J.","year":"2006","journal-title":"The Journal of Machine Learning Research"},{"key":"e_1_2_9_34_2","doi-asserted-by":"crossref","unstructured":"KordosM. BlachnikM. andStrzempaD. Do we need whatever more than k-nn? International Conference on Artificial Intelligence and Soft Computing 2010 Heidelberg Germany 414\u2013421.","DOI":"10.1007\/978-3-642-13208-7_52"}],"container-title":["Wireless Communications and Mobile Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/wcmc\/2022\/7409171.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/wcmc\/2022\/7409171.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/2022\/7409171","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T23:58:00Z","timestamp":1757462280000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/2022\/7409171"}},"subtitle":[],"editor":[{"given":"Petros","family":"Nicopolitidis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2022,1]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["10.1155\/2022\/7409171"],"URL":"https:\/\/doi.org\/10.1155\/2022\/7409171","archive":["Portico"],"relation":{},"ISSN":["1530-8669","1530-8677"],"issn-type":[{"value":"1530-8669","type":"print"},{"value":"1530-8677","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1]]},"assertion":[{"value":"2021-08-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-08","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"7409171"}}