WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

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

Эксперименты показали, что при использовании FRiS-функции можно достаточно точно предсказывать эффективность полученных подпространств при распознавании контрольной выборки. Более того, было продемонстрировано, как величина FRiS-функции, вычисленная для нового объекта z, может использоваться для оценки надежности распознавания этого объекта. Хотя зависимость между значением FRiS-функции и вероятность ошибочного распознавания для каждой задачи может быть своей, предложена эффективная методика оценки этой зависимости на основе обучающей выборки, подтвержденная моделированием на реальных прикладных задачах.

Объединение наработок по применению FRiS-функций к проблеме выбора признаков X и построения решающих правил D позволяет перейти к отысканию такого решения задачи DX (одновременного выбора системы признаков и построения решающего правила). Целью является отыскание такого набора эталонов S* и такого подпространства признаков Y*P(X), для которых среднее значение функции конкурентного сходства, вычисленное по формуле (1) было максимальным:

,

где FY(a,S)- величина функции конкурентного сходства объекта а с набором столпов S в подпространстве Y.

Алгоритм, отыскивающий приближенные решения этой экстремальной задачи, называется FRiS-Agent и состоит в следующем. С помощью алгоритма AdDel осуществляется направленный поиск системы информативных признаков Y, обеспечивающей максимальное значение среднему значению FRiS-функции, вычисленной с опорой на множество эталонных объектов SY. В свою очередь выбор SY в фиксированном подпространстве Y осуществляется алгоритмом FRiS-Stolp.

Сравнение результатов работы этого алгоритма с аналогами, используемыми для решения задачи DX, показало его преимущества.

В третьей главе описывается новый алгоритм FRiS-Tax, основанный на использовании функции конкурентного сходства, который позволяет решать задачу SD (одновременного построения таксономии и решающего правила для ее распознавания). Этот алгоритм хорошо воспроизводит действия человека-эксперта в процессе разбиения объектов на классы и позволяет автоматически выбирать «разумное» число классов.

При решении задачи таксономии все объекты выборки A изначально относятся к одному классу. Пусть этот класс описывается набором столпов S={s1, s2, …, sl}. Тогда для каждого объекта aA можно найти расстояние r1(а,S) (от объекта до ближайшего столпа из множества S). Но отсутствие образа-конкурента не позволяет определить расстояние r2 (от объекта до ближайшего столпа образа-конкурента). В связи с этим, на первом этапе вводится виртуальный образ-конкурент, ближайший столп которого удален от каждого объекта выборки на фиксированное расстояние, равное r2*. Тогда в задаче таксономии FRiS-функция объекта aA имеет вид приобретает вид:

Эту величину мы будем называть редуцированной FRiS-функцией. Наибольший интерес для нас будет представлять среднее значение редуцированной FRiS-функции при фиксированном наборе столпов S по выборке:

= (2)

При фиксированном числе столпов l эта величина достигает своего максимума, когда столпы из S располагаются в центрах зон локального сгущения объектов. Таким образом, решая экстремальную задачу:

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

Алгоритм FRiS-Cluster, отыскивающий приближенное решение этой задачи, на каждом шаге выбирает объект, добавление которого в список столпов максимально увеличивает значение критерия (2). Когда же заданное число столпов достигнуто, все объекты выборки распределяются между кластерами, определяемыми этими столпами, и окончательное положение столпа для каждого кластера уточняется.

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

Последовательное применение FRiS-Cluster и FRiS-Class образует алгоритм FRiS-Tax, разбивающий выборку на заданное число кластеров l. Число получаемых классов при этом может варьироваться, в зависимости от того, какое число кластеров было объединено на втором этапе. Чтобы отыскать оптимальное число кластеров из заданного диапазона (не больше L), необходимо последовательно построить кластеризации (этап FRiS-Cluster) для всех lL, и по формуле (1) вычислить качество каждой кластеризации. Именно то число кластеров l, при котором - является локальным максимумом (()&()) и оказывается наилучшим. На процедуру укрупнения таксонов (этап FRiS-Class) передают только варианты кластеризации, удовлетворяющие условию локальной максимальности. После второго этапа отсеиваются совпадающие варианты классификации, и такие, которые в результате объединения образуют единственный класс. Анализ оставшихся вариантов в различных модельных экспериментах показал, что все они в том или ином смысле признаются человеком-экспертом «разумными» и различаются степенью детализации.

Эффективность предложенного алгоритма была подтверждена на модельных примерах и реальной задаче. На Рис.2 сравниваются результаты его работы с существующими аналогами (алгоритмами Kmeans, Forel, Scat). Для оценки качества получаемых разбиений с числом таксонов k используется величина -средняя однородность получаемых таксонов относительно заранее известной «естественной» классификации.

