{"id":387819,"date":"2024-06-29T07:33:35","date_gmt":"2024-06-29T07:33:35","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=387819"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=387819","title":{"rendered":"<span>\u041a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440 \u043c\u0435\u0442\u043e\u0434\u043e\u043c BallTree \u043f\u043e\u0438\u0441\u043a\u0430 k-\u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043d\u0430 Python<\/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<h3>\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435<\/h3>\n<p>\u041a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044f \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 &#8212; \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0434\u043b\u044f \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u043c\u0435\u0442\u043e\u0434 \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438, \u0441\u0443\u0442\u044c \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u043e \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c\u0441\u044f \u0432 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442. <\/p>\n<p>\u041c\u0435\u0442\u043e\u0434 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442 \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439. \u041c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0440\u0430\u0437\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b. \u0421\u0430\u043c\u044b\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439, \u043d\u043e \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u043d\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c &#8212; \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u0432\u0441\u0435\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445. \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u0442\u0430\u043a \u0436\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u043f\u043e\u0438\u0441\u043a\u0430, \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u044b\u0435 KDtree \u0438 BallTree. <\/p>\n<p>\u041f\u0435\u0440\u0435\u0434\u043e \u043c\u043d\u043e\u0439 \u0441\u0442\u043e\u044f\u043b\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440 \u0441 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c \u043f\u043e\u0438\u0441\u043a\u0430 BallTree, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u0439 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441, \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a\u043e\u0439 \u0436\u0435, \u043a\u0430\u043a \u0432 <a href=\"https:\/\/scikit-learn.org\/stable\/modules\/generated\/sklearn.neighbors.BallTree.html\" rel=\"noopener noreferrer nofollow\">sklearn<\/a>). \u0412 \u0440\u0443\u043d\u0435\u0442\u0435 \u044f \u043d\u0435 \u043d\u0430\u0448\u0451\u043b \u0438\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u044e \u0438\u043b\u0438 \u0441\u0442\u0430\u0442\u044c\u044e, \u0441\u0438\u043b\u044c\u043d\u043e \u043f\u043e\u043c\u043e\u0433\u0430\u044e\u0449\u0438\u0435 \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u043a\u043e\u0434. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0440\u0435\u0448\u0438\u043b\u0441\u044f \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u043f\u043e\u0441\u0442 \u0437\u0434\u0435\u0441\u044c. \u0417\u0430\u0440\u0430\u043d\u0435\u0435 \u0441\u043f\u0430\u0441\u0438\u0431\u043e \u0437\u0430 \u043a\u0440\u0438\u0442\u0438\u043a\u0443, \u043d\u0430\u0432\u0435\u0440\u043d\u044f\u043a\u0430 \u0432 \u043a\u043e\u0434\u0435 \u0431\u0443\u0434\u0443\u0442 \u043c\u043e\u043c\u0435\u043d\u0442\u044b, \u0442\u0440\u0435\u0431\u0443\u044e\u0449\u0438\u0435 \u0441\u0435\u0440\u044c\u0451\u0437\u043d\u043e\u0439 \u043f\u0435\u0440\u0435\u0440\u0430\u0431\u043e\u0442\u043a\u0438. \u041d\u043e \u0432 \u043e\u0431\u0449\u0435\u043c \u0438 \u0446\u0435\u043b\u043e\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0440\u0430\u0431\u043e\u0447\u0435\u0435.<\/p>\n<p>\u0414\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043d\u044f\u0442\u044c \u0441\u0442\u0430\u0442\u044c\u044e &#8212; \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0437\u043d\u0430\u0442\u044c \u043e\u0441\u043d\u043e\u0432\u044b Python \u0438 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 numpy.<\/p>\n<hr\/>\n<h2>\u0422\u0435\u043e\u0440\u0438\u044f<\/h2>\n<p><strong><em>\u0414\u0430\u043d\u043e:<\/em><\/strong><\/p>\n<p><strong>1)<\/strong> \u041f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0441 \u0442\u043e\u0447\u043a\u0430\u043c\u0438 (\u0442\u043e\u0447\u043a\u0430 &#8212; \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u0430) \u0438 \u043c\u0435\u0442\u0440\u0438\u043a\u0430, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0449\u0430\u044f \u043a\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u0442\u043e\u0447\u043a\u0430\u043c\u0438.<\/p>\n<p><strong>2)<\/strong> \u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043a\u043b\u0430\u0441\u0441\u043e\u0432. \u041a\u043b\u0430\u0441\u0441\u044b &#8212; \u043d\u0435 \u043f\u0435\u0440\u0435\u0441\u0435\u043a\u0430\u044e\u0449\u0438\u0435\u0441\u044f \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0435 \u0442\u043e\u0447\u043a\u0438. \u0421 \u043a\u0430\u0436\u0434\u043e\u0439 \u0442\u043e\u0447\u043a\u043e\u0439 \u0430\u0441\u0441\u043e\u0446\u0438\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043e\u0434\u0438\u043d \u043a\u043b\u0430\u0441\u0441. \u0413\u043e\u0432\u043e\u0440\u044f\u0442, \u0447\u0442\u043e \u0442\u043e\u0447\u043a\u0430 A \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0438\u0442 \u043a\u043b\u0430\u0441\u0441\u0443 1, \u0430 \u0442\u043e\u0447\u043a\u0430 B \u043a \u043a\u043b\u0430\u0441\u0441\u0443 &#171;2&#187;, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440.<\/p>\n<p><strong>3)<\/strong> \u0422\u043e\u0447\u043a\u0430\/\u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0442\u043e\u0447\u0435\u043a \u043a\u043b\u0430\u0441\u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0439\/\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u0435\u043d.<\/p>\n<p><strong><em>\u0417\u0430\u0434\u0430\u0447\u0430:<\/em><\/strong><\/p>\n<p>\u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u0442\u044c, \u043a \u043a\u0430\u043a\u043e\u043c\u0443 \u043a\u043b\u0430\u0441\u0441\u0443 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0438\u0442 \u0434\u0430\u043d\u043d\u0430\u044f \u0442\u043e\u0447\u043a\u0430. <\/p>\n<p>\u0418\u0434\u0435\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0442\u043e\u0447\u043a\u0438, \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0430\u0449\u0438\u0435 \u043e\u0434\u043d\u043e\u043c\u0443 \u043a\u043b\u0430\u0441\u0441\u0443, \u0447\u0430\u0441\u0442\u043e \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u044e\u0442\u0441\u044f \u0440\u044f\u0434\u043e\u043c \u0434\u0440\u0443\u0433 \u0441 \u0434\u0440\u0443\u0433\u043e\u043c. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043a\u043b\u0430\u0441\u0441 \u0442\u043e\u0447\u043a\u0438 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0432 \u043d\u0430 \u0435\u0451 \u0441\u043e\u0441\u0435\u0434\u0435\u0439. \u0427\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043a\u043b\u0430\u0441\u0441\u0430 n \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u044e\u0442\u0441\u044f \u0431\u043b\u0438\u0437\u043a\u043e \u043a \u0442\u043e\u0447\u043a\u0435 &#8212; \u0442\u0435\u043c \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u0435\u0435 \u044d\u0442\u0430 \u0442\u043e\u0447\u043a\u0430 \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0438\u0442 \u043a \u043a\u043b\u0430\u0441\u0441\u0443 n. <\/p>\n<p>\u041f\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u043d\u0430\u0439\u0442\u0438 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0441\u0440\u0435\u0434\u0438 \u0432\u0441\u0435\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0442\u043e\u0447\u0435\u043a. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0434\u043e \u043a\u0430\u0436\u0434\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0432 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u0438 \u0437\u0430\u043f\u043e\u043c\u0438\u043d\u0430\u0442\u044c \u043a\u043b\u0430\u0441\u0441\u044b \u0441\u0430\u043c\u044b\u0445 \u0431\u043b\u0438\u0437\u043a\u0438\u0445 \u0442\u043e\u0447\u0435\u043a. \u0414\u0430\u043d\u043d\u044b\u0439 \u043f\u043e\u0434\u0445\u043e\u0434 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043c\u043d\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438, \u0432\u0435\u0434\u044c \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u043d\u0443\u0436\u043d\u043e \u043a\u0430\u0436\u0434\u0443\u044e \u0442\u043e\u0447\u043a\u0443. \u041d\u043e \u0435\u0441\u043b\u0438 \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a, \u0442\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u043a\u0430\u0436\u0434\u0443\u044e \u0442\u043e\u0447\u043a\u0443 \u0432\u043e \u0432\u0441\u0435\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u043d\u0435 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f, \u0442\u0430\u043a \u043a\u0430\u043a \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430 \u043f\u043e\u0434\u0441\u043a\u0430\u0436\u0435\u0442, \u043a\u0430\u043a\u0438\u0435 \u0442\u043e\u0447\u043a\u0438 \u0442\u043e\u0447\u043d\u043e \u043d\u0435 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u043c\u0438 \u0441\u043e\u0441\u0435\u0434\u044f\u043c\u0438.<\/p>\n<h3>BallTree<\/h3>\n<p>\u0412 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u043c \u0438\u0442\u043e\u0433\u0435 \u0443 \u043d\u0430\u0441 \u0434\u043e\u043b\u0436\u043d\u0430 \u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430, \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0430\u044f \u0438\u0437 \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0445 \u0448\u0430\u0440\u043e\u0432. \u041a\u0430\u0436\u0434\u0430\u044f \u0442\u043e\u0447\u043a\u0430 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043a \u043e\u0434\u043d\u043e\u043c\u0443 \u0448\u0430\u0440\u0443. \u0412\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u0440\u0430\u0437\u0431\u0438\u0442\u044b \u043d\u0430 \u043d\u0435 \u043f\u0435\u0440\u0435\u0441\u0435\u043a\u0430\u044e\u0449\u0438\u0435\u0441\u044f \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b-\u0448\u0430\u0440\u044b. \u042d\u0442\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u043e\u0431\u0440\u0430\u0437\u0443\u0435\u0442 <strong>\u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435<\/strong> <strong>\u0434\u0435\u0440\u0435\u0432\u043e<\/strong>, \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u0445 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0431\u0443\u0434\u0443\u0442 \u043b\u0435\u0436\u0430\u0442\u044c <strong>\u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u044b<\/strong>, \u0430 \u043a\u0440\u043e\u043d\u043e\u0439 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0431\u0443\u0434\u0443\u0442 <strong>\u043b\u0438\u0441\u0442\u044c\u044f<\/strong>, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0435 \u0442\u043e\u0447\u043a\u0438 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u0440\u0430\u0437\u043c\u0435\u0440 \u043b\u0438\u0441\u0442\u044c\u0435\u0432 \u0440\u0435\u0433\u0443\u043b\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u043c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u043c <strong>LeafSize<\/strong>.<\/p>\n<details class=\"spoiler\">\n<summary>\u0422\u043e\u0447\u043a\u0438<\/summary>\n<div class=\"spoiler__content\">\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/f3f\/f42\/eea\/f3ff42eea896bdf6aadc6e94620fed4c.png\" alt=\"\u041d\u0430\u0448\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a. \u0422\u043e\u0447\u043a\u0438 \u0440\u0430\u0437\u0434\u0435\u043b\u0435\u043d\u044b \u043d\u0430 3 \u043a\u043b\u0430\u0441\u0441\u0430 \u043f\u043e \u0446\u0432\u0435\u0442\u0430\u043c.\" title=\"\u041d\u0430\u0448\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a. \u0422\u043e\u0447\u043a\u0438 \u0440\u0430\u0437\u0434\u0435\u043b\u0435\u043d\u044b \u043d\u0430 3 \u043a\u043b\u0430\u0441\u0441\u0430 \u043f\u043e \u0446\u0432\u0435\u0442\u0430\u043c.\" width=\"424\" height=\"220\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f3f\/f42\/eea\/f3ff42eea896bdf6aadc6e94620fed4c.png\"\/><figcaption>\u041d\u0430\u0448\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a. \u0422\u043e\u0447\u043a\u0438 \u0440\u0430\u0437\u0434\u0435\u043b\u0435\u043d\u044b \u043d\u0430 3 \u043a\u043b\u0430\u0441\u0441\u0430 \u043f\u043e \u0446\u0432\u0435\u0442\u0430\u043c.<\/figcaption><\/figure>\n<\/div>\n<\/details>\n<p>\u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0438\u0440\u0443\u0435\u043c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:<\/p>\n<p><strong>1) <\/strong>\u041e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u043f\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438 \u0441 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0438\u043c \u0440\u0430\u0437\u0431\u0440\u043e\u0441\u043e\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0430\u0439\u0442\u0438 \u0435\u0451. \u0414\u0430\u043b\u044c\u0448\u0435 \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0441 \u044d\u0442\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c\u044e.<\/p>\n<p><strong>2)<\/strong> \u0412\u044b\u0431\u0435\u0440\u0435\u043c \u0442\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u0443\u044e \u0442\u043e\u0447\u043a\u0443 &#8212; <strong>\u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434<\/strong>. \u0426\u0435\u043d\u0442\u0440\u043e\u0438\u0434 &#8212; \u044d\u0442\u043e \u0442\u043e\u0447\u043a\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043f\u043e \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0442\u043e\u0447\u0435\u043a, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u0438\u0442\u044c \u0432 \u043e\u0434\u0438\u043d \u043a\u043b\u0430\u0441\u0442\u0435\u0440. \u0414\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043d\u0430\u0439\u0442\u0438 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u0442\u043e\u0447\u043a\u0443, \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u0430 \u043c\u0435\u043d\u044c\u0448\u0435 \u0432\u0441\u0435\u0433\u043e \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u0441\u0440\u0435\u0434\u043d\u0435\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442 \u043f\u043e \u0432\u0441\u0435\u043c \u0442\u043e\u0447\u043a\u0430\u043c \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0432\u0434\u043e\u043b\u044c \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u043e\u0439 \u0432 \u043f\u0443\u043d\u043a\u0442\u0435 1) \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438.<\/p>\n<p><strong>3) <\/strong>\u041d\u0430\u0439\u0434\u0451\u043c \u0440\u0430\u0434\u0438\u0443\u0441 \u0434\u043e \u0441\u0430\u043c\u043e\u0439 \u0434\u0430\u043b\u044c\u043d\u0435\u0439 \u043e\u0442 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u0442\u043e\u0447\u043a\u0438. \u042d\u0442\u043e \u0440\u0430\u0434\u0438\u0443\u0441 \u0448\u0430\u0440\u0430-\u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u043e\u043a\u0440\u043e\u0435\u0442 \u0432\u0441\u0451 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a (\u043f\u0440\u0438 \u043f\u0435\u0440\u0432\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u0443\u043d\u043a\u0442\u0430).<\/p>\n<details class=\"spoiler\">\n<summary>\u041f\u0435\u0440\u0432\u044b\u0439 \u0448\u0430\u0440<\/summary>\n<div class=\"spoiler__content\">\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/129\/e38\/dbd\/129e38dbd6b1b7dd32ff94ed6f6ac31d.png\" alt=\"\u0428\u0430\u0440, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0430\u0441\u0441\u043e\u0446\u0438\u0438\u0440\u043e\u0432\u0430\u043d \u0441 \u0432\u0435\u0440\u0448\u0438\u043d\u043e\u0439 \u0437\u0430\u0445\u0432\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430.\" title=\"\u0428\u0430\u0440, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0430\u0441\u0441\u043e\u0446\u0438\u0438\u0440\u043e\u0432\u0430\u043d \u0441 \u0432\u0435\u0440\u0448\u0438\u043d\u043e\u0439 \u0437\u0430\u0445\u0432\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430.\" width=\"424\" height=\"220\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/129\/e38\/dbd\/129e38dbd6b1b7dd32ff94ed6f6ac31d.png\"\/><figcaption>\u0428\u0430\u0440, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0430\u0441\u0441\u043e\u0446\u0438\u0438\u0440\u043e\u0432\u0430\u043d \u0441 \u0432\u0435\u0440\u0448\u0438\u043d\u043e\u0439 \u0437\u0430\u0445\u0432\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430.<\/figcaption><\/figure>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/133\/18b\/e78\/13318be78c6a023a5e7b6036c3190061.png\" alt=\"\u0413\u0440\u0430\u0444 ballTree \u043f\u043e\u043a\u0430 \u0447\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a. \u0415\u0441\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u043e\u0440\u0435\u043d\u044c.\" title=\"\u0413\u0440\u0430\u0444 ballTree \u043f\u043e\u043a\u0430 \u0447\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a. \u0415\u0441\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u043e\u0440\u0435\u043d\u044c.\" width=\"424\" height=\"220\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/133\/18b\/e78\/13318be78c6a023a5e7b6036c3190061.png\"\/><figcaption>\u0413\u0440\u0430\u0444 ballTree \u043f\u043e\u043a\u0430 \u0447\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a. \u0415\u0441\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u043e\u0440\u0435\u043d\u044c.<\/figcaption><\/figure>\n<\/div>\n<\/details>\n<p><strong>4) <\/strong>\u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0432\u0441\u0435\u0445 \u0442\u043e\u0447\u0435\u043a \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u043b\u043e\u0441\u044c \u043d\u0430 \u0434\u0432\u0435 \u0447\u0430\u0441\u0442\u0438 &#8212; \u0434\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u0438 \u043f\u043e\u0441\u043b\u0435 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430. \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c\u0441\u044f \u043a \u043f\u0443\u043d\u043a\u0442\u0443 \u0434\u0432\u0430, \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044f \u0435\u0433\u043e \u043d\u0430 \u043f\u0435\u0440\u0432\u043e\u0439, \u0430 \u0434\u0430\u043b\u0435\u0435 \u0432\u0442\u043e\u0440\u043e\u0439 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430. \u0414\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0435\u0441\u044f \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c <strong>LeafSize<\/strong>.<\/p>\n<details class=\"spoiler\">\n<summary>\u0412\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0435 \u0448\u0430\u0440\u044b<\/summary>\n<div class=\"spoiler__content\">\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/876\/476\/952\/876476952429124d2dbeb7b8e794ea76.png\" alt=\"\u0428\u0430\u0440\u044b, \u0441\u043e\u0437\u0434\u0430\u043d\u043d\u044b\u0435 \u043d\u0430 \u0432\u0442\u043e\u0440\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438, \u043f\u043e\u043c\u0435\u0447\u0435\u043d\u044b \u0444\u0438\u043e\u043b\u0435\u0442\u043e\u0432\u044b\u043c \u0446\u0432\u0435\u0442\u043e\u043c. \u042d\u0442\u043e \u043b\u0435\u0432\u044b\u0439 \u0438 \u043f\u0440\u0430\u0432\u044b\u0439 \u043f\u043e\u0442\u043e\u043c\u043a\u0438 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043b\u0438\u0441\u0442\u044c\u044f\u043c\u0438, \u0442\u0430\u043a \u043a\u0430\u043a \u043e\u0445\u0432\u0430\u0442\u044b\u0432\u0430\u044e\u0442 \u0432\u0441\u0435 \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0435\u0441\u044f \u0442\u043e\u0447\u043a\u0438 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430.\" title=\"\u0428\u0430\u0440\u044b, \u0441\u043e\u0437\u0434\u0430\u043d\u043d\u044b\u0435 \u043d\u0430 \u0432\u0442\u043e\u0440\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438, \u043f\u043e\u043c\u0435\u0447\u0435\u043d\u044b \u0444\u0438\u043e\u043b\u0435\u0442\u043e\u0432\u044b\u043c \u0446\u0432\u0435\u0442\u043e\u043c. \u042d\u0442\u043e \u043b\u0435\u0432\u044b\u0439 \u0438 \u043f\u0440\u0430\u0432\u044b\u0439 \u043f\u043e\u0442\u043e\u043c\u043a\u0438 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043b\u0438\u0441\u0442\u044c\u044f\u043c\u0438, \u0442\u0430\u043a \u043a\u0430\u043a \u043e\u0445\u0432\u0430\u0442\u044b\u0432\u0430\u044e\u0442 \u0432\u0441\u0435 \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0435\u0441\u044f \u0442\u043e\u0447\u043a\u0438 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430.\" width=\"424\" height=\"220\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/876\/476\/952\/876476952429124d2dbeb7b8e794ea76.png\"\/><figcaption>\u0428\u0430\u0440\u044b, \u0441\u043e\u0437\u0434\u0430\u043d\u043d\u044b\u0435 \u043d\u0430 \u0432\u0442\u043e\u0440\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438, \u043f\u043e\u043c\u0435\u0447\u0435\u043d\u044b \u0444\u0438\u043e\u043b\u0435\u0442\u043e\u0432\u044b\u043c \u0446\u0432\u0435\u0442\u043e\u043c. \u042d\u0442\u043e \u043b\u0435\u0432\u044b\u0439 \u0438 \u043f\u0440\u0430\u0432\u044b\u0439 \u043f\u043e\u0442\u043e\u043c\u043a\u0438 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043b\u0438\u0441\u0442\u044c\u044f\u043c\u0438, \u0442\u0430\u043a \u043a\u0430\u043a \u043e\u0445\u0432\u0430\u0442\u044b\u0432\u0430\u044e\u0442 \u0432\u0441\u0435 \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0435\u0441\u044f \u0442\u043e\u0447\u043a\u0438 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430.<\/figcaption><\/figure>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/1d5\/ee7\/1c2\/1d5ee71c236f46da50e82cdf7013f1d8.png\" alt=\"\u0423 \u0433\u0440\u0430\u0444\u0430 ballTree \u043f\u043e\u044f\u0432\u0438\u043b\u0438\u0441\u044c \u0432\u0435\u0440\u0448\u0438\u043d\u044b-\u043b\u0438\u0441\u0442\u044c\u044f. \u0415\u0441\u043b\u0438 \u0431\u044b \u0442\u043e\u0447\u0435\u043a \u0431\u044b\u043b\u043e \u0431\u044b \u0431\u043e\u043b\u044c\u0448\u0435, \u0442\u043e \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0435 \u0433\u0440\u0430\u0444\u0430 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u043b\u043e \u0431\u044b \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u043d\u0435 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043b\u0438\u0441\u044c \u0431\u044b \u043f\u043e \u043b\u0438\u0441\u0442\u044c\u044f\u043c.\" title=\"\u0423 \u0433\u0440\u0430\u0444\u0430 ballTree \u043f\u043e\u044f\u0432\u0438\u043b\u0438\u0441\u044c \u0432\u0435\u0440\u0448\u0438\u043d\u044b-\u043b\u0438\u0441\u0442\u044c\u044f. \u0415\u0441\u043b\u0438 \u0431\u044b \u0442\u043e\u0447\u0435\u043a \u0431\u044b\u043b\u043e \u0431\u044b \u0431\u043e\u043b\u044c\u0448\u0435, \u0442\u043e \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0435 \u0433\u0440\u0430\u0444\u0430 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u043b\u043e \u0431\u044b \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u043d\u0435 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043b\u0438\u0441\u044c \u0431\u044b \u043f\u043e \u043b\u0438\u0441\u0442\u044c\u044f\u043c.\" width=\"424\" height=\"220\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1d5\/ee7\/1c2\/1d5ee71c236f46da50e82cdf7013f1d8.png\"\/><figcaption>\u0423 \u0433\u0440\u0430\u0444\u0430 ballTree \u043f\u043e\u044f\u0432\u0438\u043b\u0438\u0441\u044c \u0432\u0435\u0440\u0448\u0438\u043d\u044b-\u043b\u0438\u0441\u0442\u044c\u044f. \u0415\u0441\u043b\u0438 \u0431\u044b \u0442\u043e\u0447\u0435\u043a \u0431\u044b\u043b\u043e \u0431\u044b \u0431\u043e\u043b\u044c\u0448\u0435, \u0442\u043e \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0435 \u0433\u0440\u0430\u0444\u0430 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u043b\u043e \u0431\u044b \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u043d\u0435 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043b\u0438\u0441\u044c \u0431\u044b \u043f\u043e \u043b\u0438\u0441\u0442\u044c\u044f\u043c.<\/figcaption><\/figure>\n<\/div>\n<\/details>\n<p><strong>5) <\/strong>\u0415\u0441\u043b\u0438 \u043e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c<strong> LeafSize <\/strong>(\u0440\u0430\u0437\u043c\u0435\u0440 \u043b\u0438\u0441\u0442\u0430)<strong> <\/strong>\u0442\u043e\u0447\u0435\u043a, \u0442\u043e \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u0438\u0445 \u0432 \u043b\u0438\u0441\u0442 \u0438 \u043f\u0440\u0438\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u043a \u0448\u0430\u0440\u0443, \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u043c\u0443 \u044d\u0442\u0438 \u0442\u043e\u0447\u043a\u0438.<\/p>\n<p><strong>6) <\/strong>\u0417\u0430\u0432\u0435\u0440\u0448\u0430\u0435\u043c \u0440\u0430\u0431\u043e\u0442\u0443 \u0442\u043e\u0433\u0434\u0430, \u043a\u043e\u0433\u0434\u0430 \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u044b \u043f\u043e \u043b\u0438\u0441\u0442\u044c\u044f\u043c.<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c, \u043f\u043e\u0441\u043b\u0435 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0434\u0435\u0440\u0435\u0432\u0430, \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u043f\u043e\u0438\u0441\u043a\u0430 k \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 <strong>\u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0439 \u0442\u043e\u0447\u043a\u0438<\/strong> \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u0441\u044f. <strong>\u041f\u043e\u0447\u0435\u043c\u0443?<\/strong><\/p>\n<p>\u0412 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u043f\u043e\u0438\u0441\u043a\u0430 \u043d\u0430\u043c \u0431\u0443\u0434\u0435\u0442 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0441\u043f\u0443\u0441\u043a\u0430\u0442\u044c\u0441\u044f \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443 \u0441\u0432\u0435\u0440\u0445\u0443 \u0432\u043d\u0438\u0437 \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u043e\u0442 \u043a\u043e\u0440\u043d\u044f. \u041d\u0430 \u043a\u0430\u0436\u0434\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 &#8212; \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u0442\u043e\u0447\u043a\u0438, \u043d\u0430\u0445\u043e\u0434\u044f\u0449\u0438\u0435\u0441\u044f \u043f\u043e \u043f\u0440\u0430\u0432\u0443\u044e \u0438\u043b\u0438 \u043b\u0435\u0432\u0443\u044e \u0441\u0442\u043e\u0440\u043e\u043d\u0443, \u0438\u043b\u0438 \u043d\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c? \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442\u044b \u0432 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0435 \u0441\u043e\u0441\u0435\u0434\u0438 \u0431\u0443\u0434\u0443\u0442 \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c\u0441\u044f \u0432 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c k (\u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043e\u0441\u0435\u0434\u0435\u0439, \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0430\u0439\u0442\u0438). \u0415\u0441\u043b\u0438 \u0431\u0443\u0434\u0435\u0442 \u043d\u0430\u0439\u0434\u0435\u043d\u0430 \u0442\u043e\u0447\u043a\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0440\u0430\u0441\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0430 \u0431\u043b\u0438\u0436\u0435, \u0447\u0435\u043c \u0441\u0430\u043c\u044b\u0439 \u0434\u0430\u043b\u044c\u043d\u0438\u0439 \u0441\u043e\u0441\u0435\u0434 &#8212; \u0442\u043e \u0435\u0433\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u043d\u0430 \u044d\u0442\u0443 \u0442\u043e\u0447\u043a\u0443. \u0415\u0441\u043b\u0438 \u0435\u0449\u0451 \u043d\u0435 \u043d\u0430\u0431\u0440\u0430\u043d\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439, \u0442\u043e \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043b\u044e\u0431\u0430\u044f \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u0430\u044f \u0442\u043e\u0447\u043a\u0430.<\/p>\n<p>\u041f\u0440\u0438 \u0434\u043e\u0441\u0442\u0438\u0436\u0435\u043d\u0438\u0438 \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0432\u044b\u0431\u0435\u0440\u0435\u043c \u0441\u0440\u0435\u0434\u0438 \u0432\u0441\u0435\u0445 \u0442\u0435\u043a\u0443\u0449\u0438\u0445 \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u044b\u0445 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0442\u043e\u0447\u043a\u0443 \u0441 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435\u043c \u043e\u0442 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0439. \u0412\u044b\u0431\u0435\u0440\u0435\u043c \u043e\u0434\u0438\u043d \u0438\u0437 \u0434\u0432\u0443\u0445 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432, \u043b\u0435\u0436\u0430\u0449\u0438\u0445 \u0432 \u043d\u0438\u0436\u043d\u0438\u0445 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u0445. \u0415\u0441\u043b\u0438 \u044d\u0442\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043e\u0442 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0434\u043e \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u0448\u0430\u0440\u0430 \u044d\u0442\u043e\u0433\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 &#8212; \u0442\u043e \u043d\u0430\u043c \u043d\u0435\u0442 \u043d\u0438\u043a\u0430\u043a\u043e\u0439 \u043d\u0430\u0434\u043e\u0431\u043d\u043e\u0441\u0442\u0438 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u0442\u043e\u0447\u043a\u0438, \u0432\u0445\u043e\u0434\u044f\u0449\u0438\u0435 \u0432 \u044d\u0442\u043e\u0442 \u0448\u0430\u0440 \u044d\u0442\u043e\u0433\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430. \u0412 \u043b\u044e\u0431\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0442\u0430\u043c \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0441\u0435\u0434\u0435\u0439, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0431\u0443\u0434\u0443\u0442 \u043b\u0435\u0436\u0430\u0442\u044c \u0431\u043b\u0438\u0436\u0435, \u0447\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0441\u0430\u043c\u044b\u0439 \u0434\u0430\u043b\u0451\u043a\u0438\u0439 \u0441\u043e\u0441\u0435\u0434, \u0432\u044b\u0433\u043e\u0434\u043d\u0435\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u0442\u043e\u0447\u043a\u0438, \u043d\u0430\u0445\u043e\u0434\u044f\u0449\u0438\u0435\u0441\u044f \u0432 \u0434\u0440\u0443\u0433\u043e\u043c \u0448\u0430\u0440\u0435. <\/p>\n<p>\u042d\u0442\u043e \u0438 \u0435\u0441\u0442\u044c \u043c\u043e\u043c\u0435\u043d\u0442 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438. \u0417\u0430\u0440\u0430\u043d\u0435\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a \u0434\u0430\u0451\u0442 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0437\u043d\u0430\u0442\u044c, \u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0434\u0430\u043b\u0435\u043a\u043e \u0431\u0443\u0434\u0443\u0442 \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u0442\u044c\u0441\u044f \u0412\u0421\u0415 \u0442\u043e\u0447\u043a\u0438 \u0432 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0435 (\u0448\u0430\u0440\u0435) \u0431\u0435\u0437 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0434\u043e \u043a\u0430\u0436\u0434\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0438\u0437 \u044d\u0442\u043e\u0433\u043e \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430.<\/p>\n<details class=\"spoiler\">\n<summary>\u041c\u043e\u043c\u0435\u043d\u0442 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438<\/summary>\n<div class=\"spoiler__content\">\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/073\/494\/f7b\/073494f7b6b7f2e55b59c68dd25ebace.png\" width=\"424\" height=\"220\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/073\/494\/f7b\/073494f7b6b7f2e55b59c68dd25ebace.png\"\/><figcaption><\/figcaption><\/figure>\n<p>\u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0447\u0442\u043e \u043d\u0430\u043c \u0434\u0430\u043b\u0438 \u043e\u0440\u0430\u043d\u0436\u0435\u0432\u0443\u044e \u0442\u043e\u0447\u043a\u0443 \u0434\u043b\u044f \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0447\u0442\u043e \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u043e\u0434\u043d\u043e\u0433\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u0441\u043e\u0441\u0435\u0434\u0430, \u0438 \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442\u043e\u043c \u0432 \u043d\u0435\u0433\u043e \u0431\u044b\u043b\u0430 \u043e\u0434\u043d\u0430 \u0438\u0437 \u0441\u0438\u043d\u0438\u0445 \u0442\u043e\u0447\u0435\u043a. \u0414\u0430\u043b\u044c\u0448\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0432\u044b\u0431\u043e\u0440 &#8212; \u043a\u0430\u043a\u0438\u0435 \u0442\u043e\u0447\u043a\u0438 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c? \u041c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c, \u0435\u0441\u0442\u044c \u0442\u043e\u0447\u043a\u0438 \u043f\u043e\u0431\u043b\u0438\u0436\u0435? \u0422\u0430\u043a \u0432\u043e\u0442 \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u0442\u043e\u0447\u043a\u0438 \u0438\u0437 \u0448\u0430\u0440\u0430 3 \u043d\u0435\u0442 \u043d\u0438\u043a\u0430\u043a\u043e\u0433\u043e \u0441\u043c\u044b\u0441\u043b\u0430, \u0442\u0430\u043a \u043a\u0430\u043a \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043e\u0442 \u043d\u0430\u0448\u0435\u0439 \u0442\u043e\u0447\u043a\u0438 \u0434\u043e \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u0448\u0430\u0440\u0430 \u0434\u043b\u0438\u043d\u0435\u0435, \u0447\u0435\u043c \u0434\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u0434\u0430\u043b\u0451\u043a\u043e\u0433\u043e \u043d\u0430 \u0434\u0430\u043d\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u0441\u043e\u0441\u0435\u0434\u0430.<\/p>\n<\/div>\n<\/details>\n<hr\/>\n<h2>\u041f\u0440\u0430\u043a\u0442\u0438\u043a\u0430 &#8212; KnnBalltreeClassifier \u043d\u0430 Python<\/h2>\n<p>\u0413\u0440\u0430\u0444 \u0431\u0443\u0434\u0435\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 \u0432\u0438\u0434\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0442\u043e\u0447\u0435\u043a, \u043e\u043f\u0435\u0440\u0438\u0440\u0443\u044f \u0438\u0445 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0447\u0442\u043e \u0438\u043d\u0434\u0435\u043a\u0441 \u043b\u0435\u0432\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u0435\u043d 2 * v, \u0430 \u043f\u0440\u0430\u0432\u043e\u0439 2 * v + 1 (v &#8212; \u0438\u043d\u0434\u0435\u043a\u0441 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b). \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u0438\u043d\u0434\u0435\u043a\u0441 \u043a\u043e\u0440\u043d\u044f = 1. \u041d\u0430\u043c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u044f\u0442\u0441\u044f \u043a\u043b\u0430\u0441\u0441\u044b \u0434\u043b\u044f \u0432\u0435\u0440\u0448\u0438\u043d \u0433\u0440\u0430\u0444\u0430, \u043a\u043b\u0430\u0441\u0441 \u0434\u043b\u044f \u0442\u043e\u0447\u043a\u0438 \u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u0439. \u0422\u0430\u043a \u0436\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u043e\u0434\u043a\u043b\u044e\u0447\u0438\u0442\u044c numpy, collections, math \u0438 random (\u0434\u043b\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 \u0442\u043e\u0447\u0435\u043a).<\/p>\n<p>\u041d\u0430\u0439\u0434\u0435\u043d\u043d\u044b\u0445 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0431\u0443\u0434\u0435\u043c \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c \u0432 set. \u041f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 (set) \u043d\u0435 \u0434\u043e\u043f\u0443\u0441\u043a\u0430\u0442\u044c \u043a \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044e \u0434\u0443\u0431\u043b\u0438\u0440\u0443\u044e\u0449\u0438\u0435\u0441\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b (\u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0434\u043e \u0442\u043e\u0447\u0435\u043a \u043c\u043e\u0433\u0443\u0442 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0442\u044c\u0441\u044f).<\/p>\n<ul>\n<li>\n<p><strong><em>\u0423\u0437\u043b\u044b \u0433\u0440\u0430\u0444\u0430 BallTree<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">class Node(object):             def __init__(self, pivot = None, points = [], radius = None):        #\u0418\u043d\u0434\u0435\u043a\u0441 \u043a\u043e\u0440\u043d\u044f - 1         self.pivot = pivot #\u0418\u043d\u0434\u0435\u043a\u0441 \u043b\u0435\u0432\u043e\u0439 \u0432\u0435\u0440\u0449\u0438\u043d\u044b - 2*v         self.radius = radius #\u0418\u043d\u0434\u0435\u043a\u0441 \u043f\u0440\u0430\u0432\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b - 2*v + 1         self.points = points     def __str__(self):         self.stringList = ''.join(str(symbol) for symbol in self.points)         return(\"pivot = \" + str(self.pivot) + \" radius = \"          + str(self.radius) + \" points = \"          + str(self.stringList))<\/code><\/pre>\n<p><strong>pivot<\/strong> &#8212; \u0442\u043e\u0447\u043a\u0430 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434 \u0448\u0430\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0430\u0441\u0441\u043e\u0446\u0438\u0438\u0440\u043e\u0432\u0430\u043d \u0441 \u044d\u0442\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u043e\u0439 \u0433\u0440\u0430\u0444\u0430.<br \/><strong>radius<\/strong> &#8212; \u0434\u043b\u0438\u043d\u0430 \u0440\u0430\u0434\u0438\u0443\u0441\u0430 \u0448\u0430\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0430\u0441\u0441\u043e\u0446\u0438\u0438\u0440\u043e\u0432\u0430\u043d \u0441 \u044d\u0442\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u043e\u0439 \u0433\u0440\u0430\u0444\u0430.<br \/><strong>points<\/strong> &#8212; \u043c\u0430\u0441\u0441\u0438\u0432 \u0442\u043e\u0447\u0435\u043a, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043b\u0435\u0436\u0430\u0442 \u0432 \u044d\u0442\u043e\u043c \u0448\u0430\u0440\u0435. \u0412\u0430\u0436\u043d\u043e\u0435 \u043f\u0440\u0438\u043c\u0435\u0447\u0430\u043d\u0438\u0435! \u0422\u043e\u0447\u043a\u0438 \u0431\u0443\u0434\u0443\u0442 \u043b\u0435\u0436\u0430\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u043c \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u043e\u043c \u0448\u0430\u0440\u0435, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0438\u0445 \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u0435\u0442. \u0421 \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f \u0433\u0440\u0430\u0444\u0430 &#8212; \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u043b\u0438\u0441\u0442\u043e\u0432\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u0435 (\u043b\u0438\u0441\u0442\u0435).<br \/>\u0414\u0430\u043b\u044c\u0448\u0435 \u0438\u0434\u0451\u0442 \u043c\u0435\u0442\u043e\u0434 \u0434\u043b\u044f \u043a\u0440\u0430\u0441\u0438\u0432\u043e\u0439 \u043f\u0435\u0447\u0430\u0442\u0438 \u043a\u043b\u0430\u0441\u0441\u0430 \u0432 \u043a\u043e\u043d\u0441\u043e\u043b\u0438. \u0423\u0434\u043e\u0431\u043d\u043e \u0434\u043b\u044f \u043e\u0442\u043b\u0430\u0434\u043a\u0438 \u0438 \u043f\u0440\u043e\u0441\u043c\u043e\u0442\u0440\u0430 ballTree \u043d\u0430 \u0442\u0435\u043a\u0443\u0449\u0435\u043c \u044d\u0442\u0430\u043f\u0435 \u0440\u0430\u0431\u043e\u0442\u044b \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b.<\/p>\n<ul>\n<li>\n<p><strong><em>\u041e\u043f\u0438\u0448\u0435\u043c \u043a\u043b\u0430\u0441\u0441 \u0442\u043e\u0447\u043a\u0438<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">class Point(object):     def __init__(self, point, index):         self.point = point         self.index = index     def __str__(self):         return(\"Vector \" + str(self.point) + \" with index \" + str(self.index))<\/code><\/pre>\n<p><strong>point<\/strong> &#8212; \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b \u0442\u043e\u0447\u043a\u0438. \u0422\u043e \u0435\u0441\u0442\u044c \u043f\u043e \u0441\u0443\u0442\u0438 \u0441\u0430\u043c\u0430 \u0442\u043e\u0447\u043a\u0430 \u043a\u0430\u043a \u043d\u0430\u0431\u043e\u0440 \u0435\u0451 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442.<\/p>\n<p><strong>index<\/strong> &#8212; \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0439 \u0438\u043d\u0434\u0435\u043a\u0441 \u0442\u043e\u0447\u043a\u0438 \u0432\u043e \u0432\u0445\u043e\u0434\u043d\u043e\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 (\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u0442\u043e\u0447\u0435\u043a). \u041f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0443\u0437\u043d\u0430\u0442\u044c \u043a\u043b\u0430\u0441\u0441\u044b \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 (\u043a\u043b\u0430\u0441\u0441\u044b \u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f \u0432 \u0434\u0440\u0443\u0433\u043e\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 \u0438 \u0430\u0441\u0441\u043e\u0446\u0438\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u0441 \u0442\u043e\u0447\u043a\u0430\u043c\u0438 \u0447\u0435\u0440\u0435\u0437 \u0438\u043d\u0434\u0435\u043a\u0441\u044b).<\/p>\n<p>\u0418 \u0441\u043d\u043e\u0432\u0430 \u043c\u0435\u0442\u043e\u0434 \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u043d\u043e\u0433\u043e \u0432\u044b\u0432\u043e\u0434\u0430 \u0432 \u043a\u043e\u043d\u0441\u043e\u043b\u044c \u043f\u0440\u0438 \u043f\u0435\u0447\u0430\u0442\u0438.<\/p>\n<ul>\n<li>\n<p><strong><em>\u041a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0442\u043e\u0440<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">def __init__(self, n_neighbors=1, leaf_size=30):     if(n_neighbors &lt;= 0):         print(\"\u041e\u0448\u0438\u0431\u043a\u0430! \u0421\u043e\u0441\u0435\u0434\u0435\u0439 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c 1\")         return     self.n_neighbors = n_neighbors     self.leaf_size = leaf_size     self.nodes = {}     self.kNSet = set()     self.points = []     self.classes = []     self.pointsOriginal = []<\/code><\/pre>\n<p><strong>n_neighbors<\/strong> &#8212; \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439, \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043d\u0430\u0439\u0442\u0438 \u0434\u043b\u044f \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438 \u043d\u043e\u0432\u043e\u0439 \u0442\u043e\u0447\u043a\u0438.<br \/><strong>leaf_size<\/strong> &#8212; \u0440\u0430\u0437\u043c\u0435\u0440 \u043b\u0438\u0441\u0442\u0430, \u0442\u043e \u0435\u0441\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a \u0432 \u043b\u0438\u0441\u0442\u043e\u0432\u044b\u0445 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u0445. \u0427\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u0440\u0430\u0437\u043c\u0435\u0440 \u043b\u0438\u0441\u0442\u0430 &#8212; \u0442\u0435\u043c \u043c\u0435\u043d\u044c\u0448\u0435 \u043b\u0438\u0441\u0442\u043e\u0432\u044b\u0445 \u0432\u0435\u0440\u0448\u0438\u043d, \u0438 \u043d\u0430\u043e\u0431\u043e\u0440\u043e\u0442.<br \/><strong>nodes<\/strong> &#8212; \u0441\u043b\u043e\u0432\u0430\u0440\u044c \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0432\u0435\u0440\u0448\u0438\u043d<br \/><strong>kNSet<\/strong> &#8212; \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439. \u0412\u0430\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0435\u0433\u043e \u0438\u043c\u0435\u043d\u043d\u043e set, \u0447\u0442\u043e\u0431\u044b \u043d\u0435 \u0431\u044b\u043b\u043e \u043f\u043e\u0432\u0442\u043e\u0440\u0435\u043d\u0438\u0439 \u0441\u0440\u0435\u0434\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.<br \/><strong>points<\/strong> &#8212; \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0442\u043e\u0447\u0435\u043a, \u0431\u0443\u0434\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b.<br \/><strong>classes<\/strong> &#8212; \u043c\u0430\u0441\u0441\u0438\u0432 \u043a\u043b\u0430\u0441\u0441\u043e\u0432 (\u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 &#8212; \u043e\u0434\u0438\u043d \u043a\u043b\u0430\u0441\u0441)<br \/><strong>pointsOriginal<\/strong> &#8212; \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0442\u043e\u0447\u0435\u043a, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043c\u0435\u043d\u044f\u0442\u044c\u0441\u044f \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0440\u0430\u0431\u043e\u0442\u044b \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b (\u043f\u043e\u043a\u0430 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u0433\u0440\u0443\u0436\u0435\u043d\u043e \u043d\u043e\u0432\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a).<\/p>\n<ul>\n<li>\n<p><strong><em>\u0412\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">def GetnpArrayOfPoints(self, xStruct):     x = []     for i in range(len(xStruct)):         x.append(xStruct[i].point)     return(np.array(x))        def Distance(self, a, b):     if(len(a) != len(b)):         print(\"\u0420\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u043d\u0435 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0435!\")         return(\"Error\")     return np.linalg.norm(a-b)             def GetMaxDistance(self, point, points):     points = self.GetnpArrayOfPoints(points)     point = point.point     #print(points) #\u0414\u043b\u044f \u043e\u0442\u043b\u0430\u0434\u043a\u0438     max = 0     for i in range(len(points)):         currentDist = self.Distance(point, points[i])         if(currentDist > max):             max = currentDist     return(max)<\/code><\/pre>\n<p><strong>GetnpArrayOfPoints<\/strong> \u0443\u043f\u0430\u043a\u043e\u0432\u044b\u0432\u0430\u0435\u0442 \u0442\u043e\u0447\u043a\u0438 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432 numpy \u0438\u0437 \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440\u0430 xStruct, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0442\u0438\u043f\u0430 Point.<br \/><strong>Distance<\/strong> &#8212; \u0438\u0449\u0435\u0442 \u0435\u0432\u043a\u043b\u0438\u0434\u043e\u0432\u043e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u0442\u043e\u0447\u043a\u0430\u043c\u0438 a \u0438 b.<br \/><strong>GetMaxDistance<\/strong> &#8212; \u0438\u0449\u0435\u0442 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043e\u0442 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u0442\u043e\u0447\u043a\u0438 point \u0434\u043e \u043a\u0430\u043a\u043e\u0439 \u043b\u0438\u0431\u043e \u0442\u043e\u0447\u043a\u0438 \u0438\u0437 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 points.<\/p>\n<ul>\n<li>\n<p><strong><em>\u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438 \u0441 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0438\u043c \u0440\u0430\u0437\u0431\u0440\u043e\u0441\u043e\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">def GetMaxSpreadDimension(self, x): #\u041d\u0443\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0442\u044c \u043f\u043e\u0434\u043e\u0442\u0440\u0435\u0437\u043e\u043a array[a:b]     x = self.GetnpArrayOfPoints(x)            difference = []     for i in range(x.shape[1]):         maximum = x[0][i]         minimum = x[0][i]         for j in range(x.shape[0]):             maximum = max(maximum, x[j][i])             minimum = min(minimum, x[j][i])         difference.append((maximum - minimum, i))     return(max(difference)[1])<\/code><\/pre>\n<p>\u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u0435\u0440\u0435\u0432\u0435\u0434\u0451\u043c \u0442\u043e\u0447\u043a\u0438 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432 \u043d\u0430\u043c\u043f\u0430\u0439, \u0430 \u0434\u0430\u043b\u044c\u0448\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u0431\u0443\u0434\u0435\u043c \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438, \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043d\u0430\u0439\u0442\u0438 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u0441 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u0440\u0430\u0437\u0431\u0440\u043e\u0441\u043e\u043c. \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0432 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f ballTree.<\/p>\n<ul>\n<li>\n<p><strong><em>\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0442\u043e\u0447\u0435\u043a \u0432\u0434\u043e\u043b\u044c \u0443\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">def SortingByDimension(self, x, startPoint, endPoint, dimension):      #\u041d\u0443\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0442\u044c \u043d\u0430\u0447\u0430\u043b\u043e \u0438 \u043a\u043e\u043d\u0435\u0446     left = x[:startPoint]                                       rigth = x[endPoint:]     x = np.array(sorted(x[startPoint:endPoint], key = lambda Point:      Point.point[dimension]))     x = np.concatenate((left, x, rigth), 0)     return(x)<\/code><\/pre>\n<p>\u0423\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0438\u043c \u0442\u043e\u0447\u043a\u0438 \u0432\u0434\u043e\u043b\u044c \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438. \u041f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0432 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0434\u0435\u0440\u0435\u0432\u0430 ballTree. \u0417\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0431\u0443\u0434\u0435\u043c \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u043e\u0447\u043a\u0438, \u043d\u0430\u0445\u043e\u0434\u044f\u0449\u0438\u0435\u0441\u044f \u043d\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0451\u043d\u043d\u043e\u043c \u043e\u0442\u0440\u0435\u0437\u043a\u0435 \u043d\u0430\u0448\u0435\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u0442\u043e \u0435\u0441\u0442\u044c \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 startPoint \u0438 \u0434\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430 endPoint. \u041f\u043e\u0441\u043b\u0435 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0443\u0447\u0430\u0441\u0442\u043a\u0430 &#8212; \u0441\u043e\u0435\u0434\u0438\u043d\u0438\u043c \u0435\u0433\u043e \u0441 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e\u043c x.<\/p>\n<ul>\n<li>\n<p><strong><em>\u041f\u043e\u0438\u0441\u043a \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">def GetCentroidIndex(self, x, dimension):    #\u041d\u0443\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0442\u044c \u043f\u043e\u0434\u043e\u0442\u0440\u0435\u0437\u043e\u043a array[a:b]         x = self.GetnpArrayOfPoints(x)         if(x.shape[0] == 0):             print(\"\u041e\u0448\u0438\u0431\u043a\u0430! \u041f\u0435\u0440\u0435\u0434\u0430\u043d \u043d\u0443\u043b\u0435\u0432\u043e\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0432 \u043f\u043e\u0438\u0441\u043a \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430\")         sum = 0         for i in range(x.shape[0]): #\u0420\u0430\u0437\u043c\u0435\u0440 x \u043d\u0435 \u043d\u0443\u043b\u0435\u0432\u043e\u0439             sum = sum + x[i][dimension]         sum = sum \/ x.shape[0]         minimum = abs(sum - x[0][dimension])         index = 0         for i in range(x.shape[0]):             if(abs(x[i][dimension] - sum) &lt; minimum):                 minimum = abs(x[i][dimension] - sum)                 index = i         return(index)<\/code><\/pre>\n<p>\u0426\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u0442\u043e\u0447\u043a\u0443, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u043b\u0430\u0441\u044c \u0431\u044b \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043f\u043e \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u0435 \u043f\u0435\u0440\u0435\u0434\u0430\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 x. \u041d\u0430\u0439\u0434\u0451\u043c \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0441\u0440\u0435\u0434\u0438 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442 \u0432\u0441\u0435\u0445 \u0442\u043e\u0447\u0435\u043a \u0438\u0437 x. \u0412\u044b\u0431\u0438\u0440\u0430\u0442\u044c \u0431\u0443\u0434\u0435\u043c \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434 \u0432\u0434\u043e\u043b\u044c \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438 dimension. \u0418\u0449\u0435\u043c \u0442\u043e\u0447\u043a\u0443, \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u043c\u0435\u0436\u0434\u0443 \u0441\u0440\u0435\u0434\u043d\u0438\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c \u043f\u043e \u0432\u0441\u0435\u043c\u0443 x \u0438 \u0435\u0451 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u0430\u043c\u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u0430.<\/p>\n<ul>\n<li>\n<p><strong><em>\u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 ballTree<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">def ConstructTree(self, leafSize, vertexIndex, startPoint, endPoint):     if(endPoint - startPoint &lt;= 0):          return #endPoint \u043d\u0435 \u0432\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u043e\u0442\u0440\u0435\u0437\u043e\u043a [ )              dimension = self.GetMaxSpreadDimension(self.points[startPoint:endPoint])     self.points = self.SortingByDimension(self.points, startPoint, endPoint,      dimension)     centroidIndex = self.GetCentroidIndex(self.points[startPoint:endPoint],      dimension) + startPoint      radius = self.GetMaxDistance(self.points[centroidIndex],      self.points[startPoint:endPoint])     self.nodes[vertexIndex] = self.Node(self.points[centroidIndex],      [], radius)          if(endPoint - startPoint &lt;= leafSize):         for i in range(startPoint, endPoint):             self.nodes[vertexIndex].points.append(self.points[i])         return     else:         self.nodes[vertexIndex].points.append(self.points[centroidIndex])     self.ConstructTree(leafSize, vertexIndex * 2, startPoint, centroidIndex)     self.ConstructTree(leafSize, vertexIndex * 2 + 1, centroidIndex + 1,      endPoint)<\/code><\/pre>\n<p>\u0420\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f. \u041f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u043d\u0430 \u0432\u0445\u043e\u0434 \u043e\u0442\u0440\u0435\u0437\u043e\u043a, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 \u0442\u043e\u0447\u043a\u0438 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430. \u041d\u0430\u0447\u0430\u043b\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u0430 &#8212; <strong>startPoint<\/strong>, \u043a\u043e\u043d\u0435\u0446 &#8212; <strong>endPoint<\/strong>. \u0421\u0430\u043c \u043f\u043e \u0441\u0435\u0431\u0435 \u043e\u0442\u0440\u0435\u0437\u043e\u043a \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u0447\u0430\u0441\u0442\u044c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0432\u0441\u0435\u0445 \u0442\u043e\u0447\u0435\u043a, \u0445\u0440\u0430\u043d\u044f\u0449\u0438\u0445\u0441\u044f \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 points. <strong>vertexIndex<\/strong> &#8212; \u0438\u043d\u0434\u0435\u043a\u0441 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b.<\/p>\n<p>\u0417\u0430\u0432\u0435\u0440\u0448\u0430\u0435\u043c \u0440\u0430\u0431\u043e\u0442\u0443, \u0435\u0441\u043b\u0438 \u0434\u043e\u0448\u043b\u0438 \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u0430 \u0434\u043e \u043a\u043e\u043d\u0446\u0430.<\/p>\n<p>\u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c, \u0432\u0434\u043e\u043b\u044c \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c (\u043a\u0430\u043a \u0432\u044b \u0437\u043d\u0430\u0435\u0442\u0435 &#8212; \u044d\u0442\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u0441 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0438\u043c \u0440\u0430\u0437\u0431\u0440\u043e\u0441\u043e\u043c).<\/p>\n<p>\u0421\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0442\u043e\u0447\u043a\u0438 \u0432\u0434\u043e\u043b\u044c \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438.<\/p>\n<p>\u0414\u0430\u043b\u044c\u0448\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434 \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u0430 \u0441 \u0442\u043e\u0447\u043a\u0430\u043c\u0438. \u041d\u0435 \u0437\u0430\u0431\u044b\u0432\u0430\u0435\u043c \u043f\u0440\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u0446\u0438\u044e \u0441 \u043d\u0443\u043b\u044f (\u0442\u043e\u0447\u043a\u0438 \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u0441 \u0435\u0434\u0438\u043d\u0438\u0446\u044b, \u0430 \u0432\u043d\u0443\u0442\u0440\u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 &#8212; \u0441 \u043d\u0443\u043b\u044f), \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0438\u043d\u0434\u0435\u043a\u0441 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u0441\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0435\u043c \u0441\u043e <strong>StartPoint<\/strong>.<\/p>\n<p>\u0414\u0430\u043b\u044c\u0448\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u0432\u0435\u0440\u0448\u0438\u043d\u0443. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u0440\u0430\u0434\u0438\u0443\u0441 \u0448\u0430\u0440\u0430 (\u044d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0434\u043e \u0441\u0430\u043c\u043e\u0439 \u043e\u0442\u0434\u0430\u043b\u0451\u043d\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u0430) \u0438 \u0441\u043e\u0437\u0434\u0430\u0451\u043c \u0432\u0435\u0440\u0448\u0438\u043d\u0443 (\u0443\u0437\u0435\u043b \u0434\u0435\u0440\u0435\u0432\u0430), \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0437\u0430\u043f\u0438\u0448\u0435\u043c \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434 (\u043d\u0430\u0439\u0434\u0435\u043d\u043d\u0443\u044e \u0442\u043e\u0447\u043a\u0443) \u0438 \u043f\u043e\u043a\u0430 \u0447\u0442\u043e \u043f\u0443\u0441\u0442\u043e\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0442\u043e\u0447\u0435\u043a, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0445\u0441\u044f \u0432 \u044d\u0442\u043e\u043c \u0448\u0430\u0440\u0435.<\/p>\n<p>\u0414\u0430\u043b\u0435\u0435 &#8212; \u0435\u0441\u043b\u0438 \u043e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u043c\u0435\u043d\u044c\u0448\u0435 \u0447\u0435\u043c <strong>leafSize<\/strong> \u0442\u043e\u0447\u0435\u043a, \u0442\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0435\u0441\u044f \u0442\u043e\u0447\u043a\u0438 \u0432\u043d\u0443\u0442\u0440\u044c \u0443\u0437\u043b\u0430 (\u0432 \u043c\u0430\u0441\u0441\u0438\u0432 <strong>Points<\/strong>), \u0442\u043e \u0435\u0441\u0442\u044c \u043d\u0430\u0448\u0430 \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043b\u0438\u0441\u0442\u043e\u0432\u043e\u0439. \u041a\u0430\u043a \u0442\u043e\u043b\u044c\u043a\u043e \u0437\u0430\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0442\u043e\u0447\u043a\u0438 \u0438\u043b\u0438 \u0440\u0430\u0437\u043c\u0435\u0440 \u043b\u0438\u0441\u0442\u0430 &#8212; \u0432\u044b\u0445\u043e\u0434\u0438\u043c. <\/p>\n<p>\u0415\u0441\u043b\u0438 \u0442\u043e\u0447\u043a\u0438 \u0435\u0449\u0451 \u0435\u0441\u0442\u044c, \u0442\u043e \u0443\u0441\u043b\u043e\u0432\u043d\u043e \u0434\u0435\u043b\u0438\u043c \u0432\u0441\u0451 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043d\u0430 \u0434\u0432\u0435 \u0447\u0430\u0441\u0442\u0438 &#8212; \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u0430 \u0434\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0439\u0434\u0430 \u0438 \u043e\u0442 \u0446\u0435\u043d\u0434\u0440\u043e\u0438\u0434\u0430 \u0434\u043e \u043a\u043e\u043d\u0446\u0430. \u041e\u0434\u043d\u0443 \u0438\u0437 \u0447\u0430\u0441\u0442\u0435\u0439 \u043f\u0435\u0440\u0435\u0434\u0430\u0451\u043c \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043e\u0442\u0440\u0435\u0437\u043a\u0430 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043b\u0435\u0432\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u0432\u0442\u043e\u0440\u0443\u044e &#8212; \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043f\u0440\u0430\u0432\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b.<\/p>\n<p>\u041f\u043e \u0438\u0442\u043e\u0433\u0443 \u0438\u043c\u0435\u0435\u043c, \u0447\u0442\u043e \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0442\u043e\u0447\u0435\u043a \u043f\u043e\u0434\u0435\u043b\u0451\u043d \u043d\u0430 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b, \u043a \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043c\u043e\u0436\u043d\u043e \u043e\u0431\u0440\u0430\u0442\u0438\u0442\u044c\u0441\u044f \u0447\u0435\u0440\u0435\u0437 \u043f\u043e\u043b\u0435 <strong>points<\/strong> \u043a\u043b\u0430\u0441\u0441\u0430 <strong>Node<\/strong> (\u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0434\u0435\u0440\u0435\u0432\u0430). \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u0438\u043d\u0434\u0435\u043a\u0441 \u043a\u0430\u0436\u0434\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0432 \u043e\u0431\u0449\u0435\u043c \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 <strong>points<\/strong> \u043a\u043b\u0430\u0441\u0441\u0430 <strong>KnnBalltreeClassifier<\/strong> \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u043a\u0430\u043a 2*v \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u043b\u0435\u0432\u044b\u0445 \u0432\u0435\u0440\u0448\u0438\u043d, 2*v+1 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u043f\u0440\u0430\u0432\u044b\u0445 \u0432\u0435\u0440\u0448\u0438\u043d \u0438 1 \u0434\u043b\u044f \u043a\u043e\u0440\u043d\u044f.<\/p>\n<ul>\n<li>\n<p><strong><em>\u041f\u043e\u0438\u0441\u043a \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">def searchBallSubtree(self, vertexIndex, newPoint, kN):     if(len(self.nodes[vertexIndex].points) > 1):         for point in self.nodes[vertexIndex].points:             distance = self.Distance(newPoint, point.point)             if(len(self.kNSet) >= kN and max(self.kNSet)[0] > distance):                 self.kNSet.remove(max(self.kNSet))             if(len(self.kNSet) &lt; kN):                 self.kNSet.add((distance, point.index))         return     leftChild = vertexIndex * 2     rightChild = vertexIndex * 2 + 1     distance = self.Distance(newPoint, self.nodes[vertexIndex].pivot.point)      if(len(self.kNSet) >= kN and max(self.kNSet)[0] > distance):         self.kNSet.remove(max(self.kNSet))     if(len(self.kNSet) &lt; kN):         self.kNSet.add((distance, self.nodes[vertexIndex].pivot.index))              if(len(self.nodes[leftChild].points) != 0):         distance = self.Distance(newPoint,                                   self.nodes[leftChild].pivot.point)         if(len(self.kNSet) &lt; kN or             max(self.kNSet)[0] > distance - self.nodes[leftChild].radius):             self.searchBallSubtree(leftChild, newPoint, kN)      if(len(self.nodes[rightChild].points) != 0):         distance = self.Distance(newPoint,                                   self.nodes[rightChild].pivot.point)         if(len(self.kNSet) &lt; kN or             max(self.kNSet)[0] > distance - self.nodes[rightChild].radius):             self.searchBallSubtree(rightChild, newPoint, kN)<\/code><\/pre>\n<p>\u0420\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f.<\/p>\n<p>\u0415\u0441\u043b\u0438 \u0432 \u0443\u0437\u043b\u0435 (\u0448\u0430\u0440\u0435, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0430\u0441\u0441\u043e\u0446\u0438\u0438\u0440\u043e\u0432\u0430\u043d \u0441 \u0432\u0435\u0440\u0448\u0438\u043d\u043e\u0439) \u0435\u0441\u0442\u044c \u0442\u043e\u0447\u043a\u0438, \u0442\u043e \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u043d\u0435\u0442 \u043b\u0438 \u0441\u0440\u0435\u0434\u0438 \u043d\u0438\u0445 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439. \u0412\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0434\u043e \u043a\u0430\u0436\u0434\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0438 \u0441\u043c\u043e\u0442\u0440\u0438\u043c, \u043c\u0435\u043d\u044c\u0448\u0435 \u043b\u0438 \u043e\u043d\u043e, \u0447\u0435\u043c \u0443 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u0434\u0430\u043b\u0451\u043a\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0432 kNSet (\u0442\u043e \u0435\u0441\u0442\u044c \u0441\u0440\u0435\u0434\u0438 \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442\u043e\u0432 \u043d\u0430 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439). <\/p>\n<p>\u0415\u0441\u043b\u0438 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0443\u0436\u0435 \u0434\u043e\u0441\u0442\u0438\u0433\u043d\u0443\u0442\u043e, \u0442\u043e \u0443\u0434\u0430\u043b\u044f\u0435\u043c \u0441\u0430\u043c\u0443\u044e \u0434\u0430\u043b\u0451\u043a\u0443\u044e \u0442\u043e\u0447\u043a\u0443 \u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u043f\u0430\u0440\u0443 (\u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435, \u0438\u043d\u0434\u0435\u043a\u0441) \u0432 <strong>knSet<\/strong>. \u041f\u043e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044e \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043b\u0435\u0433\u043a\u043e \u043d\u0430\u0439\u0442\u0438 \u0441\u0430\u043c\u0443\u044e \u0434\u0430\u043b\u0451\u043a\u043e\u0433\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u0441\u043e\u0441\u0435\u0434\u0430, \u0430 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 &#8212; \u043d\u0435\u043f\u043e\u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0441\u0430\u043c\u0443 \u0442\u043e\u0447\u043a\u0443, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 <strong>pointsOriginal<\/strong>.<\/p>\n<p>\u0415\u0441\u043b\u0438 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0435\u0449\u0451 \u043d\u0435\u0442, \u0442\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u043f\u0430\u0440\u0443 (\u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435, \u0438\u043d\u0434\u0435\u043a\u0441) \u0432 <strong>knSet<\/strong>.<\/p>\n<p>\u0414\u0430\u043b\u044c\u0448\u0435 \u043d\u0430\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u043d\u0438\u0436\u0435 \u043f\u043e ballTree \u0434\u043b\u044f \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u0438\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u0432\u0435\u0440\u0448\u0438\u043d. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u043c \u0438\u043d\u0434\u0435\u043a\u0441\u044b \u043b\u0435\u0432\u043e\u0439 \u0438 \u043f\u0440\u0430\u0432\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b.<\/p>\n<p>\u0426\u0435\u043d\u0442\u0440\u043e\u0438\u0434 \u0432\u0435\u0440\u0448\u0438\u043d\u044b &#8212; \u0442\u043e \u0436\u0435 \u0442\u043e\u0447\u043a\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u043c \u0441\u043e\u0441\u0435\u0434\u043e\u043c. \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0435\u0451 \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c (\u043a\u0430\u043a \u0442\u043e\u0447\u043a\u0438 \u0432\u043d\u0443\u0442\u0440\u0438 \u0448\u0430\u0440\u0430 \u043d\u0430 4 &#8212; 8 \u0441\u0442\u0440\u043e\u043a\u0430\u0445).<\/p>\n<p>\u0414\u0430\u043b\u044c\u0448\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u043c \u0443\u0441\u043b\u043e\u0432\u0438\u0435, \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c\u043e\u0435 \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u043c \u0430\u0431\u0437\u0430\u0446\u0435 \u0440\u0430\u0437\u0434\u0435\u043b\u0430 \u0422\u0435\u043e\u0440\u0438\u044f. \u0422\u043e \u0435\u0441\u0442\u044c \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u0443\u0437\u043d\u0430\u0435\u043c \u043f\u043e \u043b\u0435\u0432\u043e\u043c\u0443 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0443, \u043c\u043e\u0433\u0443\u0442 \u043b\u0438 \u0432 \u0435\u0433\u043e \u0448\u0430\u0440\u0435 \u043b\u0435\u0436\u0430\u0442\u044c \u0442\u043e\u0447\u043a\u0438, \u0441\u0440\u0435\u0434\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0435\u0441\u0442\u044c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0435 \u0441\u043e\u0441\u0435\u0434\u0438. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0432\u043e\u043e\u0431\u0449\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u043c, \u0435\u0441\u0442\u044c \u043b\u0438 \u0442\u0430\u043c \u043a\u0430\u043a\u0438\u0435 \u043b\u0438\u0431\u043e \u0442\u043e\u0447\u043a\u0438 \u0438 \u043d\u0430\u0431\u0440\u0430\u043b\u0438 \u043b\u0438 \u043c\u044b \u043d\u0443\u0436\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439. \u0415\u0441\u043b\u0438 \u0442\u0430\u043c \u043d\u0435\u0442 \u0442\u043e\u0447\u0435\u043a &#8212; \u0442\u043e \u043d\u0435 \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u044d\u0442\u043e\u0442 \u0448\u0430\u0440. \u0415\u0441\u043b\u0438 \u043c\u044b \u043d\u0435 \u043d\u0430\u0431\u0440\u0430\u043b\u0438 \u043d\u0443\u0436\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 &#8212; \u0442\u043e \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u044d\u0442\u043e\u0442 \u0448\u0430\u0440. \u0415\u0441\u043b\u0438 \u0443 \u043d\u0430\u0441 \u0443\u0436\u0435 \u0435\u0441\u0442\u044c \u043d\u0443\u0436\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439, \u0438 \u0441\u0430\u043c\u044b\u0439 \u0434\u0430\u043b\u044c\u043d\u0438\u0439 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0439 \u0441\u043e\u0441\u0435\u0434 \u043b\u0435\u0436\u0438\u0442 \u0431\u043b\u0438\u0436\u0435, \u0447\u0435\u043c \u0433\u0440\u0430\u043d\u0438\u0446\u0430 \u044d\u0442\u043e\u0433\u043e \u0448\u0430\u0440\u0430, \u0442\u043e \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u0448\u0430\u0440\u0430 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0434\u0430\u043b\u044c\u0448\u0435 \u043d\u0435\u0433\u043e.<\/p>\n<p>\u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u0440\u043e\u0434\u0435\u043b\u044b\u0432\u0430\u0435\u043c \u0441 \u043f\u0440\u0430\u0432\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b.<\/p>\n<p>\u0414\u0430\u043b\u0435\u0435 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e, \u0433\u0434\u0435 \u043c\u0435\u043d\u044f\u0435\u043c \u0442\u043e\u043b\u044c\u043a\u043e \u0438\u043d\u0434\u0435\u043a\u0441 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b.<\/p>\n<ul>\n<li>\n<p><strong><em>\u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430 \u0442\u043e\u0447\u0435\u043a<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">def fit(self, x, y):     if (len(x) != len(y)):         print(\"\u041e\u0448\u0438\u0431\u043a\u0430 - \u043d\u0435 \u0443 \u0432\u0441\u0435\u0445 \u0442\u043e\u0447\u0435\u043a \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u044b \u043a\u043b\u0430\u0441\u0441\u044b\")         return(\"fit Error\")     self.points = []     self.classes = []     self.pointsOriginal = x     for i in range(len(x)):         self.points.append(self.Point(x[i], i))     self.classes = y      self.ConstructTree(self.leaf_size, 1, 0, len(self.points))     return self<\/code><\/pre>\n<p>\u041d\u0430\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0442\u044c \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440\u0443 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a, \u0441\u0440\u0435\u0434\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043e\u043d \u0431\u0443\u0434\u0435\u0442 \u0438\u0441\u043a\u0430\u0442\u044c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439. \u042d\u0442\u0430 \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u0430 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f fit, \u0442\u0430\u043a \u043a\u0430\u043a \u043c\u044b \u043a\u0430\u043a \u0431\u044b \u0441\u043a\u0430\u0440\u043c\u043b\u0438\u0432\u0430\u0435\u043c \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440\u0443 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432, \u0441 \u043a\u043e\u0442\u043e\u0440\u044b\u043c\u0438 \u043e\u043d \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c. \u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u043e\u0432 \u043c\u044b \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u043c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a x \u0438 \u043c\u0430\u0441\u0441\u0438\u0432 \u0438\u0445 \u043a\u043b\u0430\u0441\u0441\u043e\u0432 y. <\/p>\n<p>\u0412 fit \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0432\u0441\u0435 \u043d\u0443\u0436\u043d\u044b\u0435 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f \u043f\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u044d\u0442\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430. <\/p>\n<p>\u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0435\u0441\u0442\u044c \u043b\u0438 \u043a\u043b\u0430\u0441\u0441\u044b \u0443 \u0432\u0441\u0435\u0445 \u0442\u043e\u0447\u0435\u043a, \u0447\u0438\u0441\u0442\u0438\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u044b \u043a\u043b\u0430\u0441\u0441\u043e\u0432 \u0438 \u0442\u043e\u0447\u0435\u043a, \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u043c \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u0432 pointsOriginal (\u0434\u0430\u043b\u0435\u0435 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u043c\u044b \u0441\u043c\u043e\u0436\u0435\u043c \u043d\u0430\u0439\u0442\u0438 \u0432 \u043d\u0451\u043c \u043d\u0443\u0436\u043d\u0443\u044e \u0442\u043e\u0447\u043a\u0443.<\/p>\n<p>\u0414\u0430\u043b\u044c\u0448\u0435 \u0441\u043e\u0437\u0434\u0430\u0451\u043c \u043c\u0430\u0441\u0441\u0438\u0432 \u0438\u0437 \u043a\u043b\u0430\u0441\u0441\u043e\u0432 <strong>Point<\/strong> (\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0445\u0440\u0430\u043d\u044f\u0442 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u0438\u043d\u0434\u0435\u043a\u0441 \u0438 \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0441\u0430\u043c \u0432\u0435\u043a\u0442\u043e\u0440 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442) \u0438 \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u043c\u0430\u0441\u0441\u0438\u0432 \u043a\u043b\u0430\u0441\u0441\u043e\u0432 \u0432 <strong>classes<\/strong>.<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043c\u044b \u0433\u043e\u0442\u043e\u0432\u044b \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0434\u0435\u0440\u0435\u0432\u043e.<\/p>\n<ul>\n<li>\n<p><strong><em>\u041f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0430\u043d\u0438\u0435 \u043a\u043b\u0430\u0441\u0441\u0430<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">def predict(self, x):     predictions = []     for i in range(len(x)):         self.kNSet.clear()         self.searchBallSubtree(1, x[i], self.n_neighbors)         results = []         for index in self.kNSet: #kNSet \u0445\u0440\u0430\u043d\u0438\u0442 \u043f\u0430\u0440\u0443 (\u0434\u0438\u0441\u0442\u0430\u043d\u0446\u0438\u044f, \u0438\u043d\u0434\u0435\u043a\u0441)             results.append(self.classes[index[1]])          resultClass = Counter(results).most_common()[0][0]         predictions.append(resultClass)     return np.array(predictions)<\/code><\/pre>\n<p>\u0421\u043c\u044b\u0441\u043b \u043d\u0430\u0448\u0435\u0433\u043e \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440\u0430 &#8212; \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u0442\u044c \u043a\u043b\u0430\u0441\u0441 \u0442\u043e\u0447\u043a\u0438, \u043e\u0441\u043d\u043e\u0432\u044b\u0432\u0430\u044f\u0441\u044c \u043d\u0430 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u044f\u0445. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0432 \u044d\u0442\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043c\u044b \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u043c \u043a\u043b\u0430\u0441\u0441\u044b \u0432\u0441\u0435\u0445 \u0442\u043e\u0447\u0435\u043a, \u043f\u043e\u0434\u0430\u043d\u043d\u044b\u0445 \u0432 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u0435 \u043a\u0430\u043a \u043c\u0430\u0441\u0441\u0438\u0432 x.<\/p>\n<p>\u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0441\u043e\u0437\u0434\u0430\u0451\u043c \u043c\u0430\u0441\u0441\u0438\u0432 <strong>predictions<\/strong>, \u0438\u0449\u0435\u043c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0438\u0437 x. \u041d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u044b\u0439 \u043a\u043b\u0430\u0441\u0441 \u0442\u043e\u0447\u043a\u0438 &#8212; \u044d\u0442\u043e \u0441\u0430\u043c\u044b\u0439 \u0447\u0430\u0441\u0442\u043e \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u044e\u0449\u0438\u0439\u0441\u044f \u043a\u043b\u0430\u0441\u0441 \u0441\u0440\u0435\u0434\u0438 \u0442\u043e\u0447\u0435\u043a \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439. \u0423\u0437\u043d\u0430\u0451\u043c \u043c\u044b \u0435\u0433\u043e \u043d\u0430 10 \u0441\u0442\u0440\u043e\u0447\u043a\u0435 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043c\u0435\u0442\u043e\u0434\u0430 most_common.<\/p>\n<ul>\n<li>\n<p><strong><em>\u041f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0430\u043d\u0438\u0435 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0438 \u043a\u043b\u0430\u0441\u0441\u0430<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">def predict_proba(self, X):         classesCount = np.unique(self.classes)     results = []     for point in X:         neighborsClasses = self.get_kneighbors_classes(point)         result = []         for clas in classesCount:             count = 0             for neighborClass in neighborsClasses:                 if(clas == neighborClass):                     count += 1             result.append(count\/self.n_neighbors * 100)         results.append(result)     return(np.array(results))<\/code><\/pre>\n<p>\u0415\u0441\u043b\u0438 \u043c\u044b \u043d\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u0445\u043e\u0442\u0438\u043c \u0437\u043d\u0430\u0442\u044c, \u043a\u0430\u043a\u043e\u043c\u0443 \u043a\u043b\u0430\u0441\u0441\u0443 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0438\u0442 \u0442\u043e\u0447\u043a\u0430, \u0430 \u0445\u043e\u0442\u0438\u043c \u0437\u043d\u0430\u0442\u044c \u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e \u0447\u0442\u043e \u043e\u043d\u0430 \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0438\u0442 \u043a \u044d\u0442\u043e\u043c\u0443 \u0438\u043b\u0438 \u043a\u0430\u043a\u043e\u043c\u0443 \u043b\u0438\u0431\u043e \u0434\u0440\u0443\u0433\u043e\u043c\u0443 \u043a\u043b\u0430\u0441\u0441\u0443 \u043f\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0443 \u0440\u0430\u0431\u043e\u0442\u044b \u043d\u0430\u0448\u0435\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u0442\u043e \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u044d\u0442\u0438\u043c \u043c\u0435\u0442\u043e\u0434\u043e\u043c. <\/p>\n<p>\u0427\u0442\u043e\u0431\u044b \u043d\u0430\u0439\u0442\u0438 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0438, \u043d\u0430\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0430\u0439\u0442\u0438 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043a\u043b\u0430\u0441\u0441\u043e\u0432 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0432\u0438\u0434\u0430 \u0441\u0440\u0435\u0434\u0438 \u0432\u0441\u0435\u0445 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0438 \u043f\u043e\u0434\u0435\u043b\u0438\u0442\u044c \u043d\u0430 \u043e\u0431\u0449\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043a\u043b\u0430\u0441\u0441\u043e\u0432 (\u0440\u0430\u0432\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439). \u0412\u044b\u0440\u0430\u0437\u0438\u043c \u043e\u0442\u0432\u0435\u0442 \u0432 \u043f\u0440\u043e\u0446\u0435\u043d\u0442\u0430\u0445 (12 \u0441\u0442\u0440\u043e\u0447\u043a\u0430).<\/p>\n<ul>\n<li>\n<p><strong><em>\u041f\u0440\u043e\u0441\u043c\u043e\u0442\u0440 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u043e \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u044b\u0445 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u044f\u0445<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">def get_kneighbors_classes(self, x):     self.kNSet.clear()     self.searchBallSubtree(1, x, self.n_neighbors)     result = []     for index in self.kNSet:         result.append(self.classes[index[1]])      return np.array(result)          def kneighbors(self, x, n_neighbors):     results = []     for i in range(len(x)):         self.kNSet.clear()         self.searchBallSubtree(1, x[i], n_neighbors)         result = []          for index in self.kNSet:             result.append(self.pointsOriginal[index[1]])         results.append(result)         return np.array(np.array(results))<\/code><\/pre>\n<p>\u0418\u043d\u043e\u0433\u0434\u0430 \u043d\u0430\u043c \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u044f\u0445 \u043d\u0430\u0448\u0435\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430.<\/p>\n<p><strong>get_kneighbors_classes<\/strong> \u043d\u0430\u0439\u0434\u0451\u0442 \u0438 \u0432\u044b\u0434\u0430\u0441\u0442 \u043d\u0430\u043c \u043a\u043b\u0430\u0441\u0441\u044b \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0442\u043e\u0447\u043a\u0438 <strong>x<\/strong>.<br \/><strong>kneighbors<\/strong> \u043d\u0430\u0439\u0434\u0451\u0442 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0442\u043e\u0447\u0435\u043a \u0438\u0437 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 <strong>x<\/strong>.<\/p>\n<details class=\"spoiler\">\n<summary>\u041a\u043e\u0434 \u043a\u043b\u0430\u0441\u0441\u0430 KnnBalltreeClassifier<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"python\">import random import math import numpy as np from collections import Counter  class KnnBalltreeClassifier(object):     '''\u041a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442 \u0432\u0437\u0432\u0435\u0448\u0435\u043d\u043d\u043e\u0435 \u0433\u043e\u043b\u043e\u0441\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u043c \u0441\u043e\u0441\u0435\u0434\u044f\u043c.      \u041f\u0440\u0438 \u043f\u043e\u0434\u0441\u0447\u0435\u0442\u0435 \u0440\u0430\u0441c\u0442\u043e\u044f\u043d\u0438\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f l2-\u043c\u0435\u0442\u0440\u0438\u043a\u0430.     \u041f\u043e\u0438\u0441\u043a \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u0441\u043e\u0441\u0435\u0434\u0430 \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0438\u0441\u043a\u043e\u043c \u043f\u043e ball-\u0434\u0435\u0440\u0435\u0432\u0443.     \u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b     ----------     n_neighbors : int, optional         \u0427\u0438\u0441\u043b\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439, \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u044e\u0449\u0438\u0445\u0441\u044f \u0432 \u0433\u043e\u043b\u043e\u0441\u043e\u0432\u0430\u043d\u0438         - 'distance' : \u0432\u0435\u0441\u0430 \u043e\u0431\u0440\u0430\u0442\u043d\u043e \u043f\u0440\u043e\u043f\u043e\u0440\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044e \u0434 \u043e \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u0446\u0438\u0440\u0443\u0435\u043c\u043e\u0433\u043e \u043e\u0431\u044a\u0435\u043a\u0442\u0430         -  \u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442 \u043d\u0430 \u0432\u0445\u043e\u0434 \u043c\u0430\u0441\u0441\u0438\u0432 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043c\u0430\u0441\u0441\u0438\u0432 \u0432\u0435\u0441\u043e\u0432     leaf_size: int, optional         \u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0439 \u0440\u0430\u0437\u043c\u0435\u0440 \u043b\u0438\u0441\u0442\u0430 \u0434\u0435\u0440\u0435\u0432\u0430     '''     class Node(object):                 def __init__(self, pivot = None, points = [], radius = None): #\u0418\u043d\u0434\u0435\u043a\u0441 \u043a\u043e\u0440\u043d\u044f - 1             self.pivot = pivot #\u0418\u043d\u0434\u0435\u043a\u0441 \u043b\u0435\u0432\u043e\u0439 \u0432\u0435\u0440\u0449\u0438\u043d\u044b - 2*v             self.radius = radius #\u0418\u043d\u0434\u0435\u043a\u0441 \u043f\u0440\u0430\u0432\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b - 2*v + 1             self.points = points         def __str__(self):             self.stringList = ''.join(str(symbol) for symbol in self.points)             return(\"pivot = \" + str(self.pivot) + \" radius = \" + str(self.radius) + \" points = \"                  + str(self.stringList))              class Point(object):             def __init__(self, point, index):                 self.point = point                 self.index = index             def __str__(self):                 return(\"Vector \" + str(self.point) + \" with index \" + str(self.index))      def __init__(self, n_neighbors=1 leaf_size=30):         if(n_neighbors &lt;= 0):             print(\"\u041e\u0448\u0438\u0431\u043a\u0430! \u0421\u043e\u0441\u0435\u0434\u0435\u0439 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c 1\")             return         self.n_neighbors = n_neighbors         self.leaf_size = leaf_size         self.nodes = {}         self.kNSet = set()         self.points = []         self.classes = []         self.pointsOriginal = []      def GetnpArrayOfPoints(self, xStruct):         x = []         for i in range(len(xStruct)):             x.append(xStruct[i].point)         return(np.array(x))          def Distance(self, a, b):         if(len(a) != len(b)):             print(\"\u0420\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u043d\u0435 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0435!\")             return(\"Error\")         return np.linalg.norm(a-b)      def GetMaxDistance(self, point, points):         points = self.GetnpArrayOfPoints(points)         point = point.point         #print(points)          max = 0         for i in range(len(points)):             currentDist = self.Distance(point, points[i])             if(currentDist > max):                 max = currentDist         return(max)      def GetMaxSpreadDimension(self, x): #\u041d\u0443\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0442\u044c \u043f\u043e\u0434\u043e\u0442\u0440\u0435\u0437\u043e\u043a array[a:b]         x = self.GetnpArrayOfPoints(x)                difference = []         for i in range(x.shape[1]):             maximum = x[0][i]             minimum = x[0][i]             for j in range(x.shape[0]):                 maximum = max(maximum, x[j][i])                 minimum = min(minimum, x[j][i])             difference.append((maximum - minimum, i))         return(max(difference)[1])      def SortingByDimension(self, x, startPoint, endPoint, dimension): #\u041d\u0443\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0442\u044c \u043d\u0430\u0447\u0430\u043b\u043e \u0438          left = x[:startPoint]                                           rigth = x[endPoint:]         x = np.array(sorted(x[startPoint:endPoint], key = lambda Point: Point.point[dimension]))         x = np.concatenate((left, x, rigth), 0)         return(x)      def GetCentroidIndex(self, x, dimension): #\u041d\u0443\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0442\u044c \u043f\u043e\u0434\u043e\u0442\u0440\u0435\u0437\u043e\u043a array[a:b]         x = self.GetnpArrayOfPoints(x)         if(x.shape[0] == 0):             print(\"\u041e\u0448\u0438\u0431\u043a\u0430! \u041f\u0435\u0440\u0435\u0434\u0430\u043d \u043d\u0443\u043b\u0435\u0432\u043e\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0432 \u043f\u043e\u0438\u0441\u043a \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430\")         sum = 0         for i in range(x.shape[0]): #\u0420\u0430\u0437\u043c\u0435\u0440 x \u043d\u0435 \u043d\u0443\u043b\u0435\u0432\u043e\u0439             sum = sum + x[i][dimension]         sum = sum \/ x.shape[0]         minimum = abs(sum - x[0][dimension])         index = 0         for i in range(x.shape[0]):             if(abs(x[i][dimension] - sum) &lt; minimum):                 minimum = abs(x[i][dimension] - sum)                 index = i         return(index)      def ConstructTree(self, leafSize, vertexIndex, startPoint, endPoint):         if(endPoint - startPoint &lt;= 0):              return #endPoint \u043d\u0435 \u0432\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u043e\u0442\u0440\u0435\u0437\u043e\u043a [ )                   dimension = self.GetMaxSpreadDimension(self.points[startPoint:endPoint])         self.points = self.SortingByDimension(self.points, startPoint, endPoint, dimension)         centroidIndex = self.GetCentroidIndex(self.points[startPoint:endPoint], dimension) + startPoint           radius = self.GetMaxDistance(self.points[centroidIndex], self.points[startPoint:endPoint])         self.nodes[vertexIndex] = self.Node(self.points[centroidIndex], [], radius)         if(endPoint - startPoint &lt;= leafSize):             for i in range(startPoint, endPoint):                 self.nodes[vertexIndex].points.append(self.points[i])             return         else:             self.nodes[vertexIndex].points.append(self.points[centroidIndex])         self.ConstructTree(leafSize, vertexIndex * 2, startPoint, centroidIndex)         self.ConstructTree(leafSize, vertexIndex * 2 + 1, centroidIndex + 1, endPoint)      def searchBallSubtree(self, vertexIndex, newPoint, kN):         if(len(self.nodes[vertexIndex].points) > 1):             for point in self.nodes[vertexIndex].points:                 distance = self.Distance(newPoint, point.point)                 if(len(self.kNSet) >= kN and max(self.kNSet)[0] > distance):                     self.kNSet.remove(max(self.kNSet))                 if(len(self.kNSet) &lt; kN):                     self.kNSet.add((distance, point.index))             return         leftChild = vertexIndex * 2         rightChild = vertexIndex * 2 + 1         distance = self.Distance(newPoint, self.nodes[vertexIndex].pivot.point)          if(len(self.kNSet) >= kN and max(self.kNSet)[0] > distance):             self.kNSet.remove(max(self.kNSet))         if(len(self.kNSet) &lt; kN):             self.kNSet.add((distance, self.nodes[vertexIndex].pivot.index))                  if(len(self.nodes[leftChild].points) != 0):             distance = self.Distance(newPoint, self.nodes[leftChild].pivot.point)             if(len(self.kNSet) &lt; kN or max(self.kNSet)[0] > distance - self.nodes[leftChild].radius):                 self.searchBallSubtree(leftChild, newPoint, kN)          if(len(self.nodes[rightChild].points) != 0):             distance = self.Distance(newPoint, self.nodes[rightChild].pivot.point)             if(len(self.kNSet) &lt; kN or max(self.kNSet)[0] > distance - self.nodes[rightChild].radius):                 self.searchBallSubtree(rightChild, newPoint, kN)                    def fit(self, x, y):         if (len(x) != len(y)):             print(\"\u041e\u0448\u0438\u0431\u043a\u0430 - \u043d\u0435 \u0443 \u0432\u0441\u0435\u0445 \u0442\u043e\u0447\u0435\u043a \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u044b \u043a\u043b\u0430\u0441\u0441\u044b\")             return(\"fit Error\")         self.points = []         self.classes = []         self.pointsOriginal = x         for i in range(len(x)):             self.points.append(self.Point(x[i], i))         self.classes = y          self.ConstructTree(self.leaf_size, 1, 0, len(self.points))         return self          def predict(self, x):         predictions = []         for i in range(len(x)):             self.kNSet.clear()             self.searchBallSubtree(1, x[i], self.n_neighbors)             results = []             for index in self.kNSet: #kNSet \u0445\u0440\u0430\u043d\u0438\u0442 \u043f\u0430\u0440\u0443 (\u0434\u0438\u0441\u0442\u0430\u043d\u0446\u0438\u044f, \u0438\u043d\u0434\u0435\u043a\u0441)                 results.append(self.classes[index[1]])             resultClass = Counter(results).most_common()[0][0]             predictions.append(resultClass)         return np.array(predictions)              def predict_proba(self, X):             classesCount = np.unique(self.classes)         results = []         for point in X:             neighborsClasses = self.get_kneighbors_classes(point)             result = []             for clas in classesCount:                 count = 0                 for neighborClass in neighborsClasses:                     if(clas == neighborClass):                         count += 1                 result.append(count\/self.n_neighbors * 100)             results.append(result)         return(np.array(results))        def get_kneighbors_classes(self, x):         self.kNSet.clear()         self.searchBallSubtree(1, x, self.n_neighbors)         result = []         for index in self.kNSet:             result.append(self.classes[index[1]])          return np.array(result)              def kneighbors(self, x, n_neighbors):         results = []         for i in range(len(x)):             self.kNSet.clear()             self.searchBallSubtree(1, x[i], n_neighbors)             result = []              for index in self.kNSet:                 result.append(self.pointsOriginal[index[1]])             results.append(result)             return np.array(np.array(results))<\/code><\/pre>\n<\/div>\n<\/details>\n<h2>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u043a\u043e\u0434\u0430<\/h2>\n<p>\u041a\u043e\u0434 \u043c\u043e\u0436\u043d\u043e \u043b\u0435\u0433\u043a\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u043d\u0430 \u0438\u0441\u043a\u0443\u0441\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u0442\u043e\u0447\u0435\u043a. <\/p>\n<p>\u0421\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u043c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a \u043d\u0430 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438. \u041a\u043b\u0430\u0441\u0441 \u043a\u0430\u0436\u0434\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0430\u0441\u0441\u043e\u0446\u0438\u0438\u0440\u0443\u0435\u043c \u0441 \u0447\u0435\u0442\u0432\u0435\u0440\u0442\u044c\u044e \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0442\u043e\u0447\u043a\u0430 \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f.<\/p>\n<pre><code class=\"python\">import pandas as pd import csv import matplotlib.pyplot as plt  import random import math import pylab as pl import numpy as np import matplotlib.pyplot as plt import pdb from collections import Counter import matplotlib.colors as mcolors  def Gen2dDataset(self, points_num):     points = []     classes = []     for i in range(points_num):         tempX = np.random.uniform(-5,5)         tempY = np.random.uniform(-5,5)         points.append((tempX, tempY))         if tempX &lt;= 0 and tempY &lt;= 0:             classes.append(1)         elif tempX &lt;= 0 and tempY >= 0:             classes.append(2)         elif tempX >= 0 and tempY &lt;= 0:             classes.append(3)         elif tempX >= 0 and tempY >= 0:             classes.append(4)     return np.array(points), np.array(classes)<\/code><\/pre>\n<p>\u0418 \u0437\u0430\u043f\u0443\u0441\u0442\u0438\u043c \u043d\u0430\u0448 \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440 \u043d\u0430 \u044d\u0442\u043e\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435.<\/p>\n<pre><code class=\"python\">def Visual2dPointClassTest(model):     np.random.seed(42)     points, classes = Gen2dDataset(100)      fig, ax = plt.subplots()      ax.set_title('\u041e\u0431\u044a\u0435\u043a\u0442\u044b \u0438 \u043a\u043b\u0430\u0441\u0441\u044b')     ax.scatter(points[:,0], points[:,1], c = classes,              norm = plt.Normalize(0, 5),             s = 10)       model.fit(points, classes)     checkPoints = [[2, 1], [-2, -2], [-3, 4.5], [0, -1]]     print(\"\u0422\u043e\u0447\u043a\u0438 \u0434\u043b\u044f \u043a\u043b\u0430\u0441\u0441\u0444\u0438\u043a\u0430\u0446\u0438\u0438:\")     print(np.array(checkPoints))     checkClasses = self.model.predict(checkPoints)     print(\"\u0411\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0435 \u0441\u043e\u0441\u0435\u0434\u0438:\")     print(self.model.kneighbors(checkPoints, 3))     print(\"\u0418\u0445 \u043a\u043b\u0430\u0441\u0441\u044b:\")     print(checkClasses)     print(\"\u0412\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0438 (\u043f\u043e \u043a\u043b\u0430\u0441\u0441\u0430\u043c):\")     print(self.model.predict_proba(checkPoints))     print(\"\u0416\u0438\u0440\u043d\u044b\u0435 \u0442\u043e\u0447\u043a\u0438 - \u0442\u0435\u0441\u0442\u043e\u0432\u044b\u0435 \u0442\u043e\u0447\u043a\u0438 \u0434\u043b\u044f \u043a\u043b\u0430\u0441\u0441\u0444\u0438\u043a\u0430\u0446\u0438\u0438:\")     ax.scatter(np.array(checkPoints)[:,0], np.array(checkPoints)[:,1],              c = checkClasses, norm = plt.Normalize(0, 5),              s = 40)<\/code><\/pre>\n<p><strong>model<\/strong> &#8212; \u044d\u0442\u043e \u044d\u043a\u0437\u0435\u043c\u043f\u043b\u044f\u0440 \u043d\u0430\u0448\u0435\u0433\u043e \u043a\u043b\u0430\u0441\u0441\u0430 <strong>KnnBalltreeClassifier.<\/strong><\/p>\n<p>\u041c\u043e\u0436\u0435\u043c \u0442\u0430\u043a \u0436\u0435 \u043f\u0440\u043e\u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0440\u0430\u0431\u043e\u0442\u0443 \u043f\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044e ballTree (\u0441 \u0440\u0438\u0441\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0433\u0440\u0430\u0444\u0438\u043a\u043e\u0432).<\/p>\n<pre><code class=\"python\">def ConstructTreeTest(model):     np.random.seed(42)     points, classes = Gen2dDataset(100)     fig, ax = plt.subplots()     ax.axis('equal')     model.fit(points, classes)     print(\"\u0423\u0437\u043b\u044b(\u0432\u0435\u0440\u0448\u0438\u043d\u044b) \u0434\u0435\u0440\u0435\u0432\u0430:\")     for node in model.nodes.values():         print(node)     for node in model.nodes.values():         arrayOfPoints = []         for point in node.points:             arrayOfPoints.append(point)             ax.scatter(points[:,0], points[:,1], c = classes,              norm = plt.Normalize(0, 5),             s = 10)         ax.scatter(node.pivot.point[0], node.pivot.point[1], c = 'red',              norm = plt.Normalize(0, 5),             s = 25)         circle1 = plt.Circle(node.pivot.point, node.radius,                               color='r', fill = False)         ax.add_patch(circle1)<\/code><\/pre>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0442\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0441\u043e\u0432\u0435\u0442\u0443\u044e \u0432 jupiter notebook. \u0412\u0441\u0435\u043c \u0434\u043e\u0431\u0440\u0430 \u0438 \u0443\u0441\u043f\u0435\u0445\u043e\u0432 \u0432 \u0443\u0447\u0451\u0431\u0435.<\/p>\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\/575130\/\"> https:\/\/habr.com\/ru\/articles\/575130\/<\/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<h3>\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435<\/h3>\n<p>\u041a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044f \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 &#8212; \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0434\u043b\u044f \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u043c\u0435\u0442\u043e\u0434 \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438, \u0441\u0443\u0442\u044c \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u043e \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c\u0441\u044f \u0432 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442. <\/p>\n<p>\u041c\u0435\u0442\u043e\u0434 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442 \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439. \u041c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0440\u0430\u0437\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b. \u0421\u0430\u043c\u044b\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439, \u043d\u043e \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u043d\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c &#8212; \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u0432\u0441\u0435\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445. \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u0442\u0430\u043a \u0436\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u043f\u043e\u0438\u0441\u043a\u0430, \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u044b\u0435 KDtree \u0438 BallTree. <\/p>\n<p>\u041f\u0435\u0440\u0435\u0434\u043e \u043c\u043d\u043e\u0439 \u0441\u0442\u043e\u044f\u043b\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440 \u0441 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c \u043f\u043e\u0438\u0441\u043a\u0430 BallTree, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u0439 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441, \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a\u043e\u0439 \u0436\u0435, \u043a\u0430\u043a \u0432 <a href=\"https:\/\/scikit-learn.org\/stable\/modules\/generated\/sklearn.neighbors.BallTree.html\" rel=\"noopener noreferrer nofollow\">sklearn<\/a>). \u0412 \u0440\u0443\u043d\u0435\u0442\u0435 \u044f \u043d\u0435 \u043d\u0430\u0448\u0451\u043b \u0438\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u044e \u0438\u043b\u0438 \u0441\u0442\u0430\u0442\u044c\u044e, \u0441\u0438\u043b\u044c\u043d\u043e \u043f\u043e\u043c\u043e\u0433\u0430\u044e\u0449\u0438\u0435 \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u043a\u043e\u0434. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0440\u0435\u0448\u0438\u043b\u0441\u044f \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u043f\u043e\u0441\u0442 \u0437\u0434\u0435\u0441\u044c. \u0417\u0430\u0440\u0430\u043d\u0435\u0435 \u0441\u043f\u0430\u0441\u0438\u0431\u043e \u0437\u0430 \u043a\u0440\u0438\u0442\u0438\u043a\u0443, \u043d\u0430\u0432\u0435\u0440\u043d\u044f\u043a\u0430 \u0432 \u043a\u043e\u0434\u0435 \u0431\u0443\u0434\u0443\u0442 \u043c\u043e\u043c\u0435\u043d\u0442\u044b, \u0442\u0440\u0435\u0431\u0443\u044e\u0449\u0438\u0435 \u0441\u0435\u0440\u044c\u0451\u0437\u043d\u043e\u0439 \u043f\u0435\u0440\u0435\u0440\u0430\u0431\u043e\u0442\u043a\u0438. \u041d\u043e \u0432 \u043e\u0431\u0449\u0435\u043c \u0438 \u0446\u0435\u043b\u043e\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0440\u0430\u0431\u043e\u0447\u0435\u0435.<\/p>\n<p>\u0414\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043d\u044f\u0442\u044c \u0441\u0442\u0430\u0442\u044c\u044e &#8212; \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0437\u043d\u0430\u0442\u044c \u043e\u0441\u043d\u043e\u0432\u044b Python \u0438 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 numpy.<\/p>\n<hr\/>\n<h2>\u0422\u0435\u043e\u0440\u0438\u044f<\/h2>\n<p><strong><em>\u0414\u0430\u043d\u043e:<\/em><\/strong><\/p>\n<p><strong>1)<\/strong> \u041f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0441 \u0442\u043e\u0447\u043a\u0430\u043c\u0438 (\u0442\u043e\u0447\u043a\u0430 &#8212; \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u0430) \u0438 \u043c\u0435\u0442\u0440\u0438\u043a\u0430, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0449\u0430\u044f \u043a\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u0442\u043e\u0447\u043a\u0430\u043c\u0438.<\/p>\n<p><strong>2)<\/strong> \u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043a\u043b\u0430\u0441\u0441\u043e\u0432. \u041a\u043b\u0430\u0441\u0441\u044b &#8212; \u043d\u0435 \u043f\u0435\u0440\u0435\u0441\u0435\u043a\u0430\u044e\u0449\u0438\u0435\u0441\u044f \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0435 \u0442\u043e\u0447\u043a\u0438. \u0421 \u043a\u0430\u0436\u0434\u043e\u0439 \u0442\u043e\u0447\u043a\u043e\u0439 \u0430\u0441\u0441\u043e\u0446\u0438\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043e\u0434\u0438\u043d \u043a\u043b\u0430\u0441\u0441. \u0413\u043e\u0432\u043e\u0440\u044f\u0442, \u0447\u0442\u043e \u0442\u043e\u0447\u043a\u0430 A \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0438\u0442 \u043a\u043b\u0430\u0441\u0441\u0443 1, \u0430 \u0442\u043e\u0447\u043a\u0430 B \u043a \u043a\u043b\u0430\u0441\u0441\u0443 &#171;2&#187;, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440.<\/p>\n<p><strong>3)<\/strong> \u0422\u043e\u0447\u043a\u0430\/\u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0442\u043e\u0447\u0435\u043a \u043a\u043b\u0430\u0441\u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0439\/\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u0435\u043d.<\/p>\n<p><strong><em>\u0417\u0430\u0434\u0430\u0447\u0430:<\/em><\/strong><\/p>\n<p>\u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u0442\u044c, \u043a \u043a\u0430\u043a\u043e\u043c\u0443 \u043a\u043b\u0430\u0441\u0441\u0443 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0438\u0442 \u0434\u0430\u043d\u043d\u0430\u044f \u0442\u043e\u0447\u043a\u0430. <\/p>\n<p>\u0418\u0434\u0435\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0442\u043e\u0447\u043a\u0438, \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0430\u0449\u0438\u0435 \u043e\u0434\u043d\u043e\u043c\u0443 \u043a\u043b\u0430\u0441\u0441\u0443, \u0447\u0430\u0441\u0442\u043e \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u044e\u0442\u0441\u044f \u0440\u044f\u0434\u043e\u043c \u0434\u0440\u0443\u0433 \u0441 \u0434\u0440\u0443\u0433\u043e\u043c. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043a\u043b\u0430\u0441\u0441 \u0442\u043e\u0447\u043a\u0438 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0432 \u043d\u0430 \u0435\u0451 \u0441\u043e\u0441\u0435\u0434\u0435\u0439. \u0427\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043a\u043b\u0430\u0441\u0441\u0430 n \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u044e\u0442\u0441\u044f \u0431\u043b\u0438\u0437\u043a\u043e \u043a \u0442\u043e\u0447\u043a\u0435 &#8212; \u0442\u0435\u043c \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u0435\u0435 \u044d\u0442\u0430 \u0442\u043e\u0447\u043a\u0430 \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0438\u0442 \u043a \u043a\u043b\u0430\u0441\u0441\u0443 n. <\/p>\n<p>\u041f\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u043d\u0430\u0439\u0442\u0438 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0441\u0440\u0435\u0434\u0438 \u0432\u0441\u0435\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0442\u043e\u0447\u0435\u043a. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0434\u043e \u043a\u0430\u0436\u0434\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0432 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u0438 \u0437\u0430\u043f\u043e\u043c\u0438\u043d\u0430\u0442\u044c \u043a\u043b\u0430\u0441\u0441\u044b \u0441\u0430\u043c\u044b\u0445 \u0431\u043b\u0438\u0437\u043a\u0438\u0445 \u0442\u043e\u0447\u0435\u043a. \u0414\u0430\u043d\u043d\u044b\u0439 \u043f\u043e\u0434\u0445\u043e\u0434 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043c\u043d\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438, \u0432\u0435\u0434\u044c \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u043d\u0443\u0436\u043d\u043e \u043a\u0430\u0436\u0434\u0443\u044e \u0442\u043e\u0447\u043a\u0443. \u041d\u043e \u0435\u0441\u043b\u0438 \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a, \u0442\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u043a\u0430\u0436\u0434\u0443\u044e \u0442\u043e\u0447\u043a\u0443 \u0432\u043e \u0432\u0441\u0435\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u043d\u0435 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f, \u0442\u0430\u043a \u043a\u0430\u043a \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430 \u043f\u043e\u0434\u0441\u043a\u0430\u0436\u0435\u0442, \u043a\u0430\u043a\u0438\u0435 \u0442\u043e\u0447\u043a\u0438 \u0442\u043e\u0447\u043d\u043e \u043d\u0435 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u043c\u0438 \u0441\u043e\u0441\u0435\u0434\u044f\u043c\u0438.<\/p>\n<h3>BallTree<\/h3>\n<p>\u0412 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u043c \u0438\u0442\u043e\u0433\u0435 \u0443 \u043d\u0430\u0441 \u0434\u043e\u043b\u0436\u043d\u0430 \u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430, \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0430\u044f \u0438\u0437 \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0445 \u0448\u0430\u0440\u043e\u0432. \u041a\u0430\u0436\u0434\u0430\u044f \u0442\u043e\u0447\u043a\u0430 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043a \u043e\u0434\u043d\u043e\u043c\u0443 \u0448\u0430\u0440\u0443. \u0412\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u0440\u0430\u0437\u0431\u0438\u0442\u044b \u043d\u0430 \u043d\u0435 \u043f\u0435\u0440\u0435\u0441\u0435\u043a\u0430\u044e\u0449\u0438\u0435\u0441\u044f \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b-\u0448\u0430\u0440\u044b. \u042d\u0442\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u043e\u0431\u0440\u0430\u0437\u0443\u0435\u0442 <strong>\u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435<\/strong> <strong>\u0434\u0435\u0440\u0435\u0432\u043e<\/strong>, \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u0445 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0431\u0443\u0434\u0443\u0442 \u043b\u0435\u0436\u0430\u0442\u044c <strong>\u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u044b<\/strong>, \u0430 \u043a\u0440\u043e\u043d\u043e\u0439 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0431\u0443\u0434\u0443\u0442 <strong>\u043b\u0438\u0441\u0442\u044c\u044f<\/strong>, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0435 \u0442\u043e\u0447\u043a\u0438 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u0440\u0430\u0437\u043c\u0435\u0440 \u043b\u0438\u0441\u0442\u044c\u0435\u0432 \u0440\u0435\u0433\u0443\u043b\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u043c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u043c <strong>LeafSize<\/strong>.<\/p>\n<details class=\"spoiler\">\n<summary>\u0422\u043e\u0447\u043a\u0438<\/summary>\n<div class=\"spoiler__content\">\n<figure class=\"\"><figcaption>\u041d\u0430\u0448\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a. \u0422\u043e\u0447\u043a\u0438 \u0440\u0430\u0437\u0434\u0435\u043b\u0435\u043d\u044b \u043d\u0430 3 \u043a\u043b\u0430\u0441\u0441\u0430 \u043f\u043e \u0446\u0432\u0435\u0442\u0430\u043c.<\/figcaption><\/figure>\n<\/div>\n<\/details>\n<p>\u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0438\u0440\u0443\u0435\u043c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:<\/p>\n<p><strong>1) <\/strong>\u041e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u043f\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438 \u0441 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0438\u043c \u0440\u0430\u0437\u0431\u0440\u043e\u0441\u043e\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0430\u0439\u0442\u0438 \u0435\u0451. \u0414\u0430\u043b\u044c\u0448\u0435 \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0441 \u044d\u0442\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c\u044e.<\/p>\n<p><strong>2)<\/strong> \u0412\u044b\u0431\u0435\u0440\u0435\u043c \u0442\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u0443\u044e \u0442\u043e\u0447\u043a\u0443 &#8212; <strong>\u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434<\/strong>. \u0426\u0435\u043d\u0442\u0440\u043e\u0438\u0434 &#8212; \u044d\u0442\u043e \u0442\u043e\u0447\u043a\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043f\u043e \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0442\u043e\u0447\u0435\u043a, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u0438\u0442\u044c \u0432 \u043e\u0434\u0438\u043d \u043a\u043b\u0430\u0441\u0442\u0435\u0440. \u0414\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043d\u0430\u0439\u0442\u0438 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u0442\u043e\u0447\u043a\u0443, \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u0430 \u043c\u0435\u043d\u044c\u0448\u0435 \u0432\u0441\u0435\u0433\u043e \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u0441\u0440\u0435\u0434\u043d\u0435\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442 \u043f\u043e \u0432\u0441\u0435\u043c \u0442\u043e\u0447\u043a\u0430\u043c \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0432\u0434\u043e\u043b\u044c \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u043e\u0439 \u0432 \u043f\u0443\u043d\u043a\u0442\u0435 1) \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438.<\/p>\n<p><strong>3) <\/strong>\u041d\u0430\u0439\u0434\u0451\u043c \u0440\u0430\u0434\u0438\u0443\u0441 \u0434\u043e \u0441\u0430\u043c\u043e\u0439 \u0434\u0430\u043b\u044c\u043d\u0435\u0439 \u043e\u0442 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u0442\u043e\u0447\u043a\u0438. \u042d\u0442\u043e \u0440\u0430\u0434\u0438\u0443\u0441 \u0448\u0430\u0440\u0430-\u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u043e\u043a\u0440\u043e\u0435\u0442 \u0432\u0441\u0451 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a (\u043f\u0440\u0438 \u043f\u0435\u0440\u0432\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u0443\u043d\u043a\u0442\u0430).<\/p>\n<details class=\"spoiler\">\n<summary>\u041f\u0435\u0440\u0432\u044b\u0439 \u0448\u0430\u0440<\/summary>\n<div class=\"spoiler__content\">\n<figure class=\"\"><figcaption>\u0428\u0430\u0440, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0430\u0441\u0441\u043e\u0446\u0438\u0438\u0440\u043e\u0432\u0430\u043d \u0441 \u0432\u0435\u0440\u0448\u0438\u043d\u043e\u0439 \u0437\u0430\u0445\u0432\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430.<\/figcaption><\/figure>\n<figure class=\"\"><figcaption>\u0413\u0440\u0430\u0444 ballTree \u043f\u043e\u043a\u0430 \u0447\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a. \u0415\u0441\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u043e\u0440\u0435\u043d\u044c.<\/figcaption><\/figure>\n<\/div>\n<\/details>\n<p><strong>4) <\/strong>\u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0432\u0441\u0435\u0445 \u0442\u043e\u0447\u0435\u043a \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u043b\u043e\u0441\u044c \u043d\u0430 \u0434\u0432\u0435 \u0447\u0430\u0441\u0442\u0438 &#8212; \u0434\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u0438 \u043f\u043e\u0441\u043b\u0435 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430. \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c\u0441\u044f \u043a \u043f\u0443\u043d\u043a\u0442\u0443 \u0434\u0432\u0430, \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044f \u0435\u0433\u043e \u043d\u0430 \u043f\u0435\u0440\u0432\u043e\u0439, \u0430 \u0434\u0430\u043b\u0435\u0435 \u0432\u0442\u043e\u0440\u043e\u0439 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430. \u0414\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0435\u0441\u044f \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c <strong>LeafSize<\/strong>.<\/p>\n<details class=\"spoiler\">\n<summary>\u0412\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0435 \u0448\u0430\u0440\u044b<\/summary>\n<div class=\"spoiler__content\">\n<figure class=\"\"><figcaption>\u0428\u0430\u0440\u044b, \u0441\u043e\u0437\u0434\u0430\u043d\u043d\u044b\u0435 \u043d\u0430 \u0432\u0442\u043e\u0440\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438, \u043f\u043e\u043c\u0435\u0447\u0435\u043d\u044b \u0444\u0438\u043e\u043b\u0435\u0442\u043e\u0432\u044b\u043c \u0446\u0432\u0435\u0442\u043e\u043c. \u042d\u0442\u043e \u043b\u0435\u0432\u044b\u0439 \u0438 \u043f\u0440\u0430\u0432\u044b\u0439 \u043f\u043e\u0442\u043e\u043c\u043a\u0438 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043b\u0438\u0441\u0442\u044c\u044f\u043c\u0438, \u0442\u0430\u043a \u043a\u0430\u043a \u043e\u0445\u0432\u0430\u0442\u044b\u0432\u0430\u044e\u0442 \u0432\u0441\u0435 \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0435\u0441\u044f \u0442\u043e\u0447\u043a\u0438 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430.<\/figcaption><\/figure>\n<figure class=\"\"><figcaption>\u0423 \u0433\u0440\u0430\u0444\u0430 ballTree \u043f\u043e\u044f\u0432\u0438\u043b\u0438\u0441\u044c \u0432\u0435\u0440\u0448\u0438\u043d\u044b-\u043b\u0438\u0441\u0442\u044c\u044f. \u0415\u0441\u043b\u0438 \u0431\u044b \u0442\u043e\u0447\u0435\u043a \u0431\u044b\u043b\u043e \u0431\u044b \u0431\u043e\u043b\u044c\u0448\u0435, \u0442\u043e \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0435 \u0433\u0440\u0430\u0444\u0430 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u043b\u043e \u0431\u044b \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u043d\u0435 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043b\u0438\u0441\u044c \u0431\u044b \u043f\u043e \u043b\u0438\u0441\u0442\u044c\u044f\u043c.<\/figcaption><\/figure>\n<\/div>\n<\/details>\n<p><strong>5) <\/strong>\u0415\u0441\u043b\u0438 \u043e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c<strong> LeafSize <\/strong>(\u0440\u0430\u0437\u043c\u0435\u0440 \u043b\u0438\u0441\u0442\u0430)<strong> <\/strong>\u0442\u043e\u0447\u0435\u043a, \u0442\u043e \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u0438\u0445 \u0432 \u043b\u0438\u0441\u0442 \u0438 \u043f\u0440\u0438\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u043a \u0448\u0430\u0440\u0443, \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u043c\u0443 \u044d\u0442\u0438 \u0442\u043e\u0447\u043a\u0438.<\/p>\n<p><strong>6) <\/strong>\u0417\u0430\u0432\u0435\u0440\u0448\u0430\u0435\u043c \u0440\u0430\u0431\u043e\u0442\u0443 \u0442\u043e\u0433\u0434\u0430, \u043a\u043e\u0433\u0434\u0430 \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u044b \u043f\u043e \u043b\u0438\u0441\u0442\u044c\u044f\u043c.<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c, \u043f\u043e\u0441\u043b\u0435 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0434\u0435\u0440\u0435\u0432\u0430, \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u043f\u043e\u0438\u0441\u043a\u0430 k \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 <strong>\u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0439 \u0442\u043e\u0447\u043a\u0438<\/strong> \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u0441\u044f. <strong>\u041f\u043e\u0447\u0435\u043c\u0443?<\/strong><\/p>\n<p>\u0412 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u043f\u043e\u0438\u0441\u043a\u0430 \u043d\u0430\u043c \u0431\u0443\u0434\u0435\u0442 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0441\u043f\u0443\u0441\u043a\u0430\u0442\u044c\u0441\u044f \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443 \u0441\u0432\u0435\u0440\u0445\u0443 \u0432\u043d\u0438\u0437 \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u043e\u0442 \u043a\u043e\u0440\u043d\u044f. \u041d\u0430 \u043a\u0430\u0436\u0434\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 &#8212; \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u0442\u043e\u0447\u043a\u0438, \u043d\u0430\u0445\u043e\u0434\u044f\u0449\u0438\u0435\u0441\u044f \u043f\u043e \u043f\u0440\u0430\u0432\u0443\u044e \u0438\u043b\u0438 \u043b\u0435\u0432\u0443\u044e \u0441\u0442\u043e\u0440\u043e\u043d\u0443, \u0438\u043b\u0438 \u043d\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c? \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442\u044b \u0432 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0435 \u0441\u043e\u0441\u0435\u0434\u0438 \u0431\u0443\u0434\u0443\u0442 \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c\u0441\u044f \u0432 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c k (\u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043e\u0441\u0435\u0434\u0435\u0439, \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0430\u0439\u0442\u0438). \u0415\u0441\u043b\u0438 \u0431\u0443\u0434\u0435\u0442 \u043d\u0430\u0439\u0434\u0435\u043d\u0430 \u0442\u043e\u0447\u043a\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0440\u0430\u0441\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0430 \u0431\u043b\u0438\u0436\u0435, \u0447\u0435\u043c \u0441\u0430\u043c\u044b\u0439 \u0434\u0430\u043b\u044c\u043d\u0438\u0439 \u0441\u043e\u0441\u0435\u0434 &#8212; \u0442\u043e \u0435\u0433\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u043d\u0430 \u044d\u0442\u0443 \u0442\u043e\u0447\u043a\u0443. \u0415\u0441\u043b\u0438 \u0435\u0449\u0451 \u043d\u0435 \u043d\u0430\u0431\u0440\u0430\u043d\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439, \u0442\u043e \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043b\u044e\u0431\u0430\u044f \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u0430\u044f \u0442\u043e\u0447\u043a\u0430.<\/p>\n<p>\u041f\u0440\u0438 \u0434\u043e\u0441\u0442\u0438\u0436\u0435\u043d\u0438\u0438 \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0432\u044b\u0431\u0435\u0440\u0435\u043c \u0441\u0440\u0435\u0434\u0438 \u0432\u0441\u0435\u0445 \u0442\u0435\u043a\u0443\u0449\u0438\u0445 \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u044b\u0445 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0442\u043e\u0447\u043a\u0443 \u0441 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435\u043c \u043e\u0442 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0439. \u0412\u044b\u0431\u0435\u0440\u0435\u043c \u043e\u0434\u0438\u043d \u0438\u0437 \u0434\u0432\u0443\u0445 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432, \u043b\u0435\u0436\u0430\u0449\u0438\u0445 \u0432 \u043d\u0438\u0436\u043d\u0438\u0445 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u0445. \u0415\u0441\u043b\u0438 \u044d\u0442\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043e\u0442 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0434\u043e \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u0448\u0430\u0440\u0430 \u044d\u0442\u043e\u0433\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 &#8212; \u0442\u043e \u043d\u0430\u043c \u043d\u0435\u0442 \u043d\u0438\u043a\u0430\u043a\u043e\u0439 \u043d\u0430\u0434\u043e\u0431\u043d\u043e\u0441\u0442\u0438 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u0442\u043e\u0447\u043a\u0438, \u0432\u0445\u043e\u0434\u044f\u0449\u0438\u0435 \u0432 \u044d\u0442\u043e\u0442 \u0448\u0430\u0440 \u044d\u0442\u043e\u0433\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430. \u0412 \u043b\u044e\u0431\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0442\u0430\u043c \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0441\u0435\u0434\u0435\u0439, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0431\u0443\u0434\u0443\u0442 \u043b\u0435\u0436\u0430\u0442\u044c \u0431\u043b\u0438\u0436\u0435, \u0447\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0441\u0430\u043c\u044b\u0439 \u0434\u0430\u043b\u0451\u043a\u0438\u0439 \u0441\u043e\u0441\u0435\u0434, \u0432\u044b\u0433\u043e\u0434\u043d\u0435\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u0442\u043e\u0447\u043a\u0438, \u043d\u0430\u0445\u043e\u0434\u044f\u0449\u0438\u0435\u0441\u044f \u0432 \u0434\u0440\u0443\u0433\u043e\u043c \u0448\u0430\u0440\u0435. <\/p>\n<p>\u042d\u0442\u043e \u0438 \u0435\u0441\u0442\u044c \u043c\u043e\u043c\u0435\u043d\u0442 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438. \u0417\u0430\u0440\u0430\u043d\u0435\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a \u0434\u0430\u0451\u0442 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0437\u043d\u0430\u0442\u044c, \u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0434\u0430\u043b\u0435\u043a\u043e \u0431\u0443\u0434\u0443\u0442 \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u0442\u044c\u0441\u044f \u0412\u0421\u0415 \u0442\u043e\u0447\u043a\u0438 \u0432 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0435 (\u0448\u0430\u0440\u0435) \u0431\u0435\u0437 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0434\u043e \u043a\u0430\u0436\u0434\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0438\u0437 \u044d\u0442\u043e\u0433\u043e \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430.<\/p>\n<details class=\"spoiler\">\n<summary>\u041c\u043e\u043c\u0435\u043d\u0442 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438<\/summary>\n<div class=\"spoiler__content\">\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>\u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0447\u0442\u043e \u043d\u0430\u043c \u0434\u0430\u043b\u0438 \u043e\u0440\u0430\u043d\u0436\u0435\u0432\u0443\u044e \u0442\u043e\u0447\u043a\u0443 \u0434\u043b\u044f \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0447\u0442\u043e \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u043e\u0434\u043d\u043e\u0433\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u0441\u043e\u0441\u0435\u0434\u0430, \u0438 \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442\u043e\u043c \u0432 \u043d\u0435\u0433\u043e \u0431\u044b\u043b\u0430 \u043e\u0434\u043d\u0430 \u0438\u0437 \u0441\u0438\u043d\u0438\u0445 \u0442\u043e\u0447\u0435\u043a. \u0414\u0430\u043b\u044c\u0448\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0432\u044b\u0431\u043e\u0440 &#8212; \u043a\u0430\u043a\u0438\u0435 \u0442\u043e\u0447\u043a\u0438 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c? \u041c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c, \u0435\u0441\u0442\u044c \u0442\u043e\u0447\u043a\u0438 \u043f\u043e\u0431\u043b\u0438\u0436\u0435? \u0422\u0430\u043a \u0432\u043e\u0442 \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u0442\u043e\u0447\u043a\u0438 \u0438\u0437 \u0448\u0430\u0440\u0430 3 \u043d\u0435\u0442 \u043d\u0438\u043a\u0430\u043a\u043e\u0433\u043e \u0441\u043c\u044b\u0441\u043b\u0430, \u0442\u0430\u043a \u043a\u0430\u043a \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043e\u0442 \u043d\u0430\u0448\u0435\u0439 \u0442\u043e\u0447\u043a\u0438 \u0434\u043e \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u0448\u0430\u0440\u0430 \u0434\u043b\u0438\u043d\u0435\u0435, \u0447\u0435\u043c \u0434\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u0434\u0430\u043b\u0451\u043a\u043e\u0433\u043e \u043d\u0430 \u0434\u0430\u043d\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u0441\u043e\u0441\u0435\u0434\u0430.<\/p>\n<\/div>\n<\/details>\n<hr\/>\n<h2>\u041f\u0440\u0430\u043a\u0442\u0438\u043a\u0430 &#8212; KnnBalltreeClassifier \u043d\u0430 Python<\/h2>\n<p>\u0413\u0440\u0430\u0444 \u0431\u0443\u0434\u0435\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 \u0432\u0438\u0434\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0442\u043e\u0447\u0435\u043a, \u043e\u043f\u0435\u0440\u0438\u0440\u0443\u044f \u0438\u0445 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0447\u0442\u043e \u0438\u043d\u0434\u0435\u043a\u0441 \u043b\u0435\u0432\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u0435\u043d 2 * v, \u0430 \u043f\u0440\u0430\u0432\u043e\u0439 2 * v + 1 (v &#8212; \u0438\u043d\u0434\u0435\u043a\u0441 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b). \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u0438\u043d\u0434\u0435\u043a\u0441 \u043a\u043e\u0440\u043d\u044f = 1. \u041d\u0430\u043c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u044f\u0442\u0441\u044f \u043a\u043b\u0430\u0441\u0441\u044b \u0434\u043b\u044f \u0432\u0435\u0440\u0448\u0438\u043d \u0433\u0440\u0430\u0444\u0430, \u043a\u043b\u0430\u0441\u0441 \u0434\u043b\u044f \u0442\u043e\u0447\u043a\u0438 \u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u0439. \u0422\u0430\u043a \u0436\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u043e\u0434\u043a\u043b\u044e\u0447\u0438\u0442\u044c numpy, collections, math \u0438 random (\u0434\u043b\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 \u0442\u043e\u0447\u0435\u043a).<\/p>\n<p>\u041d\u0430\u0439\u0434\u0435\u043d\u043d\u044b\u0445 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0431\u0443\u0434\u0435\u043c \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c \u0432 set. \u041f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 (set) \u043d\u0435 \u0434\u043e\u043f\u0443\u0441\u043a\u0430\u0442\u044c \u043a \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044e \u0434\u0443\u0431\u043b\u0438\u0440\u0443\u044e\u0449\u0438\u0435\u0441\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b (\u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0434\u043e \u0442\u043e\u0447\u0435\u043a \u043c\u043e\u0433\u0443\u0442 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0442\u044c\u0441\u044f).<\/p>\n<ul>\n<li>\n<p><strong><em>\u0423\u0437\u043b\u044b \u0433\u0440\u0430\u0444\u0430 BallTree<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">class Node(object):             def __init__(self, pivot = None, points = [], radius = None):        #\u0418\u043d\u0434\u0435\u043a\u0441 \u043a\u043e\u0440\u043d\u044f - 1         self.pivot = pivot #\u0418\u043d\u0434\u0435\u043a\u0441 \u043b\u0435\u0432\u043e\u0439 \u0432\u0435\u0440\u0449\u0438\u043d\u044b - 2*v         self.radius = radius #\u0418\u043d\u0434\u0435\u043a\u0441 \u043f\u0440\u0430\u0432\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b - 2*v + 1         self.points = points     def __str__(self):         self.stringList = ''.join(str(symbol) for symbol in self.points)         return(\"pivot = \" + str(self.pivot) + \" radius = \"          + str(self.radius) + \" points = \"          + str(self.stringList))<\/code><\/pre>\n<p><strong>pivot<\/strong> &#8212; \u0442\u043e\u0447\u043a\u0430 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434 \u0448\u0430\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0430\u0441\u0441\u043e\u0446\u0438\u0438\u0440\u043e\u0432\u0430\u043d \u0441 \u044d\u0442\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u043e\u0439 \u0433\u0440\u0430\u0444\u0430.<br \/><strong>radius<\/strong> &#8212; \u0434\u043b\u0438\u043d\u0430 \u0440\u0430\u0434\u0438\u0443\u0441\u0430 \u0448\u0430\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0430\u0441\u0441\u043e\u0446\u0438\u0438\u0440\u043e\u0432\u0430\u043d \u0441 \u044d\u0442\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u043e\u0439 \u0433\u0440\u0430\u0444\u0430.<br \/><strong>points<\/strong> &#8212; \u043c\u0430\u0441\u0441\u0438\u0432 \u0442\u043e\u0447\u0435\u043a, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043b\u0435\u0436\u0430\u0442 \u0432 \u044d\u0442\u043e\u043c \u0448\u0430\u0440\u0435. \u0412\u0430\u0436\u043d\u043e\u0435 \u043f\u0440\u0438\u043c\u0435\u0447\u0430\u043d\u0438\u0435! \u0422\u043e\u0447\u043a\u0438 \u0431\u0443\u0434\u0443\u0442 \u043b\u0435\u0436\u0430\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u043c \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u043e\u043c \u0448\u0430\u0440\u0435, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0438\u0445 \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u0435\u0442. \u0421 \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f \u0433\u0440\u0430\u0444\u0430 &#8212; \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u043b\u0438\u0441\u0442\u043e\u0432\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u0435 (\u043b\u0438\u0441\u0442\u0435).<br \/>\u0414\u0430\u043b\u044c\u0448\u0435 \u0438\u0434\u0451\u0442 \u043c\u0435\u0442\u043e\u0434 \u0434\u043b\u044f \u043a\u0440\u0430\u0441\u0438\u0432\u043e\u0439 \u043f\u0435\u0447\u0430\u0442\u0438 \u043a\u043b\u0430\u0441\u0441\u0430 \u0432 \u043a\u043e\u043d\u0441\u043e\u043b\u0438. \u0423\u0434\u043e\u0431\u043d\u043e \u0434\u043b\u044f \u043e\u0442\u043b\u0430\u0434\u043a\u0438 \u0438 \u043f\u0440\u043e\u0441\u043c\u043e\u0442\u0440\u0430 ballTree \u043d\u0430 \u0442\u0435\u043a\u0443\u0449\u0435\u043c \u044d\u0442\u0430\u043f\u0435 \u0440\u0430\u0431\u043e\u0442\u044b \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b.<\/p>\n<ul>\n<li>\n<p><strong><em>\u041e\u043f\u0438\u0448\u0435\u043c \u043a\u043b\u0430\u0441\u0441 \u0442\u043e\u0447\u043a\u0438<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">class Point(object):     def __init__(self, point, index):         self.point = point         self.index = index     def __str__(self):         return(\"Vector \" + str(self.point) + \" with index \" + str(self.index))<\/code><\/pre>\n<p><strong>point<\/strong> &#8212; \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b \u0442\u043e\u0447\u043a\u0438. \u0422\u043e \u0435\u0441\u0442\u044c \u043f\u043e \u0441\u0443\u0442\u0438 \u0441\u0430\u043c\u0430 \u0442\u043e\u0447\u043a\u0430 \u043a\u0430\u043a \u043d\u0430\u0431\u043e\u0440 \u0435\u0451 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442.<\/p>\n<p><strong>index<\/strong> &#8212; \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0439 \u0438\u043d\u0434\u0435\u043a\u0441 \u0442\u043e\u0447\u043a\u0438 \u0432\u043e \u0432\u0445\u043e\u0434\u043d\u043e\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 (\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u0442\u043e\u0447\u0435\u043a). \u041f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0443\u0437\u043d\u0430\u0442\u044c \u043a\u043b\u0430\u0441\u0441\u044b \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 (\u043a\u043b\u0430\u0441\u0441\u044b \u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f \u0432 \u0434\u0440\u0443\u0433\u043e\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 \u0438 \u0430\u0441\u0441\u043e\u0446\u0438\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u0441 \u0442\u043e\u0447\u043a\u0430\u043c\u0438 \u0447\u0435\u0440\u0435\u0437 \u0438\u043d\u0434\u0435\u043a\u0441\u044b).<\/p>\n<p>\u0418 \u0441\u043d\u043e\u0432\u0430 \u043c\u0435\u0442\u043e\u0434 \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u043d\u043e\u0433\u043e \u0432\u044b\u0432\u043e\u0434\u0430 \u0432 \u043a\u043e\u043d\u0441\u043e\u043b\u044c \u043f\u0440\u0438 \u043f\u0435\u0447\u0430\u0442\u0438.<\/p>\n<ul>\n<li>\n<p><strong><em>\u041a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0442\u043e\u0440<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">def __init__(self, n_neighbors=1, leaf_size=30):     if(n_neighbors &lt;= 0):         print(\"\u041e\u0448\u0438\u0431\u043a\u0430! \u0421\u043e\u0441\u0435\u0434\u0435\u0439 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c 1\")         return     self.n_neighbors = n_neighbors     self.leaf_size = leaf_size     self.nodes = {}     self.kNSet = set()     self.points = []     self.classes = []     self.pointsOriginal = []<\/code><\/pre>\n<p><strong>n_neighbors<\/strong> &#8212; \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439, \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043d\u0430\u0439\u0442\u0438 \u0434\u043b\u044f \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438 \u043d\u043e\u0432\u043e\u0439 \u0442\u043e\u0447\u043a\u0438.<br \/><strong>leaf_size<\/strong> &#8212; \u0440\u0430\u0437\u043c\u0435\u0440 \u043b\u0438\u0441\u0442\u0430, \u0442\u043e \u0435\u0441\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a \u0432 \u043b\u0438\u0441\u0442\u043e\u0432\u044b\u0445 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u0445. \u0427\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u0440\u0430\u0437\u043c\u0435\u0440 \u043b\u0438\u0441\u0442\u0430 &#8212; \u0442\u0435\u043c \u043c\u0435\u043d\u044c\u0448\u0435 \u043b\u0438\u0441\u0442\u043e\u0432\u044b\u0445 \u0432\u0435\u0440\u0448\u0438\u043d, \u0438 \u043d\u0430\u043e\u0431\u043e\u0440\u043e\u0442.<br \/><strong>nodes<\/strong> &#8212; \u0441\u043b\u043e\u0432\u0430\u0440\u044c \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0432\u0435\u0440\u0448\u0438\u043d<br \/><strong>kNSet<\/strong> &#8212; \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439. \u0412\u0430\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0435\u0433\u043e \u0438\u043c\u0435\u043d\u043d\u043e set, \u0447\u0442\u043e\u0431\u044b \u043d\u0435 \u0431\u044b\u043b\u043e \u043f\u043e\u0432\u0442\u043e\u0440\u0435\u043d\u0438\u0439 \u0441\u0440\u0435\u0434\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.<br \/><strong>points<\/strong> &#8212; \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0442\u043e\u0447\u0435\u043a, \u0431\u0443\u0434\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b.<br \/><strong>classes<\/strong> &#8212; \u043c\u0430\u0441\u0441\u0438\u0432 \u043a\u043b\u0430\u0441\u0441\u043e\u0432 (\u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 &#8212; \u043e\u0434\u0438\u043d \u043a\u043b\u0430\u0441\u0441)<br \/><strong>pointsOriginal<\/strong> &#8212; \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0442\u043e\u0447\u0435\u043a, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043c\u0435\u043d\u044f\u0442\u044c\u0441\u044f \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0440\u0430\u0431\u043e\u0442\u044b \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b (\u043f\u043e\u043a\u0430 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u0433\u0440\u0443\u0436\u0435\u043d\u043e \u043d\u043e\u0432\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a).<\/p>\n<ul>\n<li>\n<p><strong><em>\u0412\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438<\/em><\/strong><\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">def GetnpArrayOfPoints(self, xStruct):     x = []     for i in range(len(xStruct)):         x.append(xStruct[i].point)     return(np.array(x))        def Distance(self, a, b):     if(len(a) != len(b)):         print(\"\u0420\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u043d\u0435 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0435!\")         return(\"Error\")     return np.linalg.norm(a-b)             def GetMaxDistance(self, point, points):     points = self.GetnpArrayOfPoints(points)     point = point.point     #print(points) #\u0414\u043b\u044f \u043e\u0442\u043b\u0430\u0434\u043a\u0438     max = 0     for i in range(len(points)):         currentDist =<\/code><\/pre>\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-387819","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/387819","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=387819"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/387819\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=387819"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=387819"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=387819"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}