авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 18 | 19 || 21 | 22 |   ...   | 26 |

«Электронные библиотеки: Перспективные Методы и Технологии, Электронные коллекции English Труды RCDL 2010 ...»

-- [ Страница 20 ] --

2 Постановка задачи В случае, когда нет данных о структуре текста или запрос сформулирован недостаточно четко, ис Задача состоит в следующем: изучить возмож- пользуют метод опорных векторов. Это метод ма шинного обучения, который в отличие от метода регулярных выражений требует предварительного Труды 12ой Всероссийской научной конференции обучения на базе некоторого тренировочного набо «Электронные библиотеки: перспективные методы и ра размеченных текстов. И именно это делает метод технологии, электронные коллекции» – RCDL’2010, Казань, Россия, более гибким, настраиваемым на различные прило- Скрытые марковские модели, описанные в [10], жения. В статье [7] описаны алгоритм применения используют текущее состояние системы (в нашей данного метода для выделения определений из тек- задаче возможны всего 2 состояния: «собственное стов, а также способ нахождения текстов, релевант- имя» и «несобственное имя») и рассматриваемый ных запросу. токен для построения матрицы переходов в сле Для нашей задачи интересен случай выделения дующее состояние. Для этого используется набор определений из текста. Как и в предыдущей статье, заданных заранее характеристических функций, в которой приведен метод регулярных выражений, в которые считаются взаимно независимыми. Харак основе метода опорных векторов лежит набор пра- теристические функции – функции, зависящие от вил для анализа текста. Только в этом случае прави- рассматриваемого токена, а также, возможно, от ла менее зависимы от структуры текстов из рас- нескольких соседних токенов. Характеристические сматриваемого набора и более ориентированы на функции задаются экспертом на основе анализа особенности языка, на котором данные тексты на- обучающего текста с учетом его лингвистических и писаны. Это свойство делает метод переносимым стилистических особенностей. Например, «наблю между коллекциями. даемое слово начинается с большой буквы», «перед Кроме того, возможно повышение точности ра- наблюдаемым словом расположено слово из специ боты метода опорных векторов с помощью исполь- ального набора: mr., sir, president, doctor и т. д.». На зования алгоритма leave one out cross-validation основе построенной матрицы переходов прогнози (LOO CV) [8]. Для этого проводятся повторное рас- руют вероятное состояние, в которое попадет сис смотрение тестового множества и проверка уже тема на следующем шаге. При наличии большого найденных определений (релевантных запросу тек- числа входных токенов размерность матрицы пере стов) с учетом уточненных данных о структуре тек- ходов значительно возрастает, что усложняет вы ста. числения. Кроме того, этот метод не всегда точен.

Полу-условные случайные поля рассматривают- Он показывает хорошие результаты при выявлении ся в [9]. В данной статье исследуется задача сегмен- наиболее вероятного состояния на основе известно тирования текста с учетом строго заданного порядка го предыдущего состояния. В случае же, когда нам следования сегментов. Сегментирование – это раз- неизвестна вся последовательность состояний, упо биение текста на сегменты (отдельные части текста, мянутый метод не гарантирует хороших результа характеризующиеся каким-либо определенным тов.

свойством). Самый простой пример сегментирова- Для последнего описанного случая (последова ния текста – выделение в тексте сегментов: Заголо- тельность смены состояний неизвестна заранее) вок, Автор (Авторы), Введение, Основная часть, используется марковская модель максимальной эн Заключение. Если в качестве исходного текста рас- тропии [1]. Для определения наиболее вероятной сматривать каждое предложение в отдельности, а последовательности состояний по входным токенам выделяемыми сегментами выбрать «Собственное используется метод максимальной энтропии ин имя» и «не Собственное имя», то полу-условные формации. Кроме того, учитывается возможная за случайные поля можно использовать для решения висимость между характеристическими функциями.

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

Это вероятностная модель, основанная на цепях Условные случайные поля [11] представляют со Маркова (математический аппарат, позволяющий с бой улучшенный вариант марковских моделей мак учетом текущего состояния системы вычислить ве- симальной энтропии, в которых учитывается зави роятность попадания системы на следующем шаге в симость вероятности следующего состояния не одно из возможных состояний). В статье состоя- только от предыдущего входящего токена, но и от ниями являются сегменты, вся система – текст, а всех рассматриваемых токенов, а также, по анало состояние системы на текущем шаге – токен. Веро- гии с марковскими моделями максимальной энтро ятность попадания токена в сегмент вычисляется на пии, рассматривается возможная зависимость ха основе всех имеющихся данных о парах токен – рактеристических функций между собой. Эта мо сегмент. При этом последовательность смены сег- дель улучшает результаты, но при этом значительно ментов строго задана, что облегчает алгоритм, так возрастает сложность вычислений, следовательно, как возможные конечные состояния строго заданы. падает скорость обработки обучающего множества.

Модель эффективна для задачи сегментирования Из приведенных выше описаний методов стано текстов, но не всегда пригодна для поиска данных в вится ясно, что значимое влияние на сложность ал тексте. Например, необходимо найти такие данные, горитма оказывает число токенов, встречающихся в которые могут встречаться в любой части текста, и рассматриваемых текстах. Для некоторых задач невозможно задать точную схему предложений, в уменьшение вычислительной нагрузки достигается которых эти данные могут встретиться. за счет использования групп – объединение разных слов, похожих по смыслу. Например, в качестве где i, i = 1,..., m, – коэффициенты при характери группы можно рассматривать слова «машина» и «автомобиль». Объединение в группы может при стических функциях, зависящие от правых частей меняться при кластеризации набора текстов по Fk уравнения (1), а Z (1,..., m ) – нормализующий ключевым словам. Но, в то же время, метод непри множитель.

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

чаются вручную;

на основе этих данных подбира В статье [12] приводится алгоритм использова ются коэффициенты для характеристических функ ния двоичных деревьев для того, чтобы слова с од ций в функциях распределения).

ной основой определялись как одинаковые или по Обучающее множество разбивается на токены, хожие слова. Это также позволяет уменьшить коли чество рассматриваемых токенов. Очевидно, что o j, с которыми ведется дальнейшая работа. В на при больших объемах анализируемых текстов это шей задаче токены – слова. Для каждого токена оп значительно снижает вычислительные нагрузки.

ределяется состояние, к которому он (токен) отно Эффективный способ уменьшения количества сится. В рассматриваемой задаче используется всего рассматриваемых токенов – использование групп 2 состояния – «собственное имя» и «не собственное слов. Слова-синонимы объединяются в группы имя». Таким образом, множество состояний прини слов. Но иногда смысл слова можно определить мает вид S = {0,1}. В некоторых случаях могут быть только с учетом контекста, следовательно, одно и то же слово может быть отнесено к разным группам. В заданы функции запрета переходов между состоя ниями на каких-либо шагах. На начальном этапе таких случаях необходимо провести анализ текста.

Для построения анализатора текстов представля- также выбираются характеристические функции ет интерес метод стохастических грамматик. В [13] f i ( s j, o j ). Параметр o j дописывается в качестве этот метод применяется для распознавания речи.

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

ния в тексте какой-либо интересующей нас инфор Эти характеристические функции входят в урав мации.

нения (1), задающие ограничения на функции рас пределения вероятностей. Для составления этих 4 Описание метода уравнений с помощью эксперта проводятся сле дующие операции:

Теперь рассмотрим подробнее марковскую мо • определяется последовательность смены дель максимальной энтропии, адаптированную ав тором к поставленной задаче, аналогично тому, как состояний s1,..., sn на основе обучающего множе это было сделано в [5].

