Реализация алгоритма k-средних
Документы-вектора можно представить несколькими способами, выбрав разные значения в качестве их элементов:
- 0 или 1, в зависимости от наличия слова в документе
- Число слов в документе
- TF*IDF данного слова
Как правило для документов с малым числом слов (или же просто с набором атрибутов) лучше подходят первые два способа, а для более-менее больших документов на естественном языке TF*IDF.
Полученную сильно разреженную матрицу надо не только хранить в памяти, но и иметь возможность эффективно выполнять разные операции над ними. Библиотек для работы со sparse matrices на Java не так много, а самое плохое, что я не нашел никаких benchmarks. Достаточно удобной в использовании мне показалась Matrix Toolkits for Java.
Радикально ускорить алгоритм можно с помощью уменьшения словаря, убрав из него слова мало влияющие на результат. Как правило, достаточно всего 20-30% слов, чтобы алгоритм работал с практически такой же точностью. Один из самых простых cпособов уменьшения словаря состоит в том, чтобы выбирать слова с наибольшей функцией качества:
Полученную сильно разреженную матрицу надо не только хранить в памяти, но и иметь возможность эффективно выполнять разные операции над ними. Библиотек для работы со sparse matrices на Java не так много, а самое плохое, что я не нашел никаких benchmarks. Достаточно удобной в использовании мне показалась Matrix Toolkits for Java.
Радикально ускорить алгоритм можно с помощью уменьшения словаря, убрав из него слова мало влияющие на результат. Как правило, достаточно всего 20-30% слов, чтобы алгоритм работал с практически такой же точностью. Один из самых простых cпособов уменьшения словаря состоит в том, чтобы выбирать слова с наибольшей функцией качества:
n
— число всех документовfi
— частота встречаемости слова в i
-ом документе.Существует некий порог размера словаря, начиная с которого алгоритм k-средних начинает работать очень плохо. Обычно он лежит как раз в диапазоне 20-30%. Нужный размер проще всего подобрать экспериментальным путем.
15 комментариев:
А откуда взялась такая функция качества? И что она, собственно делает?
Эту функцию качества ввели Inderjit Dhillon, Jacob Kogan и Charles Nicholas. Назвали ее term variance quality.
Для слов, более-менее равномерно распределенных по документам она принимает маленькие значения. Для характерных слов — большие.
Не понятно. 20-30% от общего словаря (то есть с учетом слов, встречающиеся только в одном документе выборки)?
Функций качество достаточно много (information gain, статистика Хи-квадрат, term strength и пр.).Неужели ниже 20-30% (от всего словоря) при большой выборке (скажем 300 000 документов) качество резко ухудшается?
Второй вопрос. Увеличение скорости при сокрашении размерности на вашем опыте происходит только для Байеса или для другим методов машинного обучения? (просто я, например, не заметил значительного сокращения скорости обучения (с 450 000 до 50 000) при обучении SVM_Multiclass).
1. Да, конечно, совсем забыл. Сначала выкидываются все слова встречающиеся меньше чем в определенном числе документов. 20-30% это уже от обрезанного словаря.
Качество сильно зависит от словаря и от числа кластеров. Этот момент я тоже упустил. Если кластеров мало и словарь для 300 000 документов состоит из 20 000 слов, то, скорее всего, хватит и 10-15%. Если же кластеров достаточно много (>1000) и есть как большие (по 20 000 документов), так и маленькие (100 документов), да еще и словарь на те же 300 000 размером в 70 000 слов, то при значительном его обрезании, мы можем просто потерять маленькие кластеры.
2. Я тестировал Байеса и k-средних. Для них увеличение скорости заметно. Конечно, оно не строго пропорционально уменьшению словаря. В моих тестах k-средних при словаре в 30% работал примерно на 50% быстрее.
Извините что немножко не по теме, но вот информация оказалось полезной и частообновляемой, а "Subscribe to Posts (RSS)" не работает.
Фидбернер рассказал "This feed is making a “clunking” sound.
This publisher's content was recently unavailable so FeedBurner cannot present it at this time.
What to do?
Contact the publisher to notify them that their feed content is not available. This may be temporary problem, or the publisher may have permanently removed the feed from FeedBurner.
If you cannot reach the publisher, you may contact FeedBurner to report the problem. Please include the error code and message detail displayed below in your posting:
Feed Address: http://feeds.feedburner.com/krondox
HTTP Error Code: 404
Detail: Feed not found error: FeedBurner cannot locate this feed URI."
Настройте пожалуйста выдачу в виде рсс.
Cпасибо! Это я опечатался в ссылке. Правильно будет http://feeds.feedburner.com/krondix
[color=#000000]Особенности оценки кредитоспособности крупных и средних предприятий. Понятие интеллектуальной собственности. Японская модель корпоративного управления. Явление материального мира как объект открытия. [/color]
[url=http://tapikort.ru/]стратегический менеджмент[/url]
Доброго времен суток,
Надежная и проверенная [url=http://popplers.ru/]адалт партнерка[/url] [b]Popplers.ru[/b] предлагает Вам сотрудничество на выгодных условиях. Мы покупаем ваш ру трафик по выгодным ценам. Владельцам сайтов, вебмагазинов и веб мастерам мы предоставляем выгодные условия, отзывчивую поддержку и проффесиональный подход в нелегком бизнесе рунета.
отличная возможность быстро заработать, выгодная рефферальная программа, направьте ваш ру трафик в нужное русло, в русло прибыли которое принесет вам [url=http://popplers.ru/]Партнерка[/url] [b]Popplers.ru[/b] . Вывод средств в WebMoney или PayPal, возможность срочных выплат в любой день недели, личный подход к каждому партнеру.
Наши тарифы за 1000 уников:
DoorWays - 6у.е.
Popunder - 5у.е.
CJ - 5 у.е.
Clickunder - 4 у.е.
Ждем Вас в нашей программе!
Support: 498994074
Купить саксофон, флейту, кларнет и др. музыкальные духовые инструменты
вы можете купить в Москве.
Покупка, продажа, уроки, ремонт, аренда, рассрочка без %, гарантия 5 лет, 10 лет на рынке,
24 часа в сутки 7 дней в неделю
МЫ РАБОТАЕМ НА ВАШ ТАЛАНТ!
+7 (495) 789-23-69
E-mail:CityBand@inbox.ru
http://www.CityBand24.RU
Продам диски с фото-видео по теме Foot Fetish (hotlegsandfeet.com, footfetishporno.com, sexyfootgirls.com и пр.) а так-же контент с сайта publicsluts.com(и подобных). Доставка по Украине. Наш сайт xxx-ukr.com !!! ICQ 472855546
Наша Стекольная и Зеркальная Мастерская занимается розничной продажей стекла, продажей зеркал импортного производства и изделий из них. Все изделия производятся по размерам и в соответствии с пожеланиями Заказчика.
стеклянные полки купить, зеркало для ванной, зеркало для ванной комнаты, зеркало для ванной комнаты с полкой
http://www.Zerkala-Steklo.RU/
+7 (495) 972-69-34
E-mail: 9726934@mail.ru
Предлагаем дизайн интерьера от Dvizov.RU
Дизайн интерьера от Мастерской Макса Двизова.
Основное направление деятельности мастерской является интерьерный дизайн и дизайн экстерьера зданий, а так же комплексное архитектурное проектирование, дизайн интерьера, архитектурное проектирование, согласование и строительство, дизайн экстерьера, дизайн интерьера
e-mail: dvizov@inbox.ru
+7 926 444-14-43
+7 (495) 223-17-85
http://www.Dvizov.RU/
Предлагаем качественные подставки под цветы напольные, подставки под цветы металлические, подставки под цветы кованые, подставки под цветы декоративные, подставки под цветы стойки, стойки для цветов, стойки для цветов напольные
ПодставкаСтойка.Ру
http://www.PodstavkaStoika.RU/
+7 (499) 390-01-68
E-mail: 4993900168@mail.ru
Отправить комментарий