Расстояние Хэмминга (Hamming distance) Скачать в PDF

Синонимы: Кодовое расстояние

Разделы: Метрики

В теории информации и анализе данных расстояние Хэмминга между двумя строками или векторами одинаковой длины — это количество позиций, в которых соответствующие символы различны. Таким образом, для векторов $X=(x_1,x_2,...,x_n)$ и $Y=(y_1,y_2,...,y_n)$ оно может быть записано в виде:

$d_H(X,Y)=\sum _{i=1}^n\delta (x_i,y_i)$,

где $\delta (x_i,y_j)=\{\begin{array}{cc}0,& x_i=y_i\\ 1,& x_i\ne y_i\end{array}$

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

Справедливо, $d_H(X,Y)⩽n$, т.е. расстояние Хэмминга всегда меньше длины векторов (строк), между которыми оно измеряется.

В более общем контексте расстояние Хэмминга — это одна из нескольких строковых метрик для измерения расстояния редактирования между двумя последовательностями. Оно названо в честь американского математика Ричарда Хэмминга.

Например, пусть $X=\left(01011\right)$, а $Y=\left(11010\right)$, тогда $d_H(X,Y)=2$.

С помощью расстояния Хемминга можно представлять степень близости друг к другу категориальных величин. Например, закодируем с помощью унитарного кода слова:

Несложно увидеть, что расстояние между словами будет равно 2. Если для двух строк $d_H=1$, то говорят, что они являются соседними.

Определение степени близости категориальных значений с помощью расстояния Хэмминга открывает возможность для их использования в машинном обучении, в частности, в алгоритмах классификации и кластеризации.