Computationally Effective Algorithm for Information Extraction and Online Review Mining.

 

Авторы: Boris Kraychev, Ivan Koychev.

Источник: http://dse.fmi.uni-sofia.bg/SmartBook/docs/52-kraychev.pdf

 

Вычислительно эффективный алгоритм для извлечения информации из интернет-обзоров.

 

Перевод: Н.А. Сарры

  

1. Введение

Web является крупнейшим источником общедоступного личной мнения, комментариев и отзывов. Число новых страниц публикуемых каждый день в Интернете растет в геометрической прогрессии так же как и количество доступной информации. В связи с расширением Web 2.0 и мобильных интернет-устройств люди могут делиться своим мнением о продукции, новостях, книгах и любых других темах. Становится практически невозможно вручную собирать важную информацию и отслеживать новые тенденции своевременно, без автоматизированной поддержки. Цель этой работы заключается в предоставлении решений для извлечения метаданных веб-страниц, таких как автор, дата публикации, основное содержание, комментарии и т.д. с линейной вычислительной сложностью. Программы, которые выполняют такое извлечение информации, называются оболочками [15].

Каждая веб-страница может быть представлена ​​в виде иерархической структуры элементов, которых обычно около 5000 на каждой странице. Нашей целью является упрощение и согласование этой структуры в меньшую структуру, содержащую нужные метаданные, которая похожа на канал RSS, содержащий от 3 до 5 элементов на страницу. Наш основной подход заключается в исключении не имеющих значения элементов семантической оценки текстового содержания. Наша оболочка снабжена естественно-языковым процессором состоящим из таких инструментов как тэги частей речи (POS-tagger), словарь омонимов и тезарусом.

Насколько нам известно, существующие алгоритмы с деревом выравнивания использующие оболочки имеют вычислительную сложность O(n²)или выше: [16], [5]. Проблемы с использованием дерева выравнивание изучались в теории компиляции, где аналогичная проблема, обнаружения сходства в программном коде структур должна быть решена [1] с линейной вычислительной сложностью. Мы используем подобный подход в нашей оболочке извлечения данных и определяем хеш-функцию, которая линейно сравнивает элементы кандидаты корневых элементов из интернет-страницы с желаемым корневым элементом метаданных дерева.

2. Выполненная работа

Проблема построения оболочки была изучена в таких системах как Сталкер [10], где предлагается символический метод извлечения информации. К сожалению в таком случае система строго зависит от синтаксиса и нуждается в обновлении после каждой модификации HTML дизайна. [14] предлогает алгоритм для измерения расстояния между двумя деревьями. Он имеет вычислительную сложность равную размеру обоих деревьев. Метод зависит

от внутренней топологии дерева, что не обязательно требуется для приводимого содержания извлекаемой информации. [15] предложен алгоритм для извлечения веб-данных на основе частичного выравнивания дерева. Их решение имеет квадратичную сложность и может быть улучшено при определенных ограничениях. [6], а затем другие авторы, такие как [3], использовали синтаксически основанные алгоритмы, которые также связаны с точной структурой веб-страницы. Недавние исследования изучают автоматическую адаптацию оболочки [4] и использование логических марковских сетей [12].

3. Методология

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

Ограничения алгоритма связаны с HTML действиями и структурой веб-страниц для обхода данных. Эта проблема обсуждается более подробно в пункте 3.4.

3.1 Коллекция данных

На анализируемые веб-страницы собраны гусеничным алгоритмом и направлены HTML парсер общего назначения, чтобы получить их иерархическую структуру, а затем обрабатываются анализатором «дата-тип» чтобы назначить их на все конечные узлов одного из следующих типов:

- дата утверждения - например, добавлено {Автор} 20/11/2011;

- комментарий/обзор кандидата - заявление с наличием стилевых ключевых слов;

- кандидат на главный текст - длинный текст страницы, не являющийся ссылкой и содержащий морфологически полные предложения;

- имя существительное – обнаруживаемое с помощью регулярного выражения и списком известных имен собственных;

- посторонние - листья без особых назначенных типов данных.

После того как всем листьям присваивается тип, мы удаляем: все те узлы, типа Посторонние, все узлы не приводящие к одному из оставшихся листьев; и все узлы, имеющие один лист-ребенок.

На следующем шаге для каждого узла задается тройка числовых значений:

- количество подчиненных узлов (и листьев);

- количество слов в подчиненных узлах;

- стилевая оценка.

Эти значения используются как ввод дерева в соответствующую хэш-функцию.

Значение рассчитывается с помощью техники сумка-слов (лексикон (словарь) ключевых стилевых слов) [7]. Такой словарь может быть получен методами, описанными [7]. Значение используется для того чтобы узнать отзывы пользователей и комментарии.

- Фактическая оценка - фактическая оценка рассчитывается по аналогии с оценкой ключевых слов,  с автоматическим построением словаря фактически значащих слов. Применяется метод построения лексики описываемый [8].

- HTML-теги - оригинальный HTML тег узла.

- Количество подобных соседних узлов - число соседних узлы с одинаковыми HTML тегами, подобными ключевыми словами, и колчеством Factual-баллов. Используется для обнаружения повторяющихся структур на странице, таких как комментарии пользователей.

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

