Реализация байесовского классификатора на PHP: назначение тем текстам

Question

В моем проекте страницы новостей у меня есть таблица базы данных news со следующей структурой:

 - id: [integer] unique number identifying the news entry, e.g.: *1983*
 - title: [string] title of the text, e.g.: *New Life in America No Longer Means a New Name*
 - topic: [string] category which should be chosen by the classificator, e.g: *Sports*

Кроме того, есть таблица bayes с информацией очастоты слов:

 - word: [string] a word which the frequencies are given for, e.g.: *real estate*
 - topic: [string] same content as "topic" field above, e.h. *Economics*
 - count: [integer] number of occurrences of "word" in "topic" (incremented when new documents go to "topic"), e.g: *100*

Теперь я хочу, чтобы мой скрипт PHP классифицировал все записи новостей и назначил им одну из нескольких возможных категорий (тем).

Это правильная реализация?Можете ли вы улучшить его?

<?php
include 'mysqlLogin.php';
$get1 = "SELECT id, title FROM ".$prefix."news WHERE topic = '' LIMIT 0, 150";
$get2 = mysql_abfrage($get1);
// pTOPICS BEGIN
$pTopics1 = "SELECT topic, SUM(count) AS count FROM ".$prefix."bayes WHERE topic != '' GROUP BY topic";
$pTopics2 = mysql_abfrage($pTopics1);
$pTopics = array();
while ($pTopics3 = mysql_fetch_assoc($pTopics2)) {
    $pTopics[$pTopics3['topic']] = $pTopics3['count'];
}
// pTOPICS END
// pWORDS BEGIN
$pWords1 = "SELECT word, topic, count FROM ".$prefix."bayes";
$pWords2 = mysql_abfrage($pWords1);
$pWords = array();
while ($pWords3 = mysql_fetch_assoc($pWords2)) {
    if (!isset($pWords[$pWords3['topic']])) {
        $pWords[$pWords3['topic']] = array();
    }
    $pWords[$pWords3['topic']][$pWords3['word']] = $pWords3['count'];
}
// pWORDS END
while ($get3 = mysql_fetch_assoc($get2)) {
    $pTextInTopics = array();
    $tokens = tokenizer($get3['title']);
    foreach ($pTopics as $topic=>$documentsInTopic) {
        if (!isset($pTextInTopics[$topic])) { $pTextInTopics[$topic] = 1; }
        foreach ($tokens as $token) {
            echo '....'.$token;
            if (isset($pWords[$topic][$token])) {
                $pTextInTopics[$topic] *= $pWords[$topic][$token]/array_sum($pWords[$topic]);
            }
        }
        $pTextInTopics[$topic] *= $pTopics[$topic]/array_sum($pTopics); // #documentsInTopic / #allDocuments
    }
    asort($pTextInTopics); // pick topic with lowest value
    if ($chosenTopic = each($pTextInTopics)) {
        echo '<p>The text belongs to topic '.$chosenTopic['key'].' with a likelihood of '.$chosenTopic['value'].'</p>';
    }
}
?>

Обучение проводится вручную, оно не включено в этот код.Если текст «Вы можете зарабатывать деньги, если вы продаете недвижимость» относится к категории / теме «Экономика», то все слова (вы, можете, зарабатывать, ...) вставляются в таблицу bayes с "Экономикой" в качестве темы и 1 в качестве стандартного счета.Если слово уже существует в сочетании с той же темой, счет увеличивается.

Образец данных обучения:

количество слов темы

kaczynskiПолитика 1

Сони Технология 1

Банк Экономика 1

Телефон Технология 1

Сони Экономика 3

Эриксон Технология 2

Пример вывода / результата:

Название текста: Тест телефона Sony Ericsson Aspen - чувствительный Winberry

Политика

....телефон .... тест .... сони .... эриксон .... осина .... чувствительный .... winberry

технология

.... телефон НАЙДЕН.... тест .... sony НАЙДЕН ... ericsson НАЙДЕН .... осина .... чувствительный .... winberry

экономика

.... телефон.... тест .... sony НАЙДЕНО ... ericsson .... aspen .... чувствительный .... winberry

Результат: текст относится к теме Технология с вероятностью 0,013888888888889

Заранее большое спасибо!

Answer 1

Похоже, ваш код правильный, но есть несколько простых способов его оптимизировать. Например, вы вычисляете p (слово | тема) на лету для каждого слова, в то время как вы можете легко вычислить эти значения заранее. (Я предполагаю, что вы хотите классифицировать несколько документов здесь, если вы делаете только один документ, я думаю, что это нормально, поскольку вы не рассчитываете его для слов, которых нет в документе)

Аналогично, вычисление p (тема) может быть перемещено за пределы цикла.

Наконец, вам не нужно сортировать весь массив, чтобы найти максимум.

Все маленькие очки! Но это то, что вы просили:)

Я написал несколько непроверенных PHP-кодов, показывающих, как я реализую это ниже:

<?php

// Get word counts from database
$nWordPerTopic = mystery_sql();

// Calculate p(word|topic) = nWord / sum(nWord for every word)
$nTopics = array();
$pWordPerTopic = array();
foreach($nWordPerTopic as $topic => $wordCounts)
{
    // Get total word count in topic
    $nTopic = array_sum($wordCounts);

    // Calculate p(word|topic)
    $pWordPerTopic[$topic] = array();
    foreach($wordCounts as $word => $count)
        $pWordPerTopic[$topic][$word] = $count / $nTopic;

    // Save $nTopic for next step
    $nTopics[$topic] = $nTopic;
}

// Calculate p(topic)
$nTotal = array_sum($nTopics);
$pTopics = array();
foreach($nTopics as $topic => $nTopic)
    $pTopics[$topic] = $nTopic / $nTotal;

// Classify
foreach($documents as $document)
{
    $title = $document['title'];
    $tokens = tokenizer($title);
    $pMax = -1;
    $selectedTopic = null;
    foreach($pTopics as $topic => $pTopic)
    {
        $p = $pTopic;
        foreach($tokens as $word)
        {
            if (!array_key_exists($word, $pWordPerTopic[$topic]))
                continue;
            $p *= $pWordPerTopic[$topic][$word];
        }

        if ($p > $pMax)
        {
            $selectedTopic = $topic;
            $pMax = $p;
        }
    }
} 
?>

Что касается математики ...

Вы пытаетесь максимизировать p (тема | слова), поэтому найдите

arg max p(topic|words)

(т.е. тема аргумента, для которой p (topic | words) является самой высокой)

Теорема Байеса гласит

                  p(topic)*p(words|topic)
p(topic|words) = -------------------------
                        p(words)

Итак, вы ищете

         p(topic)*p(words|topic)
arg max -------------------------
               p(words)

Поскольку p (слова) документа одинаковы для любой темы, это то же самое, что и поиск

arg max p(topic)*p(words|topic)

Наивное предположение Байеса (что делает этот классификатор наивным Байеса) следующим:

p(words|topic) = p(word1|topic) * p(word2|topic) * ...

Итак, используя это, вам нужно найти

arg max p(topic) * p(word1|topic) * p(word2|topic) * ...

Где

p(topic) = number of words in topic / number of words in total

И

                   p(word, topic)                         1
p(word | topic) = ---------------- = p(word, topic) * ----------
                      p(topic)                         p(topic)

      number of times word occurs in topic     number of words in total
   = -------------------------------------- * --------------------------
            number of words in total           number of words in topic

      number of times word occurs in topic 
   = --------------------------------------
            number of words in topic