Извлечение информации из кратких текстовых спецификаций с заданным списком атрибутов тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Ашихмин, Андрей Михайлович

• Ашихмин, Андрей Михайлович
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Ашихмин, Андрей Михайлович

Введение.

Глава 1. Математическая модель проблемы.

Основные определения.

Предлагаемая схема извлечения значений атрибутов.

Релевантность фразы синсету и атрибуту.

Глава 2. Алгоритмы нахождения соответствия фраз атрибутам.

Число разбиений последовательности слов на фразы.

Поиск известных системе фраз.

Оптимальное паросочетание в двудольном графе. Венгерский алгоритм.

Генерация разбиений на фразы из ограниченного числа слов.

Соответствие атрибутам для неизвестных фраз.

Сведение к поиску паросочетания в произвольном графе.

Глава 3. Строковые метрики.

Основные определения. Расстояние Левенштейна.

Аффинные метрики.

Метрика, использующая специфику рассматриваемой предметной области.

Обучение параметров метрики.

Глава 4. Программная реализация и экспериментальные результаты.

Краткое описание программной реализации. Методика тестирования.

Виды ошибок. Результаты тестирования.

Глава 5. Унификация спецификаций при отсутствии списка атрибутов.

Постановка задачи.

Нахождение соответствующей типовой спецификации.

Обучение.

Введение диссертации (часть автореферата) на тему «Извлечение информации из кратких текстовых спецификаций с заданным списком атрибутов»

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

