Part 3 of Algorithms explained! Every few weeks I write about an algorithm and explain and implement it!
Is there an algorithm you always wanted to know about? Leave a comment!

공부하는 동안 저는'NLP'라는 과정에 참가했고 그곳에서 자연 언어 처리의 다양한 기술을 배웠습니다.내가 배운 매우 교묘한 기교는 벡터 공간 모델의 텍스트 유사성을 사용하는 것이다.나는 두 개 이상의 텍스트를 비교할 수 있는 시간이 이렇게 적다는 것을 놀랍게 발견했다.
이 글에서 나는 어떻게 벡터 공간 모델로 텍스트의 유사성을 측정하고 PHP로 실제 예를 만드는지 설명할 것이다!

데이터 가져오기 및 사전 처리

우리는 위키백과 저장을 사용하여 이 점을 실현할 것이다.나는 Albert Einstein, Marie Curie(두 과학자), Ludwig van Beethoven과 Florence Price(두 작곡가)의 위키백과 문장 내용을 다운로드했다.
이 가설은 벡터 공간 모델은 두 과학자와 두 작곡가에게 한 과학자와 한 작곡가보다 높은 유사성을 만들어 주어야 한다는 것이다.
우선, 이 글들을 불러오고 미리 처리해야 합니다.

<?php

/**
 * Removes clutter from a text.
 *
 * @param string $text
 * @return string
 */
function preprocess(string $text): string {
    // Remove any citation marks.
    $text = preg_replace('/\[\d+]/', '', $text);

    // Remove any phonetics.
    $text = preg_replace('/\/.*\//', '', $text);

    return $text;
}

/**
 * Reads out an array of texts from a given directory.
 *
 * @param string $dir
 * @return array
 */
function getTexts(string $dir): array {
    $texts = [];

    foreach (glob($dir . '/*.txt') as $file) {
        $texts[] = preprocess(file_get_contents($file));
    }

    return $texts;
}

$texts = getTexts('./texts');

텍스트 자체가 유용하지 않기 때문에, 우리는 모든 텍스트에서 그룹을 만들고, 관련 정보를 얻기 위해 필터를 할 것입니다.

그것을 기호화폐로 나누다

다음에 우리는 이 텍스트들을 표시해야 한다.이것은 우리가 모든 텍스트에 태그 (단어) 그룹을 만드는 것을 의미한다.우선, 우리는 문장부호와 특수 문자를 제거하고, 문자 a부터 z,umlauts, 빈칸, 숫자와 삐침표만 보존해야 한다.그러나 진일보한 처리를 간소화하기 위해서 우리는 먼저 텍스트를 소문자로 쓴다.

<?php

// ...

/**
 * Splits a given text into words.
 *
 * @param string $text
 * @return array
 */
function tokenize(string $text): array {
    $text = strtolower($text);

    preg_match_all('/[a-z0-9äöü\']+/', $text, $tokens);

    return $tokens[0];
}

Stopwords - 무시

우리가 다운로드한 파일은 매우 크다.우리가 만들 벡터 공간은 수백 개의 차원으로 이루어질 것이다. 이것은 특히 디버깅할 때 비현실적이다.비트를 줄이기 위해서 우리는 정지어를 필터해야 한다.
파이톤의 NLTK에는 extensive set of corpora이 있는데, 우리는 모든 종류의 일에 사용할 수 있다.디지털 70은 다양한 언어의 상용어 목록을 포함하는'Stopword'자료 라이브러리로 이 단어들은 의미 가치가 거의 없다('the','it','been','왜냐하면','둘'등).
ZIP 파일을 다운로드하고 스크립트 근처에 있는 영어 중지어 목록을 추출합니다.그리고 나서 우리는 stopwords를 불러와서 그것들로 하나의 그룹을 구성한다.주어진 토큰 그룹에서 정지자를 삭제하는 함수도 정의합니다.

<?php

// ...

$stopwords = explode("\n", trim(file_get_contents('./stopwords_english.txt')));

/**
 * Deletes all stopwords from a list of text tokens.
 *
 * @param array $textTokens
 * @param array $stopwords
 * @return array
 */
function deleteStopwords(array $textTokens, array $stopwords): array {
    return array_values(array_diff($textTokens, $stopwords));
}

