Мера расстояния

Сходство или различие между объектами классификации устанавливается в зависимости от выбранного метрического расстояния между ними. Если каждый объект описывается i свойствами (признаками), то он может быть представлен как точка в i-мерном пространстве, и сходство с другими объектами будет определяться как соответствующее расстояние. При классификации используются различные меры расстояния между объектами.

1. Евклидово расстояние

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

P~=~sqrt{sum{i=~1}{N}{(~A_{i}~-~B_{i})^{2}}}

где:

  • P – расстояние между объектами A и B;
  • A_{i} – значение i-свойства объекта A;
  • B_i – значение i-свойства объекта B.

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

  • свойства (признаки) объекта однородны по физическому смыслу и одинаково важны для классификации;
  • признаковое пространство совпадает с геометрическим пространством.

2. Квадрат евклидова расстояния

Данная мера расстояния используется в тех случаях, когда требуется придать больше значение более отдаленным друг от друга объектам. Это расстояние вычисляется следующим образом:

P~=~sum{i=~1}{N}{(~A_{i}~-~B_{i})^2}

3. Взвешенное евклидово расстояние

Применяется в тех случаях, когда каждому i-свойству удается приписать некоторый «вес» w_i{}, пропорционально степени важности признака в задаче классификации:

P~=~sqrt{sum{i=~1}{N}{w_{i}(A_{i}~-~B_{i})^{2}}}

Определение весов, как правило, связано с дополнительными исследованиями, например, организацией опроса экспертов и обработкой их мнений.

4. Хеммингово расстояние

Также называется манхэттенским, сити-блок расстоянием или расстоянием городских кварталов. Это расстояние является разностью по координатам. В большинстве случаев эта мера расстояния приводит к таким же результатам, как и для обычного расстояния Евклида. Однако отметим, что для этой меры влияние отдельных больших разностей (выбросов) уменьшается (так как они не возводятся в квадрат). Хеммингово расстояние вычисляется по формуле:

P~=~sum{i=~1}{N}{(delim{|}{~A_{i}}{|}~-~delim{|}{~B_{i}}{|})}

5. Расстояние Чебышева

Принимает значение наибольшего модуля разности между значениями соответствующих свойств (признаков) объектов:

P~=~MAX~delim{|}{~A_{i}~-~B_{i}}{|}

6. Процент несогласия

Эта мера расстояния используется в тех случаях, когда свойства (признаки) объекта являются категориальными:

P~=~VALUE~delim{|}{~A_{i}~<>~~B_{i}}{|}

Например, первый признак объекта – пол, второй – возраст, третий – место работы. Представим значения свойств (признаков) объекта в виде вектора значений. Первый вектор – (муж, 20 лет, учитель), второй вектор – (муж, 28 лет, менеджер). Процент несогласия равен 2/3. Эти вектора различаются на 66.6%.

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

Это интересно

Смотрите также