최고의 클러스터링 알고리즘? (간단히 설명)

https://stackoverflow.com/questions/853139

21-08-2019
|

문제

다음과 같은 문제를 상상해보십시오.

"기사"라는 표에 약 20,000 개의 텍스트가 포함 된 데이터베이스가 있습니다.
관련 기사를 함께 표시하기 위해 클러스터링 알고리즘을 사용하여 관련 제품을 연결하려고합니다.
알고리즘은 플랫 클러스터링을 수행해야합니다 (계층 적 아님)
관련 기사는 "관련"표에 삽입해야합니다.
클러스터링 알고리즘은 텍스트를 기반으로 두 개 이상의 기사가 관련되어 있는지 여부를 결정해야합니다.
PHP로 코딩하고 싶지만 의사 코드 또는 기타 프로그래밍 언어로 예제도 괜찮습니다.

두 입력 기사가 관련되고 "false"가 아닌 경우 "true"를 제공하는 함수 check ()로 첫 번째 드래프트를 코딩했습니다. 나머지 코드 (데이터베이스에서 기사를 선택하고 비교할 기사를 선택하고 관련 기사를 삽입 함)도 완료됩니다. 어쩌면 나머지를 향상시킬 수도 있습니다. 그러나 나에게 중요한 요점은 함수 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;
    }
}
?>

또한 클러스터링을위한 알고리즘이 많다는 것을 알고 싶습니다. 그러나 모든 사이트에는 수학적 설명만이 있습니다. 따라서 (Pseudo) 코드의 코딩 예제가 좋을 것입니다.

나는 당신이 나를 도울 수 있기를 바랍니다. 미리 감사드립니다!

해결책

텍스트 데이터 에서이 작업을 수행하는 가장 표준적인 방법은 '단어의 가방'기술을 사용하는 것입니다.

먼저 각 기사에 대해 단어의 '히스토그램'을 만듭니다. 모든 기사들 사이에서 당신은 그들 사이에 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 대신 Python을 사용해 주셔서 죄송합니다. 내 PHP는 녹슬고 지퍼를 사용하면 조금 더 쉬워집니다)

이것이 기본 아이디어입니다. 임계 값이 반의 임계 값에 주목하십시오. 아마도 히스토그램의 도트 제품을 정규화하는 좋은 방법을 찾고 싶을 것입니다 (이것은 어딘가에 기사 길이를 거의 다루어야 함)를 '관련'하는 것을 결정합니다.

또한 모든 단어를 히스토그램에 넣어서는 안됩니다. 일반적으로 동시에 사용되는 것을 포함 시키려고합니다. 모든 기사 나 하나의 기사에만 포함되지 않습니다. 이렇게하면 히스토그램에 약간의 오버 헤드가 절약되고 관계의 가치가 증가합니다.

그건 그렇고,이 기술은 더 자세히 설명됩니다. 여기

다른 팁

아마도 클러스터링은 잘못된 전략입니다 여기?

당신이 표시하고 싶다면 비슷한 조항, 사용 유사성 검색 대신에.

텍스트 기사의 경우 이것은 잘 이해됩니다. Lucene과 같은 텍스트 검색 데이터베이스에 기사를 삽입하고 현재 기사를 검색 쿼리로 사용하십시오. 루센에는 존재한다 쿼리 호출 MoreLikeThis 그것은 정확히 이것을 수행합니다 : 비슷한 기사를 찾으십시오.

클러스터링은 잘못된 도구입니다 (특히 요구 사항에 따라) 모든 기사는 일부 클러스터에 넣어야합니다. 그리고 관련 항목은 클러스터의 모든 객체에 대해 동일합니다. 데이터베이스에 이상치가있는 경우 클러스터링을 망칠 수 있습니다. 뿐만 아니라, 클러스터는 매우 클 수 있습니다. 크기 제약 조건이 없으며 클러스터링 알고리즘은 데이터 세트의 절반을 동일한 클러스터에 넣기로 결정할 수 있습니다. 따라서 데이터베이스의 각 기사에 대해 10000 개의 관련 기사가 있습니다. 유사성 검색을 사용하면 각 문서에 대해 상위 10 개 유사한 항목을 얻을 수 있습니다!

마지막으로 : 클러스터링에 대한 PHP를 잊어 버리십시오. 이를 위해 설계되지 않았으며 충분히 성능이 없습니다. 그러나 아마도 PHP의 Lucene 지수에 충분히 액세스 할 수 있습니다.

클러스터링에 대한 디자인 결정을 내려야한다고 생각합니다.

텍스트를 클러스터링하는 이유는 무엇입니까? 관련 문서를 함께 표시 하시겠습니까? 클러스터를 통해 문서 코퍼스를 탐색 하시겠습니까?
결과적으로 원하십니까? 평평한 또는 계층 적 클러스터링?
이제 우리는 두 가지 차원으로 복잡성 문제가 있습니다. 첫째, 텍스트에서 만든 기능의 수와 유형 - 개별 단어는 수만에 달할 수 있습니다. 당신은 몇 가지를 시도하고 싶을 수도 있습니다 기능 선택 - 가장 유익한 단어를 복용하거나 무시한 후 가장 많이 나타나는 N 단어를 취하는 것과 같은 단어 중지.
둘째, 문서 간 유사성을 측정하는 횟수를 최소화하려고합니다. Bubaker가 올바르게 지적했듯이 모든 문서 쌍 간의 유사성을 확인하는 것이 너무 많을 수 있습니다. 적은 수의 클러스터로의 클러스터링이 충분하다면 K- 평균 클러스터링, 기본적으로 : 초기 K 문서를 클러스터 센터로 선택하고, 모든 문서를 가장 가까운 클러스터에 할당하고, 문서 벡터 평균을 찾아서 클러스터 센터를 다시 계산하고 반복하십시오. 이것은 반복 당 k*문서 수입니다. 계층 적 클러스터링에 필요한 계산 수를 줄이기위한 휴리스틱도 있다고 생각합니다.

무엇을합니까 similar_text 접근 #1에서 호출 된 기능은 다음과 같습니다. 나는 당신이 말하는 것이 클러스터링이 아니라 유사성 지표라고 생각합니다. 나는 White Walloun의 히스토그램 접근법을 실제로 개선 할 수 없습니다.

그러나 당신은 구현합니다 check(), 당신은 그것을 최소 200m 비교하기 위해 그것을 사용해야합니다 (절반의 절반 20000^2). "관련"기사에 대한 컷오프는 데이터베이스에 저장 한 내용을 제한 할 수 있지만 텍스트의 모든 유용한 클러스터링을 포착하기에는 너무 임의적 인 것 같습니다.

내 접근 방식은 수정하는 것입니다 check() "유사성"메트릭을 반환하려면 ($prozent 또는 rtn). 쓰기 20K x 20K 파일에 매트릭스를하고 외부 프로그램을 사용하여 클러스터링을 수행하여 각 기사에 가장 가까운 이웃을 식별합니다. related 테이블. 클러스터링을 할 것입니다 R - 좋은 것이 있습니다 지도 시간 실행중인 파일의 클러스터링 R ~에서 php.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow