Методология интеграции гетерогенных информационных систем по свойствам неорганических веществ (1090084), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

. . < ρ(u, xℓ,u),где xi,u - i-й сосед объекта u. Аналогичное обозначение вводится и для ответа наi-м соседе: yi,u = y(xi,u). Таким образом, каждый объект u из X порождает своюперенумерацию выборки Xℓ = {x1,u, . . . , xℓ,u}.23Простейшим случаем данного метода является, т.н. алгоритм ближайшегососеда(nearestneighbor,NN),обозначималгоритмчерезa.Онотноситклассифицируемый объект u к тому классу, которому принадлежит ближайший объектиз обучающей выборки:a(u;Xℓ) = y1,u.Таким образом, распознавание сводится к ранжированию объектов обучающейвыборки по степени близости к распознаваемому объекту в соответствии с метрикой ρ.Качество классификации, соответственно, определяется тем, насколько удачно выбранаэта метрика.Алгоритм k-ближайших соседей (k-nearest neighbors, kNN) рассматриваетнекоторую ближайшую окрестность Vk в признаковом пространстве, содержащую kсоседних прецедентов.Каждый из соседей xi,u, i = 1, .

. . , k голосует за отнесение объекта u к классу yi,u.В результате объект u относится к тому классу, которому принадлежит большинство изk ближайших к нему объектов обучающей выборки:ka(u; X , k )  arg max  [ y  y ]li, uyY i 1Алгоритм имеет параметр k, который при решении задач конструированиянеорганических соединений подбирается по критерию скользящего контроля, т.е.выбирается то значение k, при котором число ошибок классификации минимально:kQ(k ; X )   [a( x ; X l \{x }, k )  yi ]  minliiki 1В случае разной представительности классов могут применяться модификацииметода, использующие различные весовые коэффициенты для разных классов.Достоинствами методов типа kNN являются простота реализации и возможностьвведения различных модификаций; возможность интерпретации классификациинеизвестных объектов путем предъявления ближайшего прецедента или несколькихближайших прецедентов.К основным недостаткам метода стоит отнести снижение его эффективностипри малых объемах обучающей выборки и высокой размерности признаковогопространства.

С точки зрения создания классифицирующих правил метод так жеявляется слабым, так как он вообще не создает каких-либо моделей или правил, а привыборе решения основывается на всем массиве доступных данных обучающей24выборки. В связи с этим возникает проблема выбора прецедентов, из которыхнеобходимо формировать обучающую выборку для “хорошей” классификации илипрогноза.Алгоритмыраспознавания,основанныенапринципечастичнойпрецедентности.Принцип классификации, применяемый в этих алгоритмах, основан наотнесении распознаваемого объекта u к тому классу, в котором имеется большее число«информативных» фрагментов эталонных объектов («частичных прецедентов»),приблизительно равных соответствующим фрагментам объекта u. Вычисляютсяблизости – «голоса» (равные 1 или 0) распознаваемого объекта к эталонам некоторогокласса по различным информативным фрагментам объектов класса.

Данные близости(«голоса») суммируются и нормируются на число эталонов класса. В результатевычисляется нормированное число голосов, или оценка объекта u за класс Kj = Гj(u) –эвристическая степень близости объекта u к классу Kj.После вычисления оценок объекта за каждый из классов, осуществляетсяотнесение объекта к одному из классов с помощью некоторого порогового решающегоправила [193]. Решающее правило – это правило (алгоритм, оператор), относящеераспознаваемых объект по вектору оценок ( Г 1 (u ), Г 2 (u ),..., Г k (u )) в один изклассов Kj, или вырабатывающее для объекта «отказ от распознавания». Отказ являетсяболее предпочтительным вариантом решения в случаях, когда оценки объекта малы завсе классы (объект является принципиально новым, аналоги которого отсутствуют вобучающей выборке), или он имеет две или более близкие максимальные оценки заразличные классы (объект лежит на границе классов).Алгоритмы вычисления оценок (АВО)Идеи распознавания по частичным прецедентам обобщены в моделяхраспознавания, основанных на вычислении оценок.

