Практические советы по реализации систем извлечения информации

воскресенье, октября 22, 2006

Реализация алгоритма k-средних

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

  1. 0 или 1, в зависимости от наличия слова в документе
  2. Число слов в документе
  3. TF*IDF данного слова
Как правило для документов с малым числом слов (или же просто с набором атрибутов) лучше подходят первые два способа, а для более-менее больших документов на естественном языке TF*IDF.

Полученную сильно разреженную матрицу надо не только хранить в памяти, но и иметь возможность эффективно выполнять разные операции над ними. Библиотек для работы со sparse matrices на Java не так много, а самое плохое, что я не нашел никаких benchmarks. Достаточно удобной в использовании мне показалась Matrix Toolkits for Java.

Радикально ускорить алгоритм можно с помощью уменьшения словаря, убрав из него слова мало влияющие на результат. Как правило, достаточно всего 20-30% слов, чтобы алгоритм работал с практически такой же точностью. Один из самых простых cпособов уменьшения словаря состоит в том, чтобы выбирать слова с наибольшей функцией качества:
n — число всех документов
fi — частота встречаемости слова в i-ом документе.

Существует некий порог размера словаря, начиная с которого алгоритм k-средних начинает работать очень плохо. Обычно он лежит как раз в диапазоне 20-30%. Нужный размер проще всего подобрать экспериментальным путем.

15 комментариев:

Анонимный комментирует...

А откуда взялась такая функция качества? И что она, собственно делает?

krondix комментирует...

Эту функцию качества ввели Inderjit Dhillon, Jacob Kogan и Charles Nicholas. Назвали ее term variance quality.

Для слов, более-менее равномерно распределенных по документам она принимает маленькие значения. Для характерных слов — большие.

Unknown комментирует...

Не понятно. 20-30% от общего словаря (то есть с учетом слов, встречающиеся только в одном документе выборки)?

Функций качество достаточно много (information gain, статистика Хи-квадрат, term strength и пр.).Неужели ниже 20-30% (от всего словоря) при большой выборке (скажем 300 000 документов) качество резко ухудшается?

Unknown комментирует...

Второй вопрос. Увеличение скорости при сокрашении размерности на вашем опыте происходит только для Байеса или для другим методов машинного обучения? (просто я, например, не заметил значительного сокращения скорости обучения (с 450 000 до 50 000) при обучении SVM_Multiclass).

krondix комментирует...

1. Да, конечно, совсем забыл. Сначала выкидываются все слова встречающиеся меньше чем в определенном числе документов. 20-30% это уже от обрезанного словаря.

Качество сильно зависит от словаря и от числа кластеров. Этот момент я тоже упустил. Если кластеров мало и словарь для 300 000 документов состоит из 20 000 слов, то, скорее всего, хватит и 10-15%. Если же кластеров достаточно много (>1000) и есть как большие (по 20 000 документов), так и маленькие (100 документов), да еще и словарь на те же 300 000 размером в 70 000 слов, то при значительном его обрезании, мы можем просто потерять маленькие кластеры.

krondix комментирует...

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."

Настройте пожалуйста выдачу в виде рсс.

krondix комментирует...

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