ства – для каждого токена oi из обучающего мно Рассмотрим случайную величину X, прини жества эксперт определяет соответствующее ему мающую значения xi, i = 1,..., n. Пусть заданы m состояние si ;

характеристических функций f k ( xi ), k = 1,..., m. И • по принципу максимальной энтропии стро пусть ограничения на функции распределения веро ятся матрицы вероятностей перехода между состоя ятностей заданы выражениями вида ниями Ps ' ( s | o), где s ' S – предшествующее n P( x | I ) f ( xi ) = Fk, k = 1,..., m, (1) начальное состояние системы, s S – следующее i k i = состояние системы, o – рассматриваемый токен. В n P( x | I ) = 1, качестве ограничений (1) используется предполо i i = жение, что математические ожидания значений ха где P( xi | I ) – вероятность попадания в состояние рактеристических функций на множестве всех рас сматриваемых текстов будут равны средним значе xi при условии I, f k ( xi ) – значение k -й характе ниям этих функций на обучающем множестве (ана ристической функции для состояния xi, а логично тому, как предложено в [1]):

Fk, k = 1,..., m, 1 m's m's – правая часть уравнений fa (stk, otk ) = m' P ' (s | o ) f (s, o ), ограничений, не зависящая от характеристической s tk a tk m's k =1 k =1 sS s функции f k ( xi ).

m 's – число переходов из состояния s ', где Тогда вероятностным распределением с макси t1,..., tm 's – моменты времени перехода из состоя мальной энтропией является распределение Гиббса m 1 ния s ' для обучающего множества.

exp i f i ( x j ), (2) P( x j | I ) = Z (1,..., m ) i =1 Как уже упоминалось, при таких ограничениях Наличие аббревиатуры. Предыдущее слово со функции распределения вероятностей имеют вид держит аббревиатуру и рассматриваемое слово на распределения Гиббса (2). Оценка параметров a чинается с большой буквы. В данном случае под аббревиатурой понимается несколько заглавных производится по алгоритму GIS (General Iterative букв подряд, разделенных точкой. Такая комбина Scalling) [14]. С помощью алгоритма можно итера- ция символов встречается при наличии инициалов и тивно определить приближенное значение парамет- фамилии в тексте, когда инициалы предшествуют ров, входящих в вероятностную функцию перехода, фамилии. При этом наличие точек между заглавны заданную в выражении (2). ми буквами инициалов обязательно. Это исключает Необходимым условием корректной работы ал- возможность отнесения к собственным именам об горитма является постоянное для всех рассматри- щепринятых сокращений, употребляемых для уточ ваемых токенов значение суммы вероятностных нения типа юридического лица и т. п.

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

теристических функций для текущего токена. Наличие апострофа. Рассматриваемое слово Подставив полученные значения параметров в начинается с большой буквы и в нем содержится уравнение (2), получаем набор вероятностей пере- символ «’». Исходя из особенностей грамматики ходов между состояниями для заданных токенов. английского языка, апостроф в конце слова означает Тогда на новом множестве токенов, т. е. на остав- принадлежность одушевленному предмету. Это по шемся множестве исследуемых текстов, вероят- зволяет предположить, что рассматриваемое слово – ность попадания системы в состояние s на шаге t собственное имя. Если же апостроф содержится в определяется по алгоритму Витерби [15], рекурсив- начале слова, то его наличие также, зачастую, явля ный шаг которого задается выражением ется признаком собственного имени.

