Обсуждение:Практикум на ЭВМ (317)/2011-2012
Материал из MachineLearning.
(→R) |
(→R) |
||
Строка 258: | Строка 258: | ||
Для установки языка R (реализация Random Forest) | Для установки языка R (реализация Random Forest) | ||
http://cran.gis-lab.info/ | http://cran.gis-lab.info/ | ||
- | |||
Random Forest | Random Forest |
Версия 11:15, 13 февраля 2012
Содержание |
Реальная задача «Topical Classification of Biomedical Research Papers»
Очень неплохо, Пётр! Вы интенсивно собираете баллы первой части задания.
Только я не уверен, что можно выкладывать файл с данными... Не нарушаем ли мы этим какие-нибудь правила? Ведь для того, чтобы получить данные, надо зарегистрироваться (т.е. они изначально не хранятся в открытом доступе). Корректнее предоставить одногруппникам MATLAB-код для считывания данных (по крайней мере, я писал отдельный код). Удачи! Приятно видеть "наших" в турнирной таблице! Дь-ов 22:22, 9 февраля 2012 (MSK) |
Постановка, данные
Подробное описание задачи: [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 — число документов
- TrueTopicsi — множество верно предсказаных тематик для i-го документа
- PredTopicsi — множество предсказанных тематик для 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)
Классификатор | Результат (он-лайн) | Примечание |
---|---|---|
Линейные L2-reg L2-loss L1-reg L2-loss L2-reg L1-loss liblinear | 0.393 | Различные постановки задачи обучения дали одинаковые ответы (с точностью до выбора тематик), подбор коэффициента регуляризации бессмысленен (уверенная линейная разделимость). Что можно сделать: регулировать пороги решающих правил. |
Предположение: другие классификаторы / методы, принимающие решения независимо, будут давать схожий результат; предположение независимости принадлежности статьи к разным тематикам очень наивно и нужно двигаться в сторону учета зависимостей между тематиками. 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).
Промежуточные результаты: Например, можно посмотреть максимально вероятную рубрику-пару для данной, и упорядочить по этой максимальной вероятности:
если есть | то есть | с вероятностью |
---|---|---|
46 | 50 | 71% |
52 | 73 | 69% |
73 | 52 | 65% |
50 | 46 | 65% |
40 | 42 | 53% |
Вывод. Скорее всего, рубрика 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)
- Терминология, нотация. «метками принадлежности тематикам»... придумать нормальную русскоязычную терминологию и договориться использовать ее, договориться о символьных обозначениях, например , yj. 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' )
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
Ekaterina 15:11, 13 февраля 2012 (MSK)