{"id":305198,"date":"2020-06-11T09:01:11","date_gmt":"2020-06-11T09:01:11","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=305198"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=305198","title":{"rendered":"\u0410\u0433\u043b\u043e\u043c\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u0430\u044f \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u044f: \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u0431\u044b\u0441\u0442\u0440\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0435, \u043a\u043e\u0434 \u043d\u0430 GitHub"},"content":{"rendered":"\n<div class=\"post__text post__text-html post__text_v1\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/company\/yandex\/blog\/503492\/\">\n<p><a href=\"https:\/\/habr.com\/ru\/company\/yandex\/blog\/503492\/\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/fl\/1q\/ou\/fl1qoudw9osgmptmcokjrruskws.png\"><br \/>  <\/a><\/p>\n<p>  <\/p>\n<p>\u041d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043b\u0435\u0442 \u043d\u0430\u0437\u0430\u0434 \u043c\u043d\u0435 \u043f\u043e\u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u043e\u0447\u0435\u043d\u044c \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043d\u0435\u043f\u043b\u043e\u0442\u043d\u044b\u0435 \u0433\u0440\u0430\u0444\u044b \u0441\u0440\u0435\u0434\u043d\u0435\u0433\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430 (\u0441\u043e\u0442\u043d\u0438 \u0442\u044b\u0441\u044f\u0447 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432, \u0441\u043e\u0442\u043d\u0438 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043e\u0432 \u0441\u0432\u044f\u0437\u0435\u0439). \u0422\u043e\u0433\u0434\u0430 \u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c, \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0441 \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u043c \u043d\u0430\u0431\u043e\u0440\u043e\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432 \u043f\u0440\u043e\u0441\u0442\u043e \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u043d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u0432\u0441\u0451 \u0440\u0430\u0437\u043d\u043e\u043e\u0431\u0440\u0430\u0437\u0438\u0435 \u043c\u0435\u0442\u043e\u0434\u043e\u0432, \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043d\u043d\u044b\u0445 \u0447\u0435\u043b\u043e\u0432\u0435\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u0437\u0430 \u043c\u043d\u043e\u0433\u0438\u0435 \u0434\u0435\u0441\u044f\u0442\u0438\u043b\u0435\u0442\u0438\u044f. \u0418\u043c\u0435\u044e\u0449\u0438\u0435\u0441\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0440\u0430\u0431\u043e\u0442\u0430\u043b\u0438 \u043b\u0438\u0431\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u043b\u043e\u0445\u043e, \u043b\u0438\u0431\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u043b\u043e\u0445\u043e \u0438 \u043a \u0442\u043e\u043c\u0443 \u0436\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e.<\/p>\n<p>  <\/p>\n<p>\u041a \u0441\u0447\u0430\u0441\u0442\u044c\u044e, \u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c, \u0447\u0442\u043e \u0438\u0434\u0435\u0438, \u0437\u0430\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0435 \u0432 \u043c\u0435\u0442\u0440\u0438\u043a\u0438 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0430 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438, \u043e \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u044f <a href=\"https:\/\/habr.com\/ru\/company\/yandex\/blog\/500742\/\">\u0440\u0430\u0441\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u043b \u0432 \u043f\u0440\u043e\u0448\u043b\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435<\/a>, \u043c\u043e\u0436\u043d\u043e \u0430\u0434\u0430\u043f\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438 \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043d\u0430 \u0438\u0445 \u043e\u0441\u043d\u043e\u0432\u0435 <em>\u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c<\/em> \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438. \u041e\u043d \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442 \u043e\u0447\u0435\u043d\u044c \u0432\u044b\u0441\u043e\u043a\u0438\u0445 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0430 \u0438 \u043a \u0442\u043e\u043c\u0443 \u0436\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043e\u0447\u0435\u043d\u044c \u0431\u044b\u0441\u0442\u0440\u043e \u0431\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0443\u0434\u0430\u0447\u043d\u044b\u043c \u0430\u043d\u0430\u043b\u0438\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u043c \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u0435\u043c\u044b\u0445 \u0432\u0435\u043b\u0438\u0447\u0438\u043d. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a \u043a\u043b\u0430\u0441\u0441\u0443 <em>\u0430\u0433\u043b\u043e\u043c\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u044b\u0445<\/em>: \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0435\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u043b\u0438\u044f\u043d\u0438\u0435 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u0443\u0436\u0435 \u0438\u043c\u0435\u044e\u0449\u0438\u0445\u0441\u044f \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432 \u0432 \u043e\u0434\u0438\u043d \u0431\u043e\u043b\u0435\u0435 \u043a\u0440\u0443\u043f\u043d\u044b\u0439 \u043a\u043b\u0430\u0441\u0442\u0435\u0440.<\/p>\n<p>  <\/p>\n<p>\u041e\u0431 \u044d\u0442\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u0438 \u043f\u043e\u0439\u0434\u0451\u0442 \u0440\u0435\u0447\u044c \u0432 \u0441\u0442\u0430\u0442\u044c\u0435. \u041f\u043e\u0434 \u043a\u0430\u0442\u043e\u043c \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u0435\u0439 \u0436\u0434\u0443\u0442 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u0442\u0435\u0445\u043d\u0438\u043a\u0438 \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u043d\u0438\u044f \u0435\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438, \u043a\u043e\u0434 \u043d\u0430 GitHub \u0438 \u043c\u043e\u0434\u0435\u043b\u044c\u043d\u044b\u0435 \u043d\u0430\u0431\u043e\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445.<\/p>\n<p><a name=\"habracut\"><\/a>  <\/p>\n<h3 id=\"1-aglomerativnaya-klasterizaciya\"><strong>1. \u0410\u0433\u043b\u043e\u043c\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u0430\u044f \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/h3>\n<p>  <\/p>\n<p>\u041f\u0443\u0441\u0442\u044c \u0434\u0430\u043d\u044b \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/814\/e64\/870\/814e648700be7248655d674954ec4b32.svg\" alt=\"$A=\\{a_1, ..., a_n\\}$\" data-tex=\"inline\"><\/math> \u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u043e\u043f\u0430\u0440\u043d\u043e\u0439 \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0438 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d77\/05a\/68b\/d7705a68b5e415c9438b71d5425656d5.svg\" alt=\"$s:A^2 \\rightarrow [0,1]$\" data-tex=\"inline\"><\/math>. \u041a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0431\u043b\u0438\u0437\u043e\u043a \u0441\u0430\u043c \u0441\u0435\u0431\u0435, \u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0438 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u0430:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8a8\/db5\/7fc\/8a8db57fc1f44f3a7b79e593cdf3aebb.svg\" alt=\"$s(a_i,a_i) = 1$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c8a\/6d0\/163\/c8a6d01635a27022667ade7fc26ffbfe.svg\" alt=\"$s(a_i, a_j) = s(a_j, a_i)$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0422\u0430\u043a\u0436\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/493\/c1c\/008\/493c1c008018df9bed4910321f29ff00.svg\" alt=\"$A$\" data-tex=\"inline\"><\/math> \u043d\u0430 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c4b\/199\/f11\/c4b199f11417dcfccbd4966badeb84b4.svg\" alt=\"$A=C_1 \\sqcup C_2 \\sqcup ... \\sqcup C_k$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u044f \u043e\u0431\u0440\u0430\u0437\u0443\u0435\u0442 \u043f\u043e\u043a\u0440\u044b\u0442\u0438\u0435 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430. \u041f\u0440\u0438 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438 \u043c\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e \u0438\u0437\u043e\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 (\u043d\u0435 \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0430\u0449\u0438\u0435 \u043d\u0438 \u043e\u0434\u043d\u043e\u043c\u0443 \u0438\u0437 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432) \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043e\u0431\u0440\u0430\u0437\u0443\u044e\u0442 \u0442\u0440\u0438\u0432\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430.<\/p>\n<p>  <\/p>\n<p>\u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432 \u0431\u0443\u0434\u0435\u043c \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0430\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/028\/e8a\/1e7\/028e8a1e74b8335d284dc41e5a41cf70.svg\" alt=\"$\\mathcal{L}$\" data-tex=\"inline\"><\/math>:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/645\/529\/444\/64552944475b76bd9fa6247b1363e846.svg\" alt=\"$\\mathcal{L} = \\{C_1, C_2, ..., C_k\\}$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u041f\u0443\u0441\u0442\u044c \u0432\u044b\u0431\u0440\u0430\u043d\u044b \u043e\u0431\u044a\u0435\u043a\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c6a\/200\/889\/c6a200889233190d0ffe86be0f9fadc8.svg\" alt=\"$x \\in A$\" data-tex=\"inline\"><\/math> \u0438 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d11\/f6c\/f94\/d11f6cf94553babb595dfc5abd9b06ba.svg\" alt=\"$X \\subseteq A$\" data-tex=\"inline\"><\/math>. \u0412\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0438\u043d\u0442\u0443\u0438\u0446\u0438\u0435\u0439 BCubed-\u043c\u0435\u0442\u0440\u0438\u043a \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0430 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0434\u043b\u044f \u044d\u0442\u043e\u0439 \u043f\u0430\u0440\u044b \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u0438 \u043f\u043e\u043b\u043d\u043e\u0442\u044b:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/088\/e28\/a4d\/088e28a4d957a1218842be9236a6ebc1.svg\" alt=\"${P}(x, X) = \\frac{1}{|X|}\\sum_{x' \\in X}{s(x, x')}$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b1e\/387\/719\/b1e387719fd88174fa41e3225484c1f1.svg\" alt=\"${R}(x) = \\frac{\\sum_{x' \\in X}{s(x, x')}}{\\sum_{x' \\in A}{s(x, x')}}$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0417\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e \u044d\u0442\u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0443\u0434\u043e\u0431\u043d\u044b \u0442\u0435\u043c, \u0447\u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/817\/b92\/407\/817b92407f764f57af9226e50cc788fd.svg\" alt=\"$x$\" data-tex=\"inline\"><\/math> \u043d\u0435 \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6d6\/a4f\/78f\/6d6a4f78fbacd6edecc018ce8ad3e364.svg\" alt=\"$X$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0438 \u0441\u0440\u0435\u0434\u043d\u0438\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u0438 \u043f\u043e\u043b\u043d\u043e\u0442\u044b \u0434\u043b\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6d6\/a4f\/78f\/6d6a4f78fbacd6edecc018ce8ad3e364.svg\" alt=\"$X$\" data-tex=\"inline\"><\/math> \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0441\u0430\u043c\u043e\u0433\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6d6\/a4f\/78f\/6d6a4f78fbacd6edecc018ce8ad3e364.svg\" alt=\"$X$\" data-tex=\"inline\"><\/math>:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ab2\/03f\/755\/ab203f755e220e2527afdfe477671f4c.svg\" alt=\"$P(X) = \\frac{1}{|X|}\\sum_{x \\in X}P(x, X) $\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/96b\/41a\/426\/96b41a4260370be49fcf697cb45f5659.svg\" alt=\"$R(X) = \\frac{1}{|X|}\\sum_{x \\in X}R(x, X) $\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u043a\u043e\u043c\u043f\u043e\u0437\u0438\u0446\u0438\u044e \u044d\u0442\u0438\u0445 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439, \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0432\u0448\u0438\u0441\u044c \u0438\u0434\u0435\u0435\u0439 \u043c\u0435\u0442\u0440\u0438\u043a\u0438 ECC:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/14c\/337\/915\/14c337915e2b3d0104e2bbd6d63d8ffe.svg\" alt=\"$M_\\alpha(X) = R^\\alpha(X) \\cdot P(X)$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0417\u0434\u0435\u0441\u044c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/723\/4a5\/2ba\/7234a52ba041cdb09b9328a047048fb2.svg\" alt=\"$\\alpha$\" data-tex=\"inline\"><\/math>, \u043a\u0430\u043a \u0438 \u0432 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%98%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA#F-%D0%BC%D0%B5%D1%80%D0%B0_(F-measure,_%D0%BC%D0%B5%D1%80%D0%B0_%D0%92%D0%B0%D0%BD_%D0%A0%D0%B8%D0%B7%D0%B1%D0%B5%D1%80%D0%B3%D0%B5%D0%BD%D0%B0)\">\u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0438<\/a> <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3c9\/bca\/de0\/3c9bcade02ed1bcb586c485ae9c4eba8.svg\" alt=\"$F_\\alpha$\" data-tex=\"inline\"><\/math>-\u043c\u0435\u0440\u044b, \u0437\u0430\u0434\u0430\u0451\u0442 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0432\u0430\u0436\u043d\u043e\u0441\u0442\u044c \u043f\u043e\u043b\u043d\u043e\u0442\u044b \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438. \u0412 \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/159\/037\/724\/15903772463609f1294d9587d75455bb.svg\" alt=\"$\\alpha=1$\" data-tex=\"inline\"><\/math> \u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u0440\u0430\u0432\u043d\u043e\u043f\u0440\u0430\u0432\u043d\u044b.<\/p>\n<p>  <\/p>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0434\u0432\u0430 \u043d\u0435\u043f\u0435\u0440\u0435\u0441\u0435\u043a\u0430\u044e\u0449\u0438\u0445\u0441\u044f \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e97\/eec\/3da\/e97eec3dab7c27b0b911e9ce196f4e7a.svg\" alt=\"$X \\subset A$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c30\/fd5\/54c\/c30fd554ca506c6c2a613107a5143dc0.svg\" alt=\"$Y \\subset A$\" data-tex=\"inline\"><\/math>. \u0415\u0441\u043b\u0438 \u043e\u043d\u0438 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430\u043c\u0438, \u0442\u043e \u0441\u0440\u0435\u0434\u043d\u0438\u0435 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0438 \u043f\u043e\u043b\u043d\u043e\u0442\u0430 \u0432\u0445\u043e\u0434\u044f\u0449\u0438\u0445 \u0432 \u043d\u0438\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0440\u0430\u0432\u043d\u044b:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bd9\/8b3\/bc9\/bd98b3bc9a250f94cb976bf9eb60f6fe.svg\" alt=\"$P(X, Y) = \\frac{1}{|X \\cup Y|}\\Big[ \\sum_{x \\in X}{P(x, X)} + \\sum_{y \\in Y}{P(y, Y)}\\Big]$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0e4\/570\/9c6\/0e45709c6e2b614f922fc93144106ed7.svg\" alt=\"$R(X, Y) = \\frac{1}{|X \\cup Y|}\\Big[ \\sum_{x \\in X}{R(x, X)} + \\sum_{y \\in Y}{R(y, Y)}\\Big]$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0438 \u043a\u043e\u043c\u043f\u043e\u0437\u0438\u0446\u0438\u044e \u043c\u0435\u0442\u0440\u0438\u043a \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0441\u043b\u0443\u0447\u0430\u044f:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/977\/7f1\/2be\/9777f12be81c944852b8b344270d3dfa.svg\" alt=\"$M_\\alpha(X, Y) = R^\\alpha(X, Y) \\cdot P(X, Y)$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0415\u0441\u043b\u0438 \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u0438\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6d6\/a4f\/78f\/6d6a4f78fbacd6edecc018ce8ad3e364.svg\" alt=\"$X$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c62\/ff2\/5ef\/c62ff25ef4caeaeaef7122a489ef9d07.svg\" alt=\"$Y$\" data-tex=\"inline\"><\/math> \u0432 \u043e\u0434\u0438\u043d \u043a\u043b\u0430\u0441\u0442\u0435\u0440, \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u0441\u0442\u0430\u043d\u0443\u0442 \u0440\u0430\u0432\u043d\u044b:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/094\/ae8\/836\/094ae883662c5dcf450a7e2304b4b5a0.svg\" alt=\"$P(X \\cup Y) = \\frac{1}{|X \\cup Y|}\\sum_{a \\in X \\cup Y}{P(a, X \\cup Y)}$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/26d\/0e7\/040\/26d0e7040d12aca24084e27ce20487ab.svg\" alt=\"$R(X \\cup Y) = \\frac{1}{|X \\cup Y|}\\sum_{a \\in X \\cup Y}{R(a, X \\cup Y)}$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0410 \u043a\u043e\u043c\u043f\u043e\u0437\u0438\u0446\u0438\u044f \u043c\u0435\u0442\u0440\u0438\u043a \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u0441\u044f \u043f\u0440\u043e\u0441\u0442\u043e \u043a\u0430\u043a <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/be0\/c3b\/4bc\/be0c3b4bc5c657cb11fb85971bf82c37.svg\" alt=\"$M_\\alpha(X \\cup Y)$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u0438 \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u0438 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6d6\/a4f\/78f\/6d6a4f78fbacd6edecc018ce8ad3e364.svg\" alt=\"$X$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c62\/ff2\/5ef\/c62ff25ef4caeaeaef7122a489ef9d07.svg\" alt=\"$Y$\" data-tex=\"inline\"><\/math> \u043a\u043e\u043c\u043f\u043e\u0437\u0438\u0446\u0438\u044f \u043c\u0435\u0442\u0440\u0438\u043a \u0434\u043b\u044f \u0432\u0445\u043e\u0434\u044f\u0449\u0438\u0445 \u0432 \u043d\u0438\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0438\u0437\u043c\u0435\u043d\u0438\u0442\u0441\u044f \u043d\u0430 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0443<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8ef\/479\/bc0\/8ef479bc0f2e704ce2c8393876cc2498.svg\" alt=\"$\\Delta_{\\alpha}{X, Y} = M_\\alpha(X \\cup Y) - M_\\alpha(X, Y)$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0418\u0434\u0435\u044f \u043d\u0430\u0448\u0435\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 <em>\u0430\u0433\u043b\u043e\u043c\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u043e\u0439<\/em> \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u044f\u0442\u044c \u0434\u0432\u0430 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u044d\u0442\u0430 \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c\u0430. \u0422\u043e\u0433\u0434\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0437\u0430\u043f\u0438\u0448\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:<\/p>\n<p>  <\/p>\n<blockquote><p><strong>\u0414\u0430\u043d\u044b:<\/strong>  <\/p>\n<ul>\n<li>\u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ca0\/945\/c57\/ca0945c57d7f91df83f74b40edb1c618.svg\" alt=\"$ A = \\{a_1, a_2, ..., a_n \\} $\" data-tex=\"inline\"><\/math><\/li>\n<li>\u0421\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u0430\u044f \u043f\u043e\u043f\u0430\u0440\u043d\u043e\u0439 \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d77\/05a\/68b\/d7705a68b5e415c9438b71d5425656d5.svg\" alt=\"$s:A^2 \\rightarrow [0,1]$\" data-tex=\"inline\"><\/math><\/li>\n<li>\u0422\u0440\u0438\u0432\u0438\u0430\u043b\u044c\u043d\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432: <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/727\/15e\/dda\/72715edda7d4822ac501be47b231f0e6.svg\" alt=\"$ \\mathcal{L} = \\{C_1, C_2, ..., C_n\\} $\" data-tex=\"inline\"><\/math>, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/375\/bd4\/0c9\/375bd40c94d9d4929350e5bac1e8f3e3.svg\" alt=\"$C_i = \\{a_i\\}$\" data-tex=\"inline\"><\/math><\/li>\n<\/ul>\n<p>  <strong>\u041e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u0446\u0438\u043a\u043b:<\/strong>   <\/p>\n<ol>\n<li>\u0415\u0441\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4d4\/6d6\/689\/4d46d6689a3bbd8c8cd838d777322e76.svg\" alt=\"$|\\mathcal{L}| = 1$\" data-tex=\"inline\"><\/math>, \u0432\u0435\u0440\u043d\u0443\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/028\/e8a\/1e7\/028e8a1e74b8335d284dc41e5a41cf70.svg\" alt=\"$\\mathcal{L}$\" data-tex=\"inline\"><\/math> \u0438 \u0437\u0430\u0432\u0435\u0440\u0448\u0438\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c.<\/li>\n<li>\u0412\u044b\u0431\u0440\u0430\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a6f\/4e8\/b5e\/a6f4e8b5efc92346cbe1a8fa761b438b.svg\" alt=\"$C_i, C_j = \\arg \\max_{X, Y \\in \\mathcal{L}} \\Delta_{\\alpha}(X, Y)$\" data-tex=\"inline\"><\/math>.<\/li>\n<li>\u0415\u0441\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/985\/741\/561\/985741561f27d13cee9a6facfb4fbac2.svg\" alt=\"$\\Delta_{\\alpha}(C_i, C_j) &lt; 0$\" data-tex=\"inline\"><\/math>, \u0432\u0435\u0440\u043d\u0443\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/028\/e8a\/1e7\/028e8a1e74b8335d284dc41e5a41cf70.svg\" alt=\"$\\mathcal{L}$\" data-tex=\"inline\"><\/math> \u0438 \u0437\u0430\u0432\u0435\u0440\u0448\u0438\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c.<\/li>\n<li>\u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/dc2\/948\/e52\/dc2948e520a0e79c1fa205e6404ee330.svg\" alt=\"$ \\mathcal{L} = \\mathcal{L} \\setminus \\{C_i, C_j\\} \\cup \\{C_i \\cup C_j\\}$\" data-tex=\"inline\"><\/math> \u0438 \u0432\u0435\u0440\u043d\u0443\u0442\u044c\u0441\u044f \u043a \u0448\u0430\u0433\u0443 1.<\/li>\n<\/ol>\n<p>  <\/p><\/blockquote>\n<p>\u041e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u043e\u0439 \u0442\u0430\u043a\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0431\u0443\u0434\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0435. \u041a\u0430\u0436\u0434\u0430\u044f \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044f \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0433\u043e \u0446\u0438\u043a\u043b\u0430 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c14\/a59\/bde\/c14a59bde821353b1d40d63f5578b34d.svg\" alt=\"$\\Delta_\\alpha$\" data-tex=\"inline\"><\/math> \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u043f\u0430\u0440 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432. \u041d\u043e \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u044d\u0442\u0443 \u0447\u0430\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043c\u043e\u0436\u043d\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c.<\/p>\n<p>  <\/p>\n<h3 id=\"2-uskorenie-algoritma\"><strong>2. \u0423\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430<\/strong><\/h3>\n<p>  <\/p>\n<p>\u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u0440\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432 \u0434\u0432\u0443\u0445 \u0430\u0441\u043f\u0435\u043a\u0442\u0430\u0445. \u041f\u0435\u0440\u0432\u044b\u0439 \u0441\u0432\u044f\u0437\u0430\u043d \u0441 \u0442\u0435\u043c, \u0447\u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0430\u0440 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432 \u043d\u0430 \u0448\u0430\u0433\u0435 2 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u044b\u043c \u043e\u0442 \u043e\u0431\u0449\u0435\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0438\u043c\u0435\u044e\u0449\u0438\u0445\u0441\u044f \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432; \u0432\u0442\u043e\u0440\u043e\u0439 \u2014 \u0441 \u0442\u0435\u043c, \u0447\u0442\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u044b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d1c\/138\/7ed\/d1c1387edd13f82aba0e19f2479c91c2.svg\" alt=\"$\\Delta_{\\alpha}(C_i, C_j)$\" data-tex=\"inline\"><\/math> \u043f\u0440\u0438 \u043d\u0430\u0438\u0432\u043d\u043e\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0432\u0440\u0435\u043c\u0435\u043d\u0438, \u043f\u0440\u043e\u043f\u043e\u0440\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043a\u0430\u043a \u043c\u0438\u043d\u0438\u043c\u0443\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/234\/c85\/b1c\/234c85b1c091003a644d48c588ccf173.svg\" alt=\"$|C_i| \\cdot |C_j|$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <\/p>\n<p>\u0423\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432 \u0441\u0432\u044f\u0437\u0438 \u0441 \u043f\u0435\u0440\u0432\u044b\u043c \u0430\u0441\u043f\u0435\u043a\u0442\u043e\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e. \u0417\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e \u043f\u043e\u0441\u043b\u0435 \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u044f \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/be9\/fcb\/960\/be9fcb960a47cc7659becd7ce4c851d5.svg\" alt=\"$C_i$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c13\/55d\/4ee\/c1355d4ee682504c5920c8c5cc9bd51b.svg\" alt=\"$C_j$\" data-tex=\"inline\"><\/math> \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c14\/a59\/bde\/c14a59bde821353b1d40d63f5578b34d.svg\" alt=\"$\\Delta_{\\alpha}$\" data-tex=\"inline\"><\/math> \u043d\u0443\u0436\u043d\u043e \u043e\u0431\u043d\u043e\u0432\u0438\u0442\u044c \u043b\u0438\u0448\u044c \u043d\u0430 \u0442\u0435\u0445 \u043f\u0430\u0440\u0430\u0445 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u0445\u043e\u0434\u0438\u0442 \u043b\u0438\u0431\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/be9\/fcb\/960\/be9fcb960a47cc7659becd7ce4c851d5.svg\" alt=\"$C_i$\" data-tex=\"inline\"><\/math>, \u043b\u0438\u0431\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c13\/55d\/4ee\/c1355d4ee682504c5920c8c5cc9bd51b.svg\" alt=\"$C_j$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <\/p>\n<p>\u0414\u0440\u0443\u0433\u0438\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6eb\/600\/875\/6eb600875853bee46568f0198c2c8f0b.svg\" alt=\"$\\Delta_{\\alpha}(C_k, C_l)$\" data-tex=\"inline\"><\/math> \u043d\u0435 \u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435 \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u044f \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/be9\/fcb\/960\/be9fcb960a47cc7659becd7ce4c851d5.svg\" alt=\"$C_i$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c13\/55d\/4ee\/c1355d4ee682504c5920c8c5cc9bd51b.svg\" alt=\"$C_j$\" data-tex=\"inline\"><\/math>, \u0435\u0441\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cfc\/b76\/f86\/cfcb76f862e62efbb6c2aaec388eed0f.svg\" alt=\"$\\{i, j\\} \\cap \\{k, l\\} = \\varnothing$\" data-tex=\"inline\"><\/math>. \u0421\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u043e\u0431\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043b\u0438\u0448\u044c \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435, \u0430 \u043d\u0435 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u043e\u0435 \u043f\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0443 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/028\/e8a\/1e7\/028e8a1e74b8335d284dc41e5a41cf70.svg\" alt=\"$\\mathcal{L}$\" data-tex=\"inline\"><\/math> \u0447\u0438\u0441\u043b\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439.<\/p>\n<p>  <\/p>\n<p>\u0425\u0440\u0430\u043d\u0438\u0442\u044c \u0438\u0445 \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u043c\u043e\u0436\u043d\u043e \u0432 \u043b\u044e\u0431\u043e\u0439 set-\u043f\u043e\u0434\u043e\u0431\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435, \u0442\u0430\u043a \u0447\u0442\u043e \u0438\u0437\u0432\u043b\u0435\u0447\u0435\u043d\u0438\u0435 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u043d\u0438\u043c\u0430\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/eda\/c68\/97c\/edac6897ca5bab63e49737e4cc6421e3.svg\" alt=\"$O(\\ln{|\\mathcal{L}|}^2)=O(\\ln|\\mathcal{L}|)$\" data-tex=\"inline\"><\/math> \u0432\u0440\u0435\u043c\u0435\u043d\u0438.<\/p>\n<p>  <\/p>\n<p>\u0421\u043f\u0440\u0430\u0432\u0438\u0442\u044c\u0441\u044f \u0441\u043e \u0432\u0442\u043e\u0440\u044b\u043c \u0430\u0441\u043f\u0435\u043a\u0442\u043e\u043c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u043b\u043e\u0436\u043d\u0435\u0435. \u0427\u0442\u043e\u0431\u044b \u043b\u0443\u0447\u0448\u0435 \u043f\u043e\u043d\u044f\u0442\u044c, \u043a\u0430\u043a \u0437\u0434\u0435\u0441\u044c \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u0435, \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u0443\u044e \u0430\u0434\u0434\u0438\u0442\u0438\u0432\u043d\u0443\u044e \u043f\u043e \u044f\u0447\u0435\u0439\u043a\u0430\u043c \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0444\u0443\u043d\u043a\u0446\u0438\u044e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/12a\/b92\/a58\/12ab92a586fb3d91b2b9c1e1ca0dc58c.svg\" alt=\"$f$\" data-tex=\"inline\"><\/math>. \u041f\u0440\u0438\u043c\u0435\u0440 \u0442\u0430\u043a\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u2014 \u043f\u0440\u043e\u0441\u0442\u0430\u044f \u0441\u0443\u043c\u043c\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439.<\/p>\n<p>  <\/p>\n<p>\u041f\u0443\u0441\u0442\u044c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/493\/c1c\/008\/493c1c008018df9bed4910321f29ff00.svg\" alt=\"$A$\" data-tex=\"inline\"><\/math> \u0440\u0430\u0437\u0431\u0438\u0442\u043e \u043d\u0430 \u0442\u0440\u0438 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430. \u0422\u043e\u0433\u0434\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/12a\/b92\/a58\/12ab92a586fb3d91b2b9c1e1ca0dc58c.svg\" alt=\"$f$\" data-tex=\"inline\"><\/math> \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0430 \u043d\u0430 \u0432\u0441\u0435\u0445 \u0434\u0435\u0432\u044f\u0442\u0438 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u044b\u0445 \u0444\u0440\u0430\u0433\u043c\u0435\u043d\u0442\u0430\u0445 \u043c\u0430\u0442\u0440\u0438\u0446\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0442 \u043f\u0430\u0440\u0430\u043c \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432. \u041d\u0430\u0441 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u0435\u0442, \u043a\u0430\u043a \u043e\u0431\u043d\u043e\u0432\u0438\u0442\u044c \u0435\u0451 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u0440\u0438 \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u0438 \u0434\u0432\u0443\u0445 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432 \u0432 \u043e\u0434\u0438\u043d.<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/zi\/g3\/bu\/zig3buip1wktyefhbswiqnf4iak.png\"><\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0441\u043b\u0435 \u0442\u0430\u043a\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u043e\u0441\u0442\u0430\u043d\u0435\u0442\u0441\u044f \u0447\u0435\u0442\u044b\u0440\u0435 \u043f\u0430\u0440\u044b \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432 \u0438 \u0447\u0435\u0442\u044b\u0440\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u044e\u0449\u0438\u0445 \u043d\u0430\u0441 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0438. \u0412 \u0441\u0438\u043b\u0443 \u0435\u0451 \u0430\u0434\u0434\u0438\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u044d\u0442\u0438 \u0447\u0435\u0442\u044b\u0440\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u044e\u0442\u0441\u044f \u0438\u0437 \u043f\u0440\u0435\u0434\u0448\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 \u0437\u0430 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f, \u043d\u0435 \u0437\u0430\u0432\u0438\u0441\u044f\u0449\u0435\u0435 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u0432 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432. \u041f\u0440\u0430\u0432\u0438\u043b\u0430 \u0442\u0430\u043a\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0441\u0447\u0451\u0442\u0430 \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u044b \u043d\u0430 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0435 \u0432\u044b\u0448\u0435.<\/p>\n<p>  <\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u0437\u0430\u043c\u0435\u0442\u0438\u043c: \u0435\u0441\u043b\u0438 \u0432 \u044f\u0447\u0435\u0439\u043a\u0430\u0445 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/12a\/b92\/a58\/12ab92a586fb3d91b2b9c1e1ca0dc58c.svg\" alt=\"$f$\" data-tex=\"inline\"><\/math> \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u0441\u0443\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435, \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0438 \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u044f \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0441\u0442\u0438\u043a \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438. \u0421\u0440\u0435\u0434\u043d\u0438\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u043c\u0435\u0442\u0440\u0438\u043a\u0438 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u0434\u043b\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0438\u0437 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/40a\/a32\/341\/40aa32341abe8afc6e84b17d8dc6f99b.svg\" alt=\"$X \\cup Y$\" data-tex=\"inline\"><\/math> \u0434\u043e \u0438 \u043f\u043e\u0441\u043b\u0435 \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u044f \u0431\u0443\u0434\u0443\u0442 \u0440\u0430\u0432\u043d\u044b, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c2f\/b86\/f3e\/c2fb86f3ed96410d2018bc4dfab6fded.svg\" alt=\"$P(X,Y) = \\frac{1}{|X \\cup Y|}\\Big[\\frac{f(X,X)}{|X|} + \\frac{f(Y,Y)}{|Y|}\\Big]$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/24e\/bce\/325\/24ebce325cb28d53c9027322d4c6900e.svg\" alt=\"$P(X \\cup Y) = \\frac{f(X,X) + f(X,Y) + f(Y,X) + f(Y,Y)}{|X \\cup Y|^2}$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u0442\u0443\u043f\u0438\u0442\u044c \u0438 \u0441 \u043f\u043e\u043b\u043d\u043e\u0442\u043e\u0439. \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0430\u0434\u0434\u0438\u0442\u0438\u0432\u043d\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bdb\/a74\/99b\/bdba7499baaa2899811e34409321d6eb.svg\" alt=\"$g$\" data-tex=\"inline\"><\/math> \u0442\u0430\u043a, \u0447\u0442\u043e \u043e\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u0441\u0443\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c <em>\u043d\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043f\u043e \u0441\u0442\u0440\u043e\u043a\u0430\u043c<\/em> \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0438 \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/725\/27c\/348\/72527c348f6b86bca2870c1cac2d3109.svg\" alt=\"$g(x,y) = \\frac{s(x,y)}{\\sum_{a \\in A}s(x, a)}$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0421\u0443\u043c\u043c\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bdb\/a74\/99b\/bdba7499baaa2899811e34409321d6eb.svg\" alt=\"$g$\" data-tex=\"inline\"><\/math> \u043f\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u043c \u043e\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0438 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0432\u0441\u0435\u0433\u0434\u0430 \u0440\u0430\u0432\u043d\u044f\u0435\u0442\u0441\u044f \u0435\u0434\u0438\u043d\u0438\u0446\u0435. \u0422\u043e\u0433\u0434\u0430:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/eb8\/214\/e7c\/eb8214e7c281863557e603c257d19fe9.svg\" alt=\"$R(X,Y) = \\frac{g(X,X) + g(Y,Y)}{|X \\cup Y|}$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/900\/59c\/504\/90059c5042c384e3f22b3f6cc6ed4220.svg\" alt=\"$R(X \\cup Y) = \\frac{g(X,X) + g(X,Y) + g(Y,X) + g(Y,Y)}{|X \\cup Y|}$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0420\u0430\u0437\u043d\u0438\u0446\u0430 \u0441\u043e \u0441\u043b\u0443\u0447\u0430\u0435\u043c \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u0441\u0432\u044f\u0437\u0430\u043d\u0430 \u0441 \u0442\u0435\u043c, \u0447\u0442\u043e \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u0443\u043c\u043c\u0443 \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0435\u0439 \u043d\u0430 \u0440\u0430\u0437\u043c\u0435\u0440 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430, \u0430 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u043e\u043b\u043d\u043e\u0442\u044b \u0441\u0443\u043c\u043c\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u043d\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b.<\/p>\n<p>  <\/p>\n<p>\u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0435 \u0434\u043b\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u044b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/fd7\/922\/a78\/fd7922a785a77a49b96b001df5ea1920.svg\" alt=\"$\\Delta_\\alpha(X \\cup Y, Z)$\" data-tex=\"inline\"><\/math>:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/939\/b5f\/4bc\/939b5f4bc4a199eb14918d046578ebbb.svg\" alt=\"$P(X \\cup Y,Z) = \\frac{1}{|X \\cup Y \\cup Z|}\\Big[\\frac{f(X \\cup Y,X \\cup Y)}{|X \\cup Y|} + \\frac{f(Z,Z)}{|Z|}\\Big]$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3a1\/1d5\/58f\/3a11d558fab162533be54f0cb4173b7d.svg\" alt=\"$P(X \\cup Y \\cup Z) = \\frac{f(X \\cup Y,X \\cup Y) + f(X \\cup Y,Z) + f(Z,X \\cup Y) + f(Z,Z)}{|X \\cup Y \\cup Z|^2}$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8dd\/f4a\/25e\/8ddf4a25eccc5d915d230f469bec193a.svg\" alt=\"$R(X \\cup Y,Z) = \\frac{g(X \\cup Y,X \\cup Y) + g(Z,Z)}{|X \\cup Y \\cup Z|}$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8af\/3e3\/cda\/8af3e3cda4ac33605096ca27d8bc3573.svg\" alt=\"$R(X \\cup Y \\cup Z) = \\frac{g(X \\cup Y,X \\cup Y) + g(X \\cup Y,Z) + g(Z,X \\cup Y) + g(Z,Z)}{|X \\cup Y \\cup Z|}$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0422\u043e \u0435\u0441\u0442\u044c \u0431\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u044f \u0430\u0434\u0434\u0438\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u043a\u0430\u0436\u0434\u043e\u0439 \u0432\u0432\u0435\u0434\u0451\u043d\u043d\u043e\u0439 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u044b \u043f\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u043c \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0432\u0441\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0442 \u0437\u0430 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f! \u041e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0435 <em>\u0432\u0441\u0435\u0445<\/em> \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a8c\/3d4\/a6e\/a8c3d4a6e963aa33224286ee2cfdfe56.svg\" alt=\"$O(|\\mathcal{L}| \\cdot \\ln|\\mathcal{L}|)$\" data-tex=\"inline\"><\/math> \u0432\u0440\u0435\u043c\u0435\u043d\u0438.<\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043a\u0430\u0436\u0434\u0430\u044f \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044f \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442 \u0447\u0438\u0441\u043b\u043e \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432 \u043d\u0430 \u0435\u0434\u0438\u043d\u0438\u0446\u0443, \u043f\u043e\u043b\u043d\u043e\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5a6\/905\/e58\/5a6905e58424db44945e46f3cb1f367a.svg\" alt=\"$O(n^2\\ln n)$\" data-tex=\"inline\"><\/math> \u0432\u0440\u0435\u043c\u0435\u043d\u0438. \u0415\u0441\u043b\u0438 \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u043f\u043e \u0432\u0441\u0435\u043c \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044f\u043c \u043e\u0434\u0438\u043d \u043a\u043b\u0430\u0441\u0442\u0435\u0440 \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441\u0432\u044f\u0437\u0430\u043d \u0441 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16d\/a50\/7b2\/16da507b2fc389688ef0659939dcc647.svg\" alt=\"$k$\" data-tex=\"inline\"><\/math> \u0434\u0440\u0443\u0433\u0438\u043c\u0438, \u043e\u0446\u0435\u043d\u043a\u0430 \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0443\u043b\u0443\u0447\u0448\u0430\u0435\u0442\u0441\u044f \u0434\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c19\/b0d\/2ff\/c19b0d2ff5b112877f306646f1d70294.svg\" alt=\"$O(n \\cdot k \\cdot \\ln n)$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <\/p>\n<p>\u041a\u043e\u0433\u0434\u0430 \u043d\u0443\u0436\u043d\u043e \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0442\u0435\u043a\u0441\u0442\u044b \u043d\u0430 \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0445 \u044f\u0437\u044b\u043a\u0430\u0445 \u0432 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0437\u0430\u0434\u0430\u0447\u0430\u0445, \u043f\u043b\u043e\u0442\u043d\u043e\u0441\u0442\u044c \u0433\u0440\u0430\u0444\u043e\u0432 \u043e\u0431\u044b\u0447\u043d\u043e \u043d\u0435\u0432\u0435\u043b\u0438\u043a\u0430, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043e\u0447\u0435\u043d\u044c \u0431\u044b\u0441\u0442\u0440\u043e. \u0412 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u043f\u043b\u043e\u0442\u043d\u043e\u0441\u0442\u044c \u0433\u0440\u0430\u0444\u043e\u0432 \u043c\u043e\u0436\u043d\u043e \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u043d\u0430 \u044d\u0442\u0430\u043f\u0435 \u043f\u0440\u0435\u0434\u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043f\u0440\u0438 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u0441\u0442\u0430\u0442\u0435\u0439 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u044f\u0442\u044c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0441\u0442\u0430\u0442\u0435\u0439 \u0441 \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u0445\u043e\u0436\u0438\u043c\u0438 \u0437\u0430\u0433\u043e\u043b\u043e\u0432\u043a\u0430\u043c\u0438.<\/p>\n<p>  <\/p>\n<h3 id=\"4-realizaciya\"><strong>4. \u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/h3>\n<p>  <\/p>\n<p>\u041e\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d \u043d\u0430 C++ \u0438 \u0432\u044b\u043b\u043e\u0436\u0435\u043d \u043f\u043e\u0434 \u043b\u0438\u0446\u0435\u043d\u0437\u0438\u0435\u0439 MIT <a href=\"https:\/\/github.com\/yandex\/agglomerative_clustering\/\">\u043d\u0430 GitHub<\/a>. \u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043a\u043e\u043c\u043f\u0438\u043b\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0438 \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u0442\u0441\u044f \u043d\u0430 Linux \u0438 Windows.<\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0443 \u043b\u0435\u0433\u043a\u043e \u0441\u043e\u0431\u0440\u0430\u0442\u044c:<\/p>\n<p>  <\/p>\n<pre><code class=\"plaintext\">git clone https:\/\/github.com\/yandex\/agglomerative_clustering\/ cmake . cmake --build .<\/code><\/pre>\n<p>  <\/p>\n<p>\u041f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u0435\u0451 \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u043d\u0430 \u043e\u0434\u043d\u043e\u043c \u0438\u0437 \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432, \u043d\u0430\u0445\u043e\u0434\u044f\u0449\u0438\u0445\u0441\u044f \u0432 \u0442\u043e\u043c \u0436\u0435 \u043f\u0440\u043e\u0435\u043a\u0442\u0435:<\/p>\n<p>  <\/p>\n<pre><code class=\"plaintext\">.\/agglomerative_clustering &lt; data\/2d_similarities.tsv &gt; 2d_clusters.tsv<\/code><\/pre>\n<p>  <\/p>\n<p>\u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u0431\u0443\u0434\u0435\u0442 \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d \u0444\u0430\u0439\u043b, \u0444\u043e\u0440\u043c\u0430\u0442 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u0444\u043e\u0440\u043c\u0430\u0442\u043e\u043c, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0440\u0430\u0437\u043c\u0435\u0442\u043a\u0430 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438 (\u0441\u043c. <a href=\"https:\/\/habr.com\/ru\/company\/yandex\/blog\/500742\/\">\u0441\u0442\u0430\u0442\u044c\u044e \u043f\u0440\u043e \u043c\u0435\u0442\u0440\u0438\u043a\u0438 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438<\/a>)<\/p>\n<p>  <\/p>\n<h3 id=\"5-nabory-dannyh\"><strong>5. \u041d\u0430\u0431\u043e\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445<\/strong><\/h3>\n<p>  <\/p>\n<p>\u041f\u0435\u0440\u0432\u044b\u0439 \u043f\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c\u044b\u0439 \u0441 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u043e\u0439 \u043d\u0430\u0431\u043e\u0440 \u0434\u0430\u043d\u043d\u044b\u0445 \u2014 \u0441\u0438\u043d\u0442\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439. 18 343 \u0442\u043e\u0447\u043a\u0438 \u043d\u0430 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u044b \u0438\u0437 1000 \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u0434\u0432\u0443\u043c\u0435\u0440\u043d\u044b\u0445 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0439 \u0441\u043e \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u043c\u0438 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u0446\u0435\u043d\u0442\u0440\u0430\u043c\u0438. \u0411\u043b\u0438\u0437\u043e\u0441\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u0442\u043e\u0447\u043a\u0430\u043c\u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cd2\/a6a\/d4d\/cd2a6ad4dc550b77aef38cc3b85e8af0.svg\" alt=\"$s(p_1, p_2) = \\frac{2}{1 + \\exp\\Big(\\|p_1-p_2\\|_2^2\\Big)}$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0421\u0430\u043c\u0438 \u0442\u043e\u0447\u043a\u0438 \u0438\u0437 \u044d\u0442\u043e\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430 \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0432 \u0444\u0430\u0439\u043b\u0435 <a href=\"https:\/\/github.com\/yandex\/agglomerative_clustering\/blob\/master\/data\/2d_points.tsv\"><code>data\/2d_points.tsv<\/code><\/a>, \u0430 \u043c\u043e\u0436\u043d\u043e \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0437\u0430\u043d\u043e\u0432\u043e, \u0437\u0430\u043f\u0443\u0441\u0442\u0438\u0432 \u0441\u043a\u0440\u0438\u043f\u0442 <a href=\"https:\/\/github.com\/yandex\/agglomerative_clustering\/blob\/master\/data\/2d_gen.py\"><code>data\/2d_gen.py<\/code><\/a>. \u042d\u0442\u0430\u043b\u043e\u043d\u043d\u043e\u0439 \u0441\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u044f \u0432 \u0444\u0430\u0439\u043b\u0435 <a href=\"https:\/\/github.com\/yandex\/agglomerative_clustering\/blob\/master\/data\/2d_markup.tsv\"><code>data\/2d_markup.tsv<\/code><\/a>, \u0433\u0434\u0435 \u043a\u0430\u0436\u0434\u0430\u044f \u0442\u043e\u0447\u043a\u0430 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a \u043f\u043e\u0440\u043e\u0434\u0438\u0432\u0448\u0435\u043c\u0443 \u0435\u0451 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044e.<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/ze\/6k\/hf\/ze6khfakhukhp65qpfaht2plvjm.png\"><br \/>  <b><sup><sub>\u0421\u0438\u043d\u0442\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043d\u0430\u0431\u043e\u0440 \u0442\u043e\u0447\u0435\u043a \u043d\u0430 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438<\/sub><\/sup><\/b><\/p>\n<p>  <\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u0443\u0441\u0442\u043e\u0439\u0447\u0438\u0432 \u043a \u043f\u043e\u0442\u0435\u0440\u0435 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u043e \u0441\u0432\u044f\u0437\u044f\u0445 \u043c\u0435\u0436\u0434\u0443 \u043e\u0431\u044a\u0435\u043a\u0442\u0430\u043c\u0438. \u0427\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0434\u0435\u043c\u043e\u043d\u0441\u0442\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u044d\u0442\u043e \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e, \u0432 \u043d\u0430\u0431\u043e\u0440\u0435 \u0438\u0437 \u0432\u0441\u0435\u0445 \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0435\u0439, \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043f\u0440\u0435\u0432\u043e\u0441\u0445\u043e\u0434\u044f\u0449\u0438\u0445 \u043d\u043e\u043b\u044c, \u0431\u044b\u043b\u0430 \u043e\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043e\u0434\u043d\u0430 \u0442\u0440\u0435\u0442\u044c (228 018 \u0448\u0442\u0443\u043a). \u0423\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u044f \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 <code>-f<\/code> (\u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0443 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/723\/4a5\/2ba\/7234a52ba041cdb09b9328a047048fb2.svg\" alt=\"$\\alpha$\" data-tex=\"inline\"><\/math> \u0432 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435), \u043c\u043e\u0436\u043d\u043e \u0434\u043e\u0431\u0438\u0442\u044c\u0441\u044f \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0442\u0435\u0445 \u0436\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0430, \u0447\u0442\u043e \u0438 \u043d\u0430 \u0433\u0440\u0430\u0444\u0435 \u0434\u043e \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0440\u0451\u0431\u0435\u0440:<\/p>\n<p>  <\/p>\n<pre><code class=\"plaintext\">.\/agglomerative_clustering -f 10 &lt; data\/2d_similarities.tsv &gt; 2d_clusters.tsv ..\/cluster_metrics\/cluster_metrics data\/2d_markup.tsv 2d_clusters.tsv ECC   0.62411 (0.62411) BCP   0.74112 (0.74112) BCR   0.68095 (0.68095) BCF1  0.70976 (0.70976)<\/code><\/pre>\n<p>  <\/p>\n<p>\u0417\u0434\u0435\u0441\u044c \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043c\u0435\u0442\u0440\u0438\u043a \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 <a href=\"https:\/\/habr.com\/ru\/company\/yandex\/blog\/500742\/\">\u0438\u0437 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0438<\/a>.<\/p>\n<p>  <\/p>\n<p>\u041a\u043e\u043d\u0435\u0447\u043d\u043e, \u043d\u0430\u0448 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u043c\u043e\u0436\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u0432\u0435\u043a\u0442\u043e\u0440\u043d\u044b\u0445 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430\u0445. \u0412 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043e\u043d \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0442\u0430\u043a: \u043d\u0430 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 \u043f\u0430\u0440 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043d\u043e\u0432\u043e\u0441\u0442\u043d\u044b\u0445 \u0442\u0435\u043a\u0441\u0442\u043e\u0432) \u043e\u0431\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0438, \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0430\u043d\u0438\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0438 \u0441\u0442\u0430\u043d\u043e\u0432\u044f\u0442\u0441\u044f \u0432\u0445\u043e\u0434\u043d\u044b\u043c\u0438 \u0434\u0430\u043d\u043d\u044b\u043c\u0438 \u0434\u043b\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438. \u042f\u0441\u043d\u043e, \u0447\u0442\u043e \u044d\u0442\u0438 \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0438 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0441\u043a\u043e\u043b\u044c \u0443\u0433\u043e\u0434\u043d\u043e \u00ab\u043f\u043b\u043e\u0445\u0438\u043c\u0438\u00bb: \u0441 \u043d\u0435\u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u044b\u043c \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e\u043c \u0442\u0440\u0435\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430 \u0438 \u043c\u043d\u043e\u0433\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430\u043c\u0438, \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u2014 \u0435\u0449\u0451 \u0438 \u043d\u0435\u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u044b\u0435.<\/p>\n<p>  <\/p>\n<p>\u0427\u0442\u043e\u0431\u044b \u043e\u0442\u0447\u0430\u0441\u0442\u0438 \u043e\u0431\u044a\u044f\u0441\u043d\u0438\u0442\u044c, \u043a\u0430\u043a \u043c\u043e\u0433\u0443\u0442 \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0435, \u0441 \u043a\u043e\u0442\u043e\u0440\u044b\u043c\u0438 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0442\u044c\u0441\u044f \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u044f\u0445, \u044f \u0441\u043e\u0431\u0440\u0430\u043b <a href=\"https:\/\/github.com\/yandex\/agglomerative_clustering\/blob\/master\/data\/doc.similarities.tar.gz\">\u0432\u0442\u043e\u0440\u043e\u0439 \u043d\u0430\u0431\u043e\u0440 \u0434\u0430\u043d\u043d\u044b\u0445<\/a>. \u041e\u043d \u043f\u043e\u043b\u0443\u0447\u0435\u043d \u0432 \u0445\u043e\u0434\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043e\u0434\u043d\u043e\u0439 \u0438\u0437 \u0430\u043d\u0430\u043b\u0438\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0437\u0430\u0434\u0430\u0447, \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0431\u0435\u0437 \u0440\u0430\u0437\u043c\u0435\u0442\u043a\u0438 \u0438 \u0441\u043b\u0443\u0436\u0438\u0442 \u0438\u0441\u043a\u043b\u044e\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0431\u044b\u0441\u0442\u0440\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432.<\/p>\n<p>  <\/p>\n<pre><code class=\"plaintext\">cmake -DCMAKE_BUILD_TYPE=release . cmake --build . tar zxvf data\/doc.similarities.tar.gz .\/agglomerative_clustering &lt; doc.similarities.tsv &gt; doc.clusters.tsv<\/code><\/pre>\n<p>  <\/p>\n<p>\u041f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0440\u0430\u0431\u043e\u0442\u044b \u0432\u044b\u0432\u043e\u0434\u0438\u0442 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0440\u0430\u0437\u043d\u044b\u0445 \u044d\u0442\u0430\u043f\u043e\u0432:<\/p>\n<p>  <\/p>\n<pre><code class=\"plaintext\">loaded 5000000 pairs loading documents: finished in 11.323s clustering documents: finished in 28.653s printing clusters: finished in 0.038s<\/code><\/pre>\n<p>  <\/p>\n<p>\u0412 \u044d\u0442\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0437\u0430\u0434\u0430\u0447\u0430 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438 301 836 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0441 \u043f\u044f\u0442\u044c\u044e \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u0430\u043c\u0438 \u0441\u0432\u044f\u0437\u0435\u0439 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u043e\u043a\u043e\u043b\u043e \u043f\u043e\u043b\u0443\u043c\u0438\u043d\u0443\u0442\u044b \u043d\u0430 \u043c\u043e\u0435\u0439 \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u043e\u0439 \u043c\u0430\u0448\u0438\u043d\u0435. \u0422\u0430\u043a\u043e\u0433\u043e \u0431\u044b\u0441\u0442\u0440\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f \u0431\u043e\u043b\u0435\u0435 \u0447\u0435\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0432 \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u044f\u0445, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0440\u0430\u0437\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u043b\u0441\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u041f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0443 \u043c\u043e\u0436\u043d\u043e \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u0437\u0430 \u0441\u0447\u0451\u0442 \u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u0438\u0437\u043c\u0430 \u0438 \u0445\u0430\u0440\u0434\u043a\u043e\u0440\u043d\u044b\u0445 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0439, \u043d\u043e \u0440\u0430\u0441\u0441\u043a\u0430\u0437 \u043e \u043d\u0438\u0445 \u0442\u044f\u043d\u0435\u0442 \u043d\u0430 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u043f\u043e\u0441\u0442.<\/p>\n<\/div>\n<p> \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\/company\/yandex\/blog\/503492\/\"> https:\/\/habr.com\/ru\/company\/yandex\/blog\/503492\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text-html post__text_v1\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/company\/yandex\/blog\/503492\/\">\n<p><a href=\"https:\/\/habr.com\/ru\/company\/yandex\/blog\/503492\/\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/fl\/1q\/ou\/fl1qoudw9osgmptmcokjrruskws.png\"><br \/>  <\/a><\/p>\n<p>  <\/p>\n<p>\u041d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043b\u0435\u0442 \u043d\u0430\u0437\u0430\u0434 \u043c\u043d\u0435 \u043f\u043e\u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u043e\u0447\u0435\u043d\u044c \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043d\u0435\u043f\u043b\u043e\u0442\u043d\u044b\u0435 \u0433\u0440\u0430\u0444\u044b \u0441\u0440\u0435\u0434\u043d\u0435\u0433\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430 (\u0441\u043e\u0442\u043d\u0438 \u0442\u044b\u0441\u044f\u0447 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432, \u0441\u043e\u0442\u043d\u0438 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043e\u0432 \u0441\u0432\u044f\u0437\u0435\u0439). \u0422\u043e\u0433\u0434\u0430 \u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c, \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0441 \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u043c \u043d\u0430\u0431\u043e\u0440\u043e\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432 \u043f\u0440\u043e\u0441\u0442\u043e \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u043d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u0432\u0441\u0451 \u0440\u0430\u0437\u043d\u043e\u043e\u0431\u0440\u0430\u0437\u0438\u0435 \u043c\u0435\u0442\u043e\u0434\u043e\u0432, \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043d\u043d\u044b\u0445 \u0447\u0435\u043b\u043e\u0432\u0435\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u0437\u0430 \u043c\u043d\u043e\u0433\u0438\u0435 \u0434\u0435\u0441\u044f\u0442\u0438\u043b\u0435\u0442\u0438\u044f. \u0418\u043c\u0435\u044e\u0449\u0438\u0435\u0441\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0440\u0430\u0431\u043e\u0442\u0430\u043b\u0438 \u043b\u0438\u0431\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u043b\u043e\u0445\u043e, \u043b\u0438\u0431\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u043b\u043e\u0445\u043e \u0438 \u043a \u0442\u043e\u043c\u0443 \u0436\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e.<\/p>\n<p>  <\/p>\n<p>\u041a \u0441\u0447\u0430\u0441\u0442\u044c\u044e, \u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c, \u0447\u0442\u043e \u0438\u0434\u0435\u0438, \u0437\u0430\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0435 \u0432 \u043c\u0435\u0442\u0440\u0438\u043a\u0438 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0430 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438, \u043e \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u044f <a href=\"https:\/\/habr.com\/ru\/company\/yandex\/blog\/500742\/\">\u0440\u0430\u0441\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u043b \u0432 \u043f\u0440\u043e\u0448\u043b\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435<\/a>, \u043c\u043e\u0436\u043d\u043e \u0430\u0434\u0430\u043f\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438 \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043d\u0430 \u0438\u0445 \u043e\u0441\u043d\u043e\u0432\u0435 <em>\u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c<\/em> \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438. \u041e\u043d \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442 \u043e\u0447\u0435\u043d\u044c \u0432\u044b\u0441\u043e\u043a\u0438\u0445 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0430 \u0438 \u043a \u0442\u043e\u043c\u0443 \u0436\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043e\u0447\u0435\u043d\u044c \u0431\u044b\u0441\u0442\u0440\u043e \u0431\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0443\u0434\u0430\u0447\u043d\u044b\u043c \u0430\u043d\u0430\u043b\u0438\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u043c \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u0435\u043c\u044b\u0445 \u0432\u0435\u043b\u0438\u0447\u0438\u043d. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a \u043a\u043b\u0430\u0441\u0441\u0443 <em>\u0430\u0433\u043b\u043e\u043c\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u044b\u0445<\/em>: \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0435\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u043b\u0438\u044f\u043d\u0438\u0435 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u0443\u0436\u0435 \u0438\u043c\u0435\u044e\u0449\u0438\u0445\u0441\u044f \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432 \u0432 \u043e\u0434\u0438\u043d \u0431\u043e\u043b\u0435\u0435 \u043a\u0440\u0443\u043f\u043d\u044b\u0439 \u043a\u043b\u0430\u0441\u0442\u0435\u0440.<\/p>\n<p>  <\/p>\n<p>\u041e\u0431 \u044d\u0442\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u0438 \u043f\u043e\u0439\u0434\u0451\u0442 \u0440\u0435\u0447\u044c \u0432 \u0441\u0442\u0430\u0442\u044c\u0435. \u041f\u043e\u0434 \u043a\u0430\u0442\u043e\u043c \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u0435\u0439 \u0436\u0434\u0443\u0442 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u0442\u0435\u0445\u043d\u0438\u043a\u0438 \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u043d\u0438\u044f \u0435\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438, \u043a\u043e\u0434 \u043d\u0430 GitHub \u0438 \u043c\u043e\u0434\u0435\u043b\u044c\u043d\u044b\u0435 \u043d\u0430\u0431\u043e\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445.<\/p>\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-305198","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/305198","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=305198"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/305198\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=305198"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=305198"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=305198"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}