Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

АЛГОРИТМ КУДРЯВЦЕВА ГОЛОСУВАННЯ ПО ТЕСТАХ

Нехай {1,2, ..., п} - безліч ознак. Домовимося підмножина т з {1,2, ..., п} позначати булевих вектором t = (? I, ...,? N ), маючи на увазі, що ознака г € т точно тоді, коли U = 1.

Нехай як і раніше Т = {а, = (а я , ..., a jn ): j = 1,2, ..., 774},

Т2 = {6 ^ = (6jfi, ... t bj n ): j = 1,2, .. *., 7712} - безлічі елементів навчальної вибірки, що належать класам До і К _2 відповідно.

Позначимо Т = Т (Т, Т 2 ) - * опорна множина тестів для навчальної вибірки 7i, 7a. В якості опорного безлічі Т 'можуть виступати, наприклад, безліч всіх тестів, безліч тупикових тестів, або безліч тестів фіксованою довжини.

Якщо а = (ai, ..., o n ) - елемент навчальної вибірки, t = ($ 1 / ...,? П ) € Т - деякий тест, а х = (х ь ..., х п ) - об'єкт, що підлягає класифікації, то скажемо, що mecm t голосує за елемент а на об'єкті х, якщо

тобто на ознаках з тіста t об'єкти а й х збігаються.

тоді суму

можна інтерпретувати як інтеграл голосування безлічі Tj, j = 1,2, а многочлен

є інтегральний голос всього опорного безлічі тестів Т за клас Kj 9 j = 1,2.

Многочлен R (x) = Гг (х) - Ti (x) називається многочленом голосування.

Алгоритм голосування по тестах, запропонований В.Б.Кудрявцевим, полягає в тому, що на об'єкті х, що підлягає класифікації, обчислюється многочлен голосування R (x), і якщо Л (х) <0, то х належить до класу ^, ик класу до 2 - в іншому випадку.

Розглянемо многочлен ri (x). Розкриваючи дужки в творах, отримаємо

Візьмемо лінійну частину цього многочлена по змінним

Zji = | xi - dj'ij:

Порівнюючи отримане з (1.4) і (1.5), можемо помітити, що відомий алгоритм Л є лінійним наближенням многочлена голосування.

Алгоритм голосування по тестах передбачає вміння перераховувати всі тупикові тести. У роботах [3, 5, 15, 16] наводяться асимптотично оптимальні алгоритми перерахування всіх тестів.

В роботі [20] показано, що якщо в якості опорного безлічі брати безліч "коротких" тестів (тестів, потужність яких близько logn), то алгоритм голосування стає не тільки значно менш трудомістким, але і більш надійним.

За допомогою тестових алгоритмів були успішно вирішені багато практичні завдання розпізнавання, зокрема геологічні завдання з оцінки запасів руди і подібні до них [26, 28, 29, 34, 64].

Так, дослідження ртутних родовищ дозволило дати практичні рекомендації щодо необхідності постановки геолого-розвідувальних робіт по деяким маловивченим родовищ Північного Сходу СРСР; за матеріалами Приморського геологічного управління про родовища олова Примор'я були отримані високі оцінки масштабів оруднення деяких маловивчених родовищ, що в подальшому підтвердилося під час перевірки розвідувальними роботами. На двох родовищах (Південному і Смирновскую) було встановлено, що рудні тіла, порівняно бідні оловом на поверхні, на глибині переходять в багаті руди з високим вмістом олов'яного каменю.

 
<<   ЗМІСТ   >>