Лучший алгоритм кластеризации? (Просто объяснил)

Question

Представьте себе следующую задачу:

• У вас есть база данных, содержащая около 20 000 текстов в таблице под названием «статьи»
• Вы хотите подключить соответствующие те, используя алгоритм кластеризации для того, чтобы отобразить соответствующие статьи вместе
• алгоритм должен сделать плоскую кластеризацию (не иерархическую)
• Соответствующие статьи должны быть вставлены в таблицу «связанную»
• алгоритм кластеризации должен решить, следует ли два или мор е статьи связаны или не на основе текстов
• Я хочу, чтобы закодировать в PHP, но примеры с псевдокод или других языков программирования хорошо, слишком

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

ПОДХОД 1

<?php 
$zeit = time(); 
function check($str1, $str2){ 
    $minprozent = 60; 
    similar_text($str1, $str2, $prozent); 
    $prozent = sprintf("%01.2f", $prozent); 
    if ($prozent > $minprozent) { 
     return TRUE; 
    } 
    else { 
     return FALSE; 
    } 
} 
$sql1 = "SELECT id, text FROM articles ORDER BY RAND() LIMIT 0, 20"; 
$sql2 = mysql_query($sql1); 
while ($sql3 = mysql_fetch_assoc($sql2)) { 
    $rel1 = "SELECT id, text, MATCH (text) AGAINST ('".$sql3['text']."') AS score FROM articles WHERE MATCH (text) AGAINST ('".$sql3['text']."') AND id NOT LIKE ".$sql3['id']." LIMIT 0, 20"; 
    $rel2 = mysql_query($rel1); 
    $rel2a = mysql_num_rows($rel2); 
    if ($rel2a > 0) { 
     while ($rel3 = mysql_fetch_assoc($rel2)) { 
      if (check($sql3['text'], $rel3['text']) == TRUE) { 
       $id_a = $sql3['id']; 
       $id_b = $rel3['id']; 
       $rein1 = "INSERT INTO related (article1, article2) VALUES ('".$id_a."', '".$id_b."')"; 
       $rein2 = mysql_query($rein1); 
       $rein3 = "INSERT INTO related (article1, article2) VALUES ('".$id_b."', '".$id_a."')"; 
       $rein4 = mysql_query($rein3); 
      } 
     } 
    } 
} 
?> 

ПОДХОД 2 [только проверить()]

<?php 
function square($number) { 
    $square = pow($number, 2); 
    return $square; 
} 
function check($text1, $text2) { 
    $words_sub = text_splitter($text2); // splits the text into single words 
    $words = text_splitter($text1); // splits the text into single words 
    // document 1 start 
    $document1 = array(); 
    foreach ($words as $word) { 
     if (in_array($word, $words)) { 
      if (isset($document1[$word])) { $document1[$word]++; } else { $document1[$word] = 1; } 
     } 
    } 
    $rating1 = 0; 
    foreach ($document1 as $temp) { 
     $rating1 = $rating1+square($temp); 
    } 
    $rating1 = sqrt($rating1); 
    // document 1 end 
    // document 2 start 
    $document2 = array(); 
    foreach ($words_sub as $word_sub) { 
     if (in_array($word_sub, $words)) { 
      if (isset($document2[$word_sub])) { $document2[$word_sub]++; } else { $document2[$word_sub] = 1; } 
     } 
    } 
    $rating2 = 0; 
    foreach ($document2 as $temp) { 
     $rating2 = $rating2+square($temp); 
    } 
    $rating2 = sqrt($rating2); 
    // document 2 end 
    $skalarprodukt = 0; 
    for ($m=0; $m<count($words)-1; $m++) { 
     $skalarprodukt = $skalarprodukt+(array_shift($document1)*array_shift($document2)); 
    } 
    if (($rating1*$rating2) == 0) { continue; } 
    $kosinusmass = $skalarprodukt/($rating1*$rating2); 
    if ($kosinusmass < 0.7) { 
     return FALSE; 
    } 
    else { 
     return TRUE; 
    } 
} 
?> 

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

Надеюсь, вы можете мне помочь. Заранее спасибо!

Answer 1

Самый стандартный способ, которым я знаю это сделать, по текстовым данным, таким как у вас, - использовать технику «мешок слов».

Сначала создайте «гистограмму» слов для каждой статьи. Скажем, между всеми вашими статьями, у вас есть только 500 уникальных слов между ними. Тогда эта гистограмма будет представлять собой вектор (массив, список, любой) размером 500, где данные - это количество раз, когда каждое слово появляется в статье. Так что, если первое место в векторе представлены слово «просил», и это слово появилось 5 раз в статье, вектор [0] будет 5:

for word in article.text 
    article.histogram[indexLookup[word]]++ 

Теперь, чтобы сравнить любые две статьи, это довольно просто. Мы просто умножаем два вектора:

def check(articleA, articleB) 
    rtn = 0 
    for a,b in zip(articleA.histogram, articleB.histogram) 
     rtn += a*b 
    return rtn > threshold 

(К сожалению для использования питона вместо PHP, мой PHP ржавый и использование молнии делает это немного легче)

Это основная идея. Обратите внимание, что пороговое значение является полу-произвольным; вы, вероятно, захотите найти хороший способ нормализовать точечный продукт ваших гистограмм (это почти обязательно будет учитывать длину статьи где-то) и решить, что вы считаете «связанным».

Кроме того, вы не должны просто помещать каждое слово в свою гистограмму. В общем, вы хотите включить те, которые используются часто: не в каждой статье или только в одной статье. Это экономит немного накладных расходов на вашей гистограмме и увеличивает ценность ваших отношений.

Кстати, этот метод описан более подробно here

Answer 2

Что делает функция similar_text называется в подходе # 1 выглядит? Я думаю, что вы имеете в виду не кластеризацию, а метрику сходства. Я не могу по-настоящему улучшить подход к гистограмме White- Walloun's :-) - интересная проблема для чтения.

Однако вы внедряете check(), вы должны использовать его для сравнения не менее 200M (половина 20000^2). Отсечка для «связанных с» статей может ограничить то, что вы храните в базе, но, кажется, слишком произвольно, чтобы охватить все полезные кластеризация текстов,

Мой подход должен был бы изменить check() вернуть «сходство» Метрика ($prozent или rtn). Запишите матрицу 20K x 20K в файл и используйте внешнюю программу для кластеризации, чтобы идентифицировать ближайших соседей для каждой статьи, которую вы могли бы загрузить в таблицу related. Я бы сделал кластеризацию в R - есть хороший tutorial для кластеризации данных в файле с R от php.

Answer 3

Я считаю, что вам нужно сделать некоторые конструктивные решения о кластеризации, и продолжить оттуда:

1. Почему вы кластеризация текстов? Вы хотите отображать связанные документы вместе? Вы хотите исследовать свой корпус документа через кластеры?
2. В результате, вы хотите flat или hierarchical кластеризации?
3. Теперь у нас есть проблема сложности в двух измерениях: во-первых, количество и тип функций, которые вы создаете из текста - отдельные слова могут числиться в десятках тысяч. Возможно, вы захотите попробовать feature selection - например, взять N наиболее информативных слов или N слов, появляющихся больше всего, после игнорирования stop words.
4. Во-вторых, вы хотите минимизировать количество раз, когда вы измеряете сходство между документами. Как правильно указывает пузырь, проверка сходства между всеми парами документов может быть слишком большой. Если кластеризации в небольшое количество кластеров достаточно, вы можете рассмотреть K-means clustering, который в основном: выберите исходные документы K как центры кластеров, присвойте каждому документу ближайший кластер, пересчитайте центры кластеров, найдя векторные векторные средства и итерации. Это означает только количество документов K * для каждой итерации. Я считаю, что существуют также эвристики для уменьшения необходимого количества вычислений для иерархической кластеризации.

Answer 4

Возможно, Неверная стратегия кластеризации?

Если вы хотите отобразить подобных статей, использования поиска сходства вместо.

Для текстовых статей это хорошо понято. Просто вставьте свои статьи в текстовую базу поиска, например Lucene, и используйте свою текущую статью в качестве поискового запроса.В Lucene существует query called MoreLikeThis, который выполняет именно это: найти похожие статьи.

Кластеризация - это неправильный инструмент, потому что (в частности, с вашими требованиями), каждая статья должна быть помещена в какой-либо кластер; и связанные элементы будут одинаковыми для каждого объекта в кластере. Если в базе данных есть выбросы - очень вероятный случай - они могут разрушить вашу кластеризацию. Кроме того, кластеры могут быть очень большими. Ограничений по размеру нет, алгоритм кластеризации может решить поставить половину вашего набора данных в один и тот же кластер. Таким образом, у вас есть 10000 связанных статей для каждой статьи в вашей базе данных. С поиском сходства вы можете просто получить 10 лучших предметов для каждого документа!

Последнее, но не менее важное: забыть PHP для кластеризации. Он не предназначен для этого, а не достаточно. Но вы, вероятно, можете получить доступ к индексу lucene с PHP достаточно хорошо.