이것은 정지어에서 발생하는 소음을 줄여서 관련 정보를 볼 수 밖에 없다는 것을 확보했다.
지금까지 줄곧 괜찮았다.이제 어떡하지?

어떻게 텍스트와 벡터 공간 모델을 실제 비교합니까

텍스트의 유사성 벡터 공간 모델은 매우 간단하다. 벡터 공간을 만들고, 차원마다 단어를 대표한다.모든 문자는 자초한 것으로 여겨진다.
문서는 벡터 공간의 단일 벡터입니다.단일 문서의 벡터의 모든 차원은 이 단어가 텍스트에 나타나는 빈도를 나타낸다.
두 문서를 비교하기 위해 여현의 유사성을 사용했다.이것은 0과 1 사이의 값을 생성합니다. 0은 비슷하지 않고, 1은 완전히 일치하는 것을 나타냅니다.
우리는 이 네 개의 텍스트를 비교하고 싶다.

1. "Hello World"
2. "Hello Code World"
3. "Hello Code"
4. "Code World Hello Code"

우리는 우선 벡터 공간을 계산해 내야 한다.이러한 텍스트를 빠르게 손질하면 세 개의 다른 단어가 생성됩니다.

Hello
World
Code

이것은 우리의 벡터 공간인 3차원이다.이제 네 개의 텍스트를 사용하여 이 공간에 벡터를 만들 수 있습니다.

1. "Hello World" -> (1, 1, 0)
2. "Hello Code World" -> (1, 1, 1)
3. "Hello Code" -> (1, 0, 1)
4. "Code World Hello Code" -> (1, 1, 2)

3D 벡터 공간에 있으므로 다음과 같이 표시할 수 있습니다.

현재 우리는 여현의 싱크로율을 이용하여 모든 텍스트 간의 싱크로율을 계산할 수 있다.
cos(θ)=v1∙v2∣∣v1∣∣⋅∣∣v2∣∣=∑i=1Nwi,1wi,2∑i=1Nwi,12∑i=1Nwi,22
cos(\theta)=\frac{v|u 1\bullet v|u 2}{v|u 1 | | |\cdot | | v|u 2 | |}=\frac{
\sum_{i=1}^{N}{w_{i,1}w_{i,2}
}{\sqrt{\sum{i=1}{N}{w{i,1}^2}}\sqrt{\sum{i=1}{N}{w{i,2}^2}}}
cos(θ)=∣∣v1​∣∣⋅∣∣v2​∣∣v1​∙v2​​=∑i=1N​웨스턴 주, 12세​​∑i=1N​웨스턴 주, 22세​​∑i=1N​wi,1​위스콘스 주, 2​​
어디 있어요?
θ\θθ
두 벡터 사이의 각도입니다.
wn,wn,a,a​
이 단어가 어딘가에 나오는 횟수예요.
nnn
텍스트의 벡터 공간에서
aaa
및
NNN
차원의 수량입니다.
만약 우리가 1과 가장 비슷한 텍스트를 찾고 싶다면."안녕하세요, 세상"--우리는 계산할 수 있다
∑i=1Nwi,12\sqrt{\sum{i=1}{N}{w{i,1}^2}∑i=1N​웨스턴 주, 12세​​
바로: 다행이다
12+12+02=2\sqrt{1^2+1^2+0^2}=\sqrt{2}12+12+02​=2​
.
이제 첫 번째 텍스트와 두 번째 텍스트(1. "Hello World"/(1, 1, 0)와 2)의 여현 유사성을 계산해 봅시다."안녕하세요 코드 월드"/(1,1,1):
∑i=1Nwi,1wi,2∑i=1Nwi,12∑i=1Nwi,22=(1⋅1)+(1⋅1)+(1⋅0)2⋅셋≈0.816
\압열
\sum_{i=1}^{N}{w_{i,1}w_{i,2}
}{\sqrt{\sum{i=1}{N}{w{i,1}^2}}}\sqrt{\sum{i=1}{N}{w{i,2}^2}}}}}=\frac{(1\cdot1)+(1\cdot1)+(1\cdot0)}{\sqrt{2}\cdot3}816
∑i=1N​웨스턴 주, 12세​​∑i=1N​웨스턴 주, 22세​​∑i=1N​wi,1​위스콘스 주, 2​​=2​⋅셋​(1⋅1)+(1⋅1)+(1⋅0)​≈0.816
세 번째 텍스트와 네 번째 텍스트에 대해 우리는
0.50.50.5
및
0.5770.5770.577
.
따라서'Hello World'와 가장 비슷한 텍스트는'Hello Code World'이고,'Code World Hello Code'와'Hello Code'가 그 뒤를 이었다.
우리 프로그래밍을 합시다.