t +1 ( s ) = t ( s ')* Ps ' ( s | ot +1 ), Функция частоты. Частота встречи слова во множестве документов менее 20. Данная функция s 'S используется для того, чтобы избежать рассмотре где t +1 ( s) – вероятность того, что (t + 1) -й токен ния возможных ложных собственных имен и отсе ять наиболее часто встречающиеся слова, так как попадает в состояние s '. Это значение вычисляется это, скорее всего, распространенные глаголы и для всех возможных состояний s S и выбирается предлоги.

максимальное значение. Специальные предшественники. У рассматри Следует отметить, что в приведенной формуле ваемого слова есть предшественник из специально учитываются не только предыдущее или текущее го списка предшественников (например, mr., sir., состояние системы, но и вся предыдущая цепочка president, chairman и т. д.) и само слово начинается с состояний, так как для вычисления вероятности по- большой буквы. Данный список был сформирован следующего состояния мы используем вероятность на основе анализа некоторых текстов из коллекции текущего состояния, которая вычислена по этой же и может быть дополнен при более детальном рас формуле. смотрении данного вопроса.

Перечисление собственных имен. Предыдущие 5 Описание характеристических функ- два слова – слово с большой буквы и «and». Если ций рассматриваемое слово также начинается с большой буквы, то оно может рассматриваться как кандидат В работе рассматривается применение марков- в собственные имена. Эта характеристическая ской модели максимальной энтропии к задаче из- функция схожа с той, где вместо слова «and» рас влечения собственных имен из текста. На основе сматривалось наличие символа «, ». Ее важная осо анализа специфики построения английских текстов бенность заключается в том, что для анализа необ для решения рассматриваемой задачи было сформу- ходимо использовать не только одно слово лировано 10 характеристических функций. Для пяти предшественник, а сразу два. Это повышает точ из них в [5] автором уже была проанализирована ность исследования.

эффективность применения выбранной модели. Ис- Функция длины слова. Длина рассматриваемо пользуемые характеристические функции таковы. го слова находится в пределах [3;

20] символов. Гра Необходимое условие. Слово начинается с ницы установлены автором условно, так как при большой буквы и является существительным. Это длине слова, меньшей 3, велика вероятность того, наиболее очевидная характеристическая функция, что это предлог или вспомогательное слово. Если которая, за исключением опечаток, является необ- длина превосходит 20 символов, то рассматривае ходимым условием того, что рассматриваемое слово мое слово, скорее всего, является сложным – со является собственным именем.

ставным, следовательно, маловероятно, что оно от- известных собственных имен и лингвистические носится к собственным именам. правила, характерные для языка, на котором напи саны тексты коллекции. В данном случае – это анг Комбинация с несобственным существитель ным. Предыдущие слова – существительное или лийский язык. В качестве словарей использовались местоимение и слово «and». Если рассматриваемое множества собственных имен из Wikipedia [4], а слово начинается с большой буквы, то его относим также список фамилий, содержащийся в самой кол к кандидатам в собственные имена. В данном слу- лекции Reuters21578 [2]. Так как в коллекции со чае рассматривается не только два предшествую- держится лишь файл с фамилиями, а нас интересо щих слова, что уже было отражено в характеристи- вали также и имена персон, то имена в данном слу ческих функциях данного набора. Здесь учтены час- чае мы взяли из первого списка. Таким образом, ти речи рассматриваемых слов, а также устранено данный словарь можно считать синтезированным.

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

предшественнике. Обозначим через CNE количество слов, верно Последующий глагол. Рассматриваемое слово выделенных из текста в результате разметки собст начинается с большой буквы, а следом за ним в венных имен, ENE – количество «кандидатов» – предложении (тексте) расположены глагол или ка- слов, помеченных как собственные имена при ис кая-нибудь отглагольная форма, отражающая дей- пользовании метода, TNE – действительное количе ствие. Исходя из особенностей английского языка, ство собственных имен в тексте.

глагол, как правило, следует за существительным, и Качество полученных результатов будем оцени если это существительное начинается с большой вать следующими характеристиками:

• буквы, то это может быть и собственное имя. Осо- точность определения класса (NEP – name бенность этой характеристической функции в том, entity precision) – отношение числа правильно выде что она использует не предыдущие слова, а после- ленных элементов класса к общему числу выделен дующее, а также принимает во внимание не только ных элементов этого класса само слово, но и его часть речи. CNE NEP = ;

В сформулированных характеристических функ ENE циях учитываются два слова предшествующие ис • полнота определения класса (NER – name следуемому токену и одно слово следующее за не entity recall) – отношение числа правильно опреде посредственно за ним. На значение характеристиче ленных элементов класса к общему числу элементов ских функций влияют части речи этих слов, а также данного класса в тексте результат их сравнения со специальным набором CNE слов-предшественников. Кроме того, учитываются NER =.

длина рассматриваемого слова, частота его встреч TNE во всей коллекции, а также наличие знаков препи- Кроме того, на основе значений точности и пол нания между словами. ноты определения собственных имен вычисляется дополнительная метрика – F -мера :

6 Описание экспериментов 2 NEP NER F -мера = NEP + NER Для проведения экспериментов использовалась для сравнения значений, полученных для разных коллекция английских текстов Reuters21578 [2]. Это множеств.

архив новостных публикаций, распространенных агенством Reuters в 1987 году.

В качестве обучающего множества выбиралась 7 Результаты экспериментов часть документов из вышеназванной коллекции.

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

ных коэффициентов было замечено, что коэффици При анализе текстов использовался анализатор енты в формуле распределения вероятностей для грамматики treeTagger [3]. С его помощью для каж функций «необходимое условие» и «наличие аббре дого слова определялись часть речи, к которой оно виатуры» в 1,5 раза больше, чем для других харак относится, и вероятная основа. В упомянутой про теристических функций, что говорит о большей за грамме для выделения основы слова и определения висимости вероятности от этих функций по сравне его части речи используется двоичное дерево.

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

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

При проведении аналогичных исследований, но Наибольшие значения точность выделения «соб уже для набора из 10 характеристических функций, ственных имен» достигает для наборов из девяти были получены результаты, представленные в функций, полученных исключением из полного на табл. 1. В ней для краткости наборы содержат по- бора 3, 4, 7 или 10 функции. А полнота определения рядковые номера входящих в них характеристиче- «собственных имен» достигает наибольшего значе ских функций. ния для набора без 5 функций.

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

специальным образом: сначала вычислялись при Из табл. 1 видно, что F -мера принимает отно ближенные значения коэффициентов для одинако сительно большие значения для наборов характери вых начальных значений i(0) = 1. Новое начальное стических функций (1-9);

(1-6, 8-10);

(1-3,5-10);

(1 i(0) 2,4-10). Наибольшие значения мера достигает для полагается равным значение коэффициента наборов из девяти функций, причем значения для вычисленному приближению, разделенному на 10.

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

шения поставленной задачи.

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

дования также проводились для обучающих мно Объем обучающего множества составляет 10 % от жеств, состоящих из 30% и 50% от всего множества исследуемого текстов (обучающее множество состояло из 300 и Наборы функций\ F -мера NER NEP 500 документов соответственно). Приведем значе характеристики ния рассматриваемых характеристик для найденных 1-10 0,11702 0,11 0,125 «оптимальных» наборов характеристических функ 1-9 0,2 0,5 0,125 ций (см. таблицы 2 и 3).

1-8, 10 0,0001 0,0001 0, Таблица 2. Значение точности, полноты и F -меры 1-7, 9-10 0,06140 0,035 0, для разных наборов характеристических функций.

1-6, 8-10 0,22222 1 0, Объем обучающего множества составляет 30 % от 1-5, 7-10 0,08333 0,05 0, исследуемого 1-4, 6-10 0,05801 0,03 0, 1-3, 5-10 0,2 0,5 0,125 Наборы функций\ F -мера NEP NER 1-2, 4-10 0,22222 1 0,125 характеристики 1, 3-10 0,11758 0,111 0,125 1-10 0,05797 0,0327 0, 2-10 0,08333 0,05 0,25 1-9 0,09999 0,0833 0, 1,5,9 0,05468 0,035 0,125 1-6, 8-10 0,10526 0,0909 0, 1-3, 5-10 0,10526 0,0909 0, Для рассматриваемых текстов и введенных ха 1-2, 4-10 0,04651 0,0285 0, рактеристических функций наиболее точно классы определяются для наборов из девяти функций, по- Таблица 3. Значение точности, полноты и F -меры лученных исключением из полного набора 3, 4, для разных наборов характеристических функций.

или 10 функции. Это показывает, что при определе Объем обучающего множества составляет 50 % от нии классов выделенные функции на данном наборе исследуемого текстов не несут новой полезной информации, а лишь «загрязняют» полученные результаты – пони- Наборы функций\ F -мера NEP NER жают точность при неизменном значении полноты, характеристики т. е. при их использовании выделяется большее ко- 1-10 0,04419 0,0233 0, личество токенов в качестве собственных имен, при 1-9 0,05128 0,0280 0, этом относительное количество верно определен- 1-6, 8-10 0,08510 0,0540 0, ных представителей класса собственных имен 1-3, 5-10 0,08333 0,0526 0, уменьшается. 1-2, 4-10 0,05172 0,0283 0, С точки зрения поставленной задачи – извлече Для таких начальных данных наибольшее значе ния собственных имен из текста (их в текстах, как ние F -меры принимает для наборов характеристи правило, гораздо меньше, чем несобственных) – интерес представляют точность и полнота опреде- ческих функций (1-6, 8-10) и (1-3, 5-10), причем для ления не всех рассматриваемых классов, а именно этих же наборов достигает свои наибольшие значе класса собственных имен, причем интерес пред- ния и точность определения собственных имен.

• Значит, можно считать, что для точности класса оценить эффективность применения каждо наименее значимыми являются функции 4 и 7. го из используемых словарей;

Легко заметить, что с увеличением обучающего • сравнить результаты, полученные при ис множества растет полнота определения собствен- пользовании выбранных множеств собственных ных имен, но при этом падает точность. Это проис- имен.

ходит в том случае, когда в качестве собственных Результаты, полученные во время исследования, имен выбирается большое количество токенов. Зна- приведены в таблицах 4 и 5.

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

функций. Из приведенных таблиц можно сделать • с точки зрения абсолютных показателей вывод, что для исследуемого набора характеристи- большую эффективность дает применение словаря ческих функций и рассматриваемого множества Wikipedia [4], но следует отметить, что при этом текстов при увеличении размера обучающего мно- количество выделенных кандидатов практически в жества уменьшаются точность определения «собст- два раза больше;

венных имен» и значение F -меры. Этот факт рас- • из сравнения характеристических парамет ходится с ожидаемыми результатами и требует до- ров можно сделать вывод, что применение словаря полнительного исследования. коллекции Reuters21578 [2] дает несколько более Проанализировав полученные значения, можем хорошие результаты, чем применение словаря Wiki сделать следующие выводы: pedia [4], что, в принципе, совпадает с ожидаемым • результатом;

при специфическом выборе начальных зна • чений для коэффициентов в упомянутом алгоритме среди невыделенных собственных имен значимыми на описанном наборе текстов являются следует отметить наличие арабских и японских девять характеристических функций;

имен, которые не содержались в используемых сло • варях, что ухудшило показатели;

существенными для достижения точности • определения класса собственных имен являются кроме того, добиться улучшения качества функции 1, 2, 3, 5, 6, 8, 9, 10;

разметки можно, учитывая при разметке некоторые • лингвистические правила английского языка (на с увеличением обучающего множества ме пример, добавление 's);

тод расходится;

необходимо найти такую характе • ристическую функцию для уже имеющегося набора, было выделено много «лишних» слов: ар которая обеспечит сходимость метода, а также по- тикли, предлоги, заглавные буквы – инициалы из добрать такое оптимальное по размеру обучающее словаря;

это объясняется тем, что словарь из Wiki множество, чтобы исключить возможность возник- pedia [4] содержит в себе такие имена, как Alexander новения переобучения метода;

of Makedonia;

каждое слово из имени словаря счи • талось как отдельное собственное имя.

при увеличении размера обучающего мно жества уменьшаются значение точности определе Таблица 4. Абсолютные значения, полученные ния «собственных имен» и значение F -меры, сле из эксперимента довательно, необходимо исследовать возможное ENE CNE Unique Not Unique переобучение метода и проследить за динамикой CNE found not соответствующих показателей при ограничении NE found размеров словаря;

NE • в то же время, полнота выделения «собст- Список венных имен» возрастает с увеличением тестового имен из 969 174 96 161 множества. Wikipedia Теперь рассмотрим вспомогательную задачу – Список имен из 572 128 71 207 автоматическую разметку текстов с помощью раз Reuters личных словарей. Для этого исследования также были взяты первые 1000 документов коллекции. В Таблица 5. Значения характеристических качестве словарей использовались множества соб- параметров ственных имен из Wikipedia [4], а также список фа F -мера милий, содержащийся в самой коллекции NER NEP Reuters21578 [2]. Так как в коллекции содержится CNE Wiki 0,17957 0,5223 0, лишь файл с фамилиями, а нас интересовали также pedia и имена персон, то имена в данном случае мы взяли Unique CNE 0,09907 0,5485 0, Wikipedia из первого списка. Таким образом, данный словарь CNE Reu можно считать синтезированным. 0,22377 0,3820 0, ters Кроме того, интересно посмотреть на результа Unique CNE ты, полученные только с использованием списка 0,1241 0,4057 0, Reuters фамилий из коллекции Reuters21578 [2].

В ходе проведения эксперимента ставились за- Интересные результаты получены для разметки дачи: документов только с использованием фамилий из коллекции Reuters21578 [2]. Для такого словаря вы- [4] Wikipedia. The free encyclopedia. – http://en. wi делено всего 44 CNE, что, конечно же, мало в срав- kipedia.org.

нении с общим числом собственных имен в тексте. [5] Глазова М.А. Извлечение собственных имен из Следует отметить, что среди выделенных «кан- текста с помощью метода максимальной энтро дидатов» не содержится ни одного ложного «канди- пии, основанного на цепях Маркова // Процессы дата». Если вычислять значения характеристиче- управления и устойчивость: Труды 40-й межд.

ских параметров, рассматривая в качестве искомых науч. конф. аспирантов и студентов / Под ред.

собственных имен только фамилии (их всего 119), Н.В. Смирнова, Г.Ш. Тамасяна. – СПб.: Изд.

Дом С.-Петерб. гос. ун-та, 2009. – С. 402-407.

то получаются следующие результаты: NEP =1, [6] Программная система извлечения информации NER = 0,4033, F -мера = 0,57478.

из текстов (ПС INEX). – http://www.skif.

Далее были предприняты попытки по очистке pereslavl.ru/psi-info/airec/airec-ppt.rus/inex.ppt словарей от «лишних» слов. Также добавлено пра [7] Li Hang. Learning to rank: a new technology for вило с апострофом. Полученные результаты пред text processing. – http://www-tsujii.is.s.u-tokyo.

ставлены в таблицах 6 и 7.

ac.jp/T-FaNT/T-FaNT.files/Slides/Li.pdf.

Таблица 6. Абсолютные значения после обработки [8] Yu Shui, Song Hui, Ma FanYuan. Novel SVM per словаря formance estimators for information retrieval sys tems. – Department of Computer Science and ENE CNE Unique Not Unique Technology, Shanghai Jiaotong University, Shang CNE found not hai, 2000.

NE found [9] Wu Xiaofeng, Zong Chengqing. A new approach to NE automatic document summarization//Proc. of the Список Third Int. Joint Conf. on Natural Language Proc имен из 592 181 97 154 Wikipedia essing, 2008.

[10] Blunsom Ph. Hidden Markov models. – University Таблица 7. Значения характеристических of Melbourne, Faculty of Engineering, Human параметров Language Technology, August 2004. – P. 433- F -мера [11] Lafferty J., McCallum A., Pereira F. Conditional NEP random fields: probabilistic models for segmenting CNE Wiki 0,30574 0,54029 0, and labeling sequence data. – www.cis.upenn.edu/ pedia pereira/papers/crf.pdf.

Unique CNE 0,16385 0,5543 0, Wikipedia [12] Haffari G., Whye Y. The hierarchical Dirichlet trees for information retrieval. – www.aclweb.org/ Сравнивая результаты, полученные в рассмот- anthology/N/N09/N09-1020.pdf.

ренных случаях автоматической разметки текстов, [13] De Mori R., Kuhn R. Some results on stochastic замечаем, что: language modelling. – www.aclweb.org/anthology/ • сравнение только со словарем дает не очень H/H91/H91-1043.pdf.

хорошие результаты, эффективнее проводить такое [14] Wang Shaojun, Schuurmans D., Peng F., Zhao Y.

сравнение с дополнительным использованием лек- Combining statistical language models via the la сических правил соответствующего языка;

tent maximum entropy principle. – http://www.

• springerlink.com/content/m7n3w4022706l3t5/ full плохо выделяются арабские и японские text.pdf.

имена.

[15] Компьютерное распознавание и порождение Необходимо пополнить используемый словарь речи. – http://speech-text.narod.ru/chap4_2_2.

списком специфических имен. Основные категории html.

ошибочных кандидатов:

• названия месяцев (May, August, April);

Using of maximum entropy Markov model • сторон света (West, North);

• стран (German, France), городов (London, for the problem of extracting name entities New York) и пр. географических объектов (Victoria);

from English texts • цвета (Black, White).

M. Glazova Литература In the article is presented the problem of extracting [1] McCallum A., Freitag D., Pereira F. Maximum name entities from English texts. Markov model of entropy Markov models for information extraction maximum entropy is selected to solve the problem. This and Segmentation. – http://www.ai.mit.edu/ document includes a description of set of characteristic courses/6.891-nlp/READINGS/maxent.pdf. functions, which were formulated to use in the method.

[2] LANGREITER.COM plain, simple. Also experiments for the automatic partitioning of the [3] www.ims.uni-stuttgart.de/projekte/corplex/ Tree- training set are described. In the paper you can find Tagger. results and conclusions from experiments based on the use of different vocabularies and rules.

Перспективные методы обработки проектной документации © Э.С. Клышинский Московский государственный институт электроники и математики klyshinsky@mail.ru С помощью PDM-систем осуществляется отсле Аннотация живание больших массивов данных и инженерно Cтавятся задачи, решение которых могло технической информации, необходимых на этапах бы вывести обработку проектной докумен- проектирования, производства или строительства, а тации на качественно иной уровень. В каче- также поддержки эксплуатации, сопровождения и стве таких задач рассматриваются автома- утилизации технических изделий [3]. PDM-системы тизированное выделение требований к из- позволяют создавать отчеты о конфигурации вы делиям, поиск прецедентных документов в пускаемых систем, маршрутах прохождения в ходе ходе анализа и проектирования изделия, технологического процесса изделий, их частей или проверка полноты документации при за- деталей, составлять списки материалов и деталей, вершении работ над изделием, автоматиче- необходимых для производства изделия. Одной из ская генерация документации о составных задач, решаемых PDM-системами, является обеспе частях изделия, автоматический подбор чение возможности групповой работы над проек компонентов для изготовления изделия. том.

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

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

ная документация, планы и т. д. В последнее время На данный момент ведется переход от электронного довольно широкое распространение получили сис хранилища, являющегося заменой полок с докумен темы ILM (Information Lifecycle Management) и тами, к интеллектуальной обработке документации.

PDM (Product Data Management). ILM охватывает Часть проблем в данной области уже успешно ре все процессы управления размещением, хранением, шена. При помощи средств Business Intelligence распределением, миграцией, архивированием и уда проводится эффективный анализ собранной в ILM лением данных в инфраструктуре предприятия [1, системе данных. Специальные системы автоматиче 2]. Задачей ILM является хранение документов и ски или автоматизированно формируют список де обеспечение оптимального времени доступа к ним талей и механизмов, входящих в состав изделия, со стороны пользователя и его систем. Так, напри список и порядок работ и производственных про мер, оперативная информация помещается «рядом»

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

стовой документации.

В данной работе рассматривается несколько Труды 12й Всероссийской научной конференции перспективных задач, связанных с автоматической «Электронные библиотеки: перспективные методы и обработкой текстов при проектировании и произ технологии, электронные коллекции» – RCDL’2010, водстве различных изделий. Решение этих задач Казань, Россия, должно помочь перевести некоторые процессы, вы- занного с ними контекста позволяет выделить опи полняемые до сих пор вручную, в новое русло. В сание задаваемых ими требований. Список требова основном для решения поставленных задач реко- ний может оформляться как набор гиперссылок на мендуется использование документации, подготав- найденные части документа, помогая тем самым не ливаемой в ходе обычного цикла разработки нового потерять важную информацию из окружения фразы.

продукта. При этом такой документ или набор до- Использование онтологии или тезауруса дает кументов используются в качестве поискового за- возможность сгруппировать выделенные требова проса к информации, хранимой, например, в ILM- ния по классам. Их применение позволяет перейти к или PDM-системе. задаче извлечения знаний из естественно-языковых Документ в качестве запроса активно использу- текстов [8, 9]. В результате можно сформировать ется в таких предметных областях, как рубрикация некоторую модель отношений между понятиями, текстов, составление списка заметок по той же те- связывающую отдельные слова в описание объекта матике из новостной ленты, других задачах, связан- окружающей среды. Вслед за формированием моде ных с тематическим анализом текстов [4, 5]. На ли объекта можно перейти к выделению значений конкурсе РОМИП документ-образец используется его параметров. Проделав подобные операции мож для уточнения запросов пользователя и фильтрации но перейти к проверке непротиворечивости требо выдачи. Лобовое использование документа, как ма- ваний, проверяя, например, диапазоны приписы териала для поисковых запросов, наталкивается на ваемых их параметрам значений. Становится воз огромную выдачу со стороны поисковой машины, можной группировка требований по классам, за счет ее существенное время работы. Как следствие, чего упрощается их анализ человеком, проверка пользователю становится сложно отобрать из боль- связанности и зависимостей между требованиями.

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

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

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

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

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

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

ся слов. Аналогичные профили хранятся в базе и Возможным вариантом решения задачи может для документов. Сравнение профилей позволяет служить отсев словосочетаний, равномерно распре выделить наиболее релевантные документы. При деленных по всем или почти всем документам [14].

этом вероятность пропустить необходимые ключе- Подобные словосочетания имеются в той или иной вые слова существенно снижается. Выделение про- степени в любом входном документе и, скорее все филей позволит решить задачу хранения информа- го, относятся к общей лексике. В этом случае в ции «близко» к пользователю. Подобная проблема верхнюю часть выдачи не попадут документы, встает в связи с тем, что большинство документов имеющие большое количество стандартных слово по уже завершенным проектом обычно переносится сочетаний. Более общим случаем является введение из области актуальных документов в область «мед- дискриминирующей силы словосочетаний. Здесь ленного» хранения, доступ к которой более ресур- для документа определяется набор словосочетаний, соемок. максимально отличающих данный документ от всех Вопрос построения профиля уже разбирался, на- остальных. При этом дискриминирующая сила оп пример, при кластеризации документов и достаточ- ределяется не только для словосочетаний, представ но хорошо проработан [10]. Кроме того, вместо ис- ленных в документе, но и для отсутствующих в нем, пользования отдельных слов можно оценивать их так как отсутствие словосочетаний может служить сочетания. При таком подходе можно применять отличительным стилевым или тематическим при такие методики, как латентно-семантический анализ знаком.

[11], Bag-of-Words [12, 13] или коллокации [14].

4 Проверка полноты документации Применение этих подходов позволяет повысить релевантность выдаваемых документов. При ис- Работы в данной области ведутся уже довольно пользовании в качестве запросов отдельных слов продолжительное время. Так, например, была соз подобные методы применимы значительно меньше, дана система «ЛоТА», предназначенная для анализа так как запрос может состоять из несвязанных фраз документации с использованием системы онтологий или попросту содержать в себе единственное слово. [15, 16]. Данная система предназначена для приме Формально задача может быть поставлена сле- нения при анализе документов «Логика работы сис дующим образом. Пусть дано множество докумен- темы …» в авиационной промышленности [10]. В ней предварительно проводится морфологический ся не количеством совпадений, а степенью близости анализ текста документа, с использованием онтоло- понятий в графе онтологии [17, 18].

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


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

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

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

ченные слова и словосочетания используются для 5 Автогенерация документации информационного поиска по массиву итоговой до кументации. Если по какому-либо из запросов вы- В ходе проектирования изделия разрабатывается дача отсутствует, то это служит индикатором отсут- большое количество документации в специальных ствия информации о разделе. форматах. Это могут быть чертежи, UML Аналогичным образом могут сравниваться про- диаграммы функционирования, специализирован фили фрагментов документа-запроса с профилями ные описания систем, подсистем и их взаимодейст итоговой документации. Слабая степень соответст- вия. Производимые в них изменения требуют вно вия профилей означает неполноту представленной сить изменения и в текстовое описание проделанной информации. работы. Чтобы избежать постоянной переделки тек К сожалению, метод не защищен от фрагментар- стовой документации, можно попытаться автомати ного упоминания решения, когда после постановки зировать процесс ее составления. Так, например, к вопроса следуют весьма урезанное его описание или отдельным блокам и подсистемам могут привязы пространные рассуждения из другой области. Для ваться текстовые фрагменты. Таким образом, доку распознавания такой ситуации можно оценить дис- ментация может быть превращена из текстовой в персию частоты упоминаний отдельных терминов, интерактивную. Разработчик выбирает заданный причем подобная оценка может проводиться по блок и имеет возможность ознакомиться с его опи всем выделенным фрагментам. санием. Далее, для проектной документации задает Другим недостатком метода является возможная ся логика изложения обычного линейного докумен смена терминологии при переходе от технического та, собираемого из отдельных текстовых блоков.

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

возможно даже сленгу, тогда как проект разрабаты- Кроме того, к различного вида связям могут вался профессионалами, тонко чувствующими раз- привязываться различные шаблонные языковые ницу между различными определениями. В этом конструкции. Так, например, соединение с валом случае лексический состав документов будет суще- позволяет говорить, что «вал вращает» и добавлять ственно различным. Здесь на помощь могут прийти название детали. Для задания подобного рода опи семантические методы анализа документов, напри- саний и генерации связанного текста по ним можно мер, методы, опирающиеся на онтологии. Мера со- использовать уже упоминавшуюся объектно ответствия профилей документов будет определять- ориентированную модель представления знаний [8].

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

ся определенные параметры модели. Подобная схе ма уже много лет используется в Канаде при со- Литература ставлении прогноза погоды на английском и фран [1] Головченко А. ILM – концепция и инструмен цузском языках [19].

тарий // PCWeek Review. – 2008. – № 1.

6 Автоматический подбор компонентов [2] Орлов С. Жизненный цикл ILM // LAN. – 2007.

– № 7.

Представим, что у нас имеется база данных, со [3] Беспалов В., Клишин В., Краюшкин В. Развитие держащая в себе описания различных компонент, систем PDM: вчера, сегодня, завтра... // САПР и используемых в производстве. При этом помимо графика. – 2001. – № 12.

описания характеристик компоненты имеется и тек [4] Чугреев В.Л., Яковлев С.А. Выделение крите стовое описание данного компонента. Используя риев поиска текста на основе подобия значимых подобную базу, можно провести подбор компонент, документов // ВУЗОВСКАЯ НАУКА – оптимально подходящих для выпускаемого изделия.

РЕГИОНУ: Материалы 1-й Общероссийской На данный момент уже существуют системы B2B и нучн.-техн. конф. – Вологда: ВоГТУ, 2003. – B2C, а также сервисы, подобные Яндекс.Маркет.

C. 200-202.

Результатом проектирования системы является [5] Некрестьянов И., Некрестьянова М. РОМИП' ее детальное описание, которое содержит в себе, 2006: отчет организаторов // Российский семи среди прочего, разбиение системы на отдельные нар по Оценке Методов Информационного По блоки. Используя поисковые алгоритмы, можно иска. Труды четвертого российского семинара провести поиск необходимых компонент по храни РОМИП'2006, Суздаль, 19 октября 2006 г. – мым в базе описаниям. По результатам информаци Санкт-Петербург: НУ ЦСИ, 2006. – С. 7-29.

онного поиска обычно сравниваются лишь основ [6] Пескова О.В. Автоматическое формирование ные характеристики, имеющие, как правило, число рубрикатора полнотекстовых документов // вое значение, или значение из заданного множества Электронные библиотеки: перспективные мето (цвет, тип, …). Однако ряд дополнительных харак ды и технологии, электронные коллекции: Тру теристик может помещаться в текстовом виде, и ды Десятой Всерос. науч. конф. RCDL'2008, поиск по ним будет вестись с использованием клю Дубна, 7 – 11 октября 2008 г. – Дубна: ОИЯИ, чевых слов. Как это уже замечалось выше, подоб 2008. – С. 139-148.

ный поиск может оказаться неполным. Однако ком [7] Большакова Е.И., Баева Н.В., Бордаченкова понентам проектируемой системы в документации Е.А., Васильева Н.Э. Морозов С.С. Лексико приписывается как словесное описание, содержащее синтаксические шаблоны в задачах автоматиче в себе как диапазоны необходимых значений основ ской обработки текста // Компьютерная лин ных параметров, так и описание условий эксплуата гвистика и интеллектуальные технологии: Тру ции, некоторых особенностей реализации и другие ды межд. конф. «Диалог 2007». – М.: Изд-во параметры, описание которых не может быть крат РГГУ, 2007. – С. 70-75.

ким. Описание требующихся нам компонент может [8] Лебедев А.С. Естественно-языковое програм использоваться для формирования запроса к базе, мирование как средство извлечения знаний // хранящей подобные компоненты. Для этого необ Труды ИВМиМГ, Информатика, Вып. 9. – Но ходимо извлечь из текстового описания документа восибирск, 2009. – С. 64-71.

запроса список интересующих нас параметров и [9] Андреев А.М., Березкин Д.В., Симаков К.В.

значения этих параметров. Кроме того, необходимо Модель извлечения знаний из естественно сформировать профиль остальной части описания и языковых текстов // Информационные техноло использовать его для сравнения с профилями хра гии. – 2007. – №12. – С. 57–63.

нимых описаний.

[10] Абрамов А.П., Выдрук Д.Г., Федунов Б.Е. Ком пьютерная система оценки реализуемости алго 7 Выводы ритмов деятельности экипажа // Изв. РАН. Тео Создание систем нарастающей сложности остро рия и системы управления. – 2006. – № 4. – ставит вопросы дальнейшей автоматизации всех С. 122-134.


процессов, начиная с анализа требований и закан- [11] Katz G., Giesbrecht E. Automatic identification of чивая технической поддержкой пользователя и non-compositional multi-word expressions using уничтожения отработанных изделий. Наибольший latent semantic analysis // Proc. of Multiword Ex успех в этой области был достигнут для задач соз дания и хранения документации. Одним из сле pressions: Identifying and Exploiting Underlying Properties, Sydney, 2006. – P. 12-19.

[12] Mladenic D. Text-learning and related intelligent agents: a survey// IEEE Intelligent Systems. – 1999.

– V. 14, No 4. – P. 44-54.

[13] Caropreso F., Matwin S. Beyond the bag of words:

a text representation for sentence selection// Proc.

of AI2006, Qubec, QC. – P. 324-335.

[14] Ягунова Е.В., Пивоварова Л.М. Природа колло каций в русском языке. Опыт автоматического извлечения и классификации на материале но востных текстов// Сб. НТИ, Сер. 2. – М., 2010. – № 5.

[15] Невзорова О.А. Подход к разработке методов автоматизированного контроля информацион ной целостности технических текстов //Труды десятой национальной конф. по искусственному интеллекту КИИ-2006. Т. 2. – М.: Физматлит, 2006. – С. 564-571.

[16] Невзорова О.А., Федунов Б.Е. Система анализа технических текстов «ЛоТА»: основные кон цепции и проектные решения // Изв. РАН. Тео рия и системы управления. – 2001. – № 3. – С. 138-149.

[17] Заболотняя Т.Н., Михайлюк А.Ю., Михай люк Е.С. Инверсионный контекстно-ассоциа тивный метод автоматической орфокоррекции // Штучний інтелект. – Киев, 2008. – № 3. – С. 78 88.

[18] Budanitsky A., Hirst G. Evaluating WordNet-based measures of lexical semantic relatedness // Compu tational Linguistics. – 2006. – V. 32. – No 1. – P. 13-47.

[19] Sripada S., Reiter E., Davy I., Nilssen K. Lessons from deploying NLG technology for marine weath er forecast text generation//Proc. of PAIS-2004, 2004. – P. 760-764.

Some perspective methods of project documentation processing E.S. Klyshinsky This paper describes some of tasks that can dramatically change the project documentation creation process.

There discussed tasks like automated requirements ex traction, precedent documents searching for the analysis and development stage support purposes, documenta tion fullness check on final stages, automatic documen tation generation about some part of designed product, automated components selection for designed product.

Работа выполнена при финансовой поддержке Феде ральной целевой программы «Научные и научно педагогические кадры инновационной России на 2009 2013 годы»

Статистический подход к решению проблемы определения страниц soft © С.С. Чирков Санкт-Петербургский государственный университет sergechircov@yandex.ru ных страниц, т. е. если общее число сломанных Аннотация страниц равно 5 – 8%, то число страниц soft составляет 1,5 – 2%.

Проблема распознавания страниц soft Разработчики сайтов могут использовать стра является актуальной проблемой современ ницы soft 404:

ных поисковых машин. Прежде всего, это • в качестве страниц, на которых можно по связано с тем, что страницы soft 404 нельзя местить информацию о том, почему страница не определить по коду протокола HTTP, как в доступна в данный момент, и предложить способы случае с обычными страницами 404. Ранее решения проблемы;

предложенные решения [1, 2] поиска стра • в качестве «припаркованных сайтов», т. е.

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

в работе [7] рассматривается сайт, для страниц soft 404, основанный на представ раскрутки которого использовалось более лении страниц в виде наборов слов (выра «припаркованных сайтов».

жений) и использовании алгоритмов ма Чем плохи страницы soft 404? Во-первых, поис шинного обучения для оценки близости этих ковой системе приходится индексировать такие наборов.

страницы, что требует определенного места для хранения информации. Во-вторых, страницы soft 1 Введение 404 могут привести к некорректной работе алго Ранее было произведено много исследований, ритмов поисковой системы. Одним из таких алго связанных со сломанными страницами. Сломанная ритмов является алгоритм ранжирования, самый страница – это страница, ссылка на которую сло- важный алгоритмом поисковой системы. Для при мана, или страница являющаяся soft 404. Страница мера рассмотрим алгоритм ранжирования soft 404, если переходить к понятиям кодов прото- PageRank [8]. Очевидно, что «припаркованные кола HTTP, – это страница, которую нужно было сайты» будут оказывать влияние на работу этого возвратить с HTTP кодом 404 (т. е. страница не алгоритма ранжирования, завышая реальные пози существует), но разработчики сайта решили воз- ции сайтов, на которые ссылаются «припаркован вратить её с HTTP кодом 200 (т. е. запрос клиента ные сайты», среди результатов, найденных по за обработан успешно, и сервер возвращает хорошую просу пользователя.

страницу). Рассмотрим предложенные решения поиска В ходе исследования [3], проведенного среди страниц soft 404 [1, 2]. Первое решение рассмотре 150 популярных сайтов из доменов.com,.gov,.edu, но в работе [1]. В ней авторы представили алго.org,.net и.mil, было установлено, что через полго- ритм определения сломанных страниц, также да 50% ссылок на сайтах было сломано. представили некоторую меру, при помощи которой В ходе исследования [4] было установлено, что можно подсчитать степень разложения интернета.

процент сломанных страниц внутри одного домена Коротко алгоритм определения сломанных стра верхнего уровня приблизительно равен проценту ниц можно записать так:

сломанных страниц во всем интернете. 1. Посылаем два запроса на сервер. Первый В работе [5] было установлено, что количество запрос – на интересующую нас страницу. Второй сломанных страниц во всем интернете в 1997 году запрос – на страницу, которой, вероятно, не суще составляло 5 – 8%. Сейчас эта цифра выше из-за ствует на сервере.

появления страниц soft 404. 2. Сравниваем количество перенаправлений В работе [6] было установлено, что страницы сервера для обоих запросов.

soft 404 составляют 25% от общего числа сломан- 3. Затем сравниваем содержание страниц, ис пользуя метод шинглов [9].

Труды 12й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» – RCDL’2010, Казань, Россия, 123  ROMIP BY.Web Состав Размер Предоставлена страницы домена.by из индекса Яндекс (май 2007) 1 (на глубину 3 ссылки от стартовой,) процент ссылок 676 док Яндекс внутрь коллекции ~25% 8 Гб На основании данных о количестве перенаправ- 4) Реализация алгоритма классификации по лений сервера и подсчитанных шинглах, делаем построенным векторам.

вывод о том, является ли рассматриваемая страни- Для составления выборки документов использо ца страницей soft 404 или нет. Недостатком алго- валась коллекция документов ROMIP BY.Web ритма является то, что автор считал, что главная 2007 [10] (см. таблицу выше). Коллекция состоит страница web-сайта не является soft 404. Для его из большого количества документов, и искать исследования этого было достаточно, но, как видно страницы вручную во всей коллекции не представ на практике, дело обстоит иначе (достаточно лялось возможным.

вспомнить «припаркованные сайты», которые со- Следующий итеративный алгоритм (1) позволил стоят всего из одной страницы). сократить количество страниц, среди которых Авторы работы [2] разработали инструмент нужно было искать страницы soft 404:

Walden’s Paths Path Manager, который помогает 1) Вручную составить словарь слов, чаще все пользователям в исследовании изменений, связан- го встречающихся на страницах soft 404.

