Содержание к диссертации
Введение
Глава 1. Анализ основных задач и принципов работы СППР риэлторского предприятия 12
1.1 Предпосылки возникновения и актуальность задачи автоматизации риэлторской деятельности 12
1.2 Анализ потребностей в автоматизированной обработке информации для риэлторской фирмы 15
1.2.1 Основные понятия и свойства рынка объектов недвижимости 15
1.2.2 Методы оценивания объектов недвижимости 20
1.3 Обзор информационных систем предприятий 26
1.3.1 Основные типы систем 26
1.3.2 Основные принципы работы СППР риэлторского предприятия 31
1.4 Методы анализа текстовой информации 38
1.4.1 Обработка русскоязычных неформализованных текстов 41
1.4.2Выделение слови предложений 45
1.4.3 Анализ отдельных слов русского языка 46
1.4.4 Синтаксический анализ 47
1.4.5 Практические задачи обработки текстов 52
1.5 Цели и задачи исследования 55
Глава 2. Разработка математических моделей функционирования сппр риэлторского предприятия 58
2.1 Модель представления результатов анализа отдельных элементов текста 58
2.2 Математическая модель синтаксической структуры предложения 63
2.3 Представления данных в виде семантической сети 68
2.4 Синтез фрагментов семантической сети 74
2.5 Математическая модель извлечения данных 80
2.6 Математическая модель запросов с нечёткими условиями 87
2.7 Оценивание объектов недвижимости на основе метода сравнения продаж 96
2.8 Основные выводы главы 101
Глава 3. Алгоритмы функционирования сппр риэлторского предприятрїя 105
3.1 Алгоритмическая модель извлечения информации 105
3.1.1. Алгоритм построения лексического графа и анализа отдельных слов
3.1.2. Алгоритм поиска отдельных предложений 107
3.1.3. Алгоритм извлечения информации 108
3.1.4. Построение семантической сети данных 109
3.2 Алгоритмы анализа информации 111
\« 3.2.1. Простейший алгоритм выполнения запросов и его критика 111
3.2.2. Алгоритм выполнения запросов при использовании реляционной СУБД 113
3.2.3. Вычисление значения метрики при сравнении запросов 118
3.3 Выводы главы 121
Глава 4 . Практическая реализация сппр риэлторского предприятия 123
4.1. Обобщённая архитектура полученной СППР 123
4.2. Практическая реализация и наполнение словарей 130
4.2.1. Описание предметной области СППР в терминах семантической сети 130
4.2.2. Пример содержимого базы данных 131
4.2.3. Примеры словарей нечётких значений 132
4.2.4. Пример выполнения запроса 134
4.2.5. Пример оценивания объекта недвижимости 137
4.2.6. Пример сравнения трёх запросов 139
4.3. Экономический эффект и возможности развития 143
4.4. Основные выводы главы 146
Основные выводы и результаты работы 149
Список литературы 150
Приложение №1 158
Приложение №2 164
Приложение №3 168
Приложение №4 169
Приложение №5 170
- Основные понятия и свойства рынка объектов недвижимости
- Обработка русскоязычных неформализованных текстов
- Математическая модель синтаксической структуры предложения
- Алгоритм построения лексического графа и анализа отдельных слов
Введение к работе
Актуальность темы. Бурное развитие рынка недвижимости повлекло за собой резкое увеличение количества компаний, предоставляющих риэлторские услуги, что привело к обострению конкурентной борьбы и повышению требований по уровню, скорости, удобству и качеству обслуживания клиентов. Взаимодействие с каждым конкретным клиентом состоит из двух этапов: во-первых, поиск актуального предложения рынка недвижимости, его рассмотрение и совместное обсуждение, и, во-вторых, оформление всех юридических документов в случае осуществления сделки. Эффективность работы всего предприятия зависит от качества выполнения первого этапа, успешное проведение которого требует многократной обработки всего массива актуальных предложений рынка, а при оценивании объектов недвижимости - ещё и анализа текущего состояния рынка, сложившейся сегментированности рынка и установившихся цен в каждом сегменте.
Существенное увеличение скорости и качества выполнения всех перечисленных действий требует разработки и внедрения системы поддержки принятия решений (СППР), предоставляющей возможности анализа информации о текущем состоянии рынка недвижимости. Важным требованием к СППР является необходимость анализировать данные, представленные в виде неформализованных текстов, поступающих из различных специализированных средств массовой информации.
Таким образом, актуальность диссертационной работы определяется необходимостью разработки іматематических и алгоритмических моделей функционирования СППР риэлторского предприятия, а также разработку программной архитектуры, пригодной для практической реализации системы.
Цель и задачи исследования. Целью диссертационной работы является разработка обобщённых математических моделей и принципов
функционирования СППР сотрудников риэлторского предприятия, являющейся одним из звеньев в процессе принятия маркетинговых решений фирмы.
Для достижения указанной цели в работе решались следующие основные задачи:
анализ методов обработки неформализованных текстов, оценивания объектов недвижимости и сегментирования рынка недвижимости;
разработка модели автоматизированного извлечения структурированной информации об актуальных предложениях рынка недвижимости из неформализованных текстовых документов;
разработка модели поиска предложений на рынке недвижимости, удовлетворяющих заданным нечётким условиям;
разработка математической модели оценивания . объектов недвижимости на основе метода продаж и содержимого базы данных СППР;
разработка математической модели задания и автоматизированного сегментирования рынка недвижимости.
Методы исследования. Выполненные исследования базируются на использовании методов математического моделирования, теории принятия решений, теории графов, методов оптимизации, вычислительной лингвистики, теории синтаксического анализа, нечёткой логики, теории реляционных баз данных, численных методов и программирования. Общей методологической основой является системный подход.
Научная новизна заключается в следующих результатах:
- разработана модель автоматизированного анализа текстовых
документов, позволяющая извлекать структурированную
информацию об актуальных предложениях рынка недвижимости из
неформализованных текстов, применимая в других предметных
областях;
разработана модель задания и выполнения запросов, позволяющих указывать нечёткие условия поиска информации;
задача поиска предложений рынка недвижимости сформулирована как задача оптимизации;
разработана модель оценивания объектов недвижимости на основе метода сравнения продаж и содержимого базы данных СППР, позволяющая учитывать сегментацию рынка;
разработана математическая модель задания и автоматизированной сегментации рынка недвижимости, основанная на кластеризации журнала запросов и позволяющая формулировать описания сегментов в общеупотребительных терминах.
Достоверность научных результатов. Научные положения, теоретические выводы и практические рекомендации обоснованы корректным использованием математического аппарата, подтверждены вычислительными экспериментами на ЭВМ и оценкой работы созданного экспериментального программного обеспечения.
Практическая ценность. Практическая ценность работы непосредственно следует из поставленных задач исследования работы и заключается в следующих результатах:
разработано экспериментальное программное обеспечения анализа текстовых документов и автоматизированного извлечения структурированной информации об актуальных предложениях на рынке недвижимости;
предложен способ реализации модуля выполнения запросов, содержащих нечёткие условия, к реляционной базе данных;
разработана программная архитектура и основные принципы построения СППР риэлторского предприятия.
Реализация результатов работы. Предложенная программная
' архитектура средств извлечения данных из неформализованных текстовых
русскоязычных документов принята за основу при разработке средств
наполнения информационного хранилища информационно-аналитической системы (ИАС) НЕВОД 4.0, разрабатываемой ЗАО НЛП "РЕЛЭКС". Произведено наполнение экспериментальной базы данных, позволяющей провести оценку полученных математических моделей.
Созданное экспериментальное программное обеспечение апробировано в ООО "ЮПИКС. Недвижимость", и в данный момент ведётся обсуждение дополнительных требований (стоимость разработки системы, дизайн, пользовательский интерфейс и т.п.) к Сі 11 IF риэлторского предприятия.
Полученные результаты диссертации используются в учебном процессе факультета прикладной математики, информатики и механики Воронежского госуниверситета при чтении следующих курсов: "Управление рисками", "Принятие решений" и "Методы представления знаний".
На защиту выносятся:
модель автоматизированного извлечения структурированной информации об актуальных предложениях рынка недвижимости из неформализованных тестовых документов, применимая в других предметных областях;
модель задания и выполнения запросов с нечёткими условиями;
формализация задачи поиска наиболее интересных для клиента предложений рынка недвижимости;
модель оценивания объектов недвижимости на основе метода сравнения продаж и содержимого базы данных 011 IP;
модель задания и автоматизированной сегментации рынка недвижимости, основанная на кластеризации журнала запросов.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях и совещаниях:
"Проблемы компьютерной лингвистики", г.Воронеж, май 17-18,2002
10-ая Международная конференция "Математика. Компьютер. Образование", г. Пущино, январь 2003
3-я региональная конференция "Информатика: проблемы, методологии, технологии ", г. Воронеж, февраль 12-13,2003
4-я региональная конференция "Информатика: проблемы, методологии, технологии ", г. Воронеж, февраль 3-4, 2004
Международная конференция "Образование, наука, производство и управление в XXI веке", г. Старый Оскол, октябрь 20-22, 2004
Публикации. Основные результаты диссертации опубликованы в 13
печатных работах, из них 10 работ выполнено самостоятельно. Личный вклад
автора в работах, опубликованных в соавторстве, состоит в следующем: в
< [36] автором предложен подход к визуализации семантических сетей данных;
в [46] автором разработана программная архитектура комплекса, а также подсистемы анализа текстов и подсистемы выполнения запросов; в [4] автор обосновал возможность использования технологий автоматизированного анализа текстов для обработки резюме сотрудников.
Структура и объём работы. Материал диссертации изложен на 170 страницах машинописного текста. Диссертация состоит из введения, четырех глав, выводов, списка литературы и приложений, содержит 21 рисунок, и 13 таблиц. Библиография включает 87 наименований.
Содержание работы
Во введении обосновывается актуальность темы, формулируются цели и задачи исследования, научная новизна и практическая значимость работы.
Во первой главе рассмотрено взаимодействие риэлторской фирмы с
клиентом, обоснована необходимость разработки СППР, предоставляющей
возможности выработки и оценки решений на основе неформализованной
текстовой информации. Указаны экономические подходы и базовые
принципы функционирования рынка недвижимости, которые положены в
основу функционирования СППР. Отдельное внимание уделено анализу
основных методов оценивания объектов недвижимости, при этом, приведены
t. достоинства и недостатки каждого метода.
Дана существующая классификация средств автоматизации деятельности предприятий, и показано соотношение рассматриваемой СППР с существующими видами средств анализа данных. Сформулированы основные требования, предъявляемые к функциональности СППР: загрузка информации из текстовых документов, выполнение запросов с нечёткими условиями, задание сегментации и проведение автосегментирования рынка, примерное оценивание объектов недвижимости и т.д. Рассмотрена классификация текстовых документов с точки зрения их автоматизированной обработки, и дана характеристика текстов, поступающих и специализированных средств массовой информации и содержащих данные о предложениях на рынке недвижимости. Подробно рассмотрены результаты анализа обобщённой схемы обработки текстов на русском языке, послужившей основой для создания уже существующих программных средств анализа неформализованных текстовых документов, а также дан краткий обзор практических задач обработки русскоязычных текстов.
В заключении главы сформулированы цели и задачи исследования.
Во второй главе рассмотрена математическая модель процесса автоматизированного извлечения информации из русскоязычных текстовых документов. В соответствии с обобщённой схемой обработки неформализованных русскоязычных текстов, процесс извлечения информации разделён на этап выделения в исходном тексте слов и предложений, морфологический анализ отдельных слов и синтаксический анализ. Показано, что в зависимости от типа исходных текстовых документов, этапы морфологического и синтаксического анализа могут быть существенно упрощены.
Заключительными этапами обработки текста является синтез отдельных фрагментов семантической сети данных, производимый на основе правил формализации и результатов синтаксического анализа, а также построение единой семантической сети путём объединения отдельных
фрагментов. Информация о каждом предложении на рынке недвижимости представляется в виде части семантической сети данных.
В главе предложена математическая модель выполнения запросов к семантической сети данных. В каждом запросе указывается структура искомых фрагментов семантической сети и условия, налагаемые на информационное наполнение искомых фрагментов. При задании условий могут использоваться логические предикаты и операции сравнения информационного наполнения с указанными нечёткими значениями. Результатом выполнения любого запроса является нечёткое множество фрагментов семантической сети данных, каждый из которых содержит информацию о предложении на рынке недвижимости и характеризуется, во-первых, степенью соответствия условиям запроса, во-вторых, собственными параметрами объекта недвижимости, такими как цена, месторасположение и т.д.
Приведены основные операции по» работе с полученной выборкой объектов недвижимости: поиск оптимального объекта' недвижимости, ранжирование выборки, перестроение условий запроса и т.д.
Показано, что сегментация рынка заключается в формировании набора запросов с помощью эксперта, или на основе журнализации всех выполняемых запросов, на множестве которых может быть задана метрика, проведена кластеризация и, таким образом, выявлены наиболее обособленные запросы. Рассмотрены три способа оценивания объектов недвижимости: формирование точной цены на основе наиболее похожего объекта, формирование средневзвешанной цены на основе цены нескольких объектов и, наконец, построение неточного значения цены.
Во третьей главе рассмотрены подходы к реализации алгоритмов, действующих на основе описанных в предыдущей главе моделей. Приведено детализированное описание алгоритмов построения лексического графа исходного текста, синтеза фрагментов семантической сети данных и
построения результата извлечения информации путём объединения отдельных фрагментов семантической сети данных.
Выполнение формализованных запросов к семантической сети данных заключается в поиске всех фрагментов указанной структуры и вычислении значения характеристической функции для каждого из них. Показано, что предложенный алгоритм обладает существенными недостатками (скорость работы, невозможность получения части выборки и сложность реализации), не позволяющими его использовать при построении* СППР риэлторского предприятия. Рассмотрены основные принципы работы и обобщённый алгоритм выполнения запросов, не имеющий указанных недостатков и позволяющий использовать реляционную СУБД для хранения содержимого * базы данных СППР.
Отдельный пункт главы»посвящен сравнению запросов и вычислению метрики, заданной на множестве всех возможных запросов. Показано, что вычисление значений метрики сводится к задаче численного интегрирования.
Во четвёртой главе дано описание программной архитектуры СППР риэлторского предприятия, а также указаны основные сценарии работы, пользователей с СППР. Детально рассмотрены примеры работы предложенных математических моделей поиска информации, оценивания объектов недвижимости и автоматизированного сегментирования рынка.
В главе указаны возможности продолжения работы в области как анализа текстовых документов, так и развития моделей выработки и принятия решений.
В заключении рассмотрены основные результаты работы.
В приложениях дано развёрнутое описание возможностей интегрирования модуля синтаксического анализа в подсистему извлечения данных, а также рассмотрены возможности расшиения предложенной модели оценивания объектов, учитывающего динамику изменения рынка недвижимости.
Основные понятия и свойства рынка объектов недвижимости
От функционирования СППР и точности рекомендуемых решений напрямую зависит конкурентноспособность предприятия, поэтому при построении рассматриваемого ПО необходимо учитывать всё специфику деятельности предприятия с целью достижения максимально высоких результатов от использования системы. Риэлторские предприятия производят операции на рынке объектов недвижимости [1,52,55], поэтому специфика их деятельности определяется основными свойствами рынка, который, в свою очередь, сильно зависит от предлагаемых на нём товаров и услуг, а также действующих на нём субъектов. В общем случае, рынок недвижимости, как и любой другой рынок, может быть проанализирован с точки зрения трёх позиций: 1. Товары и услуги (объекты), предлагаемые на рынке. 2. Субъекты рынка, которые осуществляют различного рода операции купли, продажи, обмена и т.д. объектов на рынке. 3. Потребности субъектов, которые удовлетворяются с помощью товаров и услуг, предлагаемых на рынке.
Основным товаром на рынке недвижимости являются объекты недвижимости, каждый из которых жёстко связан с некоторым участком земли, и характеризуется своим типом и множеством дополнительных параметров. Существуют заранее известные классификации существующих объектов недвижимости. На рис. 1.1 показаны основные типы и параметры объектов недвижимости.
Можно выделить два основных способа классификации объектов недвижимости [1,6,9]: 1. Иерархический - последовательное (по ступеням) разделение множества недвижимых объектов на соподчиненные группы с однородными объектами внутри каждого класса. Глубина классификации (число ступеней) может быть различной для разных исходных классов. Например, производственные здания по признаку этажности делятся на одно-, двух- и многоэтажные. Последние по типу освещения делятся на обеспеченные лифтами и необеспе-ченные и т.д. 2. Фасетный метод классификации предполагает выделение независимых параметров, характеризующих объекты недвижимости, и указание всех возможных значений каждого параметра. Классифицируемое множество объектов недвижимости разделяется не непересекающиеся подмножества объектов, причём объекты, входящие в одно подмножество имеют одинаковые значения всех параметров, по которым осуществляется классификация. На рынке недвижимости действует большое количество субъектов, которые могут быть разделены на несколько больших групп в зависимости от предлагаемых ими услуг и товаров: 1. Строительные предприятия, осуществляющие продажу нового жилья. В большинстве случаев, строительные организации производят продажу сразу нескольких однотипных объектов недвижимости (например, множество квартир в новом, только построенном доме), но каждый из этих объектов может быть продан независимо от других. 2. Физические и юридические лица, осуществляющие покупку объектов недвижимости, при этом, важно заметить, что одна операция может производиться сразу с несколькими объектами недвижимости. Такими предложениями являются обмен, съезд, разъезд и т.д. 3. Физические и юридические лица, осуществляющие или участвующие в перепродаже объектов недвижимости.
Каждое предложение на рынке недвижимости характеризуется описанием и параметрами по крайней мере одного объекта, с которым производится операция, а также тип этой операции: купля, продажа, обмен (с и без доплаты ), съезд, разъезд, сдача в аренду и т.д. В предложении могут фигурировать сразу несколько объектов недвижимости, если в характеристики одного объекта входит информация о дополнительных вспомогательных объектах (например, информация о гараже, погребе при продаже частного дома и т.д.), или рассматривается предложение обмена, съезда или разъезда. Таким образом, для хранения информации об актуальных предложениях на рынке недвижимости необходимо использовать некоторый способ представления знаний [19,31,51] (хотя сами описания предложений знаниями не являются, поскольку не обладают свойством активности [19,31])- Наиболее удобным средством представления информации о рынке недвижимости являются семантические сети [19,51], поскольку они позволяют хранить и обрабатывать данные из произвольной предметной области с достаточно сложной и разветвлённой системой понятий и отношений.
Наконец, важно заметить следующие свойства объектов недвижимости, проявляющиеся в отношении владельцев к своему имуществу и оказывающие влияние на выполнение операций на рынке: 1. Объекты недвижимости не перемещаемы в пространстве, и поэтому, их месторасположение имеет важное значение для владельца. 2. Объекты недвижимости долговечны и операции по их купле-продаже осуществляются редко. 3. Объекты недвижимости являются дорогим товаром. 4. Существуют высокие психологические издержки при купле-продаже объектов недвижимости, связанные с переездом и утратой установившееся связей с окружающей инфраструктурой.
Обработка русскоязычных неформализованных текстов
За время развития этого раздела науки был выработан единый обобщённый подход к обработке произвольных текстов, включающий в себя несколько этапов и инвариантный по отношению к выбору естественного языка [24,43]. Устоявшаяся схема непосредственно следует из системного анализа [30] общеизвестных принципов построения текста.
Независимо от того, на каком языке написан исходный текст, его обработка всегда будет проходить несколько стадий: разделение текста на отдельные предложения, разделение предложений на отдельные слова, анализ отдельных слов, анализ отдельных предложений, анализ всего текста. Математическая модель и реализация отдельных стадий обработки неформализованного текста специфична для каждого естественного языка, но всегда можно выделить некоторые универсальные подходы и методы, которые могут быть применены для любого языка. Так, первые две стадии, выполняющие разбиение текста на отдельные предложения и затем разбиение этих предложений на отдельные слова, практически одинаковы, для большинства естественных языков. Единственное, где могут проявляться черты, специфичные для выбранного языка - это, во-первых, обработка сокращений слов и знаков шрепинания (точнее, определение того, какие из знаков «препинания являются концом предложения, какие являются частью слов-сокращений, а какие служат для выделения частей предложения). Во-вторых, важным и специфическим элементом анализа при обработке текстов является определение концов предложений.
Анализ отдельных слов, целью которого является определение различных характеристик каждого слова, наоборот, сильно зависит от выбора конкретного естественного языка, имеющего свою собственную систему характеристик отдельных слов и способы определения значений этих характеристик. Для проведения синтаксического анализа отдельных предложений выработано несколько наиболее общих подходов, каждый из которых имеет свои достоинства и недостатки. Целью анализа является определение связей между различными словами предложения. Специфика естественного языка проявляется как в способе определения связей, так и в способе представления получаемого синтаксического графа предложения. Наконец, последняя стадия (семантический анализ), как и стадия лексического анализа (разбиения текста на слова и предложения), мало зависит от выбранного языка, но, это проявляется только в общих подходах к проведению анализа. Поскольку семантический анализ полностью основывается на результатах работы предыдущих фаз обработки текста, а они, как уже говорилось, специфичны для конкретного языка, то способы представления результатов синтаксического анализа могут сильно варьироваться в зависимости от выбора естественного языка, оказывая большое влияние не реализацию методов семантического анализа.
Группы элементов Разбиение наотдельные предложения Синтаксическаяструктурапредложения п і Т Отдельные Разбиение на отдельные ь Характеристики отдельных слов элементы ел ова w Рис. 1.4. Обобщённая схема обработки неформализованных текстов Существует несколько правил взаимодействия различных этапов обработки текстов между собой, которые, как и перечень всех возможных этапов обработки текстов, одинаковы для всех естественных языков: 1. Обработка текста последовательно проходит все указанные этапы. До тех пор, пока полностью не закончен один этап обработки некоторой части текста, не может быть начат следующий этап обработки этой части текста. 2. Результаты работы любого этапа могут быть многозначными, то есть для выходных параметров указывается не одно, а сразу несколько возможных значений (например, может существовать несколько способов трактовки одного и того же слова). 3. Любой этап обработки текста основывается на данных, полученных в результате работы одного или нескольких предыдущих этапов. Так, семантический анализ текста может основываться не только на синтаксических структурах предложений, но и учитывать характеристики отдельных слов предложений. 4. Любой этап обработки текста может использовать некоторую дополнительную информацию (различные словари, заранее заданные системы правил и т.д.), которая задаётся изначально и никак не зависит от обрабатываемого текста. . 5. Если результаты какого-либо этапа анализа неоднозначны, например, существует несколько возможных трактовок значения одного слова, то при последующей обработке текста должны рассматриваться все имеющиеся варианты. Однако, часть этих вариантов может быть отбракована и скрыта от последующих стадий. Анализа текста, написанного на русском языке, проходит через все указанные выше стадии: сначала происходит лексический анализ текста и выделение отдельных слов и предложений. Затем происходит морфологический анализ (определение морфологических характеристик каждого слова, куда входят такие параметры, как часть речи, падеж, склонение, спряжение и так далее) и морфемный анализ (разбиение слова на приставку, корень, суффикс и окончание). Далее производится синтаксический анализ текста, и, наконец, решаются различные задачи семантического анализа текста (поиск фрагментов текста, формализация, реферирование и т.д.). 1.4.2 Выделение слов и предложений
В русском языке правила разделения текста на отдельные предложения и слова практически не отличаются от большинства остальных языков: все предложения разделяются точкой, многоточием, вопросительным или восклицательным знаком, а слова разделяются либо пробелами, либо знаками препинания. Однако, существует несколько типов ситуаций, которые приводят к возможным неоднозначностям при разбиении текста на отдельные слова и предложения: 1. Точка может являться как признаком окончания предложения, так и сигнализировать о сокращении слова; 2. Знак "-" может использоваться в качестве тире, дефиса, сокращения слова или переноса слова на следующую строку; Поиск и выделение отдельных лексем текста происходит с.помощью,., . конечных автоматов [2,19]. Разрешение неоднозначностей происходит с помощью специального словаря, в котором содержатся сокращённые формьь слов (т.е. то, что может встречаться в исходном тексте), и соответствующие им полные варианты слов. При этом, для одного и того же сокращения может быть указано сразу несколько различных вариантов полного слова. Например, фрагмент текста "пер. Домостроителей" может означать как "переулок Домостроителей ", так и "пересечение Домостроителей". Определение истинного значения встретившегося сокращения происходит на последующих этапах анализа.
При обработке неформализованного текста считается, что точка, вопросительный и восклицательный знак являются признаком окончания предложения. Помимо этого, могут быть введены ограничения, позволяющие определять начало нового предложения по каким-либо дополнительным признакам (особое форматирование, признак начала новой строки и т.п.), как это сделано для газетных объявлений.
Математическая модель синтаксической структуры предложения
Основная задача предварительных этапов обработки текста заключается в подготовке входных данных для этапа семантического анализа, при выполнении которого происходит синтез фрагментов семантической сети данных. В главе 1 было показано, что в настоящий момент большинство объявлений является текстами с "бедным синтаксисом", обработка которых не требует проведения морфологического и синтаксического анализа. При извлечении данных из таких объявлений достаточно анализировать только стоящие рядом слова. С другой стороны, СППР риэлторского предприятия должна предоставлять возможность встраивания модуля синтаксического анализа для обеспечения обработки произвольных неформализованных текстов. Таким образом, модель процесса извлечения данных из неформализованных текстовых документов должна включать в себя модель синтаксической структуры отдельных предложений текста, служащей для представления информации, подаваемой на вход модулю семантического анализа. При обработке текстов с "бедным" синтаксисом структура предложений текста будет получаться путём соединения стоящих рядом слов, а при обработке произвольных текстов на русском языке синтаксическая структура будет строиться модулем синтаксического анализа.
Если дуга соединяет узлы Sj и S,, то будем обозначать её Ц (при этом i j). Каждая вершина графа является кортежем вида (2.1) и соответствует либо элементу исходного предложения, либо группе элементов исходного предложения, причём в первом случае, узел синтаксической структуры предложения будем называть исходным узлом, а во втором случае дополнительным узлом. Любой дополнительный узел всегда должен быть связан хотя бы с двумя другими узлами. Нетрудно показать, что из этого ограничения следует наличие прямой или косвенной связи между любым дополнительным узлом и некоторым исходным узлом, т.е. дополнительные узлы не могут существовать "сами по себе", а всегда опираются на некоторые исходные узлы.
Кроме того, узлы синтаксической структуры делятся на значащие и не значащие. Значащие узлы имеют связи с другими узлами, а не значащие - не имеют. К незначащим узлам относятся знаки препинания и вспомогательные слова предложения (предлоги, союзы и т.д.).
Помимо дуг-синтаксических связей, в синтаксической структуре предложения неявно присутствуют дуги, показывающие порядок элементов в исходном предложении. На представленном ниже рис. 2.4 показан пример синтаксической структуры предложения.
Заметим, что такая модель синтаксической структуры позволяет работать как с корректными синтаксическими структурами, так и с не корректными, для которых не выполняются некоторые правила естественного языка (например, условие проективности, или ограничение
"частица не не может относится к двум узлам синтаксической структуры сразу" и т.п.).
По аналогии с кортежами вида (2.1) синтаксические структуры предложения, заданные в виде (2.6) могут использоваться не только для представления информации о синтаксической структуре предложения, но и для представления информации об условии, налагаемом на синтаксическую структуру предложения. При этом, в структуре-условии указываются: 1. количество узлов предложения; 2. условие на тип каждого узла (любой узел или только дополнительный); 3. условия на каждый узел; 4. условия на наличие связей между указанными узлами предложения; 5. условия на вопросы от одних слов предложения к другим. 6. ограничение на порядок элементов в исходном предложении. Задачу проверки, удовлетворяет ли синтаксическая структура предложения заданному условию, можно представить более формально в виде вычисления значения функции IFs(S,C), которая в качестве аргумента S принимает проверяемую синтаксическую структуру, в качестве аргумента С принимает структуру-условие. IFS(S,C) возвращает вещественное число, равное нулю, если S удовлетворяет условию С, и большее нуля, если S не удовлетворяет условию С. Будем считать, что синтаксическая структура S состоит из узлов {S,} и связей {Ьц=( Рц , Qy) }, а синтаксическая структура С состоит из узлов {QJ и связей { LCk/ =( PQ/, QCy)}.
Значение функции IFs определяется следующим образом: 1. Если не существует взаимооднозначного соответствия G: {S,}o{Ck}, такого, что каждому Ск ставится в соответствие некоторое SI5 то IFs(S,C)=ao. Далее, для простаты дальнейших рассуждений будем считать, что каждому Sj G ставит в соответствие Q. 2. V дуги LCy, должна существовать дуга Ц, при этом должно выполняться РСЧ cz Рц , QCy с Qy. Если это условие не выполняется, то IFs(S,C)=oo. 3. Если Q является дополнительным узлом, то S, тоже должен быть дополнительным узлом, иначе IFs(S,C)=co 4. Если все перечисленные выше условия выполняются, то IFSCS.OIIFTCS Q). (2.8) Задачу проверки, удовлетворяет ли синтаксическая структура предложения заданному условию с учётом порядка узлов, формально можно представить аналогично функции IFS(S,C). Единственное отличие будет только в том, что на взаимооднозначное соответствие узлов налагается условие сохранения порядка узлов, т.е., если узлу S! соответствует С,, а узлу Sk соответствует Q, то из i k следует j /. Будем считать, что функция IFso(S,C) служит для проверки условия С с учётом порядка слов предложения.
Алгоритм построения лексического графа и анализа отдельных слов
Задача лексического анализа текстового документа заключается в разбиении потока символьной информации на отдельные слова. Основная сложность лексического анализа заключается в многовариантности результатов разбиения исходного текста на отдельные слова и предложения.
При построении лексического графа происходит последовательный просмотр потока символов обрабатываемого текста и определение типа участка текста, который может быть словом, словом с дефисом, словом со знаком переноса, словом со знаком переноса и дефисом, знаком препинания, при этом признаки конца строки и конца абзаца тоже рассматриваются как знаки препинания. Определять тип участка текста можно с помощью недетерминированных конечных автоматов (НКА)[2], которые предназначены для задания условий, налагаемых на последовательность символов, и, таким образом, определяющих возможное содержимое последовательности символов. Результатом работы конечного автомата является логический признак: удовлетворяет ли поданная на вход последовательность символов заданному условию или нет. Таким образом, для каждого возможного типа участка исходного текста может быть построен соответствующий РЖА.
Алгоритм лексического анализа неформализованного текста и построения- графа лексем работает на основе очереди узлов. На каждой итерации алгоритма происходит извлечение узла из очереди, построение следующих за ним узлов (которых ещё нет в графе), и проведение необходимых дуг. В главе 1 было показано, что в данный момент не существует готового к применению алгоритма синтаксического анализа, но, тем не менее, СППР риэлторского предприятия І предусматривает встраивание модуля синтаксического анализа, и требует представления информации о каждом предложении в виде синтаксической структуры. Построение ситнаксической структуры отдельного предложения текста с "бедным синтаксисом" заключается в попарном соединении стоящих рядом значимых элементов предложения.
Рассмотрим предложение S, поступающее на вход алгоритму извлечения данных в виде графа S=({S,},{L,j}). Результатом извлечения данных является множество кортежей вида Extract=(R,Sem,Colors) (формула 2.16) , а также множество Rels, вида 2.17, задающее отношения между найденными фрагментами семантической сети данных. Обобщённый алгоритм извлечения информации выглядит указанным ниже образом. Алгоритм извлечения информации из отдельного предложения: 1. Перебор всех правил R=(SyntR, SemR, MeansR, ColorsR) (см. формулу 2.15). На основе каждого правила R и алгоритма поиска подграфа в графе[28,56], происходит поиск всех вхождений SyntR в граф S. Будем считать, что результатом поиска является множество взаимооднозначных соответствий между узлами SyntR и подмножествами узлов S. 2. На основе каждого найденного на шаге 1 взаимооднозначного соответствия происходит построение кортежа Extract: - строение Sem, полностью повторяет SemR; - для каждого узла SemR происходит определение соответствующей ему текстовой информации с помощью функции MeansR, которой в качестве аргументов передаются узлы Sem (сопоставленные с SemR) и фрагмент предложения Synt (сопоставленный с SyntR); - определение множества Colors с помощью функции ColorsR. 3. Определение отношений между сформированными на. шаге 2 кортежами Extract. С помощью предложенного алгоритма могут быть сформированы множества {Extract }s и Relss для каждого отдельного предложения, после чего объединены в одну единую пару множеств {Extract} и {Rel}, при этом между кортежами Extract, принадлежащими разным предложениям, будут установлены отношения следования или конфликта. Щ
На заключительном этапе извлечения информации из неформализованных текстовых документов происходит построение семантической сети данных путём объединения отдельных фрагментов, при этом СППР может запрашивать у пользователя дополнительную информацию о тексте: 1. Какой из группы пересекающихся и взаимоконфликтующих фрагментов является "правильным", или среди указанных фрагментов нет "правильного", при этом для каждого фрагмента I указывается степень его достоверности, рассчитываемая по формуле (2.13); 2. Каким образом следует объединить два фрагмента семантической сети данных. 3. Следует ли ввести дополнительную информацию об объектах недвижимости на основе ограничений (2.13). Примером таких запросов являются случаи, когда система по названию остановки общественного транспорта автоматически определяет название района города и т.п.
С другой стороны, во всех СППР предъявляются очень жёсткие требования к скорости выполнения запросов, поэтому применение указанного алгоритма при построении подсистемы выполнения запросов невозможно.
Невозможность получения части выборки. Алгоритм производит вычисление характеристической и целевой функций для всех объектов недвижимости, находящихся в базе данных СІП IF. На практике, пользователя СППР, интересуют только часть объектов. Очевидно, что поиск и обработка всех объектов существенно замедляет работу СППР. 3. Сложность реализации. Реализация алгоритма в "чистом виде" предполагает разработку средств хранения и обработки семантической сети, по сути дела, являющихся специализированной системой управления базами данных.
