코사인 유사도와 해밍 거리

Question

두 문서 간의 유사도를 계산하기 위해 주파수라는 용어가 포함 된 특징 벡터를 만듭니다. 하지만 다음 단계에서는 "Cosine similarity"과 "Hamming distance"사이를 결정할 수 없습니다.

내 질문 :이 알고리즘에 대한 경험이 있습니까? 어느 것이 더 나은 결과를 제공합니까?

그 외에 : PHP에서 코사인 유사성을 코딩하는 법을 가르쳐 주시겠습니까? 해밍 거리에 대해서는 이미 코드를 가지고 있습니다 :

function check ($terms1, $terms2) { 
    $counts1 = array_count_values($terms1); 
    $totalScore = 0; 
    foreach ($terms2 as $term) { 
     if (isset($counts1[$term])) $totalScore += $counts1[$term]; 
    } 
    return $totalScore * 500/(count($terms1) * count($terms2)); 
} 

다른 알고리즘을 사용하고 싶지 않습니다. 나는 둘 사이에서 결정할 도움이 필요하다.

누군가 알고리즘을 개선하는 방법에 대해 말할 수 있습니다. 정지 단어 또는 일반적인 단어를 걸러 내면 더 나은 결과를 얻을 수 있습니까?

도와 주시면 감사하겠습니다. 미리 감사드립니다!

Answer 1

해밍 거리는 길이가 같고 순서가 고려 된 두 개의 문자열 사이에서 수행되어야합니다.

문서의 길이가 틀리며 단어 위치가 중요하지 않은 경우 코사인 유사도가 더 좋습니다 (필요에 따라 더 나은 솔루션이 있음에 유의하십시오). :)

여기 단어의 두 배열의 코사인 유사도 함수 :

function cosineSimilarity($tokensA, $tokensB) 
{ 
    $a = $b = $c = 0; 
    $uniqueTokensA = $uniqueTokensB = array(); 

    $uniqueMergedTokens = array_unique(array_merge($tokensA, $tokensB)); 

    foreach ($tokensA as $token) $uniqueTokensA[$token] = 0; 
    foreach ($tokensB as $token) $uniqueTokensB[$token] = 0; 

    foreach ($uniqueMergedTokens as $token) { 
     $x = isset($uniqueTokensA[$token]) ? 1 : 0; 
     $y = isset($uniqueTokensB[$token]) ? 1 : 0; 
     $a += $x * $y; 
     $b += $x; 
     $c += $y; 
    } 
    return $b * $c != 0 ? $a/sqrt($b * $c) : 0; 
} 

이 (큰 배열에 살인자 isset() 대신 in_array()됩니다) 빠릅니다.

여기서 알 수 있듯이 결과에는 각 단어의 "크기"가 고려되지 않습니다.

"거의"복사 붙여 넣은 텍스트의 멀티 게시 메시지를 검색하는 데 사용합니다. 잘 작동한다. :)

문자열 유사성 측정에 대한 가장 좋은 링크 : 더 흥미로운 독서에 대한 http://www.dcs.shef.ac.uk/~sam/stringmetrics.html

:

http://www.miislita.com/information-retrieval-tutorial/cosine-similarity-tutorial.html 다음 http://bioinformatics.oxfordjournals.org/cgi/content/full/22/18/2298

Answer 2

다른 알고리즘을 사용하고 싶지 않다는 사실을 무시하고 사과 드리지만 진지하게는 Levenshtein distance과 Damerau-Levenshtein distance이 해밍 거리보다 유용합니다. 여기 D-L distance implementation in PHP, 그리고 당신은 내가 그것이 길이 제한이 있기 때문에 당신이하지 않습니다 생각 PHP의 기본 levenshtein() 기능을, 마음에 들지 않는 경우 여기 아닌 길이 제한 버전입니다 :

function levenshtein_distance($text1, $text2) { 
    $len1 = strlen($text1); 
    $len2 = strlen($text2); 
    for($i = 0; $i <= $len1; $i++) 
     $distance[$i][0] = $i; 
    for($j = 0; $j <= $len2; $j++) 
     $distance[0][$j] = $j; 
    for($i = 1; $i <= $len1; $i++) 
     for($j = 1; $j <= $len2; $j++) 
      $distance[$i][$j] = min($distance[$i - 1][$j] + 1, $distance[$i][$j - 1] + 1, $distance[$i - 1][$j - 1] + ($text1[$i - 1] != $text2[$j - 1])); 
    return $distance[$len1][$len2]; 
} 

Answer 3

난하지 않는 한 오해, 두 알고리즘 사이의 중간에 알고리즘 이 있다고 생각합니다.

function check ($terms1, $terms2) { 
    $counts1 = array_count_values($terms1); 
    $totalScore = 0; 
    foreach ($terms2 as $term) { 
     if (isset($counts1[$term])) $totalScore += 1; 
    } 
    return $totalScore * 500/(count($terms1) * count($terms2)); 
} 

가 (. 당신은 단지 토큰 벡터의 각 일치하는 요소에 대해 1을 추가하는 것을 주)

그리고 코사인 유사성에 대한 사용 :

function check ($terms1, $terms2) { 
    $counts1 = array_count_values($terms1); 
    $counts2 = array_count_values($terms2); 
    $totalScore = 0; 
    foreach ($terms2 as $term) { 
     if (isset($counts1[$term])) $totalScore += $counts1[$term] * $counts2[$term]; 
    } 
    return $totalScore/(count($terms1) * count($terms2)); 
} 

해밍 거리, 사용을 위해 (두 문서 사이에 토큰 카운트의 제품을 추가한다는 점에 유의하십시오.)

두 가지 주요 차이점은 코사인 유사성은 yi입니다. 문서에서 두 개의 문서가 동일한 단어를 여러 번 사용하면 더 강한 표시기가 나타나고 해밍 거리는 개별 토큰의 빈도를 고려하지 않습니다..

편집는 : - 기능 단어가 매우 빈번로 (영어, 적어도), 당신이 왜곡 수도 당신이 코사인 유사성을 사용하는 거라면 나는이 조언을 할 등의 기능 단어를 제거하는 방법에 대한 쿼리를 발견 그 (것)들을 밖으로 거르지 않기 결과. 해밍 거리를 사용하면 그 효과는 그다지 크지 않지만 어떤 경우에는 그 효과가 상당 할 수 있습니다. 또한 lemmatizer에 대한 액세스 권한이있는 경우 한 문서에 "은하"가 포함되어 있고 다른 문서에 "은하계"가 포함되어있는 경우 누락이 줄어 듭니다.

당신이가는 길, 행운을 빌어 요!

Answer 4

코사인 거리 함수 내 수정 된 코드는 토토

에 의해 게시

function cosineSimilarity($tokensA, $tokensB) 
{ 
    $a = $b = $c = 0; 
    $uniqueTokensA = $uniqueTokensB = array(); 

    $uniqueMergedTokens = array_unique(array_merge($tokensA, $tokensB)); 

    foreach ($tokensA as $token) $uniqueTokensA[$token] = 0; 
    foreach ($tokensB as $token) $uniqueTokensB[$token] = 0; 

    foreach ($uniqueMergedTokens as $token) { 
     $x = isset($uniqueTokensA[$token]) ? 1 : 0; 
     $y = isset($uniqueTokensB[$token]) ? 1 : 0; 
     $a += $x * $y; 
     $b += pow($x,2); 
     $c += pow($y,2); 
    } 
    return $b * $c != 0 ? $a/sqrt($b * $c) : 0; 
}