29.09.2026 13:07
DDPronin 0 7500 Источник

Представим, что kNN отнес новую точку к некоторому классу. Пусть для простоты это будет 1-NN, в котором решение базируется на одном ближайшем соседе. Возьмем точку q=(0.1; 0) и двух кандидатов: a=(-0.6; -0.6) из класса A и b=(1.5; 1) из класса B. Расстояние до a около 0.92, до b около 1.72. Наименьшее расстояние выбрано, ответ получен. Однако знакомая схема скрывает интересную недосказанность. Какие именно признаки сделали A ближе? Возможно, почти всю разницу дал сигнал от одной координаты, возможно это вклад весьма конкретного набора координат, который можно интерпретировать как устойчивый признак более высокого порядка, а может, эти вклады распределены почти равномерно?

Аналогичный вопрос возникает и в кластеризации, например, при использовании k‑means. Алгоритм относит точку к ближайшему центру кластера. Но почему определенная точка попадает именно в свой кластер? Какие признаки на это влияют в большей мере?

На самом деле ответить на вопросы выше довольно легко. Для этого достаточно сохранить слагаемые, из которых получилось расстояние, перед тем, как «затирать» их суммированием.

На схеме слева точка сравнивается с соседями в 1-NN, справа с центрами в k-means. В обоих случаях можно посмотреть, что дала каждая координата.
На схеме слева точка сравнивается с соседями в 1-NN, справа с центрами в k‑means. В обоих случаях можно посмотреть, что дала каждая координата.

Разложение манхэттенского и евклидового расстояния

Пусть у нас есть два вектора признаков, x=(x_1,\ldots,x_n) и y=(y_1,\ldots,y_n). С разложением манхэттенского расстояния на слагаемые никаких проблем не возникает:

l_1(x,y)=\sum_{i=1}^{n}|x_i-y_i|.

Каждый модуль суммы |x_i-y_i| и является абсолютным вкладом координаты в расстояние. Иногда для сравнения долей нужен относительный вклад, который можно получить делением вклада по координате на целое расстояние: \frac{|x_i-y_i|}{l_1(x,y)}

Для квадрата евклидова расстояния картина похожая. При поиске ближайшего соседа корень можно опустить, так как он не меняет порядок расстояний и соседства.

l_2^2(x,y)=\sum_{i=1}^{n}(x_i-y_i)^2.

Обычный k‑means минимизирует именно сумму таких квадратов до центров кластеров. Вклад координаты равен ее квадрату разности, и эти вклады складываются в квадрат расстояния:

\delta_i=(x_i-y_i)^2,\qquad \sum_{i=1}^{n}\delta_i=l_2^2(x,y).

Формулы выше помогают разложить расстояние между двумя объектами. В нашем примере для 1-NN квадраты расстояний от q до a и b равны 0.85 и 2.96. Разница 2.11 складывается из 1.47 по первой координате и 0.64 по второй. Обе поддерживают выбор a.

Теперь рассмотрим центроиды c_A и c_B, найденные k‑means. Компонент суммы(c_{A,i}-c_{B,i})^2 говорит, насколько признак i раздвинул сами центры. Если интересует, какие признаки внесли больший вклад в то, что точка x попала в кластер A, сравниваем расстояния от нее до обоих центров уже по такой формуле:

m_i=(x_i-c_{B,i})^2-(x_i-c_{A,i})^2.

Положительные слагаемые тянут точку в кластер A, а отрицательные — в кластер B. Эти два варианта разложения стоит рассматривать отдельно.

import numpy as np

q = np.array([0.1, 0.0])
neighbor_a = np.array([-0.6, -0.6])
neighbor_b = np.array([1.5, 1.0])
center_a = np.array([-1.4, -0.85])
center_b = np.array([1.775, 1.35])

for_neighbors = (q - neighbor_b) ** 2 - (q - neighbor_a) ** 2
between_centers = (center_a - center_b) ** 2
for_this_point = (q - center_b) ** 2 - (q - center_a) ** 2

print("1-NN:", np.round(for_neighbors, 2), round(for_neighbors.sum(), 2))
print("Центры:", np.round(between_centers, 2), round(between_centers.sum(), 2))
print("Точка и центры:", np.round(for_this_point, 2), round(for_this_point.sum(), 2))

Как быть с косинусным расстоянием?

Косинусное расстояние очень популярно и особенно эффективно в задачах, связанных с текстами и естественным языком. Можно ли также выделить компоненты из него? Да, только сначала разделим каждый вектор на его длину: u=\frac{x}{\lVert x\rVert_2}, v=\frac{y}{\lVert y\rVert_2}. После этого косинусное расстояние примет компактный вид:

d_{\cos}(x,y)=1-\sum_{i=1}^{n} u_i v_i.

Единицу в начале, как константу, можно убрать так как она сокращается при сравнении расстояний и не влияет на соседства точек. Тогда, по принципу, показанному ранее, вклад признака в косинусное расстояние можно записать как \delta_i=-u_i v_i. Если сложить такие вклады, получится:

d_{\cos}(x,y)=1+\sum_{i=1}^{n}\delta_i.

Положительное \delta_i, возникающее, когда у координат разные знаки, увеличивает расстояние, отрицательное, наоборот, уменьшает.

Что делать с другими мерами расстояния и где это можно применить?

Рассмотрим «мешок слов», классический для NLP способ представления текста. Каждому слову из общего словаря соответствует координата. В нее можно записать число употреблений, относительную частоту слова TF или вес TF‑IDF, который учитывает также распространенность слова в других документах. Наглядное объяснение с примерами кода есть в обзоре способов векторизации текста на Хабре.