Рассмотрим существующий в настоящее время процесс поиска и возникающие при этом проблемы. В российском сегменте интернета {рунете) существует достаточно много систем, специализирующихся на поиске среди товарных предложений (например, [80], [87]). Этим системам присущи два недостатка: они либо не обладают семантической информацией о товарных !< предложениях (за исключением информации о категориях), либо требуют от фирм-партнёров предоставления семантической информации в некотором { специальном формате, например Yandex Market Language [83].

Пользователь может осуществлять поиск по ключевым словам, но * отсутствие возможности поиска по семантическим значениям атрибутов существенно повышает долю нерелевантных результатов. Приведём в качестве примера несколько предложений из списка длиной около двух тысяч позиций, выдаваемого популярной в рунете системой поиска товаров по ключевым словам для запроса "Pentium 4 2.8":

1. INTEL Pentium4 2.8GHz 512kb 533MHz mPGA-478 BOX

2. INTEL PENTIUM 4-2800 Prescott Socket-775 (1MB, 800MHz, BOX)

3. 306504-B21 Hewlett-Packard X2.8/400-512 ML530G2 ALL 306504-B21

4. Intel P4 2800E/1024Kb/533Mhz/S478 Prescott OEM [RK80546PE0721M]

5. Intel Socket 478 0512k FSB 533 Pentium IV 2.8 GHz

6. Intel P4-2.8GHZ Процессор Pentium IV 2.8 ГГц/ 512KB, Northwood, 533MHz, Socket 478, OEM /

Как видно, система определяет, что «4» и «IV», «2.8» и «2800», «Р4» и «Pentium 4» являются синонимами (скорее всего, это априорная информация, занесённая в систему экспертом). Но из-за отсутствия семантической информации о товарных предложениях совпадающие и различающиеся предложения идут вперемешку. Так, пятое и шестое предложения семантически, эквивалентны, остальные - нет. Пользователь вынужден выполнять дополнительную обработку результатов поиска.

Вариации в написаниях товарных предложений могут быть связаны с принятым стилем, опечатками, использованием сокращений, употреблением терминов без перевода с английского языка, выбором синонимов. В качестве иллюстрации приведём описание в нескольких популярных в рунете электронных магазинах [82], [71], [84] одного и того же процессора для настольных компьютеров:

• CPU Intel Core 2 Duo E4300, 1,8GHz, 2Mb, 800MHz Socket-775 OEM

• Socket 775 2Mb L2 FSB 0800 Intel Core2 Duo 1.8 Ghz (E4300)

• Процессор Intel "Core 2 Duo E4300" (1.80ГГц, 2МБ, 800МГц, EM64T)

Socket775

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

Актуальность темы исследования обусловлена тем, что большинство аналитиков предсказывают стабильный рост электронной коммерции в будущем [36]; значимость электронной коммерции для рунета была отмечена на выступлении Президента Российской Федерации Д.А. Медведева на открытии 12-го Российского интернет-форума РИФ 2008. Увеличение огромного количества документов в интернете, помимо очевидных преимуществ, порождает проблемы поиска нужной (релевантной) информации, так называемые проблемы информационной перегруженности. Ещё большие трудности возникают перед компьютерными агентами (software agents), так как подавляющее большинство документов в интернете предназначено для чтения людьми.

Инициатива семантической паутины (Semantic Web, [53]) была предложена с целью решения части этих проблем. К сожалению, её недостатком является утомительность для человека создания метаданных (семантической информации), приспособленных для компьютерной обработки. Для заполнения («накачки») семантической паутины многие исследователи предлагают использовать методы извлечения информации (information extraction), или методы неглубокой обработки текстов на естественном языке [29], [35]. Большинство работ в области извлечения информации имеют предметом исследования связанные тексты по определённой тематике. Специфика настоящего исследования состоит в том, что предметом исследования являются не просто тексты по определённой тематике, а краткие текстовые описания, в сущности представляющие перечисление значений атрибутов (краткую спецификацию) объекта с использованием множества профессиональных терминов и сокращений. Очень часто такие спецификации мало напоминают связанный текст на естественном языке (например, спецификация «[BOX] Socket 775 06Mb L2 FSB 1333 Intel® Core™2 Quad 2.50 Ghz (Q9300)»).

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

Подчеркнём специфику рассматриваемых описаний объектов. Разрабатываемая система рассчитана на строковые спецификации, фактически представляющие перечисления значений атрибутов. Типичным примером такового описания является «AMD Athlon ХР 2400+, 256Kb, FSB266, Socket А (OEM)». Система не предназначена для работы с описаниями типа «Переходник для установки процессора Socket 478 в материнскую плату Socket 423», где много связанного текста на естественном языке и требуется более глубокий уровень его обработки, включая грамматический разбор.

В процессе научных исследований в работе использовались методы дискретной математики, теории алгоритмов, комбинаторной оптимизации, теории сопоставления записей (record linkage), а так же методы нечёткого текстового поиска.

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

Тематика семантического поиска товарных предложений в интернете затрагивалась в проекте автоматизированного извлечения семантической информации для нужд электронной коммерции CROSSMARC [46]. Отличительная черта настоящего исследования состоит в том, что в проекте CROSSMARC информация извлекается из полнотекстовых HTML-документов, в то время как в настоящей работе внимание концентрируется на как можно более полном извлечении атрибутов из относительно небольших частично структурированных описаний.

Предлагаемая в работе математическая модель для задачи извлечения значений атрибутов из кратких текстовых спецификаций отличается от широко используемой в области информационного поиска модели представления текстов как мультимножеств из ключевых слов (модель векторного пространства [51]). Ключевое отличие состоит в аннотировании фраз (состоящих из одного или нескольких соседних слов) значениями атрибутов.

Разрабатываемая на основе предложенной математической модели интеллектуальная система занимает промежуточное положение между следующими двумя большими классами систем. а) Системами сопоставления записей (обнаружения дубликатов, [16]), в большинстве работ использующих некоторую строковую метрику с настраиваемыми (обучаемыми) параметрами [4], [5]. б) Системами извлечения информации [19], [7], обычно требующими большого объёма составляемых человеком правил и привязанными к конкретной узкой предметной области.