벡터 공간 구축

앞의 절차는 벡터 공간의 비트를 줄이는 데 필요한 것이다.사용 가능한 벡터 공간 모델을 만들기 위해 제로 벡터부터 시작합니다.

<?php

// ...

/**
 * Creates a zero vector of all words in all tokenized texts.
 *
 * @param array $tokenizedTexts
 * @return array
 */
function createZeroVector(array $tokenizedTexts): array {
    $keys = array_unique(array_merge(...$tokenizedTexts));
    return array_fill_keys($keys, 0);
}

텍스트마다 단어가 키로, 0이 값으로 연결된 그룹을 만들 것입니다.
이제 각 텍스트에 대한 벡터를 생성할 수 있습니다.

<?php

// ...

/**
 * Creates a vector for a given tokenized text.
 *
 * @param array $tokenizedText
 * @param array $zeroVector
 * @return array
 */
function createTextVector(array $tokenizedText, array $zeroVector): array {
    return array_merge(
        $zeroVector,
        array_count_values($tokenizedText)
    );
}

이러한 내용을 텍스트에 적용합니다.

<?php

// ...

// Load and proprocess texts.
$texts = getTexts('./texts');

// Create tokenized versions of these texts.
$tokenizedTexts = array_map('tokenize', $texts);

$tokenizedTexts = array_map(function ($textTokens) use ($stopwords) {
    return deleteStopwords($textTokens, $stopwords);
}, $tokenizedTexts);

// Create vector space model.
$zeroVector = createZeroVector($tokenizedTexts);

var_dump(count($zeroVector)); // 5541

// Create vectors for every text.
$vectors = array_map(function ($textTokens) use ($zeroVector) {
    return createTextVector($textTokens, $zeroVector);
}, $tokenizedTexts);

와, 5541비트의 벡터 공간.너무 많아.그러나 정지자를 삭제하지 않으면 5664보다 조금 적습니다.PHP는 배열에 능숙하므로 이 문제를 처리하는 데 아무런 문제가 없을 것입니다.

비교하다

