Автоматический анализ текста без модераторов

Недавно на Хабре появилась статья об автоматическом реферировании статей. Так случайно получилось, что я тоже занимаюсь автоматическим анализом текстов и добился в этом некоторых успехов.

Мне удалось добиться того, чтобы алгоритм находил повторяющиеся и близкие по содержанию тексты. Также он автоматически определяет близость текста к определенным тематикам и выделяет из общей массы те тексты, которые составляют некоторый мэйнстрим. То есть, читателю не придется просеивать всю информацию, чтобы понять главное. С увеличением объема анализируемых текстов автоматически будет отсеяно все некачественное, неинтересное, нецензурное, неактуальное, и т.п.

Идея алгоритма заключается в том, что текст разбивается на цепочки, потом производится их сравнительный анализ, выделяются специальные маркеры, на основе которых принимаются решения.

Анализ производится полностью в автоматическом режиме без модератора и главного редактора. Из-за этого алгоритм иногда ошибается и может поместить текст не в тот раздел, но причина этого скорее в том, что изначальный набор текстов обычно бывает сгруппирован с еще меньшей тщательностью. Со временем алгоритм становится все более и более аккуратным, так как со временем накапливается достаточно статистической информации.

Это не все. Алгоритм способен понимать юмор. Если текст выбивается из общей массы и блистает несуразицами, то алгоритм выделит его и пометит как «Юмор». Алгоритм вполне качественно находит шутки, а если что и не смешно — так это скорее от того, что алгоритм не очень долго работает, всего несколько недель. То есть, он еще не успел понять, что кое что уже и не смешно.

Также в автоматическом режиме можно находить новые идеи. Например, в городе Копейске в роддом провели Интернет, чтобы отцы не стояли под окнами и не выкрикивали своих жен в попытке издалека разглядеть лицо своего ребенка, а смотрели на него через Skype. Или курортникам Ялты советуют носить свисток и вооружаться газовыми баллончиками, так как в городе открыт сезон краж и грабежей. А вот Польша будет рекламировать свои яблоки в России на деньги ЕС.

Идеи выискиваются не всегда интересные, но с накоплением «опыта» и это должно исправиться. Желающие же смогут найти подходящую идею и среди того, что уже выискивается.

Алгоритм действующий и его работу можно посмотреть на сайте nfos.ru. Сайт занимается тем, что собирает новости из нескольких источников, анализирует и публикует все, что посчитает нужным опубликовать. Теперь я могу похвастаться тем, что не напрягаясь знаю все главные новости. Чего и вам желаю.

Например, вы уже знаете, что на Навального завели дело по подозрению в рейдерстве? Или слышали ли вы о том, что в Пакистане продано рекордное количество портретов Осамы?

Я так думаю, что алгоритм сгодится не только для анализа текстов, но и для анализа изображений и других неструктурированных данных или данных с не очевидной структурой. Например, для отсеивания шума, для расшифровки, анализа алгоритмов по результатам их работы и т.д. и т.п. Алгоритм потенциально сгодится для предсказания котировок акций и курсов валют, но до всего этого я вряд ли доберусь в ближайшее время, так как времени не хватает.

Весь алгоритм анализа уместился в 40 кбайт кода PHP плюс порядка 70 кбайт кода для оформления новостного ресурса. Согласитесь, что для появившегося функционала это просто мизер. Но на что действительно алгоритм прожорлив, так это на занимаемое пространство. За несколько недель накопилось уже более 1,5 гбайт информации в базе данных. И объем этот постоянно растет.

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

Напоследок хочу сказать, что для анализа не потребовался мощный хостинг. Все новости из порядка 150 источников анализируются на дешевом хостинге FirstVDS-Разгон который обходится в 249р/мес. Процессорного времени, конечно, маловато, но это заставило меня оптимизировать алгоритм, что удалось сделать без видимых потерь.

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 107

    +14
    Это всё конечно хорошо, но будет ли разобран/открыт алгоритм/код?
      +1
      У меня большие сомнения в целесообразности этого.

      Классификация текстов на основе HMM — это, в принципе, хорошо. Но
      1) посимвольная (!), причем используются модули глубокого анализа текста с АОТ
      2) со скоростью 300 байт/с, с 4 SQL (!!)- запросами на символ (!!!)
      — это уже даже не плохо. Это никак.
      HMM работают со скоростью сотен тысяч правил в секунду. SQL здесь вообще непонятно, каким боком, работать нужно даже не с внешним key-value хранилищем, а прямо в памяти процесса.

      И, совет, не нужно думать, что вы написали личинку универсального алгоритма, который и поиск, и искусственный интеллект, и автоматический брокер, а то, что он пока не работает — так это просто текстов мало. Это всего лишь крайне неэффективная реализация задачи классификации документов. Вот ниже Вам советуют съездить на РОМИП — не поедете, так хоть труды почитайте, дорожка классификации там есть уже много лет.
        0
        В принципе можно выбрать любой размер блока для анализа. Я выбрал блок размером в символ, так как при этом можно извлекать достаточно большое количество ассоциаций из памяти. А чем больше статистической информации, тем уверенней можно принимать решения. Если у кого-то есть предпочтение на другой размер блока, то это, скорее всего, тоже будет резонно.

        Я думаю, что лучший результат можно будет получить, если предварительно сделать преобразование Фурье. Возможно, это даже сократит необходимое количество запросов к БД на обработку одного символа и улучшит ассоциативность.

        Оперативная память не подходит, так как, например, уже сейчас накопилось 1,8Гб информации и это далеко не предел. А учитывая, что программа крутится на достаточно тормозном виртуальном сервере, то скорость в 300 байт/с мне кажется не такой уж и низкой.

        Спасибо за ссылку на РОМИП, почитаю. Вы тоже меня поймите, я не так давно занимаюсь этим делом и еще не успел найти свободные/доступные продукты, которые дали бы мне хотя бы тот функционал, который я получил со своим ПО. Не подумайте, что я возомнил о себе что-то сверхъестественное, количество уникальных идей в алгоритме, по сути, исчезающе мало. Но дорогу осилит идущий и я, конечно же, хочу использовать передовой опыт других людей.
          0
          Просто замечательно, что у Вас есть желание глубже разобраться в задаче. :)
          Возможно, я был излишне резок, просто мне кажется, что количество туманных анонсов о возможностях алгоритма пока что плохо соотносятся с его качеством.

          Дорожки классификации РОМИПа со списками литературы, в принципе, должно быть достаточно. Также настоятельно советую взять тот же набор данных и прогнать свой алгоритм на них, чтобы объективно оценить его качество по сравнению с остальными.
          Если РОМИП перерастете, вот тут есть совсем фундаментальная теория. Ваша задача — из области классификации, или обучения с учителем.
      +3
      Алгоритм обязательно будет открыт. Только я здесь новичок и могу публиковаться, как выяснилось, только в песочнице, что, конечно, комично и вовсе не вдохновляет.

      Если кратко, то идея такая: текст — это последовательность символов. Эта последовательность можно принять как причину и следствие. Например, в тексте «абв» за «а» следует «б», за «б» следует «в».

      То есть: а->б->в. Эта последовательность так и запоминается: а->б и б->в.

      Если вдруг возникнет противоречие, то оно будет разрешаться. Например, допустим, что алгоритму дадут проанализировать «обг». Соответственно будут цепочки: о->б и б->г. А в сумме:

      а->б
      о->б
      б->в
      б->г

      Здесь за «б» следуют и «в» и «г». Чтобы решить проблему алгоритм аннулирует зависимости б->в и б->г и запоминает новые:

      аб->в
      об->г

      Ну вот, в общем, основная идея. Дальше остается организовать поиск цепочек и анализировать насколько они противоречат/не противоречат друг другу.
        0
        А как быстро работает алгоритм? Можно ли его использовать для форумов?
          0
          На текст ~300 байт уходит ~1 сек. Это на FirstVDS-Разгон, где дают максимум 5% процессора при заявленных 400Мгц.

          Насчет форумов — не понятно с какой целью его использовать. Чтобы составлять ленту на главной странице? Может быть вы скажете что бы вы хотели получить в результате?
            0
            Секунда на 300 байт — это что, полный перебор что ли?
              0
              да, полный анализ текста. При этом производится около 1-2 тыс SQL-запросов.
                0
                на 300 байт!!!???
                  0
                  Вас что-то смущает?

                  Основное время уходит на обращение к БД. 3-4 SQL-запроса на обработку одного символа — я бы сказал немного. Учитывая, что нужно искать максимальную цепочку по каждому символу, а цепочки доходят до 500 символов и более.

                  Кстати, вы, наверное, думаете, что FirstVDS — это быстрый хостинг?
                    +1
                    А какого плана там SQL запросы? может лучше key-value заменить? (redis например)
                      0
                      Может лучше вообще в память всасывать всю базу? Какой размер?
                        0
                        Сейчас размер базы с индексами >1,7Гб. Из них данные занимают порядка 1Гб. Прирост размера около 200Мб/день.
                          0
                          Используйте memcache для ускорения ну и в самой программе тоже не помешало бы сделать кеш с временем жизни записей основанной на статистике по частоте запросов тех или иных ключей.
                            0
                            Основная задержка не в алгоритме, а в обработке SQL-запросов. На это уходит около 75% времени и более.
                              +1
                              так вы запросы и кешируйте
                                +3
                                Кеширую.
                                0
                                Да но его надо заполнять только тогда, когда оно не заполнено.

                                Пример: запрос объекта в кеше с id = 1, если объекта нет — грузим из БД, если есть грузим из памяти и обновляем поле времени последнего обращения. В след раз, если таймаут жизни записи в кеше не выйдет, то оно там будет лежать и запрос к БД не потребуется. К тому же можно еще подумать над системой оптимизации запросов к БД… но это сложней.
                              0
                              Я думаю для этого можно использовать sphinx с его аттрибутами. Должно помочь.
                            0
                            В принципе, именно key-values данные там и хранятся. Заменить можно, но я лично сомневаюсь, что прирост в скорости будет. По крайней мере не на этом хостинге.
                              0
                              Будет, причем теоретически должен быть большой большой. Можно попробовать Berkley DB использовать
                        +9
                        Хороший алгоритм. Производители и продавцы железа будут довольны.
                  +1
                  Последовательность символов или слов?
                    0
                    Я беру последовательность символов. Для ускорения и облегчения анализа я текст несколько готовлю (strtolower, выбрасываю символы) и ввел некоторые легкие ограничения. Например, я анализирую не полную последовательность, а беру текст по предложениям. Для новостного ресурса этого оказывается достаточно.
                      +1
                      Мммм… а если символы заменить целыми словами (приведенными к неопределенной форме) и анализировать соответственно большие тексты. Будет работать?

                      А как работает категоризация (отнесение текста к какой либо теме)? Я так понимаю алгоритм обучается на подготовленном наборе текстов генерируя для цепочки?
                        0
                        Думаю работать будет. Но при этом увеличивается количество вариантов на каждый последующий элемент. А это значит, что цепочки будут взаимодействовать друг с другом слабее, а это значит, из памяти будет извлекаться значительно меньше «ассоциаций», необходимых для анализа.

                        Я думаю, что в идеале количество вариантов на последовательность не должна превышать 2. 256-65536 (в случае utf-8) все еще не так много. В качестве костыля ваша идея пойдет, но мне кажется, что надо стремиться к идеалу, как вы думаете?

                        А категоризация как раз работает на принципе запоминания категории при запоминании цепочки и при вспоминании ее при поиске максимально запомненной цепочки. Дело в том, что каждый источник я помечаю темой, но если вспомненные цепочки говорят, что полученный из источника текст соответствует другой категории, то я его перепомечаю.
                        0
                        Что такое «специальный маркер»?
                          +1
                          дата создания, категория, номер кластера, конформность/противоречие, уникальность и некоторые другие. Часть из них извлекается из базы, а часть вычисляется на ходу.

                          Кстати, выяснилось, что русский язык без учета регистра и знаков препинания изменяется примерно на 90%, 10% остается неизменной.
                            0
                            Что значит «язык изменяется»?
                              0
                              я имел ввиду, что в текстах русского языка средняя длина выстраиваемых последовательностей составляет около 10 символов.
                      +2
                      У вас уже почти достаточно кармы для написания поста… Тема интересная, будем ждать подробное описание алгоритма )
                        0
                        Спасибо
                      +1
                      Посмотрел сайт. Много новостей не в своей категории находятся. Например в Экономике про отключение света и.т.д.

                      Работа со словарём мне кажется надёжнее. Слова приводятся в начальную ворму и сверяются со словарём категорий, составленным либо вручную либо автоматически на основе статистических данных прогоном например по Ленте.ру.
                        0
                        Вы не поверите, новостные ресурсы помещают информацию об отключении света именно в раздел «Экономика». Именно поэтому ваш метод вряд ли покажет лучший результат, но уж точно будет требовать больше трудозатрат, если вы захотите составлять словарь вручную.
                          0
                          Несомненно со словарём сложнее. Но не обязательно его составлять вручную, можно просто на основе статистики по избранным ресурсам. Некоторые ресурсы не правильно определяют категорию, другие напротив.

                          Просто словарь можно загрузить полностью в оперативную память и вести поиск мгновенно.
                          По поводу определения схожести текстов — тут поможет алгоритм Шинглов. Быстрый и простой алгоритм.
                            0
                            Ну сложность думаю одинаковая, что обучатся на последовательностях слов длинной, что на последовательностях символов. Точность заранее предсказать сложно, но как правило на шумах как раз со словарями работает система хуже.
                            О этих языковых моделях можно почитать здесь alias-i.com/lingpipe/demos/tutorial/classify/read-me.html.
                              0
                              А от куда в новостях «Шумы»?
                              Я как понял под Шумом понимаются слова, в которых допущена ошибка?
                                0
                                Да вы правильно поняли. Бывает и в новостях опечатки, хотя редко конечно. Поэтому как раз словари(или классификация по словарям) для новостей должны работать лучше, а для твитов хуже.
                        +1
                        Корректно ли будет вот такое обобщение: по факту вы формируете некоторое множество (нечеткое?) символьных цепочек которые встречаются во всех обучающих текстах для каждой категории?
                          0
                          Что значит нечеткое? В некотором роде да.
                            0
                            Тогда следующий вопрос: результаты рубрикации поступающих данных дополняют потом обучающее множество? Т.е. если вы разобрали новую новость и определили ее в категорию «экономика», то скорректированные цепочки этой новости будут определять принадлежность следующих за ней новостей к этой рубрике? Или же используется только ядро цепочек, построенное на обучающей выборке?
                              0
                              Детектированная категория не запоминается. Это для того, чтобы алгоритм не стал «самоуверенным». Если какая-то цепочка засветилась в нескольких категориях, то ее категория аннулируется, так как становится недостоверной.

                              Можно, конечно, выстраивать вероятности появления цепочки в категориях, но я посчитал, что это затратно. А на практике оказалось, что этого и не требуется.
                            0
                            Все таки, последовательность символов является строгой и составляет причину->следствие.
                              0
                              Ну иногда вводят понятие вероятности. Т.е. после последовательности аб->г c вероятностью 0.4 аб->c с вероятностью 0.6. У вас получается все цепочки имеют вероятность 1.
                                0
                                Да, получается так. Алгоритм ищет постоянную структуру анализируемых данных. Но если сохранять статистику частоты выбираемых цепочек, то можно будет вычислять и вероятности. Но требования к вычислительным ресурсам при этом значительно ужесточатся.

                                Впрочем, алгоритм прекрасно распараллеливается и если он будет выполняться на множестве маломощных ядер (синапсов?) то можно будет сохранять и статистику.
                                  0
                                  Не очень понятна схема разрешения конфликтов. Если у вы видите что у вас две последовательности символов ведут к разным предложениям вы расширяете(левую часть) их до тех пор пока конфликт не решится? Можно подробнее как вы это делаете?
                                    0
                                    Не так. Если я вижу, что одна предпосылка ведет к разным следствиям, то я помечаю, что она не достоверна, расширяю левую часть предпосылки и запоминаю ее следствие. На этом конфликт и разрешается.
                                      0
                                      по идее ваш алгоритм не будет работать на темах в которых разное соотношение одних и тех же слов. Т.е. вы удаляете все неоднозначности и оставляете только уникальные стопроцентные свойства последовательности — это конечно сильно экономит память. Но таким образом категория c текстами B A A A A B и A B B B B A не будут отличатся так как у них одинаковые последовательности — отличие только в их вероятностях.
                                        0
                                        Note: А и B это очень длинные слова
                                          0
                                          Если важна вероятность, то ее можно запоминать. Мой алгоритм можно будет для этого приспособить за счет ужесточения требований к вычислительным ресурсам, конечно.
                                    0
                                    к его алгоритму сложно прикрутить вероятность, так как если будет аб->c и аб->г, он сделает (Symbol1)аб->c и (Symbol2)аб->г
                                      0
                                      Это возможно, но значительно увеличивает затраты, так как при обработке каждого символа требуется (множественно) обновлять информацию в базе.
                                0
                                Можно ли сказать так что вы храните для каждого текста его непротиворечивые(удаляя конфликты по вышеописанному алгоритму) цепочки и маркеры(в которых хранится категория). И видя новый текст вы понимаете его категорию и дубликат ли он по ближайшему тексту из базы?
                                  0
                                  Да, это так.
                                  +4
                                  Вашему марковскому методу не хватает сравнения с уже существующими.
                                  Методов анализа текста, в т.ч. автоматической кластеризации и классификации много, о части из них можно почитать в книге Д.Ландэ «Интернетика»: webground.su/services.php?param=book&part=internetica_content.htm#content.
                                  А для сравнения результатов разных методик есть семинар РОМИП: romip.ru.
                                  Сейчас там идет запись в школу RUSSIR, очень рекомендую съездить (август, Питер).
                                    0
                                    Хорошо бы, конечно, купить Маннинга «Введение в информационный поиск», но, боюсь, до будущего переиздания эта задача маловыполнимая.
                                      0
                                      С августа 2011 года в продаже доступна допечатка книги Маннинга и др. «Введение в информационный поиск»

                                      Увы, но почти весь первый тираж выкупил Яндекс для своих целей
                                      0
                                      К сожалению, съездить не смогу, так как у меня в это намечается важное событие, да и кроме того я ограничен в возможностях.

                                      По поводу своего алгоритма хочу сказать, что его возможности не ограничиваются кластеризацией, так как он выстраивает причинно-следственные связи. А это значит, что его можно использовать для предугадывания событий. Мне даже кажется, что он сгодится и для построения искусственного интеллекта уровня человека. Поэтому я и стараюсь его развить.

                                      Речь о творческой составляющей. До понимания процесса поиска идей я уже дошел, дальше надо понять то, как этими идеями пользоваться.
                                        +1
                                        Ээээээ… нахождение общих подпоследовательностей сложно назвать выстраиванием причинно-следственных связей. А уж про искусственный интеллект лучше вообще не говорить всуе.
                                          0
                                          Ну я бы конечно сказал что весь искусственный интеллект на данный момент, это сложение и умножение над числами. И самая простая вещь такая как сбор статистики слов дает поразительные результаты классификации — предсказания! (я о Наивном баесе). Но скептицизм конечно есть относительно этого алгоритма, так как по той же статистике новое придумывают очень редко.
                                            0
                                            Ну тут о баесе вообще речи не идет даже близко.
                                            0
                                            А чем же это не причинно-следственные связи?
                                              0
                                              Тогда любой биграммный анализ — причинно-следственный. Не говоря уж о трех-, четырех- и т.д. n-граммном.
                                              Кстати, Гугл продает статистику пентаграмм для английского языка. Не интересует?
                                              Ваш алгоритм — подвид обычных марковских цепей, где вероятности принимают только 2 значения (0 и 1). Так же точно Вы собираете статистику, только оставляете одну цепочку, а не несколько с разными весами. Критерий разделения цепочек между категориями — тоже известная вещь.
                                              А что до творчества — машина обыгрывает чемпиона в шахматы, сочиняет неплохие с виду стихи (кстати, тоже марковскими методами), оптимально торгует на бирже, и… что? Это интеллект и творчество?
                                                0
                                                Насколько я понимаю, биграммный шифр — это метод преобразования. Я же рассматриваю текст как последовательность символов. Если есть последовательность, то из нее легко выделить предпосылки и следствия.

                                                Насчет статистики пентаграмм спасибо, я подумаю об их покупке. И насчет ссылки на Маркова тоже спасибо, думаю это будет полезно освежить это в памяти.

                                                По поводу творчества могу сказать следующее, машина далеко не самостоятельна. Она делает то, что ей говорят. А если не делает — то «глючит» и ее надо «починить». Впрочем, я считаю, что заложенные алгоритмы составляют интеллект, ведь с помощью их она принимает решение. Но творчество появится тогда, когда появится самостоятельность. Вы посмотрите что происходит сейчас — если сейчас машине не надо производить вычисления, то в halt ее в halt! Концлагерь какой-то…
                                                  0
                                                  Биграмма — последовательность из 2-х символов в тексте.
                                                  N-грамма — последовательность из n символов в тексте.
                                                  Из них набирается словарь и считается статистика.
                                                  На мой взгляд, Вы делаете РОВНО то же самое.
                                                  Дальше по этой статистике Вы делаете и классификацию и кластеризацию (последнее Вы называете мэйнстримом). То, что не укладывается (прочее) можно считать «новыми идеями».
                                                  Однако относительная доля мусора в этом остатке, естественно, возрастает. Копаться в этом "..." ради редких жемчужин вряд ли кто-то захочет.
                                                    0
                                                    вообще-то «новые идеи» являются новыми для самого алгоритма, который лопатит информацию не так уж и долго по времени. Взрослого человека конечно же не особо будет интересовать то, что является откровением для ребенка. Я считаю, что тут вопрос лишь во времени.

                                                    Но важно не это. Я считаю, что можно продвинуться дальше и сделать так, чтобы система смогла извлекать выгоду от тех идей, которые найдет.
                                                      0
                                                      Алгоритму-то наплевать, что это: «новые идеи» или нестандартные комбинации n-грамм.
                                                      Эффект будет ровно один и тот же.
                                                      Вот еще трудность: с ростом словаря n-грамм будет расти время обработки входного потока. Причем при широких границах n разнообразие n-грамм, а, следовательно, и объем словаря неограничен.
                                                        0
                                                        Нестандартные дестабилизирующие комбинации n-грамм — это юмор. А вот неожиданно всплывающая стабильная комбинация n-грамм — это уже идея. Вы так не думаете?

                                                        Кстати, у юмора тоже есть своя теоретическая основа. Тот же Петросян, составляя свои выступления, тоже действует по системе. Я об этом как-то читал.

                                                        Пока я еще не пришел к пониманию того, как можно пользоваться идеями, но я попытаюсь это понять. А как пойму, так и эффект будет.

                                                        По поводу трудности скажу, что сложность алгоритма n*log(n), где n — длинна текста. Мне кажется, что это не так уж и плохо. Например, у алгоритма быстрой сортировки сложность такого же уровня.
                                                          0
                                                          А, понял, нестандарт — юмор. Давайте сначала напомню анекдот про стандартные комбинации:
                                                          «Комиссия входит в сумасшедший дом, все пациенты собрались в кружок.
                                                          Один из пациентов говорит: „18“ — все смеются, другой: „24“ — снова смех.
                                                          Комиссии поясняют: все анекдоты пронумерованы, чтобы не терять время на рассказ.
                                                          Вдруг кто-то говорит: „44“ — молчание, а затем возглас: „Как не стыдно, здесь дамы!“

                                                          Так что, вряд ли. Поясню.
                                                          Нестандарта при ограниченном наборе n-грамм просто не будет.
                                                          А при неограниченном — его будет все больше и больше (закон Ципфа пока никто оспорить не смог). В этом случае Ваши нынешние 2Гб — так, семечки. И Вы считаете, что основная часть — юмор?

                                                          А что до сложности, неограниченность роста этого самого n гарантирует неограниченную сложность.
                                                          Попробуйте отсортировать массив хотя бы из триллиона элементов.
                                                            0
                                                            Все таки, при n=512 нестандартные комбинации будут встречаться еще очень и очень долго. А если пустот, все таки, станет маловато, то n можно будет увеличить.

                                                            Кстати, говоря о сложности я имел ввиду, что n — это длина обрабатываемого текста вне зависимости от длин хранящихся в памяти цепочек. Впрочем, максимальную длину цепочки я все-таки ограничил. Поэтому, сложность алгоритма на больших объемах информации становится почти линейной.

                                                            По сути, рассказанная в анекдоте история не имеет права на жизнь, так как анекдот интересен своей неожиданностью. Ну, а раз так то история сама становится анекдотичной.

                                                            С другой стороны, даже при неограниченном n могут образовываться места скопления n-грамм. Если текст специальным образом подготовить (например, сделать преобразования Фурье), то места скопления будут более или менее систематическими и можно будет выявлять закономерности.

                                                            Дальше уже вопрос будет не в величине n, а в количестве действующих закономерностей. Размер базы данных, конечно будет достаточно большим, но:

                                                            1. От размера базы будет зависеть подготовленность алгоритма к распознанию новизны. А знание — это сила. Если же будет сила, то будет и возможность подбавить вычислительной мощности.

                                                            2. При необходимости, слишком редко встречающиеся или малозначимые комбинации можно удалять. И тогда количество юмора в хранилище уменьшится, а количество информации о закономерностях, соответственно, увеличится.

                                                            Но зря вы так скептически относитесь к юмору. В известном афоризме говорится, что добрым словом и пистолетом можно добиться значительно большего, чем одним только добрым словом. Так же и с юмором: знанием и юмором можно добиться значительно большего, чем одним только знанием. Так как юмор может помочь там, где знаний нет.
                                        +6
                                        извините, я правильно понимаю, что вы утверждаете, что сделали семантическую классификацию текста с помощью синтаксического разбора, при чём не какого-то особенного, а просто нахождения редакционного расстояния?

                                        извините, но хоть какие-нибудь наглядные результаты есть, кроме странного сайта, на котором просто куча спарсенного RSS?
                                          +4
                                          вы не подумайте ничего плохого. просто мы сами некоторое время уже раздумываем об алгоритмах семантического анализа новостей, и если ваш алгоритм настолько действеннен, как вы его описываете, то мы бы его может даже купили.
                                          однако у меня огромный скептицизм на этот счёт. мы работали некоторое время с журналистами, и знаем специфику создания текстов ими. часто бывает, что статья в какое-нибудь СМИ создаётся журналистом методом «накопируй разных предложений из разных источников, отсортируй, чтоб схожее по смыслу было рядом». из-за этого часто поиск в гугле по выдранному из текста предложению выдаёт десяток-другой точных совпадений в разных, казалось бы, статьях. это может оказаться и единственной причиной кажущейся эффективности вашего алгоритма.
                                          а абзац про
                                          > Я так думаю, что алгоритм сгодится не только для анализа текстов, но и для
                                          ещё больше подливает масла в огонь. как бы это не оказалось просто вашим максимализмом.
                                            –2
                                            Может быть в моих словах и можно учуять запах максимализма, но говоря я стараюсь опираться на то, что видел, то есть, на результат работы алгоритма. При некоторых настройках он действительно не очень хорошо работает. Но как мне кажется, мне удалось его сбалансировать.

                                            Кстати, алгоритм можно использовать для поиска, так как он ориентируется не на ключевые слова и вообще не на слова, а на максимально близкие ассоциации по каждому символу в тексте. Что позволяет снизить влияние ошибок/опечаток.
                                              0
                                              > на максимально близкие ассоциации по каждому символу в тексте
                                              максимально близкая ассоциация в тексте к символу «А» — символ «Б»? да вы шутите, либо рвёте мне шаблон. я склоняюсь к первому.
                                              требую срочно предоставить описание алгоритма, иначе подумаю, что на хабре одним школьником больше.
                                                +1
                                                Основная идея алгоритма описана во втором комментарии к этой статье. Благодаря Trept'у я теперь знаю, что это разновидность марковской цепи. Если нужны еще подробности, спрашивайте — отвечу.

                                                Если что, прошу меня простить. Я не хотел рвать вам никакой шаблон.
                                                  0
                                                  марковские цепи хороши в статистическом анализе. в смысловом разборе они вообще никак не показали своей целесообразности. я бы даже сказал, наоборот.
                                                    0
                                                    Собственно, цепи я использую для разбиения информации на части и для обращения к ним при необходимости. Так сказать, для поиска ассоциаций. Анализ производится потом, при манипулировании информации извлеченной из памяти благодаря ассоциативным связям.

                                                    А что вы имеете ввиду под «смысловым разбором»?
                                            +2
                                            Я этому тоже подивился, поэтому и спросил про возможность использования целых слов, а не символов. Если использовать слова, то можно построить матрицу расстояний и свести все к кластеризации термов по этой матрице.
                                              –1
                                              В моем случае рассматриваются не слова, а символы, что позволяет набрать значительно больше статистики и снизить влияние шума/ошибок/опечаток. Вот если вы напишите слово с ошибкой, то Гугл его не найдет, а вы найдете в чем ошибка, и мой алгоритм с большой долей вероятности найдет к нему близкое верное слово.
                                                0
                                                Ну это и есть эффект редакционного расстояния. Я просто пытаюсь понять возможности и ограничения подобного «синтаксически-ориентированного» алгоритма.
                                                  0
                                                  вы гуглом пользовались давно? у них шикарная защита от опечаток в виде предположений «возможно, вы имели в виду». а у вас в русском языке будет огромное количество коллизий, к примеру «муха» и «меха» будут иметь одинаковое значение относительно опечатки «мха», даже если вы вводили «размножение мха». с большим успехом вместо вашего алгоритма можно было бы использовать diff. он хотя бы не имеет сложность O(n^n).
                                                    0
                                                    Боже упаси, сложность моего алгоритма значительно ниже и приблизительно составляет n*log(n).

                                                    Я понимаю ваше восхищение относительно способности гугла производить предварительную синтаксическую коррекцию, и принимаю его. Но в своем алгоритме я пытаюсь пройти несколько дальше этого.
                                                0
                                                Классификация текста — это побочный продукт алгоритма. Я считаю, что алгоритм имеет значительно более широкие возможности, так как он выстраивает причинно-следственные связи. А это значит, что его можно использовать для предугадывания событий.

                                                Если говорить о классификации, то, как мне кажется, мне удалось достигнуть оптимального уровня. Некоторые внутренности алгоритма можно увидеть здесь: creature.pishi.info/associate2/. По понятным причинам, я отключил запись, но в памяти уже достаточно, чтобы результат был интересен. Кое что там самопоясняющееся, а если что заинтересует конкретно — спрашивайте.
                                                  +1
                                                  ввел туда одну старую новость из своей RSS ленты
                                                  Москву и Московскую область окутал едкий торфяной дым. Насколько он опасен для здоровья и как можно уменьшить неблагоприятное воздействие гари на организм? Читаем здесь
                                                  Выдало вроде как:
                                                      [extremetopic] => Humor
                                                      [brothershiptopic] => Idea

                                                  правильно ли я понял что топик считается юмором? Сложно что-либо понять из внутренностей ибо все там меряется в попугаях…
                                                    0
                                                    Нет. Детектированный топик отображается в переменной «topic2». extremetopic — это указание машине того, куда помещать тексты отличающиеся экстравагантностью. brothershiptopic — это указание машине того, куда помещать тексты, которые при своей экстравагантности содержат старые истины.
                                                    0
                                                    с каждым новым комментарием вы всё больше мне напоминаете автора BolgenOS.
                                                    мне очень жалко прошлый хабрахабр, который теперь выдаёт инвайты таким, как вы.
                                                      0
                                                      случайно нажал на отправку раньше, чем надо. по вашей ссылке из 10 самых первых и самых популярных новостей за неделю (а я знаю, что это так, т.к. мой бизнес сейчас основан на новостях) 10 попали в рубрику юмор.
                                                      я пас, и ничего не понимаю в этой жизни. 32 плюса в карму новичку за какую-то [censored].
                                                        0
                                                        Очевидно вы смотрели на переменную extremetopic, а надо было смотреть на topic2, так как детектированный раздел отображается там.

                                                        Впрочем, не смею больше отнимать у вас время.
                                                          0
                                                          нет, ни в коем случае не на extremetopic.
                                                          topic и topic2 там по ссылке были патологически пусты, перепроверил сейчас снова. я смотрел по цифрам, выдаваемым в «topics», т.к. подумал, что это означает предположительный вес детектирования темы. странно, но кроме «Humour» ещё большие цифры выдавались на Sport и Top news. возможно я ошибся, и эти цифры ничего не означают, но тогда этот алгоритм мне вообще ничего не выдал ни на одну новость.
                                                            0
                                                            topic пуст потому, что он используется для запоминания информации, а от вас эту информацию для запоминания я не запрашиваю.

                                                            topic2 пуст, очевидно, потому, что система не может для вашего текста однозначно определить категорию, а поэтому не принимает решения. В случае новостного ресурса система сохранит ту категорию, которая будет ей дана перед началом анализа.

                                                            Далее по выбранному/данному топику будет взято значение из loyaltopic и если оно будет слишком мало, то новость будет отсеяна как непопулярная. Если же новость важна, то о ней обязательно напишут еще раз и еще раз, и будут по разному оформлять. После нескольких повторов, во-первых, накопится ассоциативная информация по разделу для данной информации, что позволит точнее определить категорию, а, во-вторых, повысит популярность сообщения и вероятность его публикации.

                                                            Можно, конечно, модифицировать алгоритм для того, чтобы он точнее определял категорию с первого анализа, но тогда для анализа потребуется значительно больше вычислительных ресурсов. Но надо ли это, если информация с большой долей вероятности все равно будет отсеяна?
                                                  +4
                                                  Поскольку описания алгоритма в статье нет, не стоит ли ее поместить в раздел «Я пиарюсь»? Что она делает в профильном блоге, если технических подробностей никаких?
                                                    +6
                                                    резонно. но «Я пиарюсь» из песочницы — это совсем жестоко.
                                                      0
                                                      Согласен, но чем отличаются посты «из песочницы» от всех остальных, кроме того, что они из песочницы? Если за пост дали инвайн, вероятно, он достоин Хабра.
                                                        0
                                                        Гм… оговорка по Фрейду :) Не инвайн (in vain), а инвайт :)
                                                          0
                                                          как бы не хотелось обратного, но если за пост дали инвайт, это значит только то, что нашёлся человек, которому этот пост был интересен.
                                                          а в «Я пиарюсь» для того и ограничение на min 20 кармы, чтоб хабр не превратился в доску объявлений.
                                                          +1
                                                          Просто добавь воды :)
                                                    +1
                                                    Относительно производительности в этом проекте рекомендую использовать TJ7
                                                      +1
                                                      Пробовали на хабра-комментариях?
                                                      Совпадают ли выводы алгоритма с оценкой общественности, выраженной в плюсах?
                                                      0
                                                      Ну вот на данный момент топ-комент по этой статье:

                                                      > Это всё конечно хорошо, но будет ли разобран/открыт алгоритм/код

                                                      Если выводы алгоритма будут совпадать с ним, вам это что-то скажет о его эффективности? :)
                                                        0
                                                        Если смотреть комментарии ниже топ-коммента, то в них будет раскрыт/разобран и алгоритм и исходный код.
                                                        0
                                                        Только в некоторых из них, хотя они не всегда буду даже в рамках средних плюсиков…
                                                        Просто потому что специалистов всегда меньше чем людей, читающих наискось строчки 3-4 запроса к БД на символ, и коментирующих нечто вроде Хороший алгоритм. Производители и продавцы железа будут довольны. Или уточняющих в каком блоге правильно разместить вашу статью.
                                                        К сожалению.
                                                          0
                                                          И всё-таки! Ближайшее будущее за высокоэффективными технологиями эвристико-смысловой обработки текстов. Математико-статистические и линвистические методики не оправдали себя и более того, показали свою беспомощность.
                                                            0
                                                            Эвристико-смысловая обработка текстов — это как?
                                                            0
                                                            А ровно так, как у человека.
                                                            Ведь мы, когда общаемся с помощью языковых коммуникаций, не вычисляем ни морфологию, ни синтаксис, ни семантику. Люди и мыслят и понимают друг друга с помощью Моделей Поведения Образов (Объектов). Они перманентно выстривают эти МПО в своём сознании всю жизнь и пользуются ими для декодирования естественно-язычных сообщений.
                                                            Процесс извлечения из памяти этих МПО протекает эвристически, а осмысление текста (речи) человек осуществляет с целью понимания (распознавания) мыслей, которые автор заложил в своё сообщение. (См. habrahabr.ru/post/142733/)

                                                            Only users with full accounts can post comments. Log in, please.