Материал из MachineLearning.

Реальная задача «Topical Classification of Biomedical Research Papers»

Итак, результат 0.482 можно получить простой MATLAB-программой (всего 940 байт с комментариями!), используя лишь стандартные функции size, sparse, bsxfun, full и т.д.

Постановка, данные

Подробное описание задачи: [1].

Объект (журнальная статья) описывается 25640 признаками --- целые числа 0...1000. Каждый признак означает насколько сильно журнальная статья связана с медецинским термином. Признаковые описания разреженные: большая часть признаков у одного объекта равны 0, что означает что одна журнальная статья связана лишь с небольшим числом медецинских терминов.

Имеется 83 тематик (topics). По признаковому описанию журнальной статьи нужно сказать, к каким тематикам она относится. Выход классификатора: подмножество чисел 1..83.

Данные:

• тренировочная выборка, 10'000 объектов, для каждого объекта список тематик, к которым он относится
• тестовая выборка, 10'000 объектов

На сайте соревнования выложены текстовые файлы с матрицами объект-признак, после распаковки они весят под 500МБ и очень долго считываются в матлаб. Я сделал MAT-файл data.mat (ссылка в рассылке), в котором лежат sparse-матрицы (вид представления матриц в матлабе при котором запоминается список ненулевых элементов матрицы):

• X, X_t — объект-признак для тренировочной и тестовой выборок;
• Y — матрица правильных ответов для тренировочной выборки, размера 10'000x83, в каждой строке стоят единицы на месте столбцов с номерами выбраных тематик.

Матлаб функция, которая записывает результат классификации, представленный в виде матрицы Nx83 (как Y), в файл готовый для отправки в систему: [2].

Пример: решение, которое каждому объекту ставит в соответствие 5 наиболее часто встречаемых тематик

load('data.mat');
[~, idx] = sort(sum(Y), 'descend');     % после чего в idx номера тематик в порядке убывания их популярности
Y_t = sparse(size(X_t, 1), size(Y, 2)); % пустая матрица ответа
Y_t(:,idx(1:5)) = 1;                    % для каждого объекта выбираем 5 наиболее популярных тематик
sparse2labels(Y_t, 'majority.csv');

Peter Romov 16:15, 9 февраля 2012 (MSK)

Система оценки

Качество результата подсчитывается при помощи стандартной в Information Retrieval метрике: F-score.

Введем обозначения:

• N — число документов
• TrueTopics_i — множество верно предсказаных тематик для i-го документа
• PredTopics_i — множество предсказанных тематик для i-го документа

Величины Precision и Recall для документа i:

Можно самому подсчитывать качество работы алгоритма на некоторой проверочной выборке, при условии что к ней есть правильные ответы (ground truth).

Обратите внимание: результат, которые выдает система он-лайн проверки подсчитывается на случайном подмножестве тестовой выборки, в 10 раз меньшем всей тестовой выборки.

Peter Romov 22:16, 9 февраля 2012 (MSK)

Пример matlab кода для вычисление F-меры:

function F=fscore(Y,A) 
 %Y-predicted
 %A-true
 %Y and A are n x 83 matrices where n is the size of validation set
 %Y(i,j)==1 if i document refers to j topic
 N=size(Y,1);
 Y=(Y==1)';
 A=(A==1)';
 c=(Y==1)&(A==1);
 tp=sum(c);
 p=tp./sum(Y==1);
 r=tp./sum(A==1);
 f=2*(p.*r)./(p+r); 
 F=sum(f(~isnan(f)))/N;

Kondra 23:13, 12 февраля 2012 (MSK)

Тестирование

Тестировать лучше на своей машине. Для этого можно разбивать множество объектов на два случайных подмножества: обучение и контроль. А затем проводить серию обучение/тестирование на нескольких случайных разбиениях.

matlab код функции разбивающей данные на два случайных подмножества:

function [X,Y,Xt,Yt]=splitData(S,y,n)
 %S-матрица объект-признак
 %y-матрица ответов
 %n-желаемый размер первого множества
 [m,~]=size(S);
 idx=randperm(m);
 X=S(idx(1:n),:);
 Y=y(idx(1:n),:);
 Xt=S(idx((n+1):end),:);
 Yt=y(idx((n+1):end),:);

Тестировать можно так:

function [favg,f]=test(S,y,n,m)
 %S-матрица объект-признак
 %y-матрица ответов
 %n-количество серий
 %m-желаемый размер контрольного множества
 %favg-усредненная f-мера по серии тестов
 %f-массив f-мер
 f=zeros(n,1);
 for i=1:n
     [X,Y,Xt,Yt]=splitData(S,y,m);
     model=train(Xt,Yt);
     label=classify(X,model);
     f(i)=fscore(label,Y); 
 end
 favg=sum(f)/n;

