Internet Портал МЭИ(ТУ)
Июль 2019
Пн Вт Ср Чт Пт Сб Вс
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31

Меры близости и расстояния

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

При определении понятия классификация отмечалось, что разбиение выборки на классы производится исходя из “близости” документов. С целью формализации понятия  “близость” вводятся метрики расстояния и меры близости.

Так как векторная модель представления текстовых документов позволяет представить их в виде точек в M–мерном пространстве, то для оценки  “близости” можно применять известные в аналитической геометрии соотношения, предполагая, что геометрическая близость двух (или нескольких) точек в  M–мерном пространстве будет означать их похожесть и однородность.

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

Евклидово расстояние (L2–метрика). Это наиболее часто используемая метрика, соответствующая простому геометрическому расстоянию в многомерном пространстве. Евклидово расстояние определяется по формуле:

    

 

Квадрат евклидова расстояния. В ряде случаев для придания большего веса различию между признаками евклидово расстояние возводится в квадрат:

      

 
Расстояние городских кварталов (манхэттенское расстояние) (L1метрика). Эта метрика представляет собой сумму разностей по координатам. В большинстве случаев она приводит к таким же результатам, как и в случае использования обычного евклидова расстояния, хотя влияние отдельных больших разностей в значении признаков уменьшается. Манхэттенское расстояние вычисляется по формуле:

    

 
Расстояние Чебышева (L∞метрика). Такое расстояние может оказаться полезным, когда необходимо определить два объекта в разные классы в зависимости от различий между ними по одному наиболее значимому признаку. Расстояние Чебышева вычисляется по формуле:

      

 
Кроме того, для определения “близости” между текстовыми документами  часто используется косинусоидальная мера близости (косинус угла между векторами):
В отличие от метрик расстояния, которые для наиболее похожих документов будут стремиться к нулю, косинусоидальная мера близости в этом случае будут стремиться к единице.

Расстояние городских кварталов обычно эффективно используется для бинарных признаков, а расстояние Чебышева в том случае, когда существует один признак, по которому можно осуществить эффективное разделение классов. Такая “специализация” метрик L1 иLсущественно ограничивает возможность их  применения в задачах классификации текстовой информации.

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

 

 

Вход для преподавателей



Мы находимся:
МЭИ, корпус М, 3-й этаж.
Телефон: (+7 495) 362-74-07
Кафедра управления и информатики МЭИ
Сайт создан и поддерживается лабораторией интеллектуальных информационных систем (ЛИИС) УиИ