Замечание. Термин «сопоставление записей» (record linkage) используется статистиками, эпидемиологами, историками и другими. Коммерческие базы данных и системы обработки электронной почты ссылаются на него как «обработка с целью слияния/очистки» (merge/purge processing) или «очищение списков» (list washing). Специалисты в области информатики часто используют термины «согласование данных» (data matching) или «задача идентификации объекта» (object identity problem). Другие наименования, описывающие то же понятие, включают «разрешение сущностей» (entity resolution), «устранение неоднозначности сущностей» (entity disambiguation), «обнаружение дубликатов» (duplicate detection), «согласование записей» (record matching), «идентификация экземпляров» (instance identification), «исключение дубликатов» (deduplication) и «закалка базы данных» (database hardening). Эта путаница в терминологии привела к малому числу связей между разными сообществами исследователей (см. [8], [13]). Кроме того, к сожалению, проблема сопоставления записей слабо описана в русскоязычной технической литературе.

Настоящее исследование можно считать связанным с рекурсивным алгоритмом соответствия полей [40]. Однако, в отличие от [40], в данной работе предлагаются более сложные алгоритмы, использующие венгерский алгоритм [30], [31], [42] решения задачи о назначениях, и позволяющие установить взаимно-однозначное соответствие между фразами и атрибутами.

Разработанная математическая модель извлечения значений атрибутов из кратких текстовых спецификаций является новым вкладом в развитие теории сопоставления записей и систем извлечения информации.

На защиту выносятся следующие основные положения:

1. Математическая модель процесса извлечения ' значений атрибутов из кратких текстовых спецификаций.

2. Алгоритм поиска известных системе фраз в текстовой спецификации.

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

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

Результаты исследования могут быть использованы на практике в системах электронной коммерции как компонент интеллектуального,

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

Рис. 1. Интеллектуальный поиск среди товарных предложений

По выполненным диссертационным исследованиям опубликовано 6 работ [65], [64], [66], [63], [62], [67], в том числе три [65], [63], [62] - в ведущих научных журналах, рекомендованных ВАК РФ.

Результаты диссертационного исследования докладывались, обсуждались и получили одобрение специалистов на научных конференциях и семинарах: XLVII научной конференции МФТИ, Москва-Долгопрудный, 2004 г.; III Международном научно-практическом семинаре «Интегрированные модели и sT мягкие вычисления в искусственном интеллекте», Коломна, 2005 г.; Всероссийской научно-технической конференции «Информационные технологии», Воронеж, 2005 г. научных семинарах отдела сложных систем Вычислительного центра им. А.А. Дородницына РАН, 2005-2008 гг.; научных семинарах кафедры интеллектуальных систем Московского физико-технического института, 2005-2008 гг.

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Ашихмин, Андрей Михайлович

Заключение

Подведём основные итоги исследования.

1. Разработана математическая модель процесса извлечения значений атрибутов из кратких текстовых спецификаций.

2. Предложен алгоритм поиска известных фраз в спецификации.

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

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

5. Разработанные модели реализованы в виде комплекса программ. Проведён ряд экспериментов на данных, взятых из реальных источников. Результаты экспериментов подтвердили возможность практического применения предложенных математических моделей.

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

Полезно расширить систему добавлением в неё возможности автоматического построения канонических фраз в синсетах. Допустим, что канонической записью значений атрибута «Тактовая частота» являются фразы вида «1,6 ГГц», «2,66 ГГц», «2,8 ГГц», «3,0 ГГц», а в некоторой спецификации появляется ещё не занесённая в базу частота в 3,2 ГГц, обозначенная как «3.20ГТц». Разработанная в диссертации система способна определить, что «3.20ГГц» представляет новое значение атрибута «Тактовая частота», но неспособна составить для этой фразы канонический вариант «3,2 ГГц». Полезными для решения этой задачи могут оказаться исследования в области автоматического построения грамматик, основанного на индуктивном логическом программировании [49].

Также хотелось бы не ограничивать, как это было сделано в настоящей работе, обрабатываемые спецификации рамками одной категории. Для решения этой задачи необходимо привлечь опыт, накопленный в очень широко исследованной области автоматической классификации и кластеризации текстов [50], [52].