여현 유사성의 공식을 기억하십니까?
cos(θ)=v1∙v2∣∣v1∣∣⋅∣∣v2∣∣=∑i=1Nwi,1wi,2∑i=1Nwi,12∑i=1Nwi,22
cos(\theta)=\frac{v|u 1\bullet v|u 2}{v|u 1 | | |\cdot | | v|u 2 | |}=\frac{
\sum_{i=1}^{N}{w_{i,1}w_{i,2}
}{\sqrt{\sum{i=1}{N}{w{i,1}^2}}\sqrt{\sum{i=1}{N}{w{i,2}^2}}}
cos(θ)=∣∣v1​∣∣⋅∣∣v2​∣∣v1​∙v2​​=∑i=1N​웨스턴 주, 12세​​∑i=1N​웨스턴 주, 22세​​∑i=1N​wi,1​위스콘스 주, 2​​
여기는 많은 화합이 관련되어 있기 때문에 우리는 벡터의 범수를 구할 수 있는 array_reduce과 array_map의 조합을 구할 수 있다
∣∣v1∣∣||v_1||∣∣v1​∣∣
아직 좀 쌓였어요.
v1∙v2v_1\bullet v_2v1​∙v2​
:

<?php

// ...

/**
 * Convenience function: Squares a number.
 *
 * @param int $x
 * @return int
 */
function square(int $x): int {
    return $x**2;
}

/**
 * Convenience function: Summarizes two values, to be used with array_reduce.
 *
 * @param int $carry
 * @param int $x
 * @return int
 */
function summarize(int $carry, int $x): int {
    return $carry + $x;
}

/**
 * Calculates the cosine similarity of two vectors.
 *
 * @param array $a
 * @param array $b
 * @return float
 */
function getSimilarity(array $a, array $b): float {
    $dotProduct = array_reduce(
        array_map(function ($x, $y) {
            return $x * $y;
        }, $a, $b),
        'summarize',
        0
    );

    $normA = array_reduce(array_map('square', $a), 'summarize', 0);
    $normB = array_reduce(array_map('square', $b), 'summarize', 0);

    return $dotProduct / (sqrt($normA) * sqrt($normB));
}

대단합니다. 현재 우리는 이전에 불러온 텍스트를 비교하기 위해 모든 것을 준비했습니다.

<?php

// ...

$m = [
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
];

for ($x = 0; $x < 4; $x++) {
    for ($y = 0; $y < 4; $y++) {
        $m[$y][$x] = sprintf('%0.3f', getSimilarity($vectors[$y], $vectors[$x]));
    }
}

echo '            | Curie  | Einstein | Price | Beethoven |' . "\n";
echo '------------+--------+----------+-------+-----------+' . "\n";
echo '      Curie |  '.$m[0][0].' |    '.$m[1][0].' | '.$m[2][0].' |     '.$m[3][0].' |' . "\n";
echo '------------+--------+----------+-------+-----------+' . "\n";
echo '   Einstein |  '.$m[0][1].' |    '.$m[1][1].' | '.$m[2][1].' |     '.$m[3][1].' |' . "\n";
echo '------------+--------+----------+-------+-----------+' . "\n";
echo '      Price |  '.$m[0][2].' |    '.$m[1][2].' | '.$m[2][2].' |     '.$m[3][2].' |' . "\n";
echo '------------+--------+----------+-------+-----------+' . "\n";
echo '  Beethoven |  '.$m[0][3].' |    '.$m[1][3].' | '.$m[2][3].' |     '.$m[3][3].' |' . "\n";
echo '------------+--------+----------+-------+-----------+' . "\n";

다음 표에서는 다음 결과를 보여 줍니다.

            | Curie  | Einstein | Price | Beethoven |
------------+--------+----------+-------+-----------+
      Curie |  1.000 |    0.221 | 0.157 |     0.178 |
------------+--------+----------+-------+-----------+
   Einstein |  0.221 |    1.000 | 0.151 |     0.189 |
-----------------+--------+----------+-------+-----------+
      Price |  0.157 |    0.151 | 1.000 |     0.305 |
-----------------+--------+----------+-------+-----------+
  Beethoven |  0.178 |    0.189 | 0.305 |     1.000 |
-----------------+--------+----------+-------+-----------+

비록 두 텍스트 조합의 유사성은 그다지 크지 않지만, 우리는 프라이스와 베토벤의 유사성(0.305)이 프라이스와 아인슈타인(0.151)보다 높다는 것을 확실히 보았다.그리고 퀴리와 아인슈타인 사이의 유사성은 퀴리와 프레스 사이의 유사성보다 높다.
이 모형은 통할 수 있다!

배달 생각

이런 방법은 몇 가지 현저한 장점과 단점이 있다. 첫째, 여기는 ML과 관련이 없다.신경 네트워크나 그 어떤 것도 훈련시킬 필요가 없다. 그것은 선형 대수와 함께 일한다.또한 유사성을 정렬하고 문서와 단일 문서의 관련성을 계산할 수 있습니다.
그러나 이 방법은 텍스트의 상하문을 잃어버릴 수 있다. 동의어는 포함되지 않고 용어의 순서도 무시될 수 있다. 이것은 매우 중요할 수도 있다.그러나 이는 N-gram이나 문법 데이터베이스를 통해 해결할 수 있다.용어에 대한 어간 분석도 성능을 향상시킬 수 있다(예를 들어'test'와'testing'은 현재 서로 다른 단어로 여겨진다).
요컨대, 이런 방법은 서로 다른 텍스트를 비교하는 편리한 도구이지만, 오보나 누락의 수를 줄이기 위한 추가 도구가 필요하다.
그리고 here's a PHPSandbox with the code and the texts!터미널을 열고 php ./index.php을 입력하여 실행할 수 있습니다.
나는 네가 이 문장을 즐겨 읽기를 바란다.나는 여가 시간에 과학 기술 문장을 쓰고 가끔 커피를 즐겨 마신다.
만약 당신이 나의 노력을 지지하고 싶다면, buying me a coffee 또는!