2009-05-12 6 views
19

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

  • У вас есть база данных, содержащая около 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; 
    } 
} 
?> 

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

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

+1

Есть плагины WordPress (да, да, я знаю, избавлю меня от этого), которые делают удивительно хорошую работу, они на самом деле выполняют разумную кластеризацию (как правило, они используют TF-IDF с обратной связью с помощью k-средств или чего-то еще как это), и вы можете использовать их для вдохновения (некоторые из них с открытым исходным кодом при MIT). –

+2

Я думаю, что Anony-Mousse прав: кластеризация - не идеальный инструмент здесь. Если каждый документ принадлежит только одному кластеру, то у вас есть проблема с документами, расположенными вблизи границ кластера, * более похожих * на документы в других соседних кластерах, чем на большинство документов в их собственном кластере. –

ответ

15

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

Сначала создайте «гистограмму» слов для каждой статьи. Скажем, между всеми вашими статьями, у вас есть только 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

+0

Большое спасибо! Я попытался закодировать ваш подход в PHP и вот результат: http://paste.bradleygill.com/index.php?paste_id=9290 Надеюсь, ваш PHP по-прежнему достаточно хорош, чтобы сказать, правильно это или нет. – caw

+1

Мне кажется, что это правильно, однако, в зависимости от вашего приложения, вы серьезно хотите рассмотреть вопрос о сохранении состояния термина векторов. Кроме того, рассмотрите разделение балла по длине статьи раз в длину статьи b. В противном случае вы увидите предвзятость для длинных статей, которые только незначительно связаны между собой. – Albinofrenchy

+0

Извините, конечно, глупый вопрос, но что именно вы имеете в виду: «рассмотрите вопрос о сохранении состояния векторов-векторов». Во втором пункте: вы имеете в виду «$ score = $ score/$ length_a * $ length_b» или «$ score = $ score/($ length_a * $ length_b)»? Вероятно, первый, не так ли? – caw

0

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

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

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

+0

Функция Similar_text() "вычисляет сходство между двумя строками, как описано в Oliver [1993]". Да, вы правы, это скорее показатель сходства. Но вам нужны проверки сходства для кластеризации, не так ли? – caw

1

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

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

Спасибо, хорошие вопросы! 1) Я хочу отобразить связанные документы вместе. 2) Алгоритм должен выполнять плоскую кластеризацию. 3) Это было бы полезно, если бы тексты были длинными, но в моем случае статьи содержат не более 510 символов. Так что это действительно не нужно, не так ли? 4) Подход с k-средствами звучит хорошо, но мне нужно много кластеров, и новые кластеры должны постоянно создаваться. Могу ли я использовать k-средства, хотя? – caw

+0

Вы можете использовать K-середину с большим K. Стоимость должна проверять подобие каждого документа с каждым из центров кластеров. «Непрерывно создавайте звуки новых кластеров, как иерархию иерархии сверху вниз, но вы можете работать в несколько эпох - начните с небольшого K, запустите K-средство, пока оно не сходится, и не используйте эти кластеры. Позже, увеличьте K, повторите K-средство с самого начала и используйте полученные кластеры и т. Д. –

+0

О, я не знал, как точно работает k-означает.Если он работает так, я не могу использовать его, так как я не знаю количество кластерных центров. У меня есть база данных новостных статей, и все статьи по одной и той же теме должны быть сгруппированы. – caw

5

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

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

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

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

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