Метод k-средних для обучения классификаторов Байеса
Алгоритм k-средних (k-means clustering) — очень быстрый, простой и достаточно точный метод кластеризации объектов. Идея заключается в минимизации суммарного отклонения по каждому кластеру:
Здесь,
У метода k-средних есть два серьезных недостатка:
Здесь, Si — k кластеров, μi — центроид i-го кластера. На каждой итерации алгоритма мы перемещаем каждый вектор в кластер с ближайшим центроидом. Хотя не существует каких-либо оценок сложности алгоритма, на практике хватает он сходится за достаточно малое число итераций.У метода k-средних есть два серьезных недостатка:
- Необходимо заранее знать точное число кластеров.
- Качество результата сильно зависит от выбора начального разбиения.
Поэтому, обычно, сначала применяют какой-либо другой метод кластеризации (например, Principal Direction Divisive Partitioning) для определения числа кластеров и получения начального разбиения.
Что будет если применить метод k-средних к задаче обучения классификаторов Байеса на некачественных данных? Действительно, ведь у нас уже есть готовы набор категорий-кластеров и начальное разбиение по ним. Я провел простой эксперимент. Тестовый набор включал в себя три категории документов, условно их можно назвать "Information Retrieval" (С1), "Java" (C2) и "HTML" (C3). Сами документы представляют собой короткие (несколько предложений) отрывки из статей в Википедии. Обучающую выборку я составил следующим образом: к каждой категории были отнесены 100 документов из нее самой и по 15 документов из двух других. После чего я применил Байеса ко всем 390 документам: 62 из них были классифицированны неправильно. Алгоритм k-средних разложил документы в обучающей выборке следующим образом:
Что будет если применить метод k-средних к задаче обучения классификаторов Байеса на некачественных данных? Действительно, ведь у нас уже есть готовы набор категорий-кластеров и начальное разбиение по ним. Я провел простой эксперимент. Тестовый набор включал в себя три категории документов, условно их можно назвать "Information Retrieval" (С1), "Java" (C2) и "HTML" (C3). Сами документы представляют собой короткие (несколько предложений) отрывки из статей в Википедии. Обучающую выборку я составил следующим образом: к каждой категории были отнесены 100 документов из нее самой и по 15 документов из двух других. После чего я применил Байеса ко всем 390 документам: 62 из них были классифицированны неправильно. Алгоритм k-средних разложил документы в обучающей выборке следующим образом:
C1 = 129 * C1 + 2 * C2Заново обученный Байес ошибся уже всего в 5 случаях!
C2 = 1 * C1 + 127 * C2 + 4 * C3
C3 = 1 * C2 + 126 * C3
43 комментария:
Правильно ли я понимаю, что: Вы обучили Байес на 390 примерах (и эти же примеры классифицировали с 62 ошибками). Далее была предварительная (перед повторным обучением) кластеризация обучающего множества (по сути попытка сгладить выбросы классов за счет кластеризации, попытка внести робастность в Байес). Затем алгоритм снова обучили и провели повторную классификацию с 5 ошибками.
То есть кластеризация это предварительный этап перед обучением?
Да, правильно. С помощью кластеризации улучшается качество обучающей выборки для Байеса.
В принципе, для классификации можно использовать и сам метод k-средних, но:
1. Байес работает немного быстрее и требует меньше памяти
2. Байес работает точнее: k-средних дал 8 ошибок, Байес всего 5.
Плюс есть еще один интересный трюк для улучшения качества обучающей выборки, я его, правда, еще не протестировал. Можно обучать Байеса не на всех документах из полученных кластеров, а только на тех, что однозначно отнесены к какому-либо кластеру, то есть расстояние до центроида одного из них сильно меньше расстояний до центроидов других. Есть подозрение, что ошибки кластеризатора представляют собой как раз такие пограничные вектора. На неделе проверю и напишу результат.
Егор, насколько, на Ваш взгляд подходит Байес для задач пополнения веб-каталога с большим количеством рубрик и обучающих примеров (подобных Яндексовскому)?
Понятно, что окончательно выяснить какой метод лучше можно лишь на
практике, но так как используемый метод МО в моем случае не
принципиален (я рассматриваю другой аспект веб-классификатора),
хотелось бы выбрать тот, который должен (хотя бы в теории) быть
подходящим для этой задачи.
Вот размышляю над Байесом и PrTFIDF.
И Байес, и PrTFIDF в чистом виде для классификации страниц по большой иерархии мало подходят. Мало — в первую очередь значит что будет страдать точность. Простой пример. Страница интернет-магазина, какой-нибудь zoom.cnews.ru и некоторые записи из блога того же Олега Артамонова могут содержать практически одинаковый набор терминов. В то же время они относятся не то что к разным категориям, но и к разным ветвям иерархии.
Для некоторых категорий возможно выделить какие-то характерные признаки их отличающие, например, корзина для магазинов. Еще можно попробовать выделить структуру (не только тематику) внешних и внутренных ссылок.
В последнее время я все чаще думаю о замене иерархической классификации набором плоских, что-то вроде тегов. Расставив эти теги, можно будет получить набор подходящих категорий (или даже одну) и поработать с ними.
В общем, проблема, как мне кажется, не в том какой метод текстовой классификации выбрать, проблема где-то рядом.
А работа Дунаева и Шелестова какая-то странная, 80% ошибок из-за обнуления при умножении решаются элементарным логарифмом и результат был бы, скорее всего, примерно таким же.
>> В общем, проблема, как мне кажется, не в том какой метод текстовой классификации выбрать, проблема где-то рядом.
Если мы стремимся получить максимальное качество классификации на всех рубриках, то безусловно нужен индивидуальный подход. Но сейчас мне нужно оценить влияние методов выделения значимой информации на качество классификации, и потому выбранный метод МО не принципиален. Но безусловно неободимо, чтобы он, вообщем, подходил для этой задачи и был не очень медленным.
>> И Байес, и PrTFIDF в чистом виде для классификации страниц по большой иерархии мало подходят. Мало — в первую очередь значит что будет страдать точность.
То что будет страдать точность это понятно. Вопрос насколько?
Понятно, что SVM или kNN отработают лучше, но они меня не устраивают по определенным причинам.
То есть с ухудшением качества относительно SVM процентов на 10-15% я вполне способен смириться :)
По ощущениям и рассказам людей, которые применяют Байеса для веб-классификации точность колеблется в районе 60-70%, что совпадает с точностью иерархического PrTFIDF из Дунаева и Шелестова.
В моей работе данные гораздо проще и однозначнее, поэтому точность гораздо выше — в районе 95%.
>> По ощущениям и рассказам людей, которые применяют Байеса для веб-классификации точность колеблется в районе 60-70%, что совпадает с точностью иерархического PrTFIDF из Дунаева и Шелестова.
Спасибо Егор, остановлюсь тогда на PrTFIDF. Если возникнут проблемы с качеством, будет повод придумать для них решение :)
а каким образом PDDP помогает вичислить количество кластеров ? что-то в описанях всех что нашел , всегда изначально задается кол-во разбиений
Хороший у вас блог! удачи в развитии
Отличный блог у вас, много интересных постов, буду постоянным читателем!
Прикольная статья, узнал много полезного. Сейчас читаю другие публикации
Неплохо написали, нашел для себя много интересного. Продолжайте в том же духе
Статья полезная и приятно изложена, большое спасибо за дополнительный материал!
Интересно написано, но желательно дополнить статью
Ваш блог мне очень понравился, только допишите эту статью
Отличная статья, напишите еще на эту тему, буду с нетерпением ждать
Ой, читай, прям обчитаешься! спасибо за интересную статью
Интересная стратья, узнал для себя несколько новых вещей, щас буду разбираться, в дальнейшем отпигшусь
Хороший у вас блог, дизайн очень понравился, со временем будет мощный блог
ну да, блог мне тоже очень понравился, уже частенько захожу
Статья очень поучительная, будет полезна особенно новичкам
Статья отличная, но советую дополнить материалом, будет больше полезна!
Мне очень понравился ваш блог, особенно дизайн, хочу себе на сайт такой же
Поздравляю вас Старо-Новым годом, желаю вам в новом году успехов и спасибо что вы находите время поддерживать ваш замечательный блог!
Согласе с мнениями многих, статья очень познавательная, прочитав узнал много нового!
Допишите эту статью, то до отличного материала не дотягивает
Блого просто супер, всем советую, непожалеете
Да, почитал вашу статью и был приятно удивлен написанным, мне статья понравилась. Пишите и развивайтесь дальше
интересненько. Статья вовсе неплохо написана
Да, после прочтения, я просто поражаюсь как все это бывает
Полностью согласен с предыдущими комментариями
супер как понравился ваш блог, высокого вам развития
Ок, спасибо большое, статья очень полезная для начинающих
Статья очень понравилась, узнал много полезного, буду пробовать осуществить на практике
Как то видел, но потом долго не мог найти, статья очень полезная. Всем советую
Прикольный болг, много нашел статей нужных, в которых подробно все описано, спасибо
Что то статей не много, лучше добавьте, а так блог нормальный
Hi, i read your blog from time to time and i own a similar one and i was just wondering if you get a
lot of spam comments? If so how do you stop it,
any plugin or anything you can suggest? I get so much lately it's driving me insane so any assistance is very much appreciated.
Look at my web page :: モンクレール ダウン
Write more, thats all I have to say. Literally, it seems as though you relied on
the video to make your point. You clearly
know what youre talking about, why waste your intelligence on
just posting videos to your site when you could be giving us
something enlightening to read?
my webpage :: michael kors
My page :: michael kors womens watches
You must participate in a contest for probably the greatest
blogs on the web. I'll advocate this web site!
Here is my webpage :: クロエ バッグ
That lady revives the regarding cardigans, pleats and in
addition tweeds. It's an opportunity the to learn as to grow for example to expand. It capabilities a rubber outsole for specific holder and speedy in the court moves. Leon Levin offers a wide spectrum of you need to and combinations.. http://www.premierevelocity.com/member/30874/
After I initially left a comment I appear to have clicked on the -Notify me when new comments are added- checkbox and
from now on whenever a comment is added I receive 4 emails with the exact same comment.
Perhaps there is an easy method you can remove me from that
service? Kudos!
my blog post ... Cheap Ray Bans
Wearing nike, noticing become the center of focus
of the view. Any kind of professionally designed custom logo carries its person weight in diverse acts of renseignement.
the Nike Zoom, or you can choose the more popular design Nike Dunks.
All the iconic company is surely a really smash this required Cannes by
way of tornado. http://www.voditel.ru/forum/profile.
php?mode=viewprofile&u=100768
my weblog :: cheap air max
Отправить комментарий