Для этих алгоритмов объектысуществуют одновременно в самых разных подпространствах пространства признаков.Поскольку не всегда известно, какие сочетания признаков наиболее информативны, тов АВО степень сходства объектов вычисляется при сопоставлении всех возможных илиопределенных сочетаний признаков, входящих в описания объектов [195].Используемые сочетания признаков называются опорными множествами илимножествами частичных описаний объектов. Вводится понятие обобщенной близостимежду распознаваемым объектом и объектами обучающей выборки, называемымиэталонными объектами.Эта близостьпредставляется комбинациейблизостейраспознаваемого объекта с эталонными объектами, вычисленных на множествах25частичных описаний.

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

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

Результат работы данных методов оформляется в виде такназываемого дерева решений или правил типа «ЕСЛИ ... ТО ...».В целом популярность логических методов обнаружения закономерностейопределяется наглядностью результатов их работы. Проблемами являются сложностьперебора вариантов за приемлемое время и поиск оптимальной композициивыявленных правил.Алгоритмы голосования по логическим закономерностямМатематическойзакономерностямосновойявляетсяалгоритмовкомбинацияголосованиялогических,пологическимоптимизационныхистатистических методов [199, 200].Логический анализ состоит в поиске сходства специальных фрагментовобъектов обучения, описанных в терминах признаков.

Такое соседство фрагментовсчитается «типичным» для некоторых классов и «нетипичным» для других.Подход оптимизации состоит во введении различных числовых критериев дляоценки соседства фрагментов и решения математических и программных проблем для26поиска оптимального соседства признаков. Оптимальные решения интерпретируютсякак логическая закономерность.Статистическиеоптимизацииидеииспользуютсявведениемразличныхирешающихправил(функционалов)созданиемвкритериевалгоритмахраспознавания образов.Предикат Lj(x) называется логической закономерностью класса Kj привыполнении следующих условий:Lj(xi) = 1 хотя бы для одного xi из класса Kj (1),Lj(xi) = 0 для всех объектов обучающей выборки, не принадлежащих классу Kj,т.е.

для xi  Kj (2),f(Lj) = max, где f - некоторый оптимизационный критерий (3).Критерием качества является функционал:f(Lj) = <количество объектов обучающей выборки xi из Kj : Lj(xi) = 1> / | Kj |Предикат Lj(x) называется частичной логической закономерностью класса Kj,если выполнены условия 1 и 3, а условие 2 заменено на более слабое: ({xiKj| L(xi) = 1})/ |{L(xi) = 1}| < δ,Геометрической интерпретацией (рис. 1.2.1) логической закономерности Lj(xi)является гиперпараллелепипед, содержащий максимальное число объектов обучения изкласса Kj, но не содержащий объектов других классов.Рис.

1.2.1. Геометрическая интерпретация логической закономерности.Отметим, что АВО и алгоритм голосования по логическим закономерностямможно также выделить в одну группу моделей голосования.1.2.2.4. Методы, основанные на принципе разделенияРешающее правило в этих алгоритмах основывается на построении поверхностивn-мерномпространствепризнаков(гиперповерхностиилинаборагиперповерхностей), которая в некотором смысле наилучшим образом будет разделятьнаборы классов в этом признаковом пространстве. Особо стоит отметить, что такиеметоды не всегда находят применение в задачах распознавания образов, поскольку27построение разделяющих поверхностей с увеличением количества признаков становится ввычислительном плане громоздким.Линейный дискриминант ФишераЛинейный дискриминант Фишера (FLD) был первоначально разработан [34] длярешения проблемы классификации для случая двух классов.

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

Известны способыраспространения метода FLD на число классов более двух.Линейная машинаЭтот метод принадлежит к классу методов построения линейных разделяющихгиперплоскостей. Задача при построении такой поверхности состоит в вычислениинекоторой линейной относительно признаков функции f(x) = a1x1 + a2x2 + … + anxn +an+1. Рассмотрим случай с двумя классами. При классификации используетсяследующее решающее правило: если f(u)>0, то объект u относится к первому классу,если f(u)<0, то ко второму, а если f(u)=0, то - отказ от классификации объекта.Основной задачей является поиск такой функции f(x), для которой числоневыполненных неравенств в системе:Af(ui)>0, i=1..m1Af(ui)<0, i=m1..mявляется минимальным (m – количество объектов).

Характеристики

Список файлов диссертации