Разница между оценкой, полученной данным способом, и оценкой с сайта не превосходила .

Kondra 23:43, 12 февраля 2012 (MSK)

Я думаю стоит зафиксировать разбиения и выложить его сюда, чтобы мы могли честно сравнивать результат. Peter Romov 09:24, 13 февраля 2012 (MSK)

Эксперименты

Независимые классификаторы

Идея: свести задачу предсказания "подмножества" к задаче классификации на 2 класса.

Обучаем набор из 83 классификаторов для независимого решения по каждой тематике, каждый классификатор соответствует одной тематике и отвечает на вопрос "относится/не относится".

На некоторых объектах может получиться так, что ни один классификатор не дал положительного результата, но результат "пустое множество тематик" не допускается по правилам.

Эту проблему я решил эвристически: такие объекты привязываются к одной тематике, выбирается та тематика, чей классификатор дал наиболее близкое к положительному решающее значение, т.е. чей классификатор наименее уверенно ответил отрицательно на вопрос "относится ли объект к тематике?" Таких объектов в тестовой выборке оказалось 188 (линейные классификаторы). Peter Romov 21:28, 9 февраля 2012 (MSK)

Утверждение: признаков в 2.5 раз больше числа объектов ⇒ по отношению к одной тематике, обучающая выборка линейно разделима, очень уверенно разделима. Peter Romov 21:28, 9 февраля 2012 (MSK)

Предположение: другие классификаторы / методы, принимающие решения независимо, будут давать схожий результат; предположение независимости принадлежности статьи к разным тематикам очень наивно и нужно двигаться в сторону учета зависимостей между тематиками. Peter Romov 21:28, 9 февраля 2012 (MSK)

Классификация данных как текста (метрический алгоритм)

Идея: Считаем, что представленные величины являются просто количеством соответствующих терминов в тексте, так же используем независимые классификаторы по всем рубрикам.

Заменяем матрицу данных на классическую матрицу из весов :

• (term frequency — частота слова) — отношение числа вхождения некоторого слова к общему количеству слов документа. Таким образом, оценивается важность термина в пределах отдельного документа:

• (inverse document frequency — обратная частота документа) — инверсия частоты, с которой некоторый термин встречается в документах коллекции. Учитывает тот факт, что если термин встречается во многих документах множества, то он не может являться существенным критерием принадлежности документа рубрике и наоборот:

После нормализации полученных весов строим т.н. «центроиды» — стандартизированные представители рубрик — просто среднее арифметическое векторов-представителей данной рубрики и запускаем простой метрический алгоритм для тестовой выборки — относим вектора к центроидам, которые ближе, чем некий порог, либо к минимально близкому из практических соображений.

Более подробно можно посмотреть, например, в дипломной работе.

Результат: Удалось достичь результата 0.306 с упущенной из виду нормировкой весов — итоговую функцию можно посмотреть здесь. (Вектора относятся к классам, центроиды которых удалены не более, чем на 0.8. Время построения матрицы весов — 25 минут, время классификации тестовой выборки — 2.5 часа на C2Dm/2.5GHz).

Пути улучшения: Попробовать другие метрики, модификации матрицы .

nizhibitsky 21:32, 12 февраля 2012 (MSK)

Выделение частичной иерархии

Идея: Наилучшим продолжением идеи Евгения Зака о поиске «часто вместе встречающихся» рубрик будет вычисление поддержки — ничто иное как условная вероятность совместной встречи категорий.

Реализация: Составляем матрицу условных вероятностей, например, так:

sup = zeros(83,83);
for i=1:83
    for j=1:83
        if sum(y(:,j)>0.5)~=0 && i~=j
            sup(i,j) = sum(y(:,i)>0.5&y(:,j)>0.5)/sum(y(:,j)>0.5);
        end
    end
end

Здесь - вероятность наличия рубрики при наличии рубрики (я не уверен в каноничности порядка индексов — гугл не признается, как же правильно записывается support).

Промежуточные результаты: Например, можно посмотреть максимально вероятную рубрику-пару для данной, и упорядочить по этой максимальной вероятности:

Вывод. Скорее всего, рубрика 50 является «хирургией» для «переломов» 46 (не наоборот!).

nizhibitsky 13:04, 13 февраля 2012 (MSK)

Идеи