Рис.2 Сравнение результатов работы пяти алгоритмов таксономии.

В четвертой главе исследуются и формализуются характерные особенности «естественных» классификаций. Их анализ позволяет интерпретировать процедуру автоматического построения таксономии, обладающей свойством «естественности», как задачу комбинированного типа SX (задачу построения таксономии в наиболее информативном подпространстве признаков). Предлагается методика формирования критериев оценки «естественности» классификации и описывается алгоритм NatClass для построения классификаций, обладающих свойствами «естественных».

Понятие «естественная классификация» часто возникает при попытке формализовать понятия качества классификации. Им обычно обозначают некий идеал, к которому следует стремиться при разработке методов таксономии. Знакомство с этими классификациями позволяет обнаружить ряд их интересных свойств:

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

Таким образом, в процессе построения «естественной» классификации, необходимо не только разбивать объекты на классы, но и выбирать подмножество существенных характеристик - решать задачу SX вместо задачи S. При этом для каждого подмножества характеристик, претендующих на звание существенных, оценивается функция качества зависит от двух составляющих – «геометрического» качества таксономии Qt в пространстве этих характеристик и качества ожидаемой предсказательной силы Qr полученных таксонов во всем признаковом пространстве. Если для оценки Qt существует множество разных методик, то вид критерия Qr требует дополнительных пояснений.

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

Если совокупность прогнозируемые значений признаков, не попавших в число существенных для каждого класса, рассматривать как столп этого класса, то в качестве оценки надежности прогнозов может использоваться среднее значение FRiS-функции, вычисленное по формуле (1), а задача построения «Естественной классификации» при этом запишется следующим образом:

.

Здесь FX\Y – значение функции конкурентного сходства в пространстве X\Y, n*- ограничение на количество существенных признаков, а SY может быть найдено следующим образом. В пространстве характеристик Y, претендующих на роль существенных, строится разбиение, удовлетворяющее геометрическому критерию Qt, одним из существующих алгоритмов таксономии. Центры масс полученных таксонов в пространстве всех признаков X используются в качестве прогнозируемых по имени таксона значений этих признаков и образуют множество столпов SY. А непосредственно выбор наилучшего подпространства Y* осуществляется одним из алгоритмов направленного перебора, например, AdDel.

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

В пятой главе рассматривается наиболее общая задача комбинированного типа – задача SDX. Ее можно рассматривать как задачу представления данных в виде, удобном для дальнейшего анализа и использования человеком, который в силу особенностей своего восприятия предпочитает иметь дело с небольшим числом групп объектов (задача S), описанным в небольшом информативном подпространстве признаков (задача X). Подобное сокращенное описание должно содержать систему простых правил (задача D), в соответствии с которыми каждый новый объект может быть отнесен к той или иной группе. Кроме того, сокращенное описание выборки должно удовлетворять требованию «естественности», то есть содержать систему простых правил, по которым для нового объекта значения признаков, не вошедших в число информативных, должны восстанавливаться по значениям его информативных признаков и по общим характеристикам группы, к которой относится этот объект.

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

,

.

Набор столпов SY при ограничении на его мощность m* для фиксированной подсистемы признаков Y отыскивается с помощью алгоритма таксономии FRiS-Tax, который в процессе работы строит набор столпов, обеспечивающий максимум среднего значения функции конкурентного сходства по выборке. Предсказательная сила набора признаков Y вычисляется как среднее значение конкурентного сходства в исходном пространстве X каждого объекта a исходной выборки А со столпом, ближайшим к нему в подпространстве Y.

Далее рассматривается более сложная задача - построение решения задачи SDX в виде иерархической классификации, описываемой деревом Т. Корневой вершине Т0 этого дерева соответствует все множество объектов обучающей выборки A, итоговым классам классификации - висячие вершины. Поддереву в виде вершины Тi и всех связанных с ней вершин следующего уровня,, …,соответствует разбиение группы объектов на подгруппы. На каждом таком разветвлении может использоваться свое собственное подпространство признаков Yi. Каждой промежуточной вершине (классу) ставится в соответствие свой эталонный образец (столп), который используется уже для распознавания новых объектов по дереву в соответствии со следующим итеративным правилом. Если промежуточный класс Тi в подпространстве Yi разбивается на подклассы,, …, с эталонами,, …, соответственно, то при распознавании нового объекта а, попавшего по цепочке в класс Ti, он относится к тому подклассу, расстояние до эталона которого оказывается минимальным.

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»