Como implementar uma função de kernel do espectro no MATLAB?

Question

A função de kernel espectro opera em cordas contando os mesmos n-gramas entre duas cordas. Por exemplo, 'ferramenta' tem três 2-gramas ( 'to', 'OO', e 'ol), e a similaridade entre 'ferramenta' e 'tolo' é 2. ( 'oo' e 'ol' em comum ).

Como posso escrever uma função MATLAB que poderia calcular essa métrica?

Answer 1

O primeiro passo seria a criação de uma função que pode gerar um n-grama para uma determinada string. Uma maneira de fazer isso de uma forma vetorizado é com alguma indexação inteligente.

function [subStrings, counts] = n_gram(fullString, N)
  if (N == 1)
    [subStrings, ~, index] = unique(cellstr(fullString.'));  %.'# Simple case
  else
    nString = numel(fullString);
    index = hankel(1:(nString-N+1), (nString-N+1):nString);
    [subStrings, ~, index] = unique(cellstr(fullString(index)));
  end
  counts = accumarray(index, 1);
end

Este usa a função Hankel primeiro criar uma matriz de índices que irá seleccionar cada conjunto de subsequências N-comprimento original da cadeia de caracteres dada. A indexação do string dada com esta matriz índice vai criar uma matriz de caracteres com um comprimento N-subsequência por linha. A função CELLSTR seguida, coloca cada linha da matriz de caracteres para uma célula de uma matriz de células. A função ORIGINAL subsequências, em seguida, remove repetidas, e a função de ACCUMARRAY é usado para contar as ocorrências de cada substring única (se eles são necessários para qualquer motivo).

Com a função acima você pode facilmente contar o número de n-gramas rel compartilhada entre duas cordas usando o função INTERSECT :

subStrings1 = n_gram('tool',2);
subStrings2 = n_gram('fool',2);
sharedStrings = intersect(subStrings1,subStrings2);
nShared = numel(sharedStrings);

Answer 2

O que você está procurando é chamado a distância Hamming, você pode obter uma melhor descrição do que se você fizer doc pdist.

A=['Marcin'; 'Martin'; 'Marsha']  %data

squareform(pdist(A, 'hamming'))  returns

         0    0.1667    0.5000

    0.1667         0    0.5000

    0.5000    0.5000         0

Este formulário mostra quantas letras são diferentes. Diferença entre 'Marcin' e 'Martin' é 1 de 6 letras, de modo a obter 1/6 = 0.1667 'Marcin' vs 'Marsha' tem 3 de 6, por isso 06/03 = 0,5
Se quiser que o número real de cartas que são diferentes, basta multiplicar o conjunto de matriz de comprimento (A).