ных с ресурсами, ссылки на которые присутствуют 2) Найти страницы, на которых встречаются на странице. В работе отмечено, что незначитель- слова из словаря.

ные изменения в содержании страницы оставляют 3) Разметить вручную найденные страницы.

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

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

струмент вполне можно применять для создания 5) Получена выборка размеченных страниц.

алгоритма распознавания страниц soft 404. Недос- Основные сложности, которые возникают при татком этого алгоритма является то, что первый работе по этому алгоритму, – это разметка стра раз все страницы необходимо просмотреть вруч- ниц, которую приходится выполнять асессору. Для ную, чтобы исключить уже существующие сло- того чтобы облегчить работу асессора, будем пола манные страницы. гаться на следующие наблюдения о страницах soft Недостатком алгоритма, описанного в [1], явля- 404:

ется его направленность на статические сайты, т. к. 1) Имеет значение, в каком HTML-тэге встре принятие решения о том, является ли страница soft тилось слово. Например, если фраза «error 404»

404 или нет, делается на основании равенства встретилась в тэге h1, то эта страница с большей шинглов и равенства количества перенаправлений вероятностью является soft 404, чем страница, в сервера. А для динамических сайтов значения которой эта же фраза встретилась в тэге p.

шинглов для одной и той же страницы могут раз- 2) Некоторые HTML-тэги можно объединить личаться, т. к. при каждом новом посещении стра- в группы, тогда 1 верно и для групп. Примеры:

ницы содержание будет меняться, хотя ее структу- {h1, h2, h3} – группа тэгов или {p, ра может оставаться неизменной, например, div, font, span} – группа тэгов. Такое объе http://www.vse-putem.com/djkdjk.html. динение позволит сократить количество призна В связи с этим актуальна задача создания алго- ков, описывающих страницу.

ритма, не зависящего от окружения, т. е. ссылок, 3) Существуют тэг T и слово W (фраза F) та присутствующих на рассматриваемой странице кие, что если W(F) встречается в предложении, на или других страниц сайта. ходящемся в тэге Т, то с некоторой вероятностью страницу можно отнести к одному из классов: soft 404 или хорошая страница. Например, если в тэге 2 Описание подхода к решению title встречается «about error», то рассматривае Решение включало в себя следующие этапы: мая страница c 90%-ой вероятностью будет хоро 1) Составление выборки документов, состоя- шей.

щей из страниц soft 404 и хороших страниц. В пределах одного предложения фраза, состоя 2) Составление словаря, состоящего из слов, щая из нескольких слов, имеет большую значи часто встречающихся на страницах soft 404 или мость, чем слова фразы по отдельности и в разных относящихся к теме soft 404. предложениях, принадлежащих одному тэгу. На 3) Представление страниц коллекции в виде пример, если в тэге title встретились два слова признаков. Признаку соответствует слово из сло- «about» и «error», и они находятся в двух разных варя. предложениях, то мы не можем утверждать, что 124  • данная страница с вероятностью 90% является хо- количество страниц soft 404 составляет рошей, а если в одном предложении встречается ~1% от общего числа всех страниц, «about error» – то можем. • на разметку 1000 страниц требуется Учитывая наблюдения, перечисленные выше, чел.·час.

