Байесовский наивный классификатор. Пример реализации на php

В своё время для классификации объектов мною был пару раз использован наивный байесовский классификатор, но написать заметку (больше для себя), в которой систематизировать полученный опыт у меня дошли руки только сейчас.

Тут не будет рассмотрена вся математика, лежащая в основе этого мощного инструмента. Так что на неровности в использовании терминов внимания не заостряйте ;-). Будет дан пример конкретной реализации. Конкретно на классификации дополнительных соглашений к договорам по типам, основываясь на имени записи. Так уж получилось, что предыдущий разработчик информационной системы решил не составлять для них общий справочник, и при стандартизации работы встал вопрос что делать с уже накопленной базой.

Общий принцип работы

  1. На вход классификатора поступает текст на естественном языке
  2. На основе базы обучающих примеров классификатор строит таблицу, в которой перечисляет с какой вероятностью текст относится к одному из заранее определённых классов
  3. На основе таблицы из.п.1 принимается решение к какому классу в итоге текст отнести, либо посчитать, что даже самая большая вероятность принадлежности из таблицы меньше заданного порога и посчитать классификацию несостоявшейся.

Основные части классификатора

Справочник классов

Собственно принадлежность к этим классам и будет выясняться в процессе классификации.

types.inc.php

$types = array();
$types['Расторжение'жение'] = 1;
$types['Перезаключение'] = 2;
$types['Изменение::Повышение цены'] = 3;
$types['Изменение::Уменьшение цены'] = 4;
$types['Изменение::Без изменения цены'] = 5;
$types['Переход продвижение -> техподдержка'] = 6;
$types['Переход техподдержка -> продвижение'] = 7;
$types['Закрытие этапа выдвижения'] = 13;
$types['родление этапа выдвижения'] = 9;
$types[

[свернуть]

 

Обучающие примеры

Данная табличка составляется методом опроса эксперта, который указывает какой текст к какому классу относится. От количества и качества этих примеров в основном и зависит качество классификации. Ключи массива — обучающие фразы, значения — классы из types.inc.php

examples.inc.php

$examples = array();
$examples['Расторжение'жение'] =                                          'Расторжение';
$examples['Заключение нового договора';
$examples['                 'Перезаключение';
$examples['Увеличение цены'] =                                      'Изменение::Повышение цены';
$examples['Закрытие этапа выдвижения'] =                            '; 
$examples['е этапа выдвижения';
$examples['Доп. работы'] =                                          'Дополнительные работы'; 
$examples['Изменение списка слов'] =                                'Изменение::Без изменения цены';
$examples['Расторжение (перезаключение)'] =                         'Перезаключение';
$examples['Заключение договора'] =                                  'Заключение договора';
$examples['Скидка (невыполнение)'] =                                'Изменение::Уменьшение цены';
$examples['Изменение списка слов, увеличение цены'] =               'Изменение::Повышение цены';
$examples['Приостановка'] =                                         'Приостановка';
$examples['Повышение'] =                                            'Изменение::Повышение цены';
$examples['Доп.работы'] =                                           'Дополнительные работы';
$examples['Скидка за невыполнение'] =                               'Изменение::Уменьшение цены';
$examples['Переход на бонус'] =                                     'Изменение::Уменьшение цены';
$examples['Скидка'] =                                               'Изменение::Уменьшение цены';
$examples['Прил.2'] =                                               'Новая рекламная компания';
$examples['Замена стороны в договоре'] =                            'Изменение::Без изменения цены';
$examples['Изменение списка слов, суммы'] =                         'Изменение::Повышение цены';
$examples['Скидка на август'] =                                     'Изменение::Уменьшение цены';
$examples['Скидка на декабрь'Продление этапа выдвижения'            'Изменение::Уменьшение цены';
$examples['Скидка на январь'] =                                 //.......

[свернуть]

Скрипт обучения

Данный скрипт формирует «базу знаний классификатора» — файл bayes.inc.php. Выбор готового php для хранения был сделан, чтобы не усложнять данную статью работой с текстовой или реляционной БД. На более близкой к реальности реализации массивы можно легко заполнить хоть из SQL-СУБД, хоть из бинарных конфигов.

Пара слов о том, что такое лексемы.

Из-за любви наполнявших базу к сокращениям, лексемами мы считаем не только непосредственно отдельные слова классифицируемой фразы, но и их обрезанные формы от 2 до 7 символов с начала слова, например, фраза «Расторжение» разбивается на лексемы: расторжение, ра, рас, раст, расто, растор, расторж. На практике часто берут начальную форму слова в качестве единственной лексемы, но таким инструментом, которые в сокращении «расторж» угадал бы форму «расторжение» я не имею.

learn.php

/************************** Переобучение на примерах **********************/*****// Общие функции
 
    // Общие функции
    r// Примеры для обучения
hp");
    // Примеры для обу// Классы, по которым раскладываем примеры и рабочие варианты
сы, по которым расклады// ======================================================================
("ty// Составляем словарь лексем
====// ======================================================================
оставляем словарь лексем
    // ========================// Разбиваем фразу очередного примера на массив лексем
_lexems = array();
    foreach($examples as $example=>$type){
        // Разбиваем фразу очередного примера на // ======================================================================
fore// Для каждой лексемы словаря формируем список классов, принадлежность 
unt;// к которым наличие лексемы может означать
====// ======================================================================
семы словаря формируем список классов, принадлежность 
    // к которым наличие лексемы может означать
   // ======================================================================
 
   // Вычисляем частоту вхождения лексем в классы
_lex// ======================================================================
      $all_lexems[$lex][$type] = 0;
        }
    }
// Разбиваем фразу очередного примера на массив лексем
===========================
    // Вычисл// Подсчитываем сколько раз какие классы данная лексема входит
сы
    // ======================================================================
    foreach($examples as $example=>$class){
        // Разбиваем фразу очередного прим// ======================================================================
e);
// Вычисляем частоты классов
ае// ======================================================================
а входит
        foreach($lexems as $lex=>$v){
            foreach($all_lexems as $all_lex=>$all_lex_types){
                if($lex==$all_lex)$all_lexems[$lex][$class]++;
           // Подсчитываем сколько всего лексем входило во фразы данного класса
========// при обучении
====
    // Вычисляем частоты классов
    // ======================================================================
// Подсчитываем сколько обучающих примеров было отмечено экспертом как 
      if// принадлежащие этому классу
ame]))
            $types_freq[$type_name] = array("freq"=>0,"lex"=>0);
        // Подсчитываем сколько всего лексем входило во фразы данного класса
        // при обучении
  // общее количество обучающих примеров
ype)
            if($type==$typ// Количество уникальных лексем в обучающей выборке
q"]++;
        // Подсчитыва// ======================================================================
е// Записываем результат обучения в базу знаний
н// ======================================================================
lex_name=>$lex_types)
            foreach($lex_types as $lex_type_name=>$lex_count)
                if ($type_name==$lex_type_name)
                    $types_freq[$type_name]["lex"]+=$lex_count;
    }
 
    // общее количество обучающих примеров
    $D = count($examples);
    // Количество уникальных лексем в обучающей выборке
    $V = count($all_lexems);
 
    // ======================================================================
    // Записываем результат обучения в базу знаний
    // ======================================================================
    $f

[свернуть]

База знаний классификатора

Заполняется запуском скрипта learn.php. выглядит примерно так

bayes.inc.php

$D=238;
$V=763;
$types_freq = array();
$types_freq["Расторжение"жение"]["freq"] = 12;
$types_freq["Расторжение"]["lex"Перезаключение"]["freq"ерезаключение"]["freq"] = 9;
$types_freq["Перезаключение"]["lex"freq"8;
$types_freq["Изменение::Повышение цены"]["freq"] = 23;
$types_freq["Изменение::Повышение цены"]["lex"] = 271;
$types_freq["Изменение::Уменьшение цены"]["freq"] = 56;
$types_freq["Изменение::Уменьшение цены"]["lex"Переход продвижение -> техподдержка"::Без изменения цены"]["freq"] = 22;
$types_freq["]["менение::Без изменения цены"]["lex"] = 251;
$types_freq["Переход продвижение -> техподдержка"]["freq"Закрытие этапа выдвижения"еход продвижение -> техподдержка"]["lex"] = 18;
$types_freq["Переход техподдержка -> продвижение"]["freq"lex"0;
$types_freq["Переход техподдержка -> продвижение"]["lex"] = 0;
$types_freq["Закрытие этапа выдвижения"]["freq"] = 9;
$types_freq["] = 104;
$types_freq["па выдвижения"]["] = 55;
$types_freq["Дополнительные работы" этапа выдвижения"]["freq"][" 3;
$types_freq["Продление этапа выдвижения"]["lex"] = 40;
$types_freq["Разработка"]["Новая рекламная компания"Разработка"]["lex"Заключение договора""Продление срока разработки"]["] = 14;
$all_lexems = array();
$all_lexems[" срока разработки"]["lex"] = 104;
$types_freq["Дополнительные работы"]["freq"] = 55;
$types_freq["Дополнительные работы"]["lex"] = 612;
$types_freq["Приостановка"]["freq"] = 6;
$types_freq["Приостановка"]["lex"] = 80;
$types_freq["Новая рекламная компания"]["freq"] = 20;
$types_freq["Новая рекламная компания"]["lex"] = 55;
$types_freq["Заключение договора"]["freq"] = 1;
$types_freq["Заключение договора"]["lex"] = 14;
$all_lexems = array();
$all_lexems["расторжение"] = array();
$all_lexems["расторжение"]["Расторжение"] = 11;
$all_lexems["расторжение"]["Перезаключение"] = 3;
$all_lexems["расторжение"]["Изменение::Повышение цены"] = 0;
$all_lexems["расторжение"]["Изменение::Уменьшение цены"] = 0;
$all_lexems["расторжение"]["Изменение::Без изменения ц

[свернуть]

Общие функции

funcs.inc.php

    // Подключаем базу знаний классификатора
ий классификатора
    if(file_exists("bayes.inc.php"))i/**
        Классификация фразы, возвращает массив из 3 наиболее вероятных классов
        в которые фраза входит
 
        @returns Массив, в котором ключ - класс, значение - вероятноть, с которой входная фраза ему принадлежит
    */   @returns Массив, в котор//!< Классифицируемая фраза
значени// общее количество обучающих примеров
ой входная фра// Количество уникальных лексем в обучающей выборке
n classing(
        $phase // Частоты классов
ицируемая фраза
    ){// Словарь лексем с частотой их вхождения в классы
ающих примеров
        global $D;
        // Количе// Вычисляем вес каждого класса для данной фразы
учаю// то есть количественной характеристики, коррелирующей с вероятностью
ассо// её вхождения в класс
_freq;
        // Словарь лексем с частотой их// Получаем список лексем для классифицируемой фразы
ll_lexems;
 
        $result = array();
      // Вычисляем начальное значение веса, как отношения данного класса 
анной // ко всему объёму обучающих примеров
личественной характеристики, коррелирующей с вероятнос// Если лексема известна из обучения, запоминаем, сколько раз 
foreach($types_f// она встречалась в обучающих примерах данного класса
учаем список лексем для классифицируемой фразы
            $lexes = get_lexems($phase);
            // Вычисляем начальное значение веса, как // Вычисляем вес вхождения лексемы в данный класс
          // ко всему объёму обучающих примеров
            $sum = log($class_info["freq"]/$D);
          // Прибавляем вес вхождения конкретно этой лексемы
сли лекс// к весу вхождения других лексем из входной фразы в этот класс
м, сколько раз 
                // она вс// Запоминаем общий вес класса 
щих примерах данного класса
               // Начало: Нормализация. 
   isset// Задача этого куска кода - транспонировать значение весов классов
       $// на отрезок [0,1], то есть получить вероятность принадлежности фразы
 0;
    // Ко всем классам, выделив 3 наиболее вероятных
дения лексемы в данный класс
                $P = 
                    ($Wic + 1)
                    /
                    ($V+$class_info["lex"]);
                // Прибавляем вес вхождения конкретно этой лексемы
                // к весу вхождения других лексем из входной фразы в этот класс
                $sum += log($P);
            }
            // Запоминаем общий вес класса 
            $result[$class_name] = $sum;
        }
 
        // Начало: Нормализация. 
        // Задача этого куска кода - транспонировать значение весов клас// Конец: Нормализация. 
трезок [0,1], то есть получи/**
        Функция сравнения элементов массива при сортировке
    */       // Ко всем классам, выдел/**
        Разбиение строки на лексемы
 
        @returns массив лексем
    */st_min = array();$last_max = array();
  //!< Разбираемая строка
 $type_name=>$type// Минимальная длина обрезанной лексемы
min && $type_weight!=-INF){$last_// Максимальная длина обрезанной лексемы
      if($type_weight>$max && $type_weight!=INF){$last_max[] = $max;$// Разбиваем по пробелу
     }
        uasort($result,"cmp");
        // Список разделителей
      foreach($result as $type_name=>$type_weight){
            $P = round(100*($typ// Разбиваем по разделителям
            if(count($percents)&lt;3)
                $percents[$type_name] = $P;
        }
        $sum = 0;foreach($percents as $type=>$c)$sum+=$c;
        foreach($percents as $type=>$c)$percents[$type]=round(100*$percents[$type]/$sum);
        // Конец: Нормализация. 
 
        return $percents;
   // Убираем пустые, числа
кция сравнения элементов массива при сортировке
    */
    function cmp($a, $b){return $a< $b;}
 
    ult[$k] = mb_strtolower($result[$k], "UTF-8");
 
        // Добавляем обрезанных лексемrns массив лексем
    */
    function get_lexems(
        $line //!< Разбираемая строка
    ){   
        // Минимальная длина обрезанной лексемы
        $min_length = 2;
        // Максимальная длина обрезанной лексемы
        $max_length = 7;
 
 

[свернуть]

Распознавание

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

    // Подключаем функции работы с классификатором
ты с классификатор// Фразы для классификации
php");
 
    // Фразы для классификации
    $examples["Расширение списка слов (выдв 3 мес.)";
    $examples["Доп. на скидку"ние модуля мультивалютности в систему администрирования"]="";
    $examples["Доп. на скидку"]='';
    $examples["Постановка на наш дви

Получаем следующий вывод

Array
(
    [Расширение списка слов (выдв 3 мес.)] => Array
        (
            [Изменение::Повышение цены] => 50
            [Расторжение] => 31
            [Перезаключение] => 19
        )
 
    [Внедрение модуля мультивалютности в систему администрирования] => Array
        (
            [Дополнительные работы] => 49
            [Новая рекламная компания] => 28
            [Переход продвижение -> техподдержка] => 24
        )
 
    [Доп. на скидку] => Array
        (
            [Дополнительные работы] => 42
            [Изменение::Уменьшение цены] => 39
            [Продление срока разработки] => 19
        )
 
    [Постановка на наш движок] => Array
        (
            [Разраб

Тут мы видим классифицируемые фразы и ТОП-3 классов, к которым она отнесена с вероятностью в процентах.

Как мне кажется, всё довольно логично.

Предупреждение/предостережение

Успех классификации ваших данных на 95% зависит от подобранных примеров для обучения. С одной стороны их должно быть достаточно, с другой стороны — не слишком много, ибо процесс обучения затратный, с третьей стороны — примеры должны покрывать как можно большее число встречающихся случаев.

Ссылки на источники

При реализации опирался на вот эту статью


Добавить комментарий