Диссертация (1137276), страница 18
Текст из файла (страница 18)
Моренко мы разработали небольшую утилиту WikiDP (Wiki Download and Parse) для извлечения дерева категорий изВикипедии. Она устроена так: пользователь вводит название категории из Википедии и получает на выходе дерево категорий, лежащее под этой категорией.В программе WikiDP мы учили все перечисленные трудности.
Во-первых, припопадании в новую категорию мы проверяем, была ли уже она посещена, еслида, то переходим к следующей категории, если нет, выполняем обход даннойкатегории – так мы избегаем циклы. Во-вторых, мы предлагаем пользователю ввести ограничение на глубину дерева категорий, после чего программаWikiDP показывает пользователю все подкатегории на заданном расстоянии отисходной категории и пользователь может выбрать нужные ему подкатегории.Используя WikiDP мы смогли извлечь из Википедии необходимые статьи.Пользовательский интерфейс WikiDP представлен на Рис. 6.2. Для работы с утилитой пользователь должен ввести в поле “Название категории” название категории Википедии, которая его интересует.
При этом, пробелы следуетзаменить на знак нижнего подчеркивания “_” . После этого возможны три сценария работы с утилитой:– Создать дерево категорий: сохранить в файл “data.txt” дерево категорий, корнем которой будет введенная категория;– Скачать статьи по дереву: извлечь из Википедии все тексты статей,принадлежащих к введенной категории и всем ее подкатегориям. Приэтом, если дерево категорий содержит цикл, WikiDP не сможет завершить работу и войдет в бесконечный цикл;– Скачать статьи данной категории: извлечь из Википедии все текстыстатей, принадлежащих к введенной категории. Этот сценарий не содержит угрозы бесконечного цикла, поскольку не предполагает перехода вподкатегории.Флажок “Названия статей” позволяет управлять пользователю содержанием дерева категорий: если он находится в положении “включено”, в деревокатегории будут включены названия статей.
В обратном случае, названия статей в дерево категорий включены не будут.106Рисунок 6.2 — Пользовательский интерфейс WikiDPРисунок 6.3 — Извлеченное дерево категорий категории “Дискретнаяматематика” без названий статейНа Рис. 6.3 приведен пример извлеченного дерева категорий категории“Дискретная математика” без названий статей.107ЗаключениеВ работе предложена теоретико-множественная модель представленияколлекций текстовых документов. В отличии от классических моделей – векторной, вероятностной или языковой моделей – в предлагаемой теоретико-множественной модели коллекции текстовых документов текст рассматривается некак набор термов, а как последовательность символов.
Представлением текстаслужат все символьное последовательности фиксированной длины и короче иих частоты. Утверждается, что только такое модельное представление текстапозволяет создать меру релевантности «строка – текст», не зависящую от размера входной коллекции и учитывающую нечеткие (то есть, с различием нанесколько символов) совпадения между строкой и текстом. Вводится понятиемаксимального совпадения – такого совпадения между строкой и текстом, которое при добавлении к нему символа слева и справа, перестает быть совпадением.
Именно максимальные совпадения и их частоты служат основной длявычисления нечетких оценок релевантности.Для вычисления частот теоретико-множественной модели предлагаетсяиспользовать метод аннотированного суффиксного дерева, который позволяетза линейное от размера текста время найти всего его фрагменты заданной длины и короче, а также вычислить их частоты.
В работе впервые построена модельнормированного аннотированного суффиксного дерева и введена ассоциированная с ней естественно интерпретируемая мера релевантности СУВСС, а такжеметод ее вычисления nAST-k. Предлагаемая мера релевантности СУВСС представляет собой среднюю условную частоту символа в максимальном совпадениии позволяет находить оценки релевантности строки тексту, которые– не зависят от размера входного текста или коллекции текстов;– учитывают нечеткие совпадения между входной строкой и текстом.Мера релевантности СУВСС была использована для построения таблиц релевантности «строка – текст», которые в дальнейшем используются для решенияконкретных практических задач.Предложены и верифицированы методы для решения следующих задач:1.
Метод рубрикации научных статей AnnAST в соответствии с системойрубрик, заданной таксономией. Метод позволяет получить для каждойнаучной статьи некоторое фиксированное количество таксономических108тем, отражающих содержание научной статьи. Множество таксономических тем формируется в соответствии с оценками СУВСС. Показано,что использование СУВСС в задаче рубрикации статей более эффективно, чем использование косинусной меры релевантности и меры релевантности BM 25. Метод AnnAST применен к коллекции аннотацийнаучных статей журналов ACM по информатике.2.
Метод пополнения таксономии предметной области ReTAST-w. Методсостоит из двух основных этапов. На первом этапе эксперт задает основу таксономии, на втором этапе таксономия автоматически пополняется за счет ресурсов Википедии. Дерево категорий используется длядостраивания промежуточных уровней, названия статей – в качествелистьев в новой таксономии, тексты статей – в качестве источникауточнений листьев. При этом, мера релевантности СУВСС используется на двух шагах метода: для очистки данных Википедии от шума идля определения связей между названиями категорий и темами таксономии.
Метод применен для пополнения таксономий а) теории вероятностей и математической статистики, б) численных методов, при этомосновы таксономии были заданы по паспортам ВАК соответствующихспециальностей.3. Метод фильтрации обсценной лексики fAST. Метод используется дляочистки от обсценной лексики собственной коллекции текстов. Устанавливается аналогия между очисткой от обсценной лексики и поискомпо однословному ключу с поправкой на оптимизируемый критерий.Демонстрируется эффективность метода fAST по сравнению со стандартными методами поиска по однословным ключам и редакционномурасстоянию по полноте и временной эффективности.В работе приведено описание двух программных комплексов.
Программный комплекс WikiDP используется для скачивания статей и дерева категорийрусскоязычной Википедии и работает в интерактивном режиме. Программныйкомплекс EAST полностью реализует pipeline для построения таблиц релевантности «строка – текст», начиная предобработки текстов и разбиения их на строки фиксированной длины и заканчивая вычислением СУВСС и построениемискомых таблиц релевантности «строка – текст для входных списков строк иколлекции текстов».109Нельзя не сказать об ограничениях вычислительного плана, связанныхс необходимостью создания и поддержки аннотированного суффиксного дерева для сколь-нибудь значительной коллекции тестов. В этом плане нельзя неупомянуть еще одну нашу инновацию – переход от рассмотрения текста как единой строки к рассмотрению его как совокупности коротких строк.
В какой-тостепени это снижает чувствительность метода, так как разрывает связи между словами, далеко находящимися друг от друга в тексте. Вместе с тем, этосущественно понижает глубину получаемого дерева и, следовательно, вычислительную трудоемкость метода. Вероятно, дальнейшие успехи по ускорениюработы метода могут получиться на путях его параллелизации и перехода кдистрибутивным вычислениям.110Список литературы1.
Salton G., Buckley D. Term Weighting Approaches in Automatic TextRetrieval // Information Processing & Management. — 1988. — Т. 24, №5. — С. 513—523.2. Robertson S., Zaragoza H. The Probabilistic Relevance Framework: BM25and Beyond. — Now Publishers Inc., 2009.3. Ponte J. M., Croft W. B. A Language modeling Approach to InformationRetrieval // Proc. Conference on Research and Development in InformationRetrieval. — ACM. 1998. — С. 275—281.4. Zamir O., Etzioni O. Web Document Clustering: a FeasibilityDemonstration // Proc.
International Conference on Research andDevelopment in Information Retrieval. — ACM. 1998. — С. 46—54.5. Pampapathi R., Mirkin B., Levene M. A Suffix tree Approach to Anti-spamE-mail Filtering // Machine Learning. — 2006. — Т. 65, № 1. — С. 309—338.6. Manning C. D., Schütze H. Foundations of Statistical Natural LanguageProcessing. Т. 999. — MIT Press, 1999.7. Martin D., Jurafsky D. Speech and Language Processing. An introductionto natural language processing, computational linguistics, and speechrecognition. — 2000.8. Harris Z. S.
Distributional Structure // Word. — 1954. — Т. 10, № 2—3. —С. 146—162.9. Berry M. W., Browne M. Understanding Search Engines: MathematicalModeling and Text Retrieval. Т. 17. — Siam, 2005.10. TF-ICF: A New term Weighting Scheme for Clustering Dynamic DataStreams / J. W. Reed [и др.] // Proc. International Conference on MachineLearning and Applications. — IEEE.
2006. — С. 258—263.11. Raghavan V. V., Wong S. K. M. A Critical Analysis of Vector Space Modelfor Information Retrieval // Journal of the American Society for informationScience. — 1986. — Т. 37, № 5. — С. 279.11112. Turney P. D., Pantel P. From Frequency to Meaning: Vector Space Modelsof Semantics // Journal of Artificial Intelligence Research. — 2010. — Т.
37,№ 1. — С. 141—188.13. Rehurek R., Sojka P. Software Framework for Topic Modelling with LargeCorpora // Proc. Workshop on New Challenges for NLP Frameworks. —Citeseer. 2010.14. Bird S., Klein E., Loper E. Natural Language Processing with Python. —O’Reilly Media, Inc., 2009.15.