приходим к следующему «слабому» (из-за ограни ченного количества фраз в словаре, порядка фраз) алгоритму определения страниц soft 404:

1) Составляем тренировочное множество, со стоящее из soft 404 и хороших страниц.

2) Все HTML-тэги разбиваем на группы.

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

4) Считаем частоты для фраз по следующей формуле: Рис. При использовании «слабого» алгоритма это # ( fi ) P( fi ) =, время составило 5 чел.·часов (без учета времени #( f j ) написания и тренировки самого алгоритма). С ис j пользованием словаря из 145 слов в алгоритме (1) где # ( f ) – частота появления фразы на всех стра- в исходной коллекции было найдено 95913 стра ницах тренировочного множества. ниц. На первой итерации в алгоритме (1) использо 5) Для каждой страницы составляем вектор вался словарь из 71-го слова. Из выборки, полу ченной на втором шаге алгоритма (1), применяя, A = ( a1, a 2, L, a m ), параметров где описанный выше алгоритм, удалось выделить ai = log(c jk ), i=1..m, страницу, потенциально являющуюся soft 404. По j,k сле разметки получили результат, представленный P ( fk ), если fk s j, на рис. 2. Разметка производилась одним асессо c jk = ром.

1 иначе, f k – из i-го словаря, s j – из множества предложе ний содержащихся в тэгах [(i + 1) / 2] -ой группы тэ гов. Размерность вектора A определяется количест вом групп тэгов, m = 2·(кол-во групп тэгов).