На этих подходах построена одна из идей стилометрии, дисциплины цифровых гуманитарных наук (Digital Humanities), изучающей способы определения авторства анонимных текстов. Это может быть полезно как при атрибуции художественных произведений, так и в криминалистике, когда нужно определить написано ли завещание или какой‑то иной важный документ определенным человеком. Известный пример стилометрической атрибуции связан с романом «Зов кукушки», опубликованным под именем Роберта Гэлбрейта. Получив подсказку о возможном авторе, журналисты попросили исследователей сравнить роман с книгами Дж. К. Роулинг и других писателей. Стилометрический анализ указал на Роулинг как на самого вероятного автора среди проверенных кандидатов, что, в итоге, оказалось правдой.

Начнем с классической для стилометрии Delta Берроуза. Берем общий словарь из n слов и для каждого текста считаем относительную частоту каждого слова. Относительную, чтобы длинный роман не получал большие координаты просто из‑за числа страниц. Затем частоты стандартизируем:

z_i(T)=\frac{f_i(T)-\mu_i}{\sigma_i},

где f_i(T) обозначает относительную частоту слова i в тексте T, а \mu_i и \sigma_i считаются по корпусу текстов. Значение z_i(T) показывает, насколько употребление слова в этом тексте отклоняется от корпусной нормы в единицах стандартного отклонения. У частотного «и» и менее частотного «давеча» теперь сопоставимый масштаб.

Дальше мы уже знаем, что делать. Берем манхэттенское расстояние между двумя z‑векторами и делим его на число слов.

\Delta_{\mathrm B}(T_1,T_2)=\frac1n\sum_{i=1}^{n}|z_i(T_1)-z_i(T_2)|.

Здесь вклад слова виден сразу: \delta_i=|z_i(T_1)-z_i(T_2)|/n. Сложим вклады всех слов и получим Delta Берроуза. Если слово у двух авторов отклоняется от корпусной нормы по‑разному, его вклад будет большим.

Манхэттенское расстояние можно заменить. Евклидова Delta, например, сначала складывает (z_i(T_1)-z_i(T_2))^2, затем берет корень. Крупные расхождения по отдельным словам влияют на нее сильнее. Cosine Delta сравнивает направления векторов частотных профилей. Ее знаковые вклады -u_i v_i мы разобрали выше.

Для Jensen‑Shannon Delta профили нужно подготовить иначе. Берем неотрицательные частоты, делим частоту каждого слова на его корпусное стандартное отклонение и нормируем полученный вектор до суммы 1. Получаются два распределения весов слов, p и q. Вклад слова в расхождение Йенсена‑Шеннона равен

\delta_i^{\mathrm{JS}}=\frac12p_i\log_2\frac{p_i}{m_i}+\frac12q_i\log_2\frac{q_i}{m_i},\qquad m_i=\frac{p_i+q_i}{2}.

Сумма этих неотрицательных вкладов дает полное расхождение.

Более сложный Rank‑Turbulence Delta основан на работе Питера Доддса и соавторов. Здесь сравниваются ранги слов в частотных списках двух профилей. Например, слово может занимать 10-е место у одного автора и 100-е у другого. Это изменение ранга даст ему вклад в общее расхождение. Общая величина снова складывается из вкладов отдельных слов.

Посмотрим, что получается на настоящих текстах. В исследовании мы усреднили профили произведений Ф. М. Достоевского и Л. Н. Толстого, затем посчитали расстояние между двумя авторскими профилями четырьмя способами.

На четырех фрагментах графика покомпонентного разложения показаны слова с наибольшими вкладами в расстояния между авторскими частотными профилями. Достоевский выделен оранжевым, Толстой синим. Направление полосы показывает, у какого автора слово характернее
На четырех фрагментах графика покомпонентного разложения показаны слова с наибольшими вкладами в расстояния между авторскими частотными профилями. Достоевский выделен оранжевым, Толстой синим. Направление полосы показывает, у какого автора слово характернее

Видно, что Дельта Берроуза (по сути манхэттенское расстояние) и Йенсен‑Шеннон работают очень схоже, а в косинусе расстояние порождается несколько иными словами. В Rank‑Turbulence наверх выходят в том числе «и» и «на». Мы видим, на какие различия «обращает внимание» каждая мера, что позволяет глубже понять ее работу и осознаннее выбрать способ сравнения текстов.

В случае стилометрии, если неизвестный текст оказался ближе к автору A, чем к автору B, исследователь может посмотреть, чем обеспечен перевес. Это могут быть особенности словоупотребления, частотные служебные слова, а при работе с сочетаниями слов и устойчивые обороты.

Разложение помогает и при верификации результата. Найденные слова можно найти в самих текстах, изучив контексты употребления. Связаны ли эти слова с манерой автора или, например, с сюжетом конкретной книги? Так цифровой филолог может точнее связывать численное различие со стилистическими особенностями автора. В отдельной проверке на 31 тексте мы увеличили словарь с 3000 до 3200 слов: для Delta Берроуза пересечение топ-30 вкладов по коэффициенту Жаккара составило 0.875. Затем обнулили 50 слов с наибольшими вкладами и пересчитали расстояние между авторскими профилями: оно снизилось с 0.429 до 0.394. Этот эксперимент позволяет оценить стабильность самого результата и понять, создается ли он несколькими неустойчивыми признаками или это влияние большого количества координат.

Вот так простое покомпонентное разложение превращает ответ в проверяемый и воспроизводимый список слов. По нему можно увидеть языковые привычки авторов, проследить логику работы самой меры расстояния, найти возможные помехи и выбрать фрагменты для внимательного чтения.

Подробные формулы и эксперименты приведены в нашей статье о Rank‑Turbulence Delta, опубликованной в Digital Scholarship in the Humanities, а код и данные лежат в репозитории.

Комментарии (0)