і те, що дані класифікатори компактніші, в порівнянні з деревами. p> Ідея ДНФ-методів полягає у відборі з усіляких покривають правил (правил, які коректно класифікують всі навчальні документи) В«найкращеВ» правило з точки зору деякого критерію мінімальності. У той час як дерева прийняття рішень зазвичай будуються зверху вниз за допомогою стратегії "розділяй і володарюйВ», ДНФ-правила часто формуються знизу вгору. На початку індуктивного процесу побудови класифікатора для категорії кожен навчальний документ являє собою твердження виду, де це терміни документа з навчальної множини, а одно її доповненню. Цей набір тверджень вже є ДНФ-класифікатором для ci, але очевидно, що в такому вигляді він схильний до ефекту перенавчання. Тому процес навчання включає в себе стадію генералізації, в ході якої правила спрощуються, проходячи через серію модифікацій (скорочення посилок тверджень, злиття тверджень). Це робить правила більш компактними і, в той же час, не порушує властивості покриваемості класифікатора. На завершення цього процесу, як і в випадку з деревами, виконується стадія усічення, в результаті якої підвищується узагальнююча здатність класифікатора. p> Кожен навчається алгоритм на основі правил прийняття рішень може сильно відрізнятися в методах і критеріях генералізації і усічення. Ось кілька індуктивних навчаються стандартних ДНФ-алгоритмів побудови класифікатора: Charade, DL-ESC, Ripper, Scar і Swap-1. br/>
4.5 Моделі регресії
Для побудови текстового класифікатора можна застосовувати моделі регресії. Регресія тут означає апроксимацію бінарної цільової функції функцією, значеннями якої є дійсні числа. В якості такої регресійної моделі може виступати, наприклад, метод найменших квадратів (МНК). p> У МНК з кожним документом асоційоване два вектори:
В· Вихідний вектор, який є стандартним вектором ваг термінів з безлічі
В· Результуючий вектор, складений з ваг, що характеризують приналежність документа до категорій (для документів навчальної множини, ваги вектора мають бінарні значення, для документів тестового безлічі - не бінарні)
У такому разі, завдання побудови класифікатора зводиться до знаходження для документа результуючого вектора з даного вихідного вектору. Тобто побудова класифікатора полягає в обчисленні матриці () такий, що. Дана матриця обчислюється за допомогою МНК на основі навчальних даних, мінімізуючи помилку за такою формулою:
В
де:
В· - норма Фробеніуса для матриці розміром
В· - матриця, складена з вихідних векторів навчальних документів
В· - матриця, складена з результуючих векторів навчальних документів
Матриця зазвичай обчислюється за допомогою сингулярного розкладання векторів навчальної множини. Елементи знайденої матриці характеризують ступінь ассоциированности категорії і терміна. p> Експерименти показують, що МНК є о...