6) Для классификации по построенным векто рам воспользуемся алгоритмом k-NN.

Рис. Для тренировки и тестирования представленно После 7-ми итераций алгоритма (1) получили го выше алгоритма использовались множества, со результат, представленный на рис. 3.

стоящие из 250 страниц. Выборки осуществлялись из страниц, присутствующих в выдаче поисковой системы Google по запросам «error 404», «page not found», «ошибка 404» и т. д. Все тэги были разби ты на 3 группы:

1) title;

2) p, div, em, font, span, br, b, pre и i;

3) h1, h2, h3, h4, h5, h6 и body (для случаев, когда фраза не находилась ни в одном из тэгов, а находилась в body). Рис. Для классификации страниц использовали 10 Среди хороших страниц осталось приблизи ближайших соседей как число, доставляющее мак- тельно 2 – 3% страниц soft 404 (оценка получена симальную точность алгоритму. Точность и полно- методом бутсраппина [11]).

та алгоритма указаны на рис. 1. Словарь, полученный после работы по алгорит Использование этого алгоритма позволило зна- му (1), был расширен словами, встречающимися чительно уменьшить время на разметку страниц. более чем на 1% страниц выборки. Страницы вы Для поиска 2800 страниц soft 404 во всей коллек- борки были представлены в виде векторов TF слов, ции потребовало бы 280 чел.·часов, если предпо- встречающихся в расширенном словаре. В качест ложить, что: ве алгоритмов машинного обучения были выбраны • страницы soft 404 распределены равномер- алгоритмы решающих деревьев: Random Forest но, [12] и Id3 [13], а также алгоритм, основанный на 125  методе ближайших соседей. Для того чтобы ис- 3 Результаты пользовать алгоритмы, основанные на решающих Обучение алгоритмов производилось на выбор деревьях, необходимо было перевести непрерыв ке из 95913 страниц: 6286 страниц soft 404, ные величины TF в величины, принимающие ко хороших страниц. Начнем с рассмотрения алго нечное количество значений. Перевод производит ритма Random Forest. Количество деревьев Random ся по следующему правилу:

Tree, используемых для создания Random Forest, TF = 0 0, было 5 (из-за ограничения на оперативную память TF (0, t1 ] 1, 1,5 Гб). Тренировочное множество для каждого отдельного Random Tree строилось по методу...

«бэггинга» Брэймана [14]. Для тестирования TF (t n,1] n + 1. Random Forest использовалась вся выборка. Ниже представлены результаты работы Random Forest.

Неизвестными остались только точки t1, t 2, K, t n Если 50% деревьев голосуют за soft 404:

деления отрезка [0,1]. Для каждого документа вы порог i точность полнота борки составим множество, состоящее из величин 0.5 0.8957 0. TF для каждого признака. Затем объединим все 0.6 0.8976 0. множества в одно. Точки полученного множества 0.7 0.9007 0. отсортируем по возрастанию значений TF и про 0.8 0.9614 0. нумеруем. На графике (рис. 4), приведенном ниже, 0.9 0.9608 0. видно, как расположены эти точки.

Если 80% деревьев голосуют за soft 404:

порог точность полнота 0.5 0.9702 0. 0.6 0.9712 0. 0.7 0.9741 0. 0.8 0.9962 0. 0.9 0.9967 0. Рис. На графике видно, что на отрезке [0, 0.2] точки Рис. расположены равномерно, а на отрезке [0.2, 1] плотность точек такая же, как плотность экспонен циального распределения. Этот факт можно ис пользовать при выборе точек деления t1, t2,K, tn, например:

k [( 0) / T ] i, i = 1, K, T 1, ti =, i T k i = T, K, T + k 1,, k где 0.2, k, 1 5, T, T 2.

Параметры, k и T выбираются таким образом, чтобы обеспечить алгоритмам Random Forest и Id3 Рис. максимальную точность и минимальность полу- Кривая обучения Random Forest в зависимости чаемой модели. В данной работе при настройке от количества деревьев (количество деревьев ко алгоритмов было рассмотрены несколько наборов митета) представлена на рис. 5. Кривая обучения параметров, оптимальным оказался набор (=1.5, Random Forest из 5-ти деревьев в зависимости от k=4, T=36). высоты деревьев представлена на рис. 6.

126  слова из русского и английского языков, наиболее Рассмотрим алгоритм Id3. Выборку разделили часто встречающиеся на странице soft 404. Показа на два множества: тренировочное – 100·(1-)% от но, что применение алгоритма Random Forest по выборки, тестовое – оставшиеся 100·% от выбор ки, где (0,1). Как показали результаты тестиро- зволяет получить алгоритм классификации стра ниц soft 404 с высокими показателями полноты и вания, алгоритм подвержен переобучению, связано точности, что позволяет использовать данный ал это с высокой детализацией дерева. На рис. 7 изо горитм в поисковой системе на стадии скачивания бражена кривая обучения для тренировочного и страниц перед стадией индексирования и для рас тестового множеств. На рис. 8 представлена кривая познавания страниц soft 404.

обучения алгоритма k-NN в зависимости от k.

В дальнейшем планируется провести сравни тельный анализ предложенных алгоритмов и алго ритма, рассмотренного в работе [1]. В данной ра боте этого не удалось сделать, потому что коллек ция ROMIP BY.Web была составлена в 2007 году, с того времени состояние страниц изменилось. А для оценки производительности алгоритма [1] требует ся постановка эксперимента, позволяющего скачи вать страницы из интернета.

В данной работе обучение проводилось на век торах TF, в будущем планируется провести обуче Рис. 7 ние предложенных алгоритмов на векторах BM [15]. Также планируется уменьшить размер полу чаемой модели Random Forest (1,5 Гб оперативной памяти) за счет корректировки используемых при знаков.

Также возможно создание словарей слов, отно сящихся к soft 404, на языках, отличных от русско го и английского.

Литература [1] Bar-Yossef Z., Kumar R., Broder A.Z., Tomkins A.

Sic transit gloria telae: towards an understanding of Рис. the Web’s decay// Proc. of the 13th Int. WWW Результаты сравнения различных алгоритмов Conf., 2004.

машинного обучения представлены в таблице ни [2] Francisco-Revilla L., Shipman F., Furuta R., Ka же. Как видно, алгоритм Random Forest имеет вы radkar U., Arora A.. Managing change on the web// сокие показатели полноты и точности в отличие от JCDL’01: Proc. of the 1st ACM/IEEE-CS Joint других сравниваемых алгоритмов, у которых толь Conf. on Digital libraries, 2001. – P. 67-76.

ко один из показателей близок к показателям [3] Ntoulas A., Cho J., Olston C. What’s new on the Random Forest. Следовательно, Random Forest web? The evolution of the web from a search en можно использовать на практике как классифика gine perspective// Proc. of the 13th Int. World Wide тор страниц soft 404.

Web Conf., 2004.



Pages:     | 1 |   ...   | 18 | 19 || 21 | 22 |   ...   | 26 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.