Распознавание образов
При принятии решений и оценке их качества широко применяются комбинаторные методы. При информационном поиске, нозологии (классификации болезней) и таксономии (классификации видов животных и растений) широко применяются наборы двоичных признаков. При этом каждый класс характеризуется некоторым двоичным вектором и областью изменения этого вектора, что в совокупности составляет кластер. Расстояние между центрами кластеров, а также от классифицируемого вектора до центров всех кластеров определяется мерой сходства, называемой мерой Танимото:
где X, Y - двоичные векторы, - транспонированные векторы (векторы-строки).
При вычислении признаков возможны ошибки, которые искажают истинное значение вектора и могут привести к неверной классификации. При этом одиночная ошибка приводит к искажению любого одного разряда двоичного вектора, двойная - любых двух разрядов и т. д. Пусть для классификации выбрано n двоичных признаков, а предварительные эксперименты показывают, что одиночные, двойные и даже тройные ошибки имеют заметную величину, а ошибками большей кратности можно пренебречь из-за их малой вероятности. Оценим размеры кластеров и найдем грубую оценку возможного числа кластеров при наличии n признаков.
Вектор одиночной ошибки представляет собой двоичный n-разрядный код, содержащий одну единицу (остальные разряды нулевые). Вектор двойной ошибки содержит две единицы, вектор тройной ошибки - 3 единицы. Общее число векторов одиночных, двойных и тройных ошибок равно:
Если умножить полученное значение числа векторов ошибок на возможное число кластеров, то произведение должно быть существенно меньше, чем общее количество n-разрядных векторов. Из этих рассуждений получаем оценку:
Откуда число возможных кластеров
Так, при n = 10 число кластеров К « 7.
Аналогичные оценки используются для определения границ в теории кодирования.
Упражнения
1. Вектор двоичных признаков содержит 12 компонент (12-разрядный двоичный вектор). Одиночная ошибка искажает вектор. Сколько различных ошибочных векторов при этом может быть получено? Для конкретного вектора: 100111010010 выпишите все ошибочные векторы.
2. На кодовое слово длины 16 действует пакет ошибок (ошибки группируются подряд, но не превышают 5 разрядов). Подсчитайте число возможных искажений кодового слова. Обобщите результат на n-разрядное кодовое слово и на максимальный размер пакета ошибок в k разрядов.
3. Пусть имеются два вектора, соответствующие центрам кластеров: X: 10111001 и Y: 00101111. Вычислите меру Танимото, определяющую расстояние между этими кластерами. Если вектор X принять за исследуемый вектор, а в векторе Y допускать одиночные искажения признаков, то можно определить минимальное расстояние до границ кластера. Найдите все векторы кластера с центром Y и определите минимальное расстояние между X и "ближайшим" к нему вектором из кластера Y.