• Цепочка независимых классификаторов. Как использовать простую классификацию на два класса, но все таки учитывать зависимости между метками принадлежности тематикам? Например так: принимать решение по тематике 1 исключительно по признакам, решение по тематике 2 принимать по {признакам + принадлежности тематике 1}, ..., решение по тематике N принимать по {признакам + решениям о тематиках 1...N-1}. Т.е. образовать "цепочку" из классификаторов. Peter Romov 21:41, 9 февраля 2012 (MSK)

• Разбиения. Зафиксировать несколько разбиений имеющейся обучающей выборки на тренировочную/тестовую, которую все будут использовать для оценки точности алгоритма. Это может быть полезно т.к.: 1) он-лайн система тестирования считает качество алгоритма на случайном подмножестве всей тестовой выборки (в правилах написано, что используется ≈10% объектов), т.е. оценка качества может быть неточной; 2) количество попыток отправить ответ на тестовой выборке ограничено 200 попытками, это много, но все же. Peter Romov 21:48, 9 февраля 2012 (MSK)

Случайное подмножество выбрали до начало конкурса — оно фиксировано для всех отправляющих. nizhibitsky 00:29, 10 февраля 2012 (MSK)

• Терминология, нотация. «метками принадлежности тематикам»... придумать нормальную русскоязычную терминологию и договориться использовать ее, договориться о символьных обозначениях, например , y_j. Peter Romov 21:41, 9 февраля 2012 (MSK)

• Зависимость рубрик. Идея такова: раз это реальные медицинские статьи, то рубрики, к которым они принадлежат, могут быть зависимы (например, статья из рубрики "переломы рук" точно принадлежит рубрике "хирургия"). Для того, чтобы проверить эту гипотезу я посмотрел сколько раз какие две рубрики встречаются вместе для всех статей. и получил следующие результаты (более подробно(а именно таблицу пар) напишу 13 вечером, а то спать хочется=)):

1)Из 3403 возможных пар рубрик 2377(69,9%) пар хотя бы раз встречаются вместе;

2)Среди количества одновременных встреч: минимальное 0, максимальное 1278 раз, среднее 27,68 раз. Количеств, больших среднего: 1130(23,8%).

Отсюда мысль: если статья принадлежит рубрике A, и есть рубрика B, такая что А и В вместе встречаются очень часто(скажем чаще, чем пороговое k), то наша статья принадлежит и рубрике В. E_zak 03:13, 13 февраля 2012 (MSK)

Инструменты

LIBLINEAR

LIBLINEAR — библиотека с алгоритмами линейной классификации. Отличается тем, что может работать с очень большими матрицами объект-признак достаточно быстро, может справляться с разреженными матрицами объект-признак, которые в полном объеме не помещаются в память.

Подготовка к использованию с MATLAB. Нужно скачать архив, распаковать его, пользователям не-windows прочитать README и собрать MEX-файлы. Затем в матлабе нужно добавить путь к каталогу с MEX-файлами библиотеки (у пользователей windows это подкаталог liblinear/windows), после чего должны появиться функции train и predict, если их вызвать без параметров, они покажут справочную информацию.

addpath c:/.../liblinear/windows
>> train
Usage: model = train(training_label_vector, training_instance_matrix, 'liblinear_options', 'col');
liblinear_options:
...
>> predict
Usage: [predicted_label, accuracy, decision_values/prob_estimates] = predict(testing_label_vector, testing_instance_matrix, model, 'liblinear_options','col')
liblinear_options:

Обучение модели. Пример: натренируем классификатор, отличающий документы относящиеся к категории 1 от всех остальных.

>> model = train( full(Y(:,1)), X, '-s 3 -c 100 -B 1' )

Функция имеет параметр -v N, который позволяет провести N-fold скользящий контроль, в таком режиме train выдает не модель, а точность классификации на скользящем контроле — это может помочь при настройке параметров.

Классификация. Функции классификации обязательно нужно передавать правильные метки для объектов для того чтобы она посчитала точность классификации, если правильных ответов нет (вы считаете результат на тестовой выборке — нужно сделать вектор из нулей).

>> Y_p(:,1) = predict(zeros(size(X,1), 1), X, model)
>> Y_p(:,1) = predict(full(Y(:,k)), X, model)
Accuracy = 99.36% (9936/10000)

Peter Romov 11:43, 13 февраля 2012 (MSK)

R

Для установки языка R (для реализации Random Forest) http://cran.gis-lab.info/

Random Forest http://cran.r-project.org/web/packages/randomForest/index.html

Пособие (минимальное и не факт, что адекваное, по R) http://en.wikibooks.org/wiki/R_Programming

Ekaterina 15:11, 13 февраля 2012 (MSK)