{"id":370347,"date":"2024-05-21T04:23:12","date_gmt":"2024-05-21T04:23:12","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=370347"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=370347","title":{"rendered":"<span>Nearest-Neighbors (python 3)<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>\u0418\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043a\u043e\u0434 + \u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u043a\u043e\u043c\u0430\u043d\u0434 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b + \u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0438\u0434\u0435\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430<\/p>\n<p>sklearn.neighbors\u00a0\u2014 \u044d\u0442\u043e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0440\u0430\u0431\u043e\u0442\u044b \u0441\u00a0\u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c\u0438, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u043c\u0438 \u043d\u0430\u00a0\u0441\u043e\u0441\u0435\u0434\u044f\u0445 (\u043a\u0430\u043a \u0434\u043b\u044f\u00a0\u0441\u043b\u0443\u0447\u0430\u044f \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0441\u00a0\u0443\u0447\u0438\u0442\u0435\u043b\u0435\u043c, \u0442\u0430\u043a \u0438 \u0434\u043b\u044f\u00a0\u0441\u043b\u0443\u0447\u0430\u044f \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0431\u0435\u0437\u00a0\u0443\u0447\u0438\u0442\u0435\u043b\u044f).<\/p>\n<p>\u041c\u0435\u0442\u043e\u0434 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0431\u0435\u0437\u00a0\u0443\u0447\u0438\u0442\u0435\u043b\u044f \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0441\u043d\u043e\u0432\u043e\u0439 \u0434\u043b\u044f\u00a0\u043c\u043d\u043e\u0433\u0438\u0445 \u0434\u0440\u0443\u0433\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f, \u0432\u00a0\u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438, manifold learning \u0438 \u0441\u043f\u0435\u043a\u0442\u0440\u0430\u043b\u044c\u043d\u043e\u0439 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438.<\/p>\n<p>Manifold learning\u00a0\u2014 \u044d\u0442\u043e \u043f\u043e\u0434\u0445\u043e\u0434, \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u044e\u0449\u0438\u0439\u0441\u044f \u0432\u00a0\u043d\u0435\u043b\u0438\u043d\u0435\u0439\u043d\u043e\u043c \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u043d\u0438\u0438 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438.<\/p>\n<p>\u041e\u0431\u0443\u0447\u0435\u043d\u0438\u0435 \u0441\u00a0\u0443\u0447\u0438\u0442\u0435\u043b\u0435\u043c, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043d\u0430\u00a0\u0441\u043e\u0441\u0435\u0434\u044f\u0445 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432\u00a0\u0434\u0432\u0443\u0445 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430\u0445: \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044f (\u0434\u043b\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0441\u00a0\u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u043c\u0438 \u043c\u0435\u0442\u043a\u0430\u043c\u0438) \u0438 \u0440\u0435\u0433\u0440\u0435\u0441\u0441\u0438\u044f (\u0434\u043b\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0441\u00a0\u043d\u0435\u043f\u0440\u0435\u0440\u044b\u0432\u043d\u044b\u043c\u0438 \u043c\u0435\u0442\u043a\u0430\u043c\u0438).<\/p>\n<p>\u041f\u0440\u0438\u043d\u0446\u0438\u043f \u043c\u0435\u0442\u043e\u0434\u0430 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432\u00a0\u043f\u043e\u0438\u0441\u043a\u0435 \u043f\u0440\u0435\u0434\u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0442\u0440\u0435\u043d\u0438\u0440\u043e\u0432\u043e\u0447\u043d\u044b\u0445 (\u0443\u0447\u0435\u0431\u043d\u044b\u0445) \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432, \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u043f\u043e\u00a0\u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044e \u0434\u043e\u00a0\u043d\u043e\u0432\u043e\u0439 \u0442\u043e\u0447\u043a\u0438, \u0438 \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0430\u0442\u044c \u043c\u0435\u0442\u043a\u0443 \u043f\u043e\u00a0\u043d\u0438\u043c. \u0427\u0438\u0441\u043b\u043e \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432 \u043c\u043e\u0436\u0435\u0442\u00a0\u0431\u044b\u0442\u044c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043e \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u043c \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043e\u0439 (k\u2011\u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439),\u00a0\u043b\u0438\u0431\u043e \u0432\u0430\u0440\u044c\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0432\u00a0\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442\u00a0\u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e\u0439 \u043f\u043b\u043e\u0442\u043d\u043e\u0441\u0442\u0438 \u0442\u043e\u0447\u0435\u043a (\u0440\u0430\u0434\u0438\u0443\u0441\u2011\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0435). \u0420\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435, \u0432\u043e\u043e\u0431\u0449\u0435 \u0433\u043e\u0432\u043e\u0440\u044f, \u043c\u043e\u0436\u0435\u0442\u00a0\u0431\u044b\u0442\u044c \u043b\u044e\u0431\u043e\u0439 \u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043c\u0435\u0440\u043e\u0439: \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u043e\u0435 \u0435\u0432\u043a\u043b\u0438\u0434\u043e\u0432\u043e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u043d\u044b\u043c \u0432\u044b\u0431\u043e\u0440\u043e\u043c. \u041c\u0435\u0442\u043e\u0434\u044b, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043d\u0430\u00a0\u0441\u043e\u0441\u0435\u0434\u044f\u0445, \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b \u043a\u0430\u043a\u00a0\u043d\u0435\u00a0\u043e\u0431\u043e\u0431\u0449\u0430\u044e\u0449\u0438\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f, \u0442\u0430\u043a \u043a\u0430\u043a\u00a0\u043e\u043d\u0438 \u043f\u0440\u043e\u0441\u0442\u043e \u00ab\u0437\u0430\u043f\u043e\u043c\u0438\u043d\u0430\u044e\u0442\u00bb \u0432\u0441\u0435 \u0441\u0432\u043e\u0438 \u0443\u0447\u0435\u0431\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 (\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043f\u0440\u0435\u0432\u0440\u0430\u0449\u0430\u044e\u0442\u0441\u044f \u0432\u00a0\u0431\u044b\u0441\u0442\u0440\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u0442\u0430\u043a\u0443\u044e \u043a\u0430\u043a\u00a0\u0434\u0435\u0440\u0435\u0432\u043e \u0448\u0430\u0440\u043e\u0432 \u0438\u043b\u0438\u00a0KD \u0434\u0435\u0440\u0435\u0432\u043e).<\/p>\n<p>\u041d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430\u00a0\u0441\u0432\u043e\u044e \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u0443, \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0435 \u0441\u043e\u0441\u0435\u0434\u0438 \u0443\u0441\u043f\u0435\u0448\u043d\u043e \u0441\u043f\u0440\u0430\u0432\u0438\u043b\u0438\u0441\u044c \u0441\u00a0\u0431\u043e\u043b\u044c\u0448\u0438\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u043f\u0440\u043e\u0431\u043b\u0435\u043c \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438 \u0438 \u0440\u0435\u0433\u0440\u0435\u0441\u0441\u0438\u0438, \u0432\u043a\u043b\u044e\u0447\u0430\u044f \u0440\u0443\u043a\u043e\u043f\u0438\u0441\u043d\u044b\u0435 \u0446\u0438\u0444\u0440\u044b \u0438\u043b\u0438\u00a0\u0441\u0446\u0435\u043d\u044b \u0441\u043f\u0443\u0442\u043d\u0438\u043a\u043e\u0432\u043e\u0433\u043e \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u044f. \u0411\u0443\u0434\u0443\u0447\u0438 \u043d\u0435\u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u043c\u0435\u0442\u043e\u0434\u043e\u043c, \u043e\u043d \u0447\u0430\u0441\u0442\u043e\u00a0\u0431\u044b\u0432\u0430\u0435\u0442 \u0443\u0441\u043f\u0435\u0448\u043d\u044b\u043c \u0432\u00a0\u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044f\u0445 \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438, \u0433\u0434\u0435 \u0433\u0440\u0430\u043d\u0438\u0446\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043e\u0447\u0435\u043d\u044c \u043d\u0435\u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u0430.<\/p>\n<p>\u041a\u043b\u0430\u0441\u0441\u044b \u0432\u00a0sklearn.neighbors \u043c\u043e\u0433\u0443\u0442 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c\u00a0\u043b\u0438\u0431\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u044b Numpy,\u00a0\u043b\u0438\u0431\u043e scipy.sparse \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0432\u00a0\u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445. \u0414\u043b\u044f\u00a0\u043f\u043b\u043e\u0442\u043d\u044b\u0445 \u043c\u0430\u0442\u0440\u0438\u0446 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u043c\u0435\u0442\u0440\u0438\u043a \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f. \u0414\u043b\u044f\u00a0\u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u0445 \u043c\u0430\u0442\u0440\u0438\u0446 \u0434\u043b\u044f\u00a0\u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u044b\u0435 \u043c\u0435\u0442\u0440\u0438\u043a\u0438 \u041c\u0438\u043d\u043a\u043e\u0432\u0441\u043a\u043e\u0433\u043e.<\/p>\n<p>\u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0443\u0447\u0435\u0431\u043d\u044b\u0445 \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043f\u0438\u0440\u0430\u044e\u0442\u0441\u044f \u043d\u0430\u00a0\u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043f\u043e\u00a0\u0441\u0432\u043e\u0435\u0439 \u0441\u0443\u0442\u0438. \u041e\u0434\u043d\u0438\u043c \u0438\u0437\u00a0\u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0446\u0435\u043d\u043a\u0430 \u043f\u043b\u043e\u0442\u043d\u043e\u0441\u0442\u0438 \u044f\u0434\u0440\u0430, \u043e\u0431\u0441\u0443\u0436\u0434\u0430\u0435\u043c\u0430\u044f \u0432\u00a0\u0440\u0430\u0437\u0434\u0435\u043b\u0435 \u043e\u0446\u0435\u043d\u043a\u0438 \u043f\u043b\u043e\u0442\u043d\u043e\u0441\u0442\u0438.<\/p>\n<h3>\u0411\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0435 \u0441\u043e\u0441\u0435\u0434\u0438 (\u0431\u0435\u0437 \u0443\u0447\u0438\u0442\u0435\u043b\u044f)<\/h3>\n<p>NearestNeighbors \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442 \u043c\u0435\u0442\u043e\u0434 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0431\u0435\u0437 \u0443\u0447\u0438\u0442\u0435\u043b\u044f. \u041e\u043d \u0434\u0435\u0439\u0441\u0442\u0432\u0443\u0435\u0442 \u043a\u0430\u043a \u0435\u0434\u0438\u043d\u044b\u0439 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441 \u0434\u043b\u044f \u0442\u0440\u0435\u0445 \u0440\u0430\u0437\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439: BallTree, KDTree \u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043d\u0430 \u043f\u043e\u0434\u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430\u0445 \u0432 sklearn.metrics.pairwise. \u0412\u044b\u0431\u043e\u0440 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043a\u043b\u044e\u0447\u0435\u0432\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 \u00abalgorithm\u00bb, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u043e\u0434\u043d\u0438\u043c \u0438\u0437 [&#8216;auto&#8217;, &#8216;ball_tree&#8217;, &#8216;kd_tree&#8217;, &#8216;brute&#8217;]. \u041a\u043e\u0433\u0434\u0430 \u043f\u0435\u0440\u0435\u0434\u0430\u0435\u0442\u0441\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e \u00abauto\u00bb, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u044b\u0442\u0430\u0435\u0442\u0441\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043d\u0430\u0438\u043b\u0443\u0447\u0448\u0438\u0439 \u043f\u043e\u0434\u0445\u043e\u0434 \u0438\u0437 \u043e\u0431\u0443\u0447\u0430\u044e\u0449\u0438\u0445 (\u0442\u0440\u0435\u043d\u0438\u0440\u043e\u0432\u043e\u0447\u043d\u044b\u0445) \u0434\u0430\u043d\u043d\u044b\u0445. \u0414\u043b\u044f \u043e\u0431\u0441\u0443\u0436\u0434\u0435\u043d\u0438\u044f \u0441\u0438\u043b\u044c\u043d\u044b\u0445 \u0438 \u0441\u043b\u0430\u0431\u044b\u0445 \u0441\u0442\u043e\u0440\u043e\u043d \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430 \u0441\u043c. \u00ab\u0411\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0435 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b\u00bb.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/944\/43f\/9dd\/94443f9dd367c7e093f3211f8fa691a7.png\" width=\"375\" height=\"264\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/944\/43f\/9dd\/94443f9dd367c7e093f3211f8fa691a7.png\"\/><\/figure>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/df6\/068\/d97\/df6068d97d45764cba25b63fcae2dbac.png\" width=\"375\" height=\"264\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/df6\/068\/d97\/df6068d97d45764cba25b63fcae2dbac.png\"\/><\/figure>\n<h3>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439<\/h3>\n<h4>\u041f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440<\/h4>\n<p>\u0411\u044b\u0441\u0442\u0440\u043e\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439\u00a0\u2014 \u044d\u0442\u043e \u0430\u043a\u0442\u0438\u0432\u043d\u0430\u044f \u043e\u0431\u043b\u0430\u0441\u0442\u044c \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u0439 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u041d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043d\u0430\u0438\u0432\u043d\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0441\u043e\u0441\u0435\u0434\u0430 \u0432\u043a\u043b\u044e\u0447\u0430\u0435\u0442 \u0432\u00a0\u0441\u0435\u0431\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u043c\u0435\u0436\u0434\u0443 \u0432\u0441\u0435\u043c\u0438 \u043f\u0430\u0440\u0430\u043c\u0438 \u0442\u043e\u0447\u0435\u043a \u0432\u00a0\u043d\u0430\u0431\u043e\u0440\u0435 \u0434\u0430\u043d\u043d\u044b\u0445: \u0434\u043b\u044f\u00a0N \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432 \u0432\u00a0D \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u044f\u0445 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0442\u0430\u043a\u043e\u0433\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u0430\u043a\u00a0O(D * N^2). \u041f\u043e\u0438\u0441\u043a \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043f\u0440\u0438\u00a0\u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u043c\u043e\u0436\u0435\u0442\u00a0\u0431\u044b\u0442\u044c \u043a\u043e\u043d\u043a\u0443\u0440\u0435\u043d\u0442\u043d\u043e\u0441\u043f\u043e\u0441\u043e\u0431\u043d\u044b\u043c \u0434\u043b\u044f\u00a0\u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0432\u044b\u0431\u043e\u0440\u043e\u043a \u0434\u0430\u043d\u043d\u044b\u0445. \u041e\u0434\u043d\u0430\u043a\u043e \u043f\u043e\u00a0\u043c\u0435\u0440\u0435 \u0440\u043e\u0441\u0442\u0430 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432 N \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u00a0\u0431\u044b\u0441\u0442\u0440\u043e \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043d\u0435\u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0438\u043c\u044b\u043c. \u0412\u00a0\u043a\u043b\u0430\u0441\u0441\u0430\u0445 \u0432\u043d\u0443\u0442\u0440\u0438 sklearn.neighbors \u043f\u043e\u0438\u0441\u043a \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043f\u0440\u0438\u00a0\u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0437\u0430\u0434\u0430\u0435\u0442\u0441\u044f \u0441\u00a0\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043a\u043b\u044e\u0447\u0435\u0432\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 algorithm = &#8216;brute&#8217; \u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u00a0\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043f\u043e\u0434\u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c, \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b\u0445 \u0432\u00a0sklearn.metrics.pairwise. <\/p>\n<h4>K-D Tree<\/h4>\n<p>\u0414\u043b\u044f\u00a0\u0443\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043d\u0435\u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430\u00a0\u0431\u044b\u043b\u0438 \u0438\u0437\u043e\u0431\u0440\u0435\u0442\u0435\u043d\u044b \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445. \u0412\u00a0\u0446\u0435\u043b\u043e\u043c, \u044d\u0442\u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043f\u044b\u0442\u0430\u044e\u0442\u0441\u044f \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u043e\u0431\u044a\u0435\u043a\u0442\u0430\u043c\u0438, \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e \u043a\u043e\u0434\u0438\u0440\u0443\u044f \u0441\u043e\u0432\u043e\u043a\u0443\u043f\u043d\u0443\u044e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e\u00a0\u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0438 \u0434\u043b\u044f\u00a0\u043e\u0431\u0440\u0430\u0437\u0446\u0430. \u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432\u00a0\u0442\u043e\u043c, \u0447\u0442\u043e\u00a0\u0435\u0441\u043b\u0438 \u0442\u043e\u0447\u043a\u0430 A \u043e\u0447\u0435\u043d\u044c \u0434\u0430\u043b\u0435\u043a\u0430 \u043e\u0442\u00a0\u0442\u043e\u0447\u043a\u0438 B, \u0430\u00a0\u0442\u043e\u0447\u043a\u0430 B \u043e\u0447\u0435\u043d\u044c \u0431\u043b\u0438\u0437\u043a\u0430 \u043a\u00a0\u0442\u043e\u0447\u043a\u0435 C, \u0442\u043e \u043c\u044b \u0437\u043d\u0430\u0435\u043c, \u0447\u0442\u043e\u00a0\u0442\u043e\u0447\u043a\u0438 A \u0438 C \u043e\u0447\u0435\u043d\u044c \u0434\u0430\u043b\u0435\u043a\u0438, \u0431\u0435\u0437\u00a0\u044f\u0432\u043d\u043e\u0433\u043e \u0440\u0430\u0441\u0447\u0435\u0442\u0430 \u0438\u0445 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u043f\u043e\u0438\u0441\u043a\u0430 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043c\u043e\u0436\u0435\u0442\u00a0\u0431\u044b\u0442\u044c \u0441\u0432\u0435\u0434\u0435\u043d\u0430 \u043a\u00a0O(D * N * log(N)) \u042d\u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u0438\u0435 \u043f\u043e\u00a0\u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e \u0441\u00a0\u043f\u043e\u043b\u043d\u044b\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c \u0434\u043b\u044f\u00a0\u0431\u043e\u043b\u044c\u0448\u0438\u0445 N. \u0420\u0430\u043d\u043d\u0438\u043c \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u043c \u043a\u00a0\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044e \u044d\u0442\u043e\u0439 \u0441\u043e\u0432\u043e\u043a\u0443\u043f\u043d\u043e\u0439 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438\u00a0\u0431\u044b\u043b\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 KD \u0434\u0435\u0440\u0435\u0432\u0430 (\u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u0435 \u0434\u043b\u044f\u00a0K\u2011\u043c\u0435\u0440\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430), \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043e\u0431\u043e\u0431\u0449\u0430\u0435\u0442 \u0434\u0432\u0443\u043c\u0435\u0440\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u0442\u043e\u0432 \u0438 \u0442\u0440\u0435\u0445\u043c\u0435\u0440\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043e\u043a\u0442\u0430\u043d\u0442\u043e\u0432 \u043d\u0430\u00a0\u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u0439. \u0414\u0435\u0440\u0435\u0432\u043e KD \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 \u0434\u0432\u043e\u0438\u0447\u043d\u0443\u044e \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u0440\u0430\u0437\u0434\u0435\u043b\u044f\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432 \u0432\u0434\u043e\u043b\u044c \u043e\u0441\u0435\u0439 \u0434\u0430\u043d\u043d\u044b\u0445, \u0434\u0435\u043b\u044f \u0435\u0433\u043e \u043d\u0430\u00a0\u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0435 \u043e\u0440\u0442\u043e\u0442\u043e\u043f\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u043e\u0431\u043b\u0430\u0441\u0442\u0438, \u0432\u00a0\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0442\u043e\u0447\u043a\u0438 \u0434\u0430\u043d\u043d\u044b\u0445. \u041a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u044f KD \u0434\u0435\u0440\u0435\u0432\u0430 \u043e\u0447\u0435\u043d\u044c\u00a0\u0431\u044b\u0441\u0442\u0440\u0430\u044f: \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u00a0\u043e\u0441\u044f\u043c \u0434\u0430\u043d\u043d\u044b\u0445, D\u2011\u043c\u0435\u0440\u043d\u044b\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043d\u0435\u00a0\u043d\u0443\u0436\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0442\u044c. \u041e\u0434\u043d\u0430\u0436\u0434\u044b \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u043e\u0435, KD\u2011\u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u0441\u043e\u0441\u0435\u0434\u0430 \u0434\u043b\u044f\u00a0\u0442\u043e\u0447\u043a\u0438\u2011\u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u0437\u0430\u00a0O[log(N)] \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f. \u0425\u043e\u0442\u044f \u043f\u043e\u0434\u0445\u043e\u0434 KD tree \u043e\u0447\u0435\u043d\u044c\u00a0\u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u0434\u043b\u044f\u00a0\u043f\u043e\u0438\u0441\u043a\u043e\u0432 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0441\u00a0\u043d\u0438\u0437\u043a\u0438\u043c \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c (D &lt; 20), \u043e\u043d \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043d\u0435\u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u043c \u043f\u043e\u00a0\u043c\u0435\u0440\u0435 \u0442\u043e\u0433\u043e, \u043a\u0430\u043a\u00a0D \u0440\u0430\u0441\u0442\u0435\u0442 \u043e\u0447\u0435\u043d\u044c \u0432\u0435\u043b\u0438\u043a\u043e: \u044d\u0442\u043e \u043e\u0434\u043d\u043e \u0438\u0437\u00a0\u043f\u0440\u043e\u044f\u0432\u043b\u0435\u043d\u0438\u0439 \u0442\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u00ab\u043f\u0440\u043e\u043a\u043b\u044f\u0442\u0438\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438\u00bb. \u0412\u00a0scikit\u2011learn \u043f\u043e\u0438\u0441\u043a \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 KD \u0437\u0430\u0434\u0430\u0435\u0442\u0441\u044f \u0441\u00a0\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043a\u043b\u044e\u0447\u0435\u0432\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 algorithm = &#8216;kd_tree&#8217; \u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u00a0\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043a\u043b\u0430\u0441\u0441\u0430 KDTree. <\/p>\n<h4>Ball Tree<\/h4>\n<p>\u0414\u043b\u044f\u00a0\u0443\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043d\u0435\u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 KD \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u0432\u00a0\u0431\u043e\u043b\u0435\u0435 \u0432\u044b\u0441\u043e\u043a\u0438\u0445 \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u044f\u0445\u00a0\u0431\u044b\u043b\u0430 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u0448\u0430\u0440\u043e\u0432\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430. \u0412\u00a0\u0442\u0435\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445, \u043a\u043e\u0433\u0434\u0430 \u0434\u0435\u0440\u0435\u0432\u044c\u044f KD \u0434\u0435\u043b\u044f\u0442 \u0434\u0430\u043d\u043d\u044b\u0435 \u043f\u043e\u00a0\u0434\u0435\u043a\u0430\u0440\u0442\u043e\u0432\u044b\u043c \u043e\u0441\u044f\u043c, \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432\u00a0\u0441\u0435\u0440\u0438\u044e \u0433\u043d\u0435\u0437\u0434\u043e\u0432\u044b\u0445 \u0433\u0438\u043f\u0435\u0440\u0441\u0444\u0435\u0440. \u042d\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442 \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u044e \u0434\u0435\u0440\u0435\u0432\u0430 \u0431\u043e\u043b\u0435\u0435 \u0434\u043e\u0440\u043e\u0433\u043e\u0441\u0442\u043e\u044f\u0449\u0435\u0439, \u0447\u0435\u043c KD \u0434\u0435\u0440\u0435\u0432\u043e, \u043d\u043e\u00a0\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043a\u00a0\u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043c\u043e\u0436\u0435\u0442\u00a0\u0431\u044b\u0442\u044c \u043e\u0447\u0435\u043d\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0439 \u0434\u043b\u044f\u00a0\u0432\u044b\u0441\u043e\u043a\u043e\u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u0430\u0436\u0435 \u043f\u0440\u0438\u00a0\u043e\u0447\u0435\u043d\u044c \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044f\u0445. \u0414\u0435\u0440\u0435\u0432\u043e \u0448\u0430\u0440\u043e\u0432 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u0434\u0435\u043b\u0438\u0442 \u0434\u0430\u043d\u043d\u044b\u0435 \u043d\u0430\u00a0\u0443\u0437\u043b\u044b, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c\u044b\u0435 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u043c C \u0438 \u0440\u0430\u0434\u0438\u0443\u0441\u043e\u043c r, \u0442\u0430\u043a \u0447\u0442\u043e\u00a0\u043a\u0430\u0436\u0434\u0430\u044f \u0442\u043e\u0447\u043a\u0430 \u0432\u00a0\u0443\u0437\u043b\u0435 \u043b\u0435\u0436\u0438\u0442 \u0432\u043d\u0443\u0442\u0440\u0438 \u0433\u0438\u043f\u0435\u0440\u0441\u0444\u0435\u0440\u044b, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c\u043e\u0439 r \u0438 C. \u0427\u0438\u0441\u043b\u043e \u0442\u043e\u0447\u0435\u043a\u2011\u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442\u043e\u0432 \u0434\u043b\u044f\u00a0\u043f\u043e\u0438\u0441\u043a\u0430 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442\u0441\u044f \u0437\u0430\u00a0\u0441\u0447\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0430 \u0442\u0440\u0435\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430: |x+y| &lt;= |x| + |y|.<\/p>\n<p>\u0412\u00a0\u0442\u0430\u043a\u043e\u0439 \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0438 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043e\u0434\u043d\u043e\u0433\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u043e\u0439 \u0438 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043d\u0438\u0436\u043d\u044e\u044e \u0438 \u0432\u0435\u0440\u0445\u043d\u044e\u044e \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0434\u043e\u00a0\u0432\u0441\u0435\u0445 \u0442\u043e\u0447\u0435\u043a \u0432\u00a0\u0443\u0437\u043b\u0435. \u0418\u0437\u2011\u0437\u0430 \u0441\u0444\u0435\u0440\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0438 \u0443\u0437\u043b\u043e\u0432 \u0448\u0430\u0440\u043e\u0432\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043e\u043d \u043c\u043e\u0436\u0435\u0442 \u0432\u044b\u0432\u0435\u0441\u0442\u0438 KD\u2011\u0434\u0435\u0440\u0435\u0432\u043e \u0432\u00a0\u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0440\u0430\u0437\u043c\u0435\u0440\u0430\u0445, \u0445\u043e\u0442\u044f \u0444\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0441\u0438\u043b\u044c\u043d\u043e \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442\u00a0\u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u0412\u00a0scikit\u2011learn \u043f\u043e\u0438\u0441\u043a\u0438 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043d\u0430\u00a0\u043e\u0441\u043d\u043e\u0432\u0435 \u0448\u0430\u0440\u0438\u043a\u043e\u0432\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u0437\u0430\u0434\u0430\u044e\u0442\u0441\u044f \u0441\u00a0\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043a\u043b\u044e\u0447\u0435\u0432\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 algorithm = &#8216;ball_tree&#8217; \u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u044e\u0442\u0441\u044f \u0441\u00a0\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043a\u043b\u0430\u0441\u0441\u0430 sklearn.neighbors.BallTree. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u043c\u043e\u0436\u0435\u0442 \u043d\u0430\u043f\u0440\u044f\u043c\u0443\u044e \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0441\u00a0\u043a\u043b\u0430\u0441\u0441\u043e\u043c BallTree.<\/p>\n<h4>\u0412\u044b\u0431\u043e\u0440 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439<\/h4>\n<p>\u041e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u043b\u043e\u0436\u043d\u044b\u043c \u0432\u044b\u0431\u043e\u0440\u043e\u043c \u0438 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0440\u044f\u0434\u0430 \u0444\u0430\u043a\u0442\u043e\u0440\u043e\u0432:  <\/p>\n<ul>\n<li>\n<p>\u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432 N (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, n_samples) \u0438 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c D (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, n_features).<\/p>\n<ul>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u043d\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0440\u0430\u0441\u0442\u0451\u0442 \u043a\u0430\u043a O[DN].<\/p>\n<\/li>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u043d\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0434\u0435\u0440\u0435\u0432\u0430 \u0448\u0430\u0440\u043e\u0432 \u0440\u0430\u0441\u0442\u0451\u0442 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0451\u043d\u043d\u043e \u043a\u0430\u043a O[Dlog(N)].<\/p>\n<\/li>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430 KD \u0434\u0435\u0440\u0435\u0432\u043e\u043c \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0441 D \u0442\u0430\u043a, \u0447\u0442\u043e \u0435\u0433\u043e \u0442\u0440\u0443\u0434\u043d\u043e \u0442\u043e\u0447\u043d\u043e \u043e\u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0437\u043e\u0432\u0430\u0442\u044c. \u0414\u043b\u044f \u043c\u0430\u043b\u044b\u0445 D (\u043c\u0435\u043d\u0435\u0435 20 \u0438\u043b\u0438 \u043e\u043a\u043e\u043b\u043e \u0442\u043e\u0433\u043e) \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0430\u0432\u043d\u0430 O [D * log (N)], \u0438 \u0437\u0430\u043f\u0440\u043e\u0441 KD \u0434\u0435\u0440\u0435\u0432\u0430 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043e\u0447\u0435\u043d\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u043c. \u0414\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e D \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0447\u0442\u0438 \u0434\u043e O[DN], \u0430 \u0438\u0437\u0434\u0435\u0440\u0436\u043a\u0438 \u0438\u0437-\u0437\u0430 \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043c\u043e\u0433\u0443\u0442 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u043a \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c \u043f\u0440\u0438 \u043f\u043e\u043b\u043d\u043e\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0435.<\/p>\n<\/li>\n<\/ul>\n<p>\u0414\u043b\u044f \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u043d\u0430\u0431\u043e\u0440\u043e\u0432 \u0434\u0430\u043d\u043d\u044b\u0445 (N \u043c\u0435\u043d\u0435\u0435 30 \u0438\u043b\u0438 \u043e\u043a\u043e\u043b\u043e \u0442\u043e\u0433\u043e), log(N) \u0441\u0440\u0430\u0432\u043d\u0438\u043c \u0441 N, \u0438 \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u043c, \u0447\u0435\u043c \u043c\u0435\u0442\u043e\u0434\u044b, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043d\u0430 \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435. \u041e\u0431\u0430 \u043c\u0435\u0442\u043e\u0434\u0430 KDTree \u0438 BallTree \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u043b\u0438\u0441\u0442\u0430: \u043e\u043d \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u0438\u0440\u0443\u0435\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0437\u0430\u043f\u0440\u043e\u0441 \u043f\u0435\u0440\u0435\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043e\u0431\u0435\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u044c\u0441\u044f \u043a \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0434\u043b\u044f \u043c\u0430\u043b\u044b\u0445 N.<\/p>\n<ul>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u043d\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0440\u0430\u0441\u0442\u0451\u0442 \u043a\u0430\u043a O[DN]. <\/p>\n<ul>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u043d\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0434\u0435\u0440\u0435\u0432\u0430 \u0448\u0430\u0440\u043e\u0432 \u0440\u0430\u0441\u0442\u0451\u0442 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0451\u043d\u043d\u043e \u043a\u0430\u043a O[Dlog(N)].<\/p>\n<\/li>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430 KD \u0434\u0435\u0440\u0435\u0432\u043e\u043c \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0441 D \u0442\u0430\u043a, \u0447\u0442\u043e \u0435\u0433\u043e \u0442\u0440\u0443\u0434\u043d\u043e \u0442\u043e\u0447\u043d\u043e \u043e\u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0437\u043e\u0432\u0430\u0442\u044c. \u0414\u043b\u044f \u043c\u0430\u043b\u044b\u0445 D (\u043c\u0435\u043d\u0435\u0435 20 \u0438\u043b\u0438 \u043e\u043a\u043e\u043b\u043e \u0442\u043e\u0433\u043e) \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0430\u0432\u043d\u0430 O [D * log (N)], \u0438 \u0437\u0430\u043f\u0440\u043e\u0441 KD \u0434\u0435\u0440\u0435\u0432\u0430 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043e\u0447\u0435\u043d\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u043c. \u0414\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e D \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0447\u0442\u0438 \u0434\u043e O[DN], \u0430 \u0438\u0437\u0434\u0435\u0440\u0436\u043a\u0438 \u0438\u0437-\u0437\u0430 \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043c\u043e\u0433\u0443\u0442 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u043a \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c \u043f\u0440\u0438 \u043f\u043e\u043b\u043d\u043e\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0435.<\/p>\n<\/li>\n<\/ul>\n<p>\u0414\u043b\u044f \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u043d\u0430\u0431\u043e\u0440\u043e\u0432 \u0434\u0430\u043d\u043d\u044b\u0445 (N \u043c\u0435\u043d\u0435\u0435 30 \u0438\u043b\u0438 \u043e\u043a\u043e\u043b\u043e \u0442\u043e\u0433\u043e), log(N) \u0441\u0440\u0430\u0432\u043d\u0438\u043c \u0441 N, \u0438 \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u043c, \u0447\u0435\u043c \u043c\u0435\u0442\u043e\u0434\u044b, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043d\u0430 \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435. \u041e\u0431\u0430 \u043c\u0435\u0442\u043e\u0434\u0430 KDTree \u0438 BallTree \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u043b\u0438\u0441\u0442\u0430: \u043e\u043d \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u0438\u0440\u0443\u0435\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0437\u0430\u043f\u0440\u043e\u0441 \u043f\u0435\u0440\u0435\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043e\u0431\u0435\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u044c\u0441\u044f \u043a \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0434\u043b\u044f \u043c\u0430\u043b\u044b\u0445 N.<\/p>\n<\/li>\n<\/ul>\n<p>\u0412\u0440\u0435\u043c\u044f \u043d\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0440\u0430\u0441\u0442\u0451\u0442 \u043a\u0430\u043a O[DN]. <\/p>\n<ul>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u043d\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0434\u0435\u0440\u0435\u0432\u0430 \u0448\u0430\u0440\u043e\u0432 \u0440\u0430\u0441\u0442\u0451\u0442 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0451\u043d\u043d\u043e \u043a\u0430\u043a O[Dlog(N)].<\/p>\n<\/li>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430 KD \u0434\u0435\u0440\u0435\u0432\u043e\u043c \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0441 D \u0442\u0430\u043a, \u0447\u0442\u043e \u0435\u0433\u043e \u0442\u0440\u0443\u0434\u043d\u043e \u0442\u043e\u0447\u043d\u043e \u043e\u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0437\u043e\u0432\u0430\u0442\u044c. \u0414\u043b\u044f \u043c\u0430\u043b\u044b\u0445 D (\u043c\u0435\u043d\u0435\u0435 20 \u0438\u043b\u0438 \u043e\u043a\u043e\u043b\u043e \u0442\u043e\u0433\u043e) \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0430\u0432\u043d\u0430 O [D * log (N)], \u0438 \u0437\u0430\u043f\u0440\u043e\u0441 KD \u0434\u0435\u0440\u0435\u0432\u0430 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043e\u0447\u0435\u043d\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u043c. \u0414\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e D \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0447\u0442\u0438 \u0434\u043e O[DN], \u0430 \u0438\u0437\u0434\u0435\u0440\u0436\u043a\u0438 \u0438\u0437-\u0437\u0430 \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043c\u043e\u0433\u0443\u0442 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u043a \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c \u043f\u0440\u0438 \u043f\u043e\u043b\u043d\u043e\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0435.<\/p>\n<\/li>\n<\/ul>\n<p>\u0414\u043b\u044f \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u043d\u0430\u0431\u043e\u0440\u043e\u0432 \u0434\u0430\u043d\u043d\u044b\u0445 (N \u043c\u0435\u043d\u0435\u0435 30 \u0438\u043b\u0438 \u043e\u043a\u043e\u043b\u043e \u0442\u043e\u0433\u043e), log(N) \u0441\u0440\u0430\u0432\u043d\u0438\u043c \u0441 N, \u0438 \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u043c, \u0447\u0435\u043c \u043c\u0435\u0442\u043e\u0434\u044b, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043d\u0430 \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435. \u041e\u0431\u0430 \u043c\u0435\u0442\u043e\u0434\u0430 KDTree \u0438 BallTree \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u043b\u0438\u0441\u0442\u0430: \u043e\u043d \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u0438\u0440\u0443\u0435\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0437\u0430\u043f\u0440\u043e\u0441 \u043f\u0435\u0440\u0435\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043e\u0431\u0435\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u044c\u0441\u044f \u043a \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0434\u043b\u044f \u043c\u0430\u043b\u044b\u0445 N.<\/p>\n<\/li>\n<li>\n<p>\u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445: \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u044f\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \/ \u0438\u043b\u0438 \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e\u0441\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0445. \u0412\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u044f\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438 d &lt;= D \u043c\u043d\u043e\u0433\u043e\u043e\u0431\u0440\u0430\u0437\u0438\u044f, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043b\u0435\u0436\u0430\u0442 \u0434\u0430\u043d\u043d\u044b\u0435, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u043b\u0438\u043d\u0435\u0439\u043d\u043e \u0438\u043b\u0438 \u043d\u0435\u043b\u0438\u043d\u0435\u0439\u043d\u043e \u0432\u043b\u043e\u0436\u0435\u043d\u044b \u0432 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432. \u0420\u0430\u0437\u0440\u0435\u0448\u0430\u044e\u0449\u0430\u044f \u0441\u043f\u043e\u0441\u043e\u0431\u043d\u043e\u0441\u0442\u044c \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a \u0441\u0442\u0435\u043f\u0435\u043d\u0438, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0434\u0430\u043d\u043d\u044b\u0435 \u0437\u0430\u043f\u043e\u043b\u043d\u044f\u044e\u0442 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u043e\u0432 (\u044d\u0442\u043e \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u043e\u0442\u043b\u0438\u0447\u0430\u0442\u044c \u043e\u0442 \u043f\u043e\u043d\u044f\u0442\u0438\u044f, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u043e\u0433\u043e \u0432 \u00ab\u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u0445\u00bb \u043c\u0430\u0442\u0440\u0438\u0446\u0430\u0445. \u0412 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u043c\u043e\u0433\u0443\u0442 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u043d\u0443\u043b\u0435\u0432\u044b\u0435 \u0437\u0430\u043f\u0438\u0441\u0438, \u043d\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0432\u0441\u0435 \u0435\u0449\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u00ab\u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e\u0439\u00bb \u0432 \u044d\u0442\u043e\u043c \u0441\u043c\u044b\u0441\u043b\u0435).<\/p>\n<ul>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u043d\u0435 \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0437\u0430 \u0441\u0447\u0435\u0442 \u0432\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445.<\/p>\n<\/li>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0434\u0435\u0440\u0435\u0432\u0430 \u0448\u0430\u0440\u043e\u0432 \u0438 KD \u0434\u0435\u0440\u0435\u0432\u0430 \u043c\u043e\u0436\u0435\u0442 \u0441\u0438\u043b\u044c\u043d\u043e \u0437\u0430\u0432\u0438\u0441\u0435\u0442\u044c \u043e\u0442 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445. \u0412 \u043e\u0431\u0449\u0435\u043c, \u0431\u043e\u043b\u0435\u0435 \u0440\u0435\u0434\u043a\u0438\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u0441 \u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c\u044e \u043f\u0440\u0438\u0432\u043e\u0434\u044f\u0442 \u043a \u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u043e\u043c\u0443 \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432. \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 KD \u0434\u0435\u0440\u0435\u0432\u0430 \u0432\u044b\u0440\u043e\u0432\u043d\u0435\u043d\u043e \u043f\u043e \u043e\u0441\u044f\u043c\u0438 \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u043e\u0432, \u043e\u043d\u043e, \u043a\u0430\u043a \u043f\u0440\u0430\u0432\u0438\u043b\u043e, \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0434\u0435\u043c\u043e\u043d\u0441\u0442\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0442\u0430\u043a\u043e\u0433\u043e \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u0438\u044f, \u043a\u0430\u043a \u0448\u0430\u0440\u043e\u0432\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0434\u043b\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445. \u041d\u0430\u0431\u043e\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u044b\u0435 \u0432 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u043c \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0438, \u043a\u0430\u043a \u043f\u0440\u0430\u0432\u0438\u043b\u043e, \u043e\u0447\u0435\u043d\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u0438 \u043e\u0447\u0435\u043d\u044c \u0445\u043e\u0440\u043e\u0448\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0442 \u0434\u043b\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043d\u0430 \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u0445.<\/p>\n<\/li>\n<\/ul>\n<p>\u0412\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u043d\u0435 \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0437\u0430 \u0441\u0447\u0435\u0442 \u0432\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445. <\/p>\n<\/li>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0434\u0435\u0440\u0435\u0432\u0430 \u0448\u0430\u0440\u043e\u0432 \u0438 KD \u0434\u0435\u0440\u0435\u0432\u0430 \u043c\u043e\u0436\u0435\u0442 \u0441\u0438\u043b\u044c\u043d\u043e \u0437\u0430\u0432\u0438\u0441\u0435\u0442\u044c \u043e\u0442 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445. \u0412 \u043e\u0431\u0449\u0435\u043c, \u0431\u043e\u043b\u0435\u0435 \u0440\u0435\u0434\u043a\u0438\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u0441 \u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c\u044e \u043f\u0440\u0438\u0432\u043e\u0434\u044f\u0442 \u043a \u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u043e\u043c\u0443 \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432. \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 KD \u0434\u0435\u0440\u0435\u0432\u0430 \u0432\u044b\u0440\u043e\u0432\u043d\u0435\u043d\u043e \u043f\u043e \u043e\u0441\u044f\u043c\u0438 \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u043e\u0432, \u043e\u043d\u043e, \u043a\u0430\u043a \u043f\u0440\u0430\u0432\u0438\u043b\u043e, \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0434\u0435\u043c\u043e\u043d\u0441\u0442\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0442\u0430\u043a\u043e\u0433\u043e \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u0438\u044f, \u043a\u0430\u043a \u0448\u0430\u0440\u043e\u0432\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0434\u043b\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445. \u041d\u0430\u0431\u043e\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u044b\u0435 \u0432 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u043c \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0438, \u043a\u0430\u043a \u043f\u0440\u0430\u0432\u0438\u043b\u043e, \u043e\u0447\u0435\u043d\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u0438 \u043e\u0447\u0435\u043d\u044c \u0445\u043e\u0440\u043e\u0448\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0442 \u0434\u043b\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043d\u0430 \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u0445.<\/p>\n<\/li>\n<li>\n<p>\u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043e\u0441\u0435\u0434\u0435\u0439 k, \u0437\u0430\u043f\u0440\u043e\u0448\u0435\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u0442\u043e\u0447\u043a\u0438 \u0437\u0430\u043f\u0440\u043e\u0441\u0430.<\/p>\n<ul>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0432 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043d\u0435 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f k.<\/p>\n<\/li>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u0448\u0430\u0440\u0430 \u0438 \u0432\u0440\u0435\u043c\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 KD \u0431\u0443\u0434\u0443\u0442 \u0437\u0430\u043c\u0435\u0434\u043b\u044f\u0442\u044c\u0441\u044f \u0441 \u0440\u043e\u0441\u0442\u043e\u043c k. \u042d\u0442\u043e \u0441\u0432\u044f\u0437\u0430\u043d\u043e \u0441 \u0434\u0432\u0443\u043c\u044f \u044d\u0444\u0444\u0435\u043a\u0442\u0430\u043c\u0438: \u0432\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, \u0431\u043e\u043b\u044c\u0448\u0438\u0439 k \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043a \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0431\u043e\u043b\u044c\u0448\u0435\u0439 \u0447\u0430\u0441\u0442\u0438 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430 \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u043e\u0432. \u0412\u043e-\u0432\u0442\u043e\u0440\u044b\u0445, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 k > 1 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0439 \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0441\u0442\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u0432 \u043f\u0440\u0438 \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0438 \u0434\u0435\u0440\u0435\u0432\u0430.<\/p>\n<\/li>\n<\/ul>\n<\/li>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u0448\u0430\u0440\u0430 \u0438 \u0432\u0440\u0435\u043c\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 KD \u0431\u0443\u0434\u0443\u0442 \u0437\u0430\u043c\u0435\u0434\u043b\u044f\u0442\u044c\u0441\u044f \u0441 \u0440\u043e\u0441\u0442\u043e\u043c k. \u042d\u0442\u043e \u0441\u0432\u044f\u0437\u0430\u043d\u043e \u0441 \u0434\u0432\u0443\u043c\u044f \u044d\u0444\u0444\u0435\u043a\u0442\u0430\u043c\u0438: \u0432\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, \u0431\u043e\u043b\u044c\u0448\u0438\u0439 k \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043a \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0431\u043e\u043b\u044c\u0448\u0435\u0439 \u0447\u0430\u0441\u0442\u0438 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430 \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u043e\u0432. \u0412\u043e-\u0432\u0442\u043e\u0440\u044b\u0445, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 k > 1 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0439 \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0441\u0442\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u0432 \u043f\u0440\u0438 \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0438 \u0434\u0435\u0440\u0435\u0432\u0430. <\/p>\n<p>\u0412\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0432 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043d\u0435 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f k. <\/p>\n<\/li>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u0448\u0430\u0440\u0430 \u0438 \u0432\u0440\u0435\u043c\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 KD \u0431\u0443\u0434\u0443\u0442 \u0437\u0430\u043c\u0435\u0434\u043b\u044f\u0442\u044c\u0441\u044f \u0441 \u0440\u043e\u0441\u0442\u043e\u043c k. \u042d\u0442\u043e \u0441\u0432\u044f\u0437\u0430\u043d\u043e \u0441 \u0434\u0432\u0443\u043c\u044f \u044d\u0444\u0444\u0435\u043a\u0442\u0430\u043c\u0438: \u0432\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, \u0431\u043e\u043b\u044c\u0448\u0438\u0439 k \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043a \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0431\u043e\u043b\u044c\u0448\u0435\u0439 \u0447\u0430\u0441\u0442\u0438 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430 \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u043e\u0432. \u0412\u043e-\u0432\u0442\u043e\u0440\u044b\u0445, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 k > 1 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0439 \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0441\u0442\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u0432 \u043f\u0440\u0438 \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0438 \u0434\u0435\u0440\u0435\u0432\u0430.<\/p>\n<\/li>\n<\/ul>\n<p>\u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 k \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u0431\u043e\u043b\u044c\u0448\u0438\u043c \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e N, \u0441\u043f\u043e\u0441\u043e\u0431\u043d\u043e\u0441\u0442\u044c \u043e\u0431\u0440\u0435\u0437\u0430\u0442\u044c \u0432\u0435\u0442\u0432\u0438 \u0432 \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u043e\u043c \u0437\u0430\u043f\u0440\u043e\u0441\u0435 \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442\u0441\u044f. \u0412 \u044d\u0442\u043e\u0439 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438 \u0437\u0430\u043f\u0440\u043e\u0441\u044b Brute force \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u043c\u0438.<\/p>\n<ul>\n<li>\n<p>\u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a \u0437\u0430\u043f\u0440\u043e\u0441\u0430. \u0418 \u0448\u0430\u0440\u043e\u0432\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e, \u0438 KD \u0434\u0435\u0440\u0435\u0432\u043e \u0442\u0440\u0435\u0431\u0443\u044e\u0442 \u0444\u0430\u0437\u044b \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f. \u0421\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043d\u0435\u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043f\u0440\u0438 \u0430\u043c\u043e\u0440\u0442\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u043e \u043c\u043d\u043e\u0433\u0438\u043c \u0437\u0430\u043f\u0440\u043e\u0441\u0430\u043c. \u041e\u0434\u043d\u0430\u043a\u043e, \u0435\u0441\u043b\u0438 \u0431\u0443\u0434\u0435\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u043e \u043b\u0438\u0448\u044c \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432, \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u044f \u043c\u043e\u0436\u0435\u0442 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0447\u0430\u0441\u0442\u044c \u043e\u0431\u0449\u0435\u0439 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438. \u0415\u0441\u043b\u0438 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043e\u0447\u0435\u043d\u044c \u043c\u0430\u043b\u043e \u0442\u043e\u0447\u0435\u043a \u0437\u0430\u043f\u0440\u043e\u0441\u0430, \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u043b\u0443\u0447\u0448\u0435, \u0447\u0435\u043c \u043c\u0435\u0442\u043e\u0434 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0434\u0435\u0440\u0435\u0432\u0430.<\/p>\n<\/li>\n<\/ul>\n<p>\u0412 \u043d\u0430\u0441\u0442\u043e\u044f\u0449\u0435\u0435 \u0432\u0440\u0435\u043c\u044f algorithm = &#8216;auto&#8217; \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442 &#8216;kd_tree&#8217; \u0435\u0441\u043b\u0438 k &lt; N\/2 \u0438 &#8216;effective_metric_&#8217; \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 &#8216;VALID_METRICS&#8217; \u0441\u043f\u0438\u0441\u043a\u0430 &#8216;kd_tree&#8217;. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442 &#8216;ball_tree&#8217;, \u0435\u0441\u043b\u0438 k &lt; N\/2 \u0438 &#8216;effective_metric_&#8217; \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 &#8216;VALID_METRICS&#8217; \u0441\u043f\u0438\u0441\u043a\u0430 &#8216;ball_tree&#8217;. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442 &#8216;brute&#8217;, \u0435\u0441\u043b\u0438 k &lt; N\/2 \u0438 &#8216;effective_metric_&#8217; \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 &#8216;VALID_METRICS&#8217; \u0441\u043f\u0438\u0441\u043a\u0430 &#8216;kd_tree&#8217; \u0438\u043b\u0438 &#8216;ball_tree&#8217;. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442 &#8216;brute&#8217;, \u0435\u0441\u043b\u0438 k >= N\/2. \u042d\u0442\u043e\u0442 \u0432\u044b\u0431\u043e\u0440 \u043e\u0441\u043d\u043e\u0432\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u0438, \u0447\u0442\u043e \u0447\u0438\u0441\u043b\u043e \u0442\u043e\u0447\u0435\u043a \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432 \u043a\u0430\u043a \u043c\u0438\u043d\u0438\u043c\u0443\u043c \u0442\u043e\u0433\u043e \u0436\u0435 \u043f\u043e\u0440\u044f\u0434\u043a\u0430, \u0447\u0442\u043e \u0438 \u0447\u0438\u0441\u043b\u043e \u0442\u0440\u0435\u043d\u0438\u0440\u043e\u0432\u043e\u0447\u043d\u044b\u0445 (\u043e\u0431\u0443\u0447\u0430\u044e\u0449\u0438\u0445) \u0442\u043e\u0447\u0435\u043a \u0432\u044b\u0431\u043e\u0440\u043a\u0438, \u0438 \u0447\u0442\u043e leaf_size \u0431\u043b\u0438\u0437\u043e\u043a \u043a \u0441\u0432\u043e\u0435\u043c\u0443 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e \u043f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e 30.  <\/p>\n<h4>\u042d\u0444\u0444\u0435\u043a\u0442 leaf_size<\/h4>\n<p>\u041a\u0430\u043a \u043e\u0442\u043c\u0435\u0447\u0430\u043b\u043e\u0441\u044c \u0432\u044b\u0448\u0435, \u0434\u043b\u044f \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0432\u044b\u0431\u043e\u0440\u043e\u043a \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u043c, \u0447\u0435\u043c \u0437\u0430\u043f\u0440\u043e\u0441 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0434\u0435\u0440\u0435\u0432\u0430. \u042d\u0442\u043e\u0442 \u0444\u0430\u043a\u0442 \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0432 \u0434\u0435\u0440\u0435\u0432\u0435 \u0448\u0430\u0440\u043e\u0432 \u0438 KD \u0434\u0435\u0440\u0435\u0432\u0435, \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435 \u043f\u0435\u0440\u0435\u043a\u043b\u044e\u0447\u0430\u044f\u0441\u044c \u043d\u0430 \u043f\u043e\u0438\u0441\u043a \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0432 \u043b\u0438\u0441\u0442\u043e\u0432\u044b\u0445 \u0443\u0437\u043b\u0430\u0445. \u0423\u0440\u043e\u0432\u0435\u043d\u044c \u044d\u0442\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u044f \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u0434\u0430\u0442\u044c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u043c leaf_size. \u042d\u0442\u043e\u0442 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 \u0438\u043c\u0435\u0435\u0442 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u044d\u0444\u0444\u0435\u043a\u0442\u043e\u0432:<\/p>\n<p><strong>\u0412\u0440\u0435\u043c\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f<\/strong><\/p>\n<p>\u0411\u043e\u043b\u0435\u0435 \u043a\u0440\u0443\u043f\u043d\u044b\u0439 leaf_size \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043a \u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u043e\u043c\u0443 \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0434\u0435\u0440\u0435\u0432\u0430, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043c\u0435\u043d\u044c\u0448\u0435 \u0443\u0437\u043b\u043e\u0432.<\/p>\n<p><strong>\u0412\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430<\/strong><\/p>\n<p>\u041a\u0430\u043a \u0431\u043e\u043b\u044c\u0448\u043e\u0439, \u0442\u0430\u043a \u0438 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0439 leaf_size \u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u0438\u0432\u0435\u0441\u0442\u0438 \u043a \u0441\u0443\u0431\u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438 \u0437\u0430\u043f\u0440\u043e\u0441\u0430. \u0414\u043b\u044f \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430 leaf_size, \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0430\u044e\u0449\u0435\u0433\u043e\u0441\u044f \u043a 1, \u0441\u043b\u0443\u0436\u0435\u0431\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435, \u0443\u0447\u0430\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 \u0432 \u043f\u0440\u043e\u0434\u0432\u0438\u0436\u0435\u043d\u0438\u0438 \u043f\u043e \u0443\u0437\u043b\u0430\u043c, \u043c\u043e\u0433\u0443\u0442 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0437\u0430\u043c\u0435\u0434\u043b\u0438\u0442\u044c \u0432\u0440\u0435\u043c\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430. \u0414\u043b\u044f leaf_size, \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0430\u044e\u0449\u0435\u0433\u043e\u0441\u044f \u043a \u0440\u0430\u0437\u043c\u0435\u0440\u0443 \u0442\u0440\u0435\u043d\u0438\u0440\u043e\u0432\u043e\u0447\u043d\u043e\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430, \u0437\u0430\u043f\u0440\u043e\u0441\u044b \u0441\u0442\u0430\u043d\u043e\u0432\u044f\u0442\u0441\u044f \u043f\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443 \u043f\u043e\u043b\u043d\u044b\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c. \u0425\u043e\u0440\u043e\u0448\u0438\u043c \u043a\u043e\u043c\u043f\u0440\u043e\u043c\u0438\u0441\u0441\u043e\u043c \u043c\u0435\u0436\u0434\u0443 \u043d\u0438\u043c\u0438 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 leaf_size = 30, \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e \u0434\u043b\u044f \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430.<\/p>\n<p>\u043f\u0430\u043c\u044f\u0442\u044c \u041f\u043e \u043c\u0435\u0440\u0435 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u044f leaf_size \u043f\u0430\u043c\u044f\u0442\u044c, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u0430\u044f \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b, \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442\u0441\u044f. \u042d\u0442\u043e \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u0432\u0430\u0436\u043d\u043e \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0448\u0430\u0440\u043e\u0432\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f D-\u043c\u0435\u0440\u043d\u044b\u0439 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430. \u0422\u0440\u0435\u0431\u0443\u0435\u043c\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0434\u043b\u044f BallTree \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u0435\u043b\u044c\u043d\u043e 1 \/ leaf_size, \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u043d\u043e\u0435 \u043d\u0430 \u0440\u0430\u0437\u043c\u0435\u0440 \u043e\u0431\u0443\u0447\u0430\u044e\u0449\u0435\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430.<\/p>\n<h3>\u041a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440 \u043f\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u043c\u0443 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0443<\/h3>\n<p>\u041a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440 NearestCentroid &#8212; \u044d\u0442\u043e \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u043a\u0430\u0436\u0434\u044b\u0439 \u043a\u043b\u0430\u0441\u0441 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u043c \u0435\u0433\u043e \u0447\u043b\u0435\u043d\u043e\u0432. \u041f\u043e \u0441\u0443\u0442\u0438, \u044d\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442 \u0435\u0433\u043e \u043f\u043e\u0445\u043e\u0436\u0438\u043c \u043d\u0430 \u0444\u0430\u0437\u0443 \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u044f \u043c\u0435\u0442\u043a\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 sklearn.KMeans. \u041e\u043d \u0442\u0430\u043a\u0436\u0435 \u043d\u0435 \u0438\u043c\u0435\u0435\u0442 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432 \u0434\u043b\u044f \u0432\u044b\u0431\u043e\u0440\u0430, \u0447\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442 \u0435\u0433\u043e \u0445\u043e\u0440\u043e\u0448\u0438\u043c \u0431\u0430\u0437\u043e\u0432\u044b\u043c \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440\u043e\u043c. \u0422\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435, \u043e\u043d \u0441\u0442\u0440\u0430\u0434\u0430\u0435\u0442 \u043e\u0442 \u043d\u0435\u0432\u044b\u043f\u0443\u043a\u043b\u044b\u0445 \u043a\u043b\u0430\u0441\u0441\u043e\u0432, \u0430 \u0442\u0430\u043a\u0436\u0435 \u043a\u043e\u0433\u0434\u0430 \u043a\u043b\u0430\u0441\u0441\u044b \u0438\u043c\u0435\u044e\u0442 \u0440\u0435\u0437\u043a\u043e \u0440\u0430\u0437\u043d\u044b\u0435 \u043e\u0442\u043a\u043b\u043e\u043d\u0435\u043d\u0438\u044f, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f \u0440\u0430\u0432\u043d\u0430\u044f \u0434\u0438\u0441\u043f\u0435\u0440\u0441\u0438\u044f \u0432\u043e \u0432\u0441\u0435\u0445 \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u044f\u0445. \u0421\u043c. \u041b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u0434\u0438\u0441\u043a\u0440\u0438\u043c\u0438\u043d\u0430\u043d\u0442\u043d\u044b\u0439 \u0430\u043d\u0430\u043b\u0438\u0437 (sklearn.discriminant_analysis.LinearDiscriminantAnalysis) \u0438 \u041a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u044b\u0439 \u0434\u0438\u0441\u043a\u0440\u0438\u043c\u0438\u043d\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0439 \u0430\u043d\u0430\u043b\u0438\u0437 (sklearn.discriminant_analysis.QuadraticDiscriminantAnalysis) \u0434\u043b\u044f \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435 \u0434\u0435\u043b\u0430\u044e\u0442 \u044d\u0442\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u044f.<\/p>\n<p>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e NearestCentroid \u043f\u0440\u043e\u0441\u0442\u043e:<\/p>\n<pre><code>    >>> from sklearn.neighbors.nearest_centroid import NearestCentroid     >>> import numpy as np     >>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])     >>> y = np.array([1, 1, 1, 2, 2, 2])     >>> clf = NearestCentroid()     >>> clf.fit(X, y)     NearestCentroid(metric = 'euclidean', shrink_threshold = None)     >>> print(clf.predict([[-0.8, -1]]))<\/code><\/pre>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/bd7\/197\/f7a\/bd7197f7a0bade22f454db6ab91a14e2.png\" width=\"640\" height=\"480\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bd7\/197\/f7a\/bd7197f7a0bade22f454db6ab91a14e2.png\"\/><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/84b\/b0f\/43c\/84bb0f43c2676907f3340869a8e32c89.png\" width=\"640\" height=\"480\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/84b\/b0f\/43c\/84bb0f43c2676907f3340869a8e32c89.png\"\/><\/figure>\n<h4>\u0411\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0439 \u0434\u0435\u0444\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434<\/h4>\n<p>\u0423 \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440\u0430 NearestCentroid \u0435\u0441\u0442\u044c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 shrink_threshold, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0434\u0435\u0444\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432. \u0424\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438, \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043a\u0430\u0436\u0434\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u0434\u0435\u043b\u0438\u0442\u0441\u044f \u043d\u0430 \u0434\u0438\u0441\u043f\u0435\u0440\u0441\u0438\u044e \u0432\u043d\u0443\u0442\u0440\u0438 \u043a\u043b\u0430\u0441\u0441\u0430 \u044d\u0442\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438. \u0417\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0439 \u0437\u0430\u0442\u0435\u043c \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u044e\u0442\u0441\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430 shrink_threshold. \u041f\u0440\u0435\u0436\u0434\u0435 \u0432\u0441\u0435\u0433\u043e, \u0435\u0441\u043b\u0438 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043f\u0435\u0440\u0435\u0441\u0435\u043a\u0430\u0435\u0442 \u043d\u043e\u043b\u044c, \u043e\u043d\u043e \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0440\u0430\u0432\u043d\u044b\u043c \u043d\u0443\u043b\u044e. \u041f\u043e \u0441\u0443\u0442\u0438, \u044d\u0442\u043e \u0443\u0441\u0442\u0440\u0430\u043d\u044f\u0435\u0442 \u044d\u0442\u0443 \u0444\u0443\u043d\u043a\u0446\u0438\u044e, \u0432\u043b\u0438\u044f\u044f \u043d\u0430 \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044e. \u042d\u0442\u043e \u043f\u043e\u043b\u0435\u0437\u043d\u043e, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0434\u043b\u044f \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0448\u0443\u043c\u043d\u044b\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u0439. \u0412 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u043e\u043c \u043d\u0438\u0436\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u043f\u043e\u0440\u043e\u0433\u0430 \u0443\u0441\u0430\u0434\u043a\u0438 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u043c\u043e\u0434\u0435\u043b\u0438 \u043e\u0442 0,81 \u0434\u043e 0,82.  <\/p>\n<pre><code>print(__doc__)  import numpy as np import matplotlib.pyplot as plt from matplotlib.colors import ListedColormap from sklearn import datasets from sklearn.neighbors import NearestCentroid  n_neighbors = 15  # import some data to play with iris = datasets.load_iris() # we only take the first two features. We could avoid this ugly # slicing by using a two-dim dataset X = iris.data[:, :2] y = iris.target  h = .02  # step size in the mesh  # Create color maps cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF']) cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF'])  for shrinkage in [None, .2]:     # we create an instance of Neighbours Classifier and fit the data.     clf = NearestCentroid(shrink_threshold = shrinkage)     clf.fit(X, y)     y_pred = clf.predict(X)     print(shrinkage, np.mean(y == y_pred))     # Plot the decision boundary. For that, we will assign a color to each     # point in the mesh [x_min, x_max]x[y_min, y_max].     x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1     y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1     xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))     Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])      # Put the result into a color plot     Z = Z.reshape(xx.shape)     plt.figure()     plt.pcolormesh(xx, yy, Z, cmap = cmap_light)      # Plot also the training points     plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold, edgecolor='b', s=20)     plt.title(\"3-Class classification (shrink_threshold=%r)\"               % shrinkage)     plt.axis('tight')  plt.show()<\/code><\/pre>\n<h4>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u043c\u0435\u043c\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u043a\u043b\u0430\u0441\u0441\u0430 NearestNeighbors:<\/h4>\n<ul>\n<li>\n<p>fit(X, y = None)<\/p>\n<\/li>\n<\/ul>\n<p>\u041e\u0431\u0443\u0447\u0430\u0435\u0442 \u043c\u043e\u0434\u0435\u043b\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f X \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0442\u0440\u0435\u043d\u0438\u0440\u043e\u0432\u043e\u0447\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445<\/p>\n<p>\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:<\/p>\n<p>X : {\u043c\u0430\u0441\u0441\u0438\u0432, \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u0430\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u0430, \u0434\u0435\u0440\u0435\u0432\u043e \u0448\u0430\u0440\u043e\u0432, KD \u0434\u0435\u0440\u0435\u0432\u043e}<\/p>\n<p>\u0422\u0440\u0435\u043d\u0438\u0440\u043e\u0432\u043e\u0447\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435. \u0415\u0441\u043b\u0438 \u043c\u0430\u0441\u0441\u0438\u0432 \u0438\u043b\u0438 \u043c\u0430\u0442\u0440\u0438\u0446\u0430, \u0444\u043e\u0440\u043c\u0430 [n_samples, n_features], \u0438\u043b\u0438 [n_samples, n_samples] \u0435\u0441\u043b\u0438 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442 metric = &#8216;precomputed&#8217;.<\/p>\n<p>y &#8212; \u043e\u0442\u0432\u0435\u0442\u044b \u0434\u043b\u044f \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u0432\u044b\u0431\u043e\u0440\u043a\u0438<\/p>\n<h4>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u043c\u0435\u043c\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u043a\u043b\u0430\u0441\u0441\u0430 NearestCentroid:<\/h4>\n<ul>\n<li>\n<p>\u041a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0442\u043e\u0440<\/p>\n<\/li>\n<li>\n<p>predict(X)[source]<\/p>\n<\/li>\n<\/ul>\n<p>\u041f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044e \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u0442\u0435\u0441\u0442\u043e\u0432\u043e\u0439 \u0432\u044b\u0431\u043e\u0440\u043a\u0438 X \u0438 \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442 \u043e\u0442\u0432\u0435\u0442\u044b \u0432 \u043c\u0430\u0441\u0441\u0438\u0432.<\/p>\n<p>The predicted class C for each sample in X is returned.<\/p>\n<p>\u0410\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u044b: X : \u043c\u0430\u0441\u0441\u0438\u0432\u043e-\u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0435 \u0442\u0438\u043f\u044b, \u0444\u043e\u0440\u043c\u0430 = [n_samples, n_features]<\/p>\n<p>\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442: C : \u043c\u0430\u0441\u0441\u0438\u0432, \u0444\u043e\u0440\u043c\u0430 = [n_samples]<\/p>\n<h3>\u041e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435<\/h3>\n<p>\u0415\u0441\u043b\u0438 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 metric, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u044b\u043b \u043f\u0435\u0440\u0435\u0434\u0430\u043d \u0432 \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0442\u043e\u0440 \u0440\u0430\u0432\u0435\u043d \u201cprecomputed\u201d, \u0442\u043e \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e X \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u0435\u0439 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u043c\u0435\u0436\u0434\u0443 \u0434\u0430\u043d\u043d\u044b\u043c\u0438, \u043f\u043e\u0434\u043b\u0435\u0436\u0430\u0449\u0438\u043c\u0438 \u043f\u0440\u043e\u0433\u043d\u043e\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044e.<\/p>\n<h4>\u0421\u0441\u044b\u043b\u043a\u0438:<\/h4>\n<ol>\n<li>\n<p><a href=\"http:\/\/scikit-learn.org\/stable\/modules\/neighbors.html#classification\" rel=\"noopener noreferrer nofollow\">\u0421\u0442\u0430\u0442\u044c\u044f: KNN (\u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044f + \u0440\u0435\u0433\u0440\u0435\u0441\u0441\u0438\u044f) \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 scikitlearn \u0441 \u043f\u0440\u0438\u043c\u0435\u0440\u0430\u043c\u0438 \u043a\u043e\u0434\u0430<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/scikit-learn.org\/stable\/modules\/generated\/sklearn.neighbors.NearestCentroid.html#sklearn.neighbors.NearestCentroid\" rel=\"noopener noreferrer nofollow\">\u0414\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u0430\u0446\u0438\u044f \u043f\u043e \u043a\u043b\u0430\u0441\u0441\u0443 NearestCentroid<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/scikit-learn.org\/stable\/modules\/generated\/sklearn.neighbors.NearestNeighbors.html#sklearn.neighbors.NearestNeighbors\" rel=\"noopener noreferrer nofollow\">\u0414\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u0430\u0446\u0438\u044f \u043f\u043e \u043a\u043b\u0430\u0441\u0441\u0443 NearestNeighbors<\/a><\/p>\n<\/li>\n<\/ol>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/799009\/\"> https:\/\/habr.com\/ru\/articles\/799009\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>\u0418\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043a\u043e\u0434 + \u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u043a\u043e\u043c\u0430\u043d\u0434 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b + \u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0438\u0434\u0435\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430<\/p>\n<p>sklearn.neighbors\u00a0\u2014 \u044d\u0442\u043e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0440\u0430\u0431\u043e\u0442\u044b \u0441\u00a0\u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c\u0438, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u043c\u0438 \u043d\u0430\u00a0\u0441\u043e\u0441\u0435\u0434\u044f\u0445 (\u043a\u0430\u043a \u0434\u043b\u044f\u00a0\u0441\u043b\u0443\u0447\u0430\u044f \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0441\u00a0\u0443\u0447\u0438\u0442\u0435\u043b\u0435\u043c, \u0442\u0430\u043a \u0438 \u0434\u043b\u044f\u00a0\u0441\u043b\u0443\u0447\u0430\u044f \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0431\u0435\u0437\u00a0\u0443\u0447\u0438\u0442\u0435\u043b\u044f).<\/p>\n<p>\u041c\u0435\u0442\u043e\u0434 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0431\u0435\u0437\u00a0\u0443\u0447\u0438\u0442\u0435\u043b\u044f \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0441\u043d\u043e\u0432\u043e\u0439 \u0434\u043b\u044f\u00a0\u043c\u043d\u043e\u0433\u0438\u0445 \u0434\u0440\u0443\u0433\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f, \u0432\u00a0\u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438, manifold learning \u0438 \u0441\u043f\u0435\u043a\u0442\u0440\u0430\u043b\u044c\u043d\u043e\u0439 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438.<\/p>\n<p>Manifold learning\u00a0\u2014 \u044d\u0442\u043e \u043f\u043e\u0434\u0445\u043e\u0434, \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u044e\u0449\u0438\u0439\u0441\u044f \u0432\u00a0\u043d\u0435\u043b\u0438\u043d\u0435\u0439\u043d\u043e\u043c \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u043d\u0438\u0438 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438.<\/p>\n<p>\u041e\u0431\u0443\u0447\u0435\u043d\u0438\u0435 \u0441\u00a0\u0443\u0447\u0438\u0442\u0435\u043b\u0435\u043c, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043d\u0430\u00a0\u0441\u043e\u0441\u0435\u0434\u044f\u0445 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432\u00a0\u0434\u0432\u0443\u0445 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430\u0445: \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044f (\u0434\u043b\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0441\u00a0\u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u043c\u0438 \u043c\u0435\u0442\u043a\u0430\u043c\u0438) \u0438 \u0440\u0435\u0433\u0440\u0435\u0441\u0441\u0438\u044f (\u0434\u043b\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0441\u00a0\u043d\u0435\u043f\u0440\u0435\u0440\u044b\u0432\u043d\u044b\u043c\u0438 \u043c\u0435\u0442\u043a\u0430\u043c\u0438).<\/p>\n<p>\u041f\u0440\u0438\u043d\u0446\u0438\u043f \u043c\u0435\u0442\u043e\u0434\u0430 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432\u00a0\u043f\u043e\u0438\u0441\u043a\u0435 \u043f\u0440\u0435\u0434\u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0442\u0440\u0435\u043d\u0438\u0440\u043e\u0432\u043e\u0447\u043d\u044b\u0445 (\u0443\u0447\u0435\u0431\u043d\u044b\u0445) \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432, \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u043f\u043e\u00a0\u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044e \u0434\u043e\u00a0\u043d\u043e\u0432\u043e\u0439 \u0442\u043e\u0447\u043a\u0438, \u0438 \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0430\u0442\u044c \u043c\u0435\u0442\u043a\u0443 \u043f\u043e\u00a0\u043d\u0438\u043c. \u0427\u0438\u0441\u043b\u043e \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432 \u043c\u043e\u0436\u0435\u0442\u00a0\u0431\u044b\u0442\u044c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043e \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u043c \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043e\u0439 (k\u2011\u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439),\u00a0\u043b\u0438\u0431\u043e \u0432\u0430\u0440\u044c\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0432\u00a0\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442\u00a0\u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e\u0439 \u043f\u043b\u043e\u0442\u043d\u043e\u0441\u0442\u0438 \u0442\u043e\u0447\u0435\u043a (\u0440\u0430\u0434\u0438\u0443\u0441\u2011\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0435). \u0420\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435, \u0432\u043e\u043e\u0431\u0449\u0435 \u0433\u043e\u0432\u043e\u0440\u044f, \u043c\u043e\u0436\u0435\u0442\u00a0\u0431\u044b\u0442\u044c \u043b\u044e\u0431\u043e\u0439 \u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043c\u0435\u0440\u043e\u0439: \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u043e\u0435 \u0435\u0432\u043a\u043b\u0438\u0434\u043e\u0432\u043e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u043d\u044b\u043c \u0432\u044b\u0431\u043e\u0440\u043e\u043c. \u041c\u0435\u0442\u043e\u0434\u044b, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043d\u0430\u00a0\u0441\u043e\u0441\u0435\u0434\u044f\u0445, \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b \u043a\u0430\u043a\u00a0\u043d\u0435\u00a0\u043e\u0431\u043e\u0431\u0449\u0430\u044e\u0449\u0438\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f, \u0442\u0430\u043a \u043a\u0430\u043a\u00a0\u043e\u043d\u0438 \u043f\u0440\u043e\u0441\u0442\u043e \u00ab\u0437\u0430\u043f\u043e\u043c\u0438\u043d\u0430\u044e\u0442\u00bb \u0432\u0441\u0435 \u0441\u0432\u043e\u0438 \u0443\u0447\u0435\u0431\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 (\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043f\u0440\u0435\u0432\u0440\u0430\u0449\u0430\u044e\u0442\u0441\u044f \u0432\u00a0\u0431\u044b\u0441\u0442\u0440\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u0442\u0430\u043a\u0443\u044e \u043a\u0430\u043a\u00a0\u0434\u0435\u0440\u0435\u0432\u043e \u0448\u0430\u0440\u043e\u0432 \u0438\u043b\u0438\u00a0KD \u0434\u0435\u0440\u0435\u0432\u043e).<\/p>\n<p>\u041d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430\u00a0\u0441\u0432\u043e\u044e \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u0443, \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0435 \u0441\u043e\u0441\u0435\u0434\u0438 \u0443\u0441\u043f\u0435\u0448\u043d\u043e \u0441\u043f\u0440\u0430\u0432\u0438\u043b\u0438\u0441\u044c \u0441\u00a0\u0431\u043e\u043b\u044c\u0448\u0438\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u043f\u0440\u043e\u0431\u043b\u0435\u043c \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438 \u0438 \u0440\u0435\u0433\u0440\u0435\u0441\u0441\u0438\u0438, \u0432\u043a\u043b\u044e\u0447\u0430\u044f \u0440\u0443\u043a\u043e\u043f\u0438\u0441\u043d\u044b\u0435 \u0446\u0438\u0444\u0440\u044b \u0438\u043b\u0438\u00a0\u0441\u0446\u0435\u043d\u044b \u0441\u043f\u0443\u0442\u043d\u0438\u043a\u043e\u0432\u043e\u0433\u043e \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u044f. \u0411\u0443\u0434\u0443\u0447\u0438 \u043d\u0435\u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u043c\u0435\u0442\u043e\u0434\u043e\u043c, \u043e\u043d \u0447\u0430\u0441\u0442\u043e\u00a0\u0431\u044b\u0432\u0430\u0435\u0442 \u0443\u0441\u043f\u0435\u0448\u043d\u044b\u043c \u0432\u00a0\u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044f\u0445 \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438, \u0433\u0434\u0435 \u0433\u0440\u0430\u043d\u0438\u0446\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043e\u0447\u0435\u043d\u044c \u043d\u0435\u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u0430.<\/p>\n<p>\u041a\u043b\u0430\u0441\u0441\u044b \u0432\u00a0sklearn.neighbors \u043c\u043e\u0433\u0443\u0442 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c\u00a0\u043b\u0438\u0431\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u044b Numpy,\u00a0\u043b\u0438\u0431\u043e scipy.sparse \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0432\u00a0\u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445. \u0414\u043b\u044f\u00a0\u043f\u043b\u043e\u0442\u043d\u044b\u0445 \u043c\u0430\u0442\u0440\u0438\u0446 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u043c\u0435\u0442\u0440\u0438\u043a \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f. \u0414\u043b\u044f\u00a0\u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u0445 \u043c\u0430\u0442\u0440\u0438\u0446 \u0434\u043b\u044f\u00a0\u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u044b\u0435 \u043c\u0435\u0442\u0440\u0438\u043a\u0438 \u041c\u0438\u043d\u043a\u043e\u0432\u0441\u043a\u043e\u0433\u043e.<\/p>\n<p>\u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0443\u0447\u0435\u0431\u043d\u044b\u0445 \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043f\u0438\u0440\u0430\u044e\u0442\u0441\u044f \u043d\u0430\u00a0\u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043f\u043e\u00a0\u0441\u0432\u043e\u0435\u0439 \u0441\u0443\u0442\u0438. \u041e\u0434\u043d\u0438\u043c \u0438\u0437\u00a0\u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0446\u0435\u043d\u043a\u0430 \u043f\u043b\u043e\u0442\u043d\u043e\u0441\u0442\u0438 \u044f\u0434\u0440\u0430, \u043e\u0431\u0441\u0443\u0436\u0434\u0430\u0435\u043c\u0430\u044f \u0432\u00a0\u0440\u0430\u0437\u0434\u0435\u043b\u0435 \u043e\u0446\u0435\u043d\u043a\u0438 \u043f\u043b\u043e\u0442\u043d\u043e\u0441\u0442\u0438.<\/p>\n<h3>\u0411\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0435 \u0441\u043e\u0441\u0435\u0434\u0438 (\u0431\u0435\u0437 \u0443\u0447\u0438\u0442\u0435\u043b\u044f)<\/h3>\n<p>NearestNeighbors \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442 \u043c\u0435\u0442\u043e\u0434 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0431\u0435\u0437 \u0443\u0447\u0438\u0442\u0435\u043b\u044f. \u041e\u043d \u0434\u0435\u0439\u0441\u0442\u0432\u0443\u0435\u0442 \u043a\u0430\u043a \u0435\u0434\u0438\u043d\u044b\u0439 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441 \u0434\u043b\u044f \u0442\u0440\u0435\u0445 \u0440\u0430\u0437\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439: BallTree, KDTree \u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043d\u0430 \u043f\u043e\u0434\u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430\u0445 \u0432 sklearn.metrics.pairwise. \u0412\u044b\u0431\u043e\u0440 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043a\u043b\u044e\u0447\u0435\u0432\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 \u00abalgorithm\u00bb, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u043e\u0434\u043d\u0438\u043c \u0438\u0437 [&#8216;auto&#8217;, &#8216;ball_tree&#8217;, &#8216;kd_tree&#8217;, &#8216;brute&#8217;]. \u041a\u043e\u0433\u0434\u0430 \u043f\u0435\u0440\u0435\u0434\u0430\u0435\u0442\u0441\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e \u00abauto\u00bb, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u044b\u0442\u0430\u0435\u0442\u0441\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043d\u0430\u0438\u043b\u0443\u0447\u0448\u0438\u0439 \u043f\u043e\u0434\u0445\u043e\u0434 \u0438\u0437 \u043e\u0431\u0443\u0447\u0430\u044e\u0449\u0438\u0445 (\u0442\u0440\u0435\u043d\u0438\u0440\u043e\u0432\u043e\u0447\u043d\u044b\u0445) \u0434\u0430\u043d\u043d\u044b\u0445. \u0414\u043b\u044f \u043e\u0431\u0441\u0443\u0436\u0434\u0435\u043d\u0438\u044f \u0441\u0438\u043b\u044c\u043d\u044b\u0445 \u0438 \u0441\u043b\u0430\u0431\u044b\u0445 \u0441\u0442\u043e\u0440\u043e\u043d \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430 \u0441\u043c. \u00ab\u0411\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0435 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b\u00bb.  <\/p>\n<figure class=\"\"><\/figure>\n<figure class=\"\"><\/figure>\n<h3>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439<\/h3>\n<h4>\u041f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440<\/h4>\n<p>\u0411\u044b\u0441\u0442\u0440\u043e\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439\u00a0\u2014 \u044d\u0442\u043e \u0430\u043a\u0442\u0438\u0432\u043d\u0430\u044f \u043e\u0431\u043b\u0430\u0441\u0442\u044c \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u0439 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u041d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043d\u0430\u0438\u0432\u043d\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0441\u043e\u0441\u0435\u0434\u0430 \u0432\u043a\u043b\u044e\u0447\u0430\u0435\u0442 \u0432\u00a0\u0441\u0435\u0431\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u043c\u0435\u0436\u0434\u0443 \u0432\u0441\u0435\u043c\u0438 \u043f\u0430\u0440\u0430\u043c\u0438 \u0442\u043e\u0447\u0435\u043a \u0432\u00a0\u043d\u0430\u0431\u043e\u0440\u0435 \u0434\u0430\u043d\u043d\u044b\u0445: \u0434\u043b\u044f\u00a0N \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432 \u0432\u00a0D \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u044f\u0445 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0442\u0430\u043a\u043e\u0433\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u0430\u043a\u00a0O(D * N^2). \u041f\u043e\u0438\u0441\u043a \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043f\u0440\u0438\u00a0\u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u043c\u043e\u0436\u0435\u0442\u00a0\u0431\u044b\u0442\u044c \u043a\u043e\u043d\u043a\u0443\u0440\u0435\u043d\u0442\u043d\u043e\u0441\u043f\u043e\u0441\u043e\u0431\u043d\u044b\u043c \u0434\u043b\u044f\u00a0\u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0432\u044b\u0431\u043e\u0440\u043e\u043a \u0434\u0430\u043d\u043d\u044b\u0445. \u041e\u0434\u043d\u0430\u043a\u043e \u043f\u043e\u00a0\u043c\u0435\u0440\u0435 \u0440\u043e\u0441\u0442\u0430 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432 N \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u00a0\u0431\u044b\u0441\u0442\u0440\u043e \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043d\u0435\u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0438\u043c\u044b\u043c. \u0412\u00a0\u043a\u043b\u0430\u0441\u0441\u0430\u0445 \u0432\u043d\u0443\u0442\u0440\u0438 sklearn.neighbors \u043f\u043e\u0438\u0441\u043a \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043f\u0440\u0438\u00a0\u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0437\u0430\u0434\u0430\u0435\u0442\u0441\u044f \u0441\u00a0\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043a\u043b\u044e\u0447\u0435\u0432\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 algorithm = &#8216;brute&#8217; \u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u00a0\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043f\u043e\u0434\u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c, \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b\u0445 \u0432\u00a0sklearn.metrics.pairwise. <\/p>\n<h4>K-D Tree<\/h4>\n<p>\u0414\u043b\u044f\u00a0\u0443\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043d\u0435\u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430\u00a0\u0431\u044b\u043b\u0438 \u0438\u0437\u043e\u0431\u0440\u0435\u0442\u0435\u043d\u044b \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445. \u0412\u00a0\u0446\u0435\u043b\u043e\u043c, \u044d\u0442\u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043f\u044b\u0442\u0430\u044e\u0442\u0441\u044f \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u043e\u0431\u044a\u0435\u043a\u0442\u0430\u043c\u0438, \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e \u043a\u043e\u0434\u0438\u0440\u0443\u044f \u0441\u043e\u0432\u043e\u043a\u0443\u043f\u043d\u0443\u044e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e\u00a0\u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0438 \u0434\u043b\u044f\u00a0\u043e\u0431\u0440\u0430\u0437\u0446\u0430. \u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432\u00a0\u0442\u043e\u043c, \u0447\u0442\u043e\u00a0\u0435\u0441\u043b\u0438 \u0442\u043e\u0447\u043a\u0430 A \u043e\u0447\u0435\u043d\u044c \u0434\u0430\u043b\u0435\u043a\u0430 \u043e\u0442\u00a0\u0442\u043e\u0447\u043a\u0438 B, \u0430\u00a0\u0442\u043e\u0447\u043a\u0430 B \u043e\u0447\u0435\u043d\u044c \u0431\u043b\u0438\u0437\u043a\u0430 \u043a\u00a0\u0442\u043e\u0447\u043a\u0435 C, \u0442\u043e \u043c\u044b \u0437\u043d\u0430\u0435\u043c, \u0447\u0442\u043e\u00a0\u0442\u043e\u0447\u043a\u0438 A \u0438 C \u043e\u0447\u0435\u043d\u044c \u0434\u0430\u043b\u0435\u043a\u0438, \u0431\u0435\u0437\u00a0\u044f\u0432\u043d\u043e\u0433\u043e \u0440\u0430\u0441\u0447\u0435\u0442\u0430 \u0438\u0445 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u043f\u043e\u0438\u0441\u043a\u0430 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043c\u043e\u0436\u0435\u0442\u00a0\u0431\u044b\u0442\u044c \u0441\u0432\u0435\u0434\u0435\u043d\u0430 \u043a\u00a0O(D * N * log(N)) \u042d\u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u0438\u0435 \u043f\u043e\u00a0\u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e \u0441\u00a0\u043f\u043e\u043b\u043d\u044b\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c \u0434\u043b\u044f\u00a0\u0431\u043e\u043b\u044c\u0448\u0438\u0445 N. \u0420\u0430\u043d\u043d\u0438\u043c \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u043c \u043a\u00a0\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044e \u044d\u0442\u043e\u0439 \u0441\u043e\u0432\u043e\u043a\u0443\u043f\u043d\u043e\u0439 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438\u00a0\u0431\u044b\u043b\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 KD \u0434\u0435\u0440\u0435\u0432\u0430 (\u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u0435 \u0434\u043b\u044f\u00a0K\u2011\u043c\u0435\u0440\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430), \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043e\u0431\u043e\u0431\u0449\u0430\u0435\u0442 \u0434\u0432\u0443\u043c\u0435\u0440\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u0442\u043e\u0432 \u0438 \u0442\u0440\u0435\u0445\u043c\u0435\u0440\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043e\u043a\u0442\u0430\u043d\u0442\u043e\u0432 \u043d\u0430\u00a0\u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u0439. \u0414\u0435\u0440\u0435\u0432\u043e KD \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 \u0434\u0432\u043e\u0438\u0447\u043d\u0443\u044e \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u0440\u0430\u0437\u0434\u0435\u043b\u044f\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432 \u0432\u0434\u043e\u043b\u044c \u043e\u0441\u0435\u0439 \u0434\u0430\u043d\u043d\u044b\u0445, \u0434\u0435\u043b\u044f \u0435\u0433\u043e \u043d\u0430\u00a0\u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0435 \u043e\u0440\u0442\u043e\u0442\u043e\u043f\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u043e\u0431\u043b\u0430\u0441\u0442\u0438, \u0432\u00a0\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0442\u043e\u0447\u043a\u0438 \u0434\u0430\u043d\u043d\u044b\u0445. \u041a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u044f KD \u0434\u0435\u0440\u0435\u0432\u0430 \u043e\u0447\u0435\u043d\u044c\u00a0\u0431\u044b\u0441\u0442\u0440\u0430\u044f: \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u00a0\u043e\u0441\u044f\u043c \u0434\u0430\u043d\u043d\u044b\u0445, D\u2011\u043c\u0435\u0440\u043d\u044b\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043d\u0435\u00a0\u043d\u0443\u0436\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0442\u044c. \u041e\u0434\u043d\u0430\u0436\u0434\u044b \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u043e\u0435, KD\u2011\u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u0441\u043e\u0441\u0435\u0434\u0430 \u0434\u043b\u044f\u00a0\u0442\u043e\u0447\u043a\u0438\u2011\u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u0437\u0430\u00a0O[log(N)] \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f. \u0425\u043e\u0442\u044f \u043f\u043e\u0434\u0445\u043e\u0434 KD tree \u043e\u0447\u0435\u043d\u044c\u00a0\u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u0434\u043b\u044f\u00a0\u043f\u043e\u0438\u0441\u043a\u043e\u0432 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0441\u00a0\u043d\u0438\u0437\u043a\u0438\u043c \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c (D &lt; 20), \u043e\u043d \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043d\u0435\u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u043c \u043f\u043e\u00a0\u043c\u0435\u0440\u0435 \u0442\u043e\u0433\u043e, \u043a\u0430\u043a\u00a0D \u0440\u0430\u0441\u0442\u0435\u0442 \u043e\u0447\u0435\u043d\u044c \u0432\u0435\u043b\u0438\u043a\u043e: \u044d\u0442\u043e \u043e\u0434\u043d\u043e \u0438\u0437\u00a0\u043f\u0440\u043e\u044f\u0432\u043b\u0435\u043d\u0438\u0439 \u0442\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u00ab\u043f\u0440\u043e\u043a\u043b\u044f\u0442\u0438\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438\u00bb. \u0412\u00a0scikit\u2011learn \u043f\u043e\u0438\u0441\u043a \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 KD \u0437\u0430\u0434\u0430\u0435\u0442\u0441\u044f \u0441\u00a0\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043a\u043b\u044e\u0447\u0435\u0432\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 algorithm = &#8216;kd_tree&#8217; \u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u00a0\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043a\u043b\u0430\u0441\u0441\u0430 KDTree. <\/p>\n<h4>Ball Tree<\/h4>\n<p>\u0414\u043b\u044f\u00a0\u0443\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043d\u0435\u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 KD \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u0432\u00a0\u0431\u043e\u043b\u0435\u0435 \u0432\u044b\u0441\u043e\u043a\u0438\u0445 \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u044f\u0445\u00a0\u0431\u044b\u043b\u0430 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u0448\u0430\u0440\u043e\u0432\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430. \u0412\u00a0\u0442\u0435\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445, \u043a\u043e\u0433\u0434\u0430 \u0434\u0435\u0440\u0435\u0432\u044c\u044f KD \u0434\u0435\u043b\u044f\u0442 \u0434\u0430\u043d\u043d\u044b\u0435 \u043f\u043e\u00a0\u0434\u0435\u043a\u0430\u0440\u0442\u043e\u0432\u044b\u043c \u043e\u0441\u044f\u043c, \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432\u00a0\u0441\u0435\u0440\u0438\u044e \u0433\u043d\u0435\u0437\u0434\u043e\u0432\u044b\u0445 \u0433\u0438\u043f\u0435\u0440\u0441\u0444\u0435\u0440. \u042d\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442 \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u044e \u0434\u0435\u0440\u0435\u0432\u0430 \u0431\u043e\u043b\u0435\u0435 \u0434\u043e\u0440\u043e\u0433\u043e\u0441\u0442\u043e\u044f\u0449\u0435\u0439, \u0447\u0435\u043c KD \u0434\u0435\u0440\u0435\u0432\u043e, \u043d\u043e\u00a0\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043a\u00a0\u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043c\u043e\u0436\u0435\u0442\u00a0\u0431\u044b\u0442\u044c \u043e\u0447\u0435\u043d\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0439 \u0434\u043b\u044f\u00a0\u0432\u044b\u0441\u043e\u043a\u043e\u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u0430\u0436\u0435 \u043f\u0440\u0438\u00a0\u043e\u0447\u0435\u043d\u044c \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044f\u0445. \u0414\u0435\u0440\u0435\u0432\u043e \u0448\u0430\u0440\u043e\u0432 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u0434\u0435\u043b\u0438\u0442 \u0434\u0430\u043d\u043d\u044b\u0435 \u043d\u0430\u00a0\u0443\u0437\u043b\u044b, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c\u044b\u0435 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u043c C \u0438 \u0440\u0430\u0434\u0438\u0443\u0441\u043e\u043c r, \u0442\u0430\u043a \u0447\u0442\u043e\u00a0\u043a\u0430\u0436\u0434\u0430\u044f \u0442\u043e\u0447\u043a\u0430 \u0432\u00a0\u0443\u0437\u043b\u0435 \u043b\u0435\u0436\u0438\u0442 \u0432\u043d\u0443\u0442\u0440\u0438 \u0433\u0438\u043f\u0435\u0440\u0441\u0444\u0435\u0440\u044b, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c\u043e\u0439 r \u0438 C. \u0427\u0438\u0441\u043b\u043e \u0442\u043e\u0447\u0435\u043a\u2011\u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442\u043e\u0432 \u0434\u043b\u044f\u00a0\u043f\u043e\u0438\u0441\u043a\u0430 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442\u0441\u044f \u0437\u0430\u00a0\u0441\u0447\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0430 \u0442\u0440\u0435\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430: |x+y| &lt;= |x| + |y|.<\/p>\n<p>\u0412\u00a0\u0442\u0430\u043a\u043e\u0439 \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0438 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043e\u0434\u043d\u043e\u0433\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u043e\u0439 \u0438 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043d\u0438\u0436\u043d\u044e\u044e \u0438 \u0432\u0435\u0440\u0445\u043d\u044e\u044e \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0434\u043e\u00a0\u0432\u0441\u0435\u0445 \u0442\u043e\u0447\u0435\u043a \u0432\u00a0\u0443\u0437\u043b\u0435. \u0418\u0437\u2011\u0437\u0430 \u0441\u0444\u0435\u0440\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0438 \u0443\u0437\u043b\u043e\u0432 \u0448\u0430\u0440\u043e\u0432\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043e\u043d \u043c\u043e\u0436\u0435\u0442 \u0432\u044b\u0432\u0435\u0441\u0442\u0438 KD\u2011\u0434\u0435\u0440\u0435\u0432\u043e \u0432\u00a0\u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0440\u0430\u0437\u043c\u0435\u0440\u0430\u0445, \u0445\u043e\u0442\u044f \u0444\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0441\u0438\u043b\u044c\u043d\u043e \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442\u00a0\u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u0412\u00a0scikit\u2011learn \u043f\u043e\u0438\u0441\u043a\u0438 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043d\u0430\u00a0\u043e\u0441\u043d\u043e\u0432\u0435 \u0448\u0430\u0440\u0438\u043a\u043e\u0432\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u0437\u0430\u0434\u0430\u044e\u0442\u0441\u044f \u0441\u00a0\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043a\u043b\u044e\u0447\u0435\u0432\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 algorithm = &#8216;ball_tree&#8217; \u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u044e\u0442\u0441\u044f \u0441\u00a0\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043a\u043b\u0430\u0441\u0441\u0430 sklearn.neighbors.BallTree. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u043c\u043e\u0436\u0435\u0442 \u043d\u0430\u043f\u0440\u044f\u043c\u0443\u044e \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0441\u00a0\u043a\u043b\u0430\u0441\u0441\u043e\u043c BallTree.<\/p>\n<h4>\u0412\u044b\u0431\u043e\u0440 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439<\/h4>\n<p>\u041e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u043b\u043e\u0436\u043d\u044b\u043c \u0432\u044b\u0431\u043e\u0440\u043e\u043c \u0438 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0440\u044f\u0434\u0430 \u0444\u0430\u043a\u0442\u043e\u0440\u043e\u0432:  <\/p>\n<ul>\n<li>\n<p>\u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432 N (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, n_samples) \u0438 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c D (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, n_features).<\/p>\n<ul>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u043d\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0440\u0430\u0441\u0442\u0451\u0442 \u043a\u0430\u043a O[DN].<\/p>\n<\/li>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u043d\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0434\u0435\u0440\u0435\u0432\u0430 \u0448\u0430\u0440\u043e\u0432 \u0440\u0430\u0441\u0442\u0451\u0442 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0451\u043d\u043d\u043e \u043a\u0430\u043a O[Dlog(N)].<\/p>\n<\/li>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430 KD \u0434\u0435\u0440\u0435\u0432\u043e\u043c \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0441 D \u0442\u0430\u043a, \u0447\u0442\u043e \u0435\u0433\u043e \u0442\u0440\u0443\u0434\u043d\u043e \u0442\u043e\u0447\u043d\u043e \u043e\u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0437\u043e\u0432\u0430\u0442\u044c. \u0414\u043b\u044f \u043c\u0430\u043b\u044b\u0445 D (\u043c\u0435\u043d\u0435\u0435 20 \u0438\u043b\u0438 \u043e\u043a\u043e\u043b\u043e \u0442\u043e\u0433\u043e) \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0430\u0432\u043d\u0430 O [D * log (N)], \u0438 \u0437\u0430\u043f\u0440\u043e\u0441 KD \u0434\u0435\u0440\u0435\u0432\u0430 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043e\u0447\u0435\u043d\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u043c. \u0414\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e D \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0447\u0442\u0438 \u0434\u043e O[DN], \u0430 \u0438\u0437\u0434\u0435\u0440\u0436\u043a\u0438 \u0438\u0437-\u0437\u0430 \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043c\u043e\u0433\u0443\u0442 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u043a \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c \u043f\u0440\u0438 \u043f\u043e\u043b\u043d\u043e\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0435.<\/p>\n<\/li>\n<\/ul>\n<p>\u0414\u043b\u044f \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u043d\u0430\u0431\u043e\u0440\u043e\u0432 \u0434\u0430\u043d\u043d\u044b\u0445 (N \u043c\u0435\u043d\u0435\u0435 30 \u0438\u043b\u0438 \u043e\u043a\u043e\u043b\u043e \u0442\u043e\u0433\u043e), log(N) \u0441\u0440\u0430\u0432\u043d\u0438\u043c \u0441 N, \u0438 \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u043c, \u0447\u0435\u043c \u043c\u0435\u0442\u043e\u0434\u044b, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043d\u0430 \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435. \u041e\u0431\u0430 \u043c\u0435\u0442\u043e\u0434\u0430 KDTree \u0438 BallTree \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u043b\u0438\u0441\u0442\u0430: \u043e\u043d \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u0438\u0440\u0443\u0435\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0437\u0430\u043f\u0440\u043e\u0441 \u043f\u0435\u0440\u0435\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043e\u0431\u0435\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u044c\u0441\u044f \u043a \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0434\u043b\u044f \u043c\u0430\u043b\u044b\u0445 N.<\/p>\n<ul>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u043d\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0440\u0430\u0441\u0442\u0451\u0442 \u043a\u0430\u043a O[DN]. <\/p>\n<ul>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u043d\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0434\u0435\u0440\u0435\u0432\u0430 \u0448\u0430\u0440\u043e\u0432 \u0440\u0430\u0441\u0442\u0451\u0442 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0451\u043d\u043d\u043e \u043a\u0430\u043a O[Dlog(N)].<\/p>\n<\/li>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430 KD \u0434\u0435\u0440\u0435\u0432\u043e\u043c \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0441 D \u0442\u0430\u043a, \u0447\u0442\u043e \u0435\u0433\u043e \u0442\u0440\u0443\u0434\u043d\u043e \u0442\u043e\u0447\u043d\u043e \u043e\u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0437\u043e\u0432\u0430\u0442\u044c. \u0414\u043b\u044f \u043c\u0430\u043b\u044b\u0445 D (\u043c\u0435\u043d\u0435\u0435 20 \u0438\u043b\u0438 \u043e\u043a\u043e\u043b\u043e \u0442\u043e\u0433\u043e) \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0430\u0432\u043d\u0430 O [D * log (N)], \u0438 \u0437\u0430\u043f\u0440\u043e\u0441 KD \u0434\u0435\u0440\u0435\u0432\u0430 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043e\u0447\u0435\u043d\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u043c. \u0414\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e D \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0447\u0442\u0438 \u0434\u043e O[DN], \u0430 \u0438\u0437\u0434\u0435\u0440\u0436\u043a\u0438 \u0438\u0437-\u0437\u0430 \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043c\u043e\u0433\u0443\u0442 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u043a \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c \u043f\u0440\u0438 \u043f\u043e\u043b\u043d\u043e\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0435.<\/p>\n<\/li>\n<\/ul>\n<p>\u0414\u043b\u044f \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u043d\u0430\u0431\u043e\u0440\u043e\u0432 \u0434\u0430\u043d\u043d\u044b\u0445 (N \u043c\u0435\u043d\u0435\u0435 30 \u0438\u043b\u0438 \u043e\u043a\u043e\u043b\u043e \u0442\u043e\u0433\u043e), log(N) \u0441\u0440\u0430\u0432\u043d\u0438\u043c \u0441 N, \u0438 \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u043c, \u0447\u0435\u043c \u043c\u0435\u0442\u043e\u0434\u044b, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043d\u0430 \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435. \u041e\u0431\u0430 \u043c\u0435\u0442\u043e\u0434\u0430 KDTree \u0438 BallTree \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u043b\u0438\u0441\u0442\u0430: \u043e\u043d \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u0438\u0440\u0443\u0435\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0437\u0430\u043f\u0440\u043e\u0441 \u043f\u0435\u0440\u0435\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043e\u0431\u0435\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u044c\u0441\u044f \u043a \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0434\u043b\u044f \u043c\u0430\u043b\u044b\u0445 N.<\/p>\n<\/li>\n<\/ul>\n<p>\u0412\u0440\u0435\u043c\u044f \u043d\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0440\u0430\u0441\u0442\u0451\u0442 \u043a\u0430\u043a O[DN]. <\/p>\n<ul>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u043d\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0434\u0435\u0440\u0435\u0432\u0430 \u0448\u0430\u0440\u043e\u0432 \u0440\u0430\u0441\u0442\u0451\u0442 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0451\u043d\u043d\u043e \u043a\u0430\u043a O[Dlog(N)].<\/p>\n<\/li>\n<li>\n<p>\u0412\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430 KD \u0434\u0435\u0440\u0435\u0432\u043e\u043c \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0441 D \u0442\u0430\u043a, \u0447\u0442\u043e \u0435\u0433\u043e \u0442\u0440\u0443\u0434\u043d\u043e \u0442\u043e\u0447\u043d\u043e \u043e\u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0437\u043e\u0432\u0430\u0442\u044c. \u0414\u043b\u044f \u043c\u0430\u043b\u044b\u0445 D (\u043c\u0435\u043d\u0435\u0435 20 \u0438\u043b\u0438 \u043e\u043a\u043e\u043b\u043e \u0442\u043e\u0433\u043e) \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0430\u0432\u043d\u0430 O [D * log (N)], \u0438 \u0437\u0430\u043f\u0440\u043e\u0441 KD \u0434\u0435\u0440\u0435\u0432\u0430 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043e\u0447\u0435\u043d\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u043c. \u0414\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e D \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0447\u0442\u0438 \u0434\u043e O[DN], \u0430 \u0438\u0437\u0434\u0435\u0440\u0436\u043a\u0438 \u0438\u0437-\u0437\u0430 \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043c\u043e\u0433\u0443\u0442 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u043a \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0440\u043e\u0441\u0430, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c \u043f\u0440\u0438 \u043f\u043e\u043b\u043d\u043e\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0435.<\/p>\n<\/li>\n<\/ul>\n<p>\u0414\u043b\u044f \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u043d\u0430\u0431\u043e\u0440\u043e\u0432 \u0434\u0430\u043d\u043d\u044b\u0445 (N \u043c\u0435\u043d\u0435\u0435 30 \u0438\u043b\u0438 \u043e\u043a\u043e\u043b\u043e \u0442\u043e\u0433\u043e), log(N) \u0441\u0440\u0430\u0432\u043d\u0438\u043c \u0441 N, \u0438 \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u043c, \u0447\u0435\u043c \u043c\u0435\u0442\u043e\u0434\u044b, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043d\u0430 \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435. \u041e\u0431\u0430 \u043c\u0435\u0442\u043e\u0434\u0430 KDTree \u0438 BallTree \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u043b\u0438\u0441\u0442\u0430: \u043e\u043d \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u0438\u0440\u0443\u0435\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0437\u0430\u043f\u0440\u043e\u0441 \u043f\u0435\u0440\u0435\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043e\u0431\u0435\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u044c\u0441\u044f \u043a \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0434\u043b\u044f \u043c\u0430\u043b\u044b\u0445 N.<\/p>\n<\/li>\n<li>\n<p>\u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445: <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-370347","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/370347","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=370347"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/370347\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=370347"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=370347"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=370347"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}