Нелишним было бы привлечение некоторых методов более глубокой обработки текстов на естественном языке, таких как грамматический анализ [86], [47], использование тезаурусов общеупотребительной лексики, например WordNet [15], и других приёмов. Это позволило бы обрабатывать спецификации вида «Переходник для установки процессора Socket 478 в материнскую плату Socket 423», хотя, конечно, следует заметить, что проблема обработки произвольных текстов на естественном языке далека от темы данной работы и является очень глубокой.

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

Список литературы диссертационного исследования кандидат физико-математических наук Ашихмин, Андрей Михайлович, 2008 год

1. Allchin, D. Error Types / Allchin, Douglas // Perspectives on Science. 2001 -Vol. 9, No.l - p. 38-58.

2. Alpaydin, E. Introduction to Machine Learning / Ethem Alpaydin. MIT Press, 2004. - 415 p. - (Adaptive Computation and Machine Learning).

3. Arnold K. The Java™ Programming Language / Ken Arnold, James Gosling, David Holmes. 4th ed. - Addison-Wesley Professional, 2005. - 928 p.

4. Bilenko, M. Learning to combine trained distance metrics for duplicate detection in databases / Mikhail Bilenko and Raymond J. Mooney // Technical Report AI 02-296, Artificial Intelligence Lab, University of Texas at Austin. -2002.

5. Chapman S. String similarity metrics for information integration Electronic resource. / Sam Chapman Electronic publication. - 2006-. - Access http://www.dcs.shef.ac.uk/~sam/stringmetrics.html, free.

6. Chinchor, N. A. Overview of MUC-7/MET-2 / Nancy A. Chinchor // Proceedings of the Seventh Message Understanding Conference(MUC7) -1998.

7. Christen, P. Febrl Freely extensible biomedical record linkage / Christen, Peter, Churches, Tim // ANU Computer Science Technical Reports. - 2002.

8. Cohen, W.W. A Comparison of String Distance Metrics for Name-Matching Tasks / William W. Cohen, Pradeep Ravikumar, Stephen E. Fienberg // Proceedings of the IJCAI-2003. 2003. - p. 73-78.

9. Damerau, F.J. A technique for computer detection and correction of spelling errors / F.J. Damerau // Communications of the ACM. 1964. - v. 7, n. 4 - p. 171-176.

10. Debreu, G. Topological methods in cardinal utility theory / G. Debreu // Mathematical methods in the social sciences. Stanford, California : Stanford University Press, 1960.

11. Description logic handbook / F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, P.F. Patel-Schneider. Cambridge University Press, 2003. - 574 p.

12. Elmagarmid, A. Duplicate Record Detection: A Survey / Elmagarmid, A.K. Ipeirotis, P.G. Verykios, V.S. // IEEE Transactions on Knowledge and Data Engineering 2007 - Vol. 19, Iss. 1-p. 1-16.

13. Extensible Markup Language (XML) Electronic resource. / W3C Electronic publication. - W3C,1996- - Access http://www.w3.org/XML, free.

14. Fellbaum, C. WordNet: An Electronic Lexical Database / Christiane Fellbaum. The MIT Press, 1998. - 445 p.

15. Fellegi, I.P. A Theory for record linkage / Ivan P Fellegi, Alan В Sunter // Journal of the American Statistical Association 1969 - Vol. 64, No. 328 - p. 1183-1210.

16. Fiscus, J. Multiple dimension Levenshtein edit distance calculations for evaluating automatic speech recognition systems during simultaneous speech / Jonathan Fiscus, Jerome Ajot, Nicolas Radde, Christophe Laprun // Proceeding of LREC — 2006.

17. Fred, A. A comparative study of string dissimilarity measures in structural clustering / A. Fred and J. Leitao // Proc. Int'l Conf. Advances in Pattern Recognition. 1998. - p. 385-394.

18. GATE: A framework and graphical development environment for robust NLP tools and applications / H. Cunningham, D. Maynard, K. Bontcheva, V. Tablan

19. Proceedings of the 40th Anniversary Meeting of the Association for Computational Linguistics (ACL'02). Philadelphia, 2002.

20. Gotoh, O. An improved algorithm for matching biological sequences / Gotoh, O. // Journal of Molecular Biology. 1982 - Vol. 162, No. 3 - p. 705-708.

21. Graham, T. Unicode: A Primer / Tony Graham. Wiley, 2000. - 528 p.

22. Hamming. R. W. Error detecting and error correcting codes / Richard W. Hamming // The Bell System Technical Journal. 1950. - Vol. 26, No. 2 — p. 147-160.

23. HeJ3, A. An iterative algorithm for ontology mapping capable of using training data / Andreas HeB // The Semantic Web: Research and Applications. — 2006 -p. 19-33 (Lecture notes in computer science).

24. Hidden Markov models and the Baum-Welch algorithm / Lloyd R. Welch // IEEE Information Theory Society Newsletter. 2003. - 53 (4).

25. Jaro, M. A. Advances in record linking methodology as applied to the 1985 census of Tampa Florida / M. A. Jaro // Journal of the American Statistical Society. 1989.-Vol. 84-p. 1183-1210.

26. Jaro, M. A. Probabilistic linkage of large public health data file / M. A. Jaro // Statistics in Medicine. 1995 - Vol. 14 - p. 491^98.

27. Kalai, A. Probabilistic and on-line methods in machine learning: PhD. Thesis / Adam Kalai, Santosh Vempala; Carnegie Mellon University. Pittsburgh, 2001.

28. KIM: Semantic Annotation Platform / Borislav Popov, Atanas Kiryakov, Angel Kirilov, Dimitar Manov, Damyan Ognyanoff, Miroslav Goranov // The

29. SemanticWeb. ISWC 2003. 2003. - Volume 2870/2003 - p. 834-849. -(Lecture notes in computer science).

30. Kuhn, H. W. The Hungarian method for the assignment problem / Harold W. Kuhn // Naval Research Logistics Quarterly. 1955 - V. 2 - p. 83-97.

31. Kuhn, H. W. Variants of the Hungarian method for assignment problems/ Harold W. Kuhn // Naval Research Logistics Quarterly. 1956 - V. 3 — p. 253-258.

32. Maedche, Er. Bootstrapping an ontology-based information extraction system / Er Maedche, Giinter Neumann, Steffen Staab // Studies in Fuzziness and Soft Computing. Intelligent Exploration of the Web. 2003. - p. 345-359.

33. Maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains, A / L. E. Baum, T. Petrie, G. Soules, and N. Weiss // The Annals of Mathematical Statistics. 1970. - vol. 41, no. 1 - p. 164-171.

34. McDowell, L.K. Ontology-driven information extraction with OntoSyphon / Luke K. McDowell and Michael Cafarella // The SemanticWeb. ISWC 2006. -2006. Volume 4273/2006 - p. 428-444. - (Lecture notes in computer science).

35. Means, G. Meta capitalism: the E-business revolution & the design of 21st century companies and markets / Grady Means, David Schneider — New York : Wiley, 2000. -208 p.

36. Merging the results of approximate match operations / Sudipto Guha, Nick Koudas, Amit Marathe, Divesh Srivastava // Proceedings of the Thirtieth international conference on Very large data bases. 2004. - Vol. 30 — p. 636647.

37. Mohri, M. Weighted finite-state transducers in speech recognition / Mehryar Mohri, Fernando Pereira, Michael Riley // Computer Speech & Language. -2002. Vol. 16, Iss. 1 - p. 69-88.

38. Monge, A.E. Integrating external information sources to guide worldwide web information retrieval / Alvaro E. Monge, Charles P. Elkan // AAAi 1995 Fall Symposium on Knowledge Navigation and Retrieval. 1995 - p. 1-12.

39. Monge, A.E. The field matching problem: Algorithms and applications / Alvaro E. Monge and Charles P. Elkan // Proceedings of the Second International Conference on Knowledge Discovery and Data Mining. 1996 — p. 267-270.

40. Monge, A.E. The WEBFIND tool for finding scientific papers over the worldwide web / Alvaro E. Monge, Charles P. Elkan // Proceedings of the Third International Congress on Computer Science Research. 1996.

41. Munkres, J. Algorithms for the assignment and transportation problems / James Munkres // Journal of the Society of Industrial and Applied Mathematics. -1957-Vol. 5, No l,p. 32-38.

42. Needleman, S.B. A general method applicable to the search for similarities in the amino acid sequence of two proteins / Needleman S.B., Wunsch C.D. // Journal of Molecular Biology. 1970 - Vol. 48, No. 3 - p. 443-453.

43. Pazienza, M.T. Combining ontological knowledge and wrapper induction techniques into an e-retail system / Maria Teresa Pazienza, O. Stellato, Michele Vindigni // Workshop on Adaptive Text Extraction and Mining (ATEM03) held with ECML/PKDD Cavtat, 2003.

44. Pereira, F. Definite clause grammars for language analysis / F. Pereira, D. Warren // Readings in natural language processing. 1986. — p. 101-124.

45. Pulman, S. Grammar learning using inductive logic programming / Stephen Pulman and James Cussens // Oxford University Working Papers in Linguistics, Philology and Phonetics. 2001. - Vol. 6 - p. 31-45.

46. Rennie, J.D.M. Improving Multiclass Text Classification with the Support Vector Machine / Jason D. M. Rennie, Ryan Rifkin // Massachusetts Institute of Technology. Al Memo AIM-2001-026. 2001.

47. Salton, G. A vector space model for automatic indexing / G. Salton, A. Wong, and C. S. Yang // Communications of the ACM 1975 - Vol. 18, No. 11 - p. 613-620.

48. Sebastiani, F. Machine learning in automated text categorization / Fabrizio Sebastiani // ACM Computing Surveys. 2002. - Vol. 34, No. 1 - p. 1-47.

49. Spinning the semantic web: Bringing the World Wide Web to its full potential / Edited by Dieter Fensel, James A. Hendler, Henry Lieberman and Wolfgang Wahlster; foreword by Tim Berners-Lee The MIT Press, 2003. - 503 p.

50. Stoilos, G. A string metric for ontology alignment / Giorgos Stoilos, Giorgos Stamou, Stefanos Kollias // International Semantic Web Conference. — 2005 — p. 624-637.

51. String metric Electronic resource. / Wikipedia. Electronic publication. -Wikimedia Foundation, Inc., 2008. Accesshttp://en.wikipedia.org/wiki/String metric, free.

52. Unit testing Electronic resource. / Wikipedia. Electronic publication. -Wikimedia Foundation, Inc., 2008. Access http://en.wikipedia.org/wiki/Unittesting, free.

53. Winkler, W. E. The state of record linkage and current research problems / William E. Winkler. Washington, DC : Statistical Research Division, U.S. Census Bureau, 1999.

54. Алгоритмы: построение и анализ. / Томас X. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. — 2-ое изд. — М. : Издательский дом «Вильяме», 2007. — 1296 с.

55. Асанов М.О. Дискретная математика: графы, матроиды, алгоритмы / Асанов М.О., Баранский В.А., Расин В.В. Ижевск : НИЦ «Регулярная и хаотическая динамика», 2001. — 288 с.

56. Ашихмин А. М. На пути к семантической паутине: поиск среди товарных предложений / A.M. Ашихмин // Труды Института системного анализа Российской академии наук. Динамика неоднородных систем. — Москва, 2007.-е. 184-189.

57. Ашихмин А. М. Оценка вероятности несовместных и условно независимых логических комбинаций булевых случайных переменных / A.M. Ашихмин, И.В. Севастьянов // Труды Института системного анализа

58. Российской академии наук. Динамика неоднородных систем. Москва, 2006.- с. 110-115.

59. Ашихмин А. М. Применение вероятностной логики для семантического поиска товаров в Интернете / Ашихмин А. М., Севастьянов И. В. // Известия АН. Теория и системы управления. Москва, 2005. - № 5 - с. 130-136.

60. Ашихмин А. М. Семантический поиск среди товарных предложений в Интернете / A.M. Ашихмин, В.Н. Захаров, И.В. Севастьянов // Информационные технологии: Материалы Всерос. научно-техн. конф. — Воронеж, 2005. с. 114-116.

61. ГОСТ 7. 79-2000 (ИСО 9-95). Правила транслитерации кирилловского письма латинским алфавитом: Офиц. изд. / Межгос. совет по стандартизации, метрологии и сертификации. Минск: Межгос. совет по стандартизации, метрологии и сертификации, 2002. — 19 с.

62. Гула А.Ю. Задачи идентификации физических и юридических лиц в хранилищах данных / А.Ю. Гула, А.П. Игнатенко, А.В. Чадюк // Проблеми програмування. — 2008. № 2-3. Спещальний випуск.

63. Компиляторы: принципы, технологии и инструментарий / Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман 2-ое изд. - М. : Издательский дом «Вильяме», 2008. - 1184 с.

64. Кузьмин О.В. Обобщённые пирамиды Паскаля и их приложения. / О.В. Кузьмин. — Новосибирск : Наука, 2000. — 294 с.

65. Левенштейн В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов / Левенштейн В.И. // Докл. АН СССР 1965 - 163, № 4 — с. 845-848.

66. Мальцев А. И. Алгебраические системы. / Мальцев А. И. — М.: Наука, 1970.-392 с.

67. НИКС: Компьютерный супермаркет Электронный ресурс. / НИКС -Компьютерный Супермаркет Электрон, магазин - М. : «НИКС -Компьютерный Супермаркет», 1991-2008. - Режим доступа: http://nix.ru, свободный.

68. Новиков Ф. А. Дискретная математика для программистов. / Новиков Ф. А. СПб.: Питер, 2001. - 304 с.7 8.0 Л ДИ- OLDI Электронный ресурс. / ОЛДИ — Электрон, магазин М. :

69. ОЛДИ, 2000-. Режим доступа: http://oldi.ru, свободный. 79.Пападимитриу X. Комбинаторная оптимизация: Алгоритмы и сложность / Пападимитриу X., Стайглиц К.; пер. с англ. В. Б. Алексеева. — М. : Мир, 1985.-510с.

70. Прайс.РУ Price.RU Электронный ресурс. / ООО "Прайс Экспресс" -Электрон, дан. - М. : ООО "Прайс Экспресс", 1997-2008 - Режим доступа: http://price.ru, свободный.

71. Рассел, С., Норвиг, П. Искусственный интеллект: современный подход / С. Рассел, П. Норвиг. 2-ое изд. - М. : Издательский дом «Вильяме», 2006. - 1408 с.

72. Санрайз-ПРО Электронный ресурс. / Sunrise Электрон, магазин — М. : Sunrise, 2001-2008 - Режим доступа: http://pro.sunrise.ru, свободный.

73. Требования к методу передачи данных. Описание формата данных YML Электронный ресурс. / Яндекс Электрон, дан. - М. : Яндекс, 2008 -Режим доступа: http://partner.market.yandex.ru/legal/tt, свободный.

74. Ф-Центр Электронный ресурс. / Компания «Ф-Центр» — Электрон, магазин — М. : Компания «Ф-Центр», 1998-2008 Режим доступа: http://www.fcenter.ru, свободный.

75. Хачатрян А. Р. Неточный вывод на знаниях / Хачатрян А. Р. // Искусственный интеллект. В 3-х кн. Кн. 2. Модели и методы: Справочник / Под ред. Д. А. Поспелова. - М.: Радио и связь, 1990. С. 105110.

76. Хомский Н. Синтаксические структуры / Хомский Н.; пер. с англ. К. И. Бабицкого и В. А. Успенского // Новое в лингвистике. II. М. : ИИЛ, 1962. -с. 412-527.

77. Яндекс.Маркет Электронный ресурс. / Яндекс Электрон, дан. — М. : Яндекс, 1997-2008 - Режим доступа: http://market.yandex.ru, свободный.