Как реализовать функцию ядра спектра в MATLAB?

Функция ядра спектра работает со строками, подсчитывая одинаковые n-граммы между двумя строками. Например, слово «tool» имеет три 2-грамма («to», «oo» и «ol»), а сходство между «tool» и «fool» равно 2. («oo» и «ol» общие ).

Как я могу написать функцию MATLAB, которая могла бы вычислить эту метрику?


matlab n-gram
person Community    schedule 27.07.2009    source источник
comment
Мне кажется, что вы заинтересованы в создании функции ядра для какой-то другой цели, скажем, для классификатора машины опорных векторов. Для этого одно только расстояние Хэмминга не использует все преимущества доступной информации. Посмотрите ссылки на источники здесь: en.wikipedia.org/wiki/String_kernel Удачи! Я пытаюсь сделать то же самое.   -  person    schedule 07.08.2011

Ответы (2)


arrow_upward
2
arrow_downward

Первым шагом будет создание функции, которая может генерировать n-грамму для заданной строки. Один из способов сделать это в векторной форме — использовать умную индексацию.

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

При этом используется функция HANKEL, чтобы сначала создать матрицу индексов, которая будет выбрать каждый набор уникальных подстрок длины N из данной строки. Индексация данной строки с помощью этой индексной матрицы создаст массив символов с одной подстрокой N-длины на строку. Затем функция CELLSTR помещает каждую строку массива символов в ячейку. массива ячеек. Затем функция UNIQUE удаляет повторяющиеся подстроки, а функция ACCUMARRAY используется для подсчета вхождений каждой уникальной подстроки (если они необходимы для какой-либо причине).

С помощью приведенной выше функции вы можете легко подсчитать количество n-грамм, разделенных между двумя строками, используя ПЕРЕСЕЧЕНИЕ:

subStrings1 = n_gram('tool',2);
subStrings2 = n_gram('fool',2);
sharedStrings = intersect(subStrings1,subStrings2);
nShared = numel(sharedStrings);
person gnovice    schedule 27.07.2009
comment
Вы должны добавить subStrings = intersect(subStrings, subStrings); к функции n_gram, чтобы избежать повторения. Например, n_gram('hubbub', 2) будет иметь повторяющийся элемент ub в исходной формулировке. - person mtrw; 28.07.2009
comment
@mtrw: Хороший вопрос, но функция UNIQUE работала бы лучше. Я обновлю соответственно. - person gnovice; 28.07.2009
comment
Уф. Да, UNIQUE было бы куда уместнее. - person mtrw; 28.07.2009

arrow_upward
-1
arrow_downward

То, что вы ищете, называется расстоянием Хэмминга, вы можете получить более точное описание, если сделаете 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

Эта форма показывает вам, сколько букв отличается. Разница между «Marcin» и «Martin» составляет 1 из 6 букв, поэтому вы получаете 1/6 = 0,1667. «Marcin» и «Marsha» имеют 3 из 6, поэтому 3/6 = 0,5
Если вы хотите фактическое количество букв, которые отличаются, просто умножьте всю матрицу на длину (A).

person Marcin    schedule 05.08.2009
comment
Это не совсем похоже на то, что описывает вопрос. - person gnovice; 05.08.2009