Page 207 - 4496

де X, Y - двійкові вектори, Х t, У t - транспоновані вектори
(вектори-рядки).
При обчисленні ознак можливі помилки, які
спотворюють істинне значення вектора і можуть привести до
невірної класифікації. При цьому одиночна помилка
приводить до спотворення будь-якого одного розряду
двійкового вектора, подвійна - будь-яких двох розрядів і т.д.
Хай для класифікації вибрано n двійкових ознак, а попередні
експерименти показують, що одиночні, подвійні і навіть
потрійні помилки мають помітну величину, а помилками
більшої кратності можна нехтувати через їх малу вірогідність.
Оцінимо розміри кластерів і знайдемо грубу оцінку
можливого числа кластерів за наявності n ознак.
Вектор одиночної помилки є двійковим n-розрядним
кодом, що містить одну одиницю (решта розрядів нульова).
Вектор подвійної помилки містить дві одиниці, вектор
потрійної помилки - 3 одиниці. Загальне число векторів
одиночних, подвійних і потрійних помилок рівне:

Якщо помножити набуте значення числа векторів
помилок на можливе число кластерів, то одержане число
повинен бути істотно менше ніж загальна кількість n-
розрядних векторів. З цих міркувань одержуємо оцінку:

Звідки число можливих кластерів:

Так, при n = 10 число кластерів K << 7.
Аналогічні оцінки використовуються для визначення
меж в теорії кодування.

5.19.7 Теорія графів

204