3.2 Согласование с оболочкой дерева

Нашей целью является автоматически извлекать Rich Site Summary(RSS) публиковать онлайн-отзывы и комментарии на веб-странице. Желательно получить на выходе простую структуру дерева, которая должна быть привязана к одному из методов, описанных в предыдущем разделе.

Обычный алгоритм, как дерево простых совпадений, и адаптированный центра звезды [16], имеют вычислительную сложность O(n²) или выше. Наш подход заключается в значительном сокращении вычислительной сложности, применяя хеш-функции, которая оценивает суб-деревья в каждом узле. Метод применяется в разработке компиляторов [1] и уместен применительно к извлечению информации. Учитывая, что хэш-функция распределяет N-узлов дерева на B «ведер» сложность алгоритма будет О(N/B). В зависимости от хэш-функции разработки мы можем игнорировать порядок листьев или дерево внутренней структуры и сравнивать деревья только по листьям, содержащим информацию.

Например, результатом работы функции может быть отсортированный список листьев «Типы данных» в основном под-дереве данного узла. Например ‘ACD’ может быть хэш-значением для всех предков равных листу Автора, один лист Комментарий и один Дата-лист, игнорируя их точный порядок в дереве. Противоречия решаются предпочтением узлу с ближайшей высотой и первым горизонтальным возникновением.

3.3 Вычислительная сложность алгоритма

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

Фаза сокращения дерева, которая очищает листья с ненужными типами данных, и родительских узлов, не приводящих к значимым листьям, имеет также линейную сложность и выполняется от листьев к корневому узлу.

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

- связь типа данных - O(N)

- дерево понижение – O(N)

- дерево выравнивания – O(N/B)

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

3.4 Ограничения и решения

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

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

Не все веб-сайты имеют одинаковую структуру основного текста, а также список комментариев или отзывов, но без потери нашей линейной сложности мы можем добавить больше возможностей для сравнения деревьев во время фазы выравнивания дерева. Это приведет к увеличению сложности до O (M х N), M определяется числом совпадающих деревьев, которые меньше данного постоянно и могут быть проигнорированы. Набор для деревьев может быть описан в виде коллекции на странице блога, шаблонов страниц и социальной медиа средой, в зависимости от назначения качества типа данных это может быть излишним.

Выводы

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

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

 

 

 

 

Литература

 

1. Baxter I.D., Yahin A., Moura L., Sant‘Anna M., Bier L. 1998. Clone Detection Using Abstract Syntax Trees. Proc. of ICSM’98.

2. Ciravegna F. 2000. Learning to Tag for Information Extraction from Text. Proc. of the ECAI-2000.

3. Crescenzi V., Mecca G. 2004. Automatic Information Extraction from Large Websites. J. ACM, Vol. 51, Nr. 5 New York, NY, USA: ACM (2004) p. 731—779.

4. Ferrara E., Baumgartner R. 2011. Combinations of Intelligent Methods and Applications – Springer.

5. Ferrara E., Fiumara G., Baumgartner R. 2010. .Web Data Extraction, Applications and Techniques: A Survey., Technical Report.

6. Freitag D. 1998. Information Extraction From HTML: Application of a General Learning Approach. Proc. of the 15th National Conference on Artificial Intelligence (AAAI-98).

7. Godbole N., Srinivasaiah M., Skiena S. 2007. Large-scale Sentiment Analysis for News and Blogs, ICWSM.

8. Grefenslette G., Qu Y., Evans and D.A.,Shanahan J. G. 2006. Validating the Coverage of Lexical Resources for Affect Analysis and Automatically Classifying New Words along Semantic Axes, Springer.

9. Hassan A., Radev D. 2010. Identifying Text Polarity Using Random Walks, Proceedings of the Association for Computational Linguistics.

10. Muslea I., Minton S., Knoblock C. A. 1999. A Hierarchical Approach to Wrapper Induction. Proc. of the Intl. Conf. on Autonomous Agents (AGENTS’99), pp. 190–197.

11. Peng F., McCallum A. 2004. Accurate Information Extraction from research papers using conditional random fields, HLT-NAACL04, p. 329-336.

12. Satpal S., Bhadra S., Sundararajan S., Rastogi R., Sen P. 2011. Proceedings of the 20th international conference companion on World Wide Web, ACM New York, NY, USA.

13. Tekli J., Chbeir R., Yetongnon K. 2009. .An overview of XML similarity: Background, current trends and future directions., Computer science review, vol. 3, no. 3, pp.151-173.

14. Yang W. 1991. Identifying Syntactic Differences between Two Programs. Software Practice Experiment, 21(7), pp. 739–755.

15. Zhai Y., Liu B. 2005. Extracting Web Data Using Instance-Based Learning. Proc. of 6th Intl. Conf. on Web Information Systems Engineering (WISE‘05), pp. 318–331.

16. Zhai Y., Liu B. 2005 Web Data Extraction based on Partial Tree Alignment. Proc. of the 14th Intl. World Wide Web Conference (WWW‘05), pp. 76–85.