Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 54
Текст из файла (страница 54)
Менгером [83, с, 102 — 106). Т е о р е м а 9.1. а) Минимальное число связей, удаление которых разъединяет две какие-либо вершины графа, равно максимальному числу не содержащих общих связей путей между этими двумя вершинами; б) минимальное число вершин, удаление которых разъединяет какие-либо две несмежные (не связанные непосредственно) вершины графа, равно максимальному числу непересекающихся (за исключением концов) путей между этими двумя вершинами. С л еде т в и е 9.1. Каждая пара п„п, различных вершин й-компоненты 6' графа 6 соединена й путями подграфа 6', не содержащими общих связей, причем подграф 6'— максимальный подграф с этим свойством. С л е д с т в и е 9.2.
Каждая пара по о~различных вершин й-блока 6' графа 6=(К Е) смдинена Й путями подграфа 6, не содержащими общих точек (за исключением концов), причем 6' — максимальный подграф с этим свойством, если (У) ) й + 1. Опишем, например, как на основе следствия 9.1 построить процедуру Ар выделения й-компонент графа 6'. Схизма алгоритма 1. Применяя процедуру выделения Ьсвязок из п.
9.3.3, разобьем граф 6' на Й-связки 6'„..., 6'„. ! 2. Пусть 6„' — некоторая й-связка. Выделим все одноточечные й-компоненты. Согласно следствию 9.1 вершина и, графа 6, является одноточечной компонентой тогда и только тогда, когда существует хотя бы одна другая вершина п, этого графа, такая, что и, и п~ соединяет меньше, чем й путей, не содержащих общих связей, 3. Пусть 6я — подграф й-связки 6~~, у которой удалены все одноточечные компоненты.
Так как любые две й-компоненты одного графа не пересекаются, то 6т представляет собой граф, связные компоненты которого являются Й-компонентамн графа 6 . (Фактически здесь описана конструкция оператора удаления У (см. п. 9.3.3) для получения й-компонент,) Применяя теперь алгоритм выделения компонент графа 6'„ получаем, наконец, набор й-компонент графа 6т. Применяя шаги 2 и 3 последовательно к й-связкам бт, д = 1, ..., гп,, получаем набор всех й-компонент графа 6'. ВЫВОДЫ 1.
Алгоритмы разделения смесей легко модифицируются для работы при наличии неполных обучающих выборок. Такой тип задания априорной информации весьма эффективен — известны примеры, когда использование ОВ объема 1О % исходной совокупности резко улучшало результаты классификации. 2. Описаны методы и алгоритмы классификации в ситуации, когда исследователь желает получить разбиение объектов на классы, согласованное с ограничениями на связи между объектами.
3. Описаны методы и алгоритмы классификации, основанные на представлении исходной информации о классифицируемых объектах в виде последовательности подграфов 281 6' с= ... «=- 6"' графа близости 6, где 6' — граф близости на уровне 1-го порога. 4. Каждый метод классификации опирается на модель класса в виде максимального подграфа (Р-компоненты) одного из графов близости 6', 1= О, ..., т, где г" — свойство класса.
В качестве моделей классов рассматриваются й-связки, й-компоненты, й-блоки и й-клики. б. Описана общая схема алгоритмов, задающих последовательность покрытий 5«с ... с 5"' совокупности обьектов О„..., О„, где 5' — покрытие, образованное всеми г-компонентами графа 6'. Рассмотрены важнейшие примеры алгоритмов и взаимосвязи между получаемыми с их помощью классификациями. Глава 10. ТЕОРИЯ АВТОМАТИЧЕСКОИ КЛАССИФИКАЦИИ Математическая модель алгоритма автоматической классификации (ААК) 10.1. Как и выше, предполагаем, что исходная информация об исследуемой совокупности (выборке) объектов О = (О„..., О„) представлена либо в форме матрицы «объект — свойство» Х вЂ” -= (х)'~), 1 < ! < и, 1 < у < р, либо матрицы взаимных близостей р = (р;,), 1 ( С ! < и.
В случае числовых признаков отождествляем объект О, с точкой Х, = = (х,">, ..., х)ю) евклидова пространства !«». Начнем с развернутой характеристики компонент математической модели алгоритма автоматической классификации (АК) (!О, 4!). 1О.1.1. Пространство состояний 5о. Эта компонента описывает допустимые классификации, возникающие на шагах алгоритма. Так, если результатом т-го шага является разбиение 5 = (5„..., 5») совокупности О на й непересекающихся классов, то 5о — это пространство всех разбиений множества из и элементов иа фиксированное или нефиксированное число классов в зависимости от того, не зависит или зависит й от номера шага.
В алгоритмах метода динамических сгущений роль 5о играет пространство покрытий (см. з 7.4). В рассматриваемой модели каждый элемент 5 Е 5о отождествляется с некоторым отображением выборки О в множество «, — множество значений классификаций. Состав и структура «. определяют тип решаемой задачи, т. е., по существу, дают средство ответить на вопрос. какую задачу классификации предполагается решить? Например, когда Л = (1, ..., А) — список номеров классов, то Зо = (з: О-~- Л) совпадает с множеством разбиений выборки О на й непересекающихся классов О и р е д е л е н и е !0.1.
Будем считать, что классификация гн Π— э. 2 выборки О согласована с информацией, выражаемой функцией ~р: О-~-2з (обозначение з с <р), если з (О,) с ~р (О,) для любого ~'. В этом случае пространство допустимых классификаций будет иметь впд: 5о = (з: Π— ~ 2:з~ р). Таким образом, чтобы задать пространство состояний 5о, необходимо формализовать задачу, т. е. указать Л и сформулировать условия, выделяющие 5о в множестве всех отображений из О в Л. 10.1.2. Пространство описаний Е. Эта компонента связана с выбором средств информативного описания классов для достижения цели классификации. Например, в алгоритмах метода динамических сгущений роль й играет пространство представительств (см. и, 7.4.1).
В рассматриваемой модели каждый элемент 1 с Е отождествляется с некоторым отображением Л в Уо, где Уо— множество значений, в терминах которых выражается результат классификации. Пример 10.1. Пусть О= (Х,, ...,Х„) с: Ко и Л = (1, ..., Ц. Тогда, если описывать каждый класс 3 с: О 1 егосредним — У, Х с РР, то Уо = Ргг и 1 5 ~ хез а =- (2 У ) = И' х ... х Я = Ю'. П р и м е р 10.2. Пусть имеется набор опорных точек У(, ..., У~6, У' Е Яо, причем известно, что ядро д-го класса У, У с )гг, должно находиться в окрестности радиуса гч точки У', причем случай гч=0 для некоторых д не исключается, то 7.=((У 1') У ййо (У вЂ” У (~г, д — 1, ..., й).
Роль опорных точек (У') могут играть как реальные представители классов, так й точки, построенные на основе дополнительных сведений — формальные представители классов. П р и м е р 10.3. Пусть предполагается описывать класс 5 с: О набором из гп его представителей. Тогда Уо— совокупность всех гп — элементных подмножеств в О. 283 Пространство Уо может иметь совершенно иную природу, чем пространство измеряемых признаков.
Так, если в качестве ядра класса брать проходящее через центр класса линейное пространство главных факторов этого класса, то 1'о является многообразием линейных подпространств в в Р». Более того, само Уо может быть составлено нз пространств различной природы соответственно предположениям о природе различных классов (см. данное ниже описание модели алгоритма Форель). Таким образом, чтобы задать пространство описаний Ь, необходимо выбрать, в каких терминах выражать результат классификация, т.
е. указать пространство информативного описания классов н сформулировать условия, выделяющие Е в множестве всех отображений из 2 в )'о. 10.1.3. Множество порцпй Р, в которых выборка поступает на класснфнкацню н генератор порций 6. Зта компонента вводится для того, чтобы в рамках модели можно было рассматривать алгоритмы как параллельного (Р = (О,) состоит нз одного элемента, символизирующего всю выборку), так н последовательного типа (напрнмер, если на классификацию поступает по одному объекту, то Р = О).
Генератор порций 6 описывает способ получения нз выборки О порций объектов для проведения очередного шага алгоритма. В общем случае 6 представляет собой оператор, значение которого на (и+ 1)-м шаге зависит от результата классификации з н ее описания 1, полученных на предыдущем шаге. Например, в алгоритмах, использующих пороговые значения (прн классификации выборок большого объема), генератор 6 из всей выборки отбирает только те элементы, которые отстоят от ядер классов, полученных на т-м шаге, не более чем на пороговое значение с +,.
10.1.4. Классификатор К. Эта компонента представляет собой оператор нз 5о ХЕ х Р в Зо, называемый классификатором, поскольку он определяет, что нужно сделать с имеющнмнся средствами Уо для данного типа 2 задачи АК, чтобы нз предыдущего состояния з выборки О с описанием 1 перейти в другое состояние 1 „при поступлении очередной порции Р +, с: О, т. е. провести перекласснфнкацню. Частным случаем оператора К является функция назначения и: 1, -ь Зо (см. 5 7.4).
Обычно оператор К строят исходя нз функционала Р, оценивающего качество классификация согласно априорному представлению исследователя о «хорошей» классификации. П р н м е р 10.4. Опишем, как строится оператор К в исторически одном из первых н наиболее общем алгоритме разбиения на й классов методом локальной оптимизации.
Пусть з: О-ь. 2' = (1, ..., й) — некоторая классификация и Х с О. Обозначим через з (4, Х) новую классификацию: з(э, Х) (Х')=з(Х'), если ХФХ' и з(4, Х) (Х)=п. Фиксируем критерий качества классификации Р: Яо-+ Я' и определим оператор К: Зо х Р-д- Зодля алгоритмов последовательного типа, т. е. когда Р = О, формулой К(з, Х)=з, если Р(з) пипР(з(4, Х)); (10.1) К(з, Х) =з(п, Х), где д=~з(Х) и 4= агнш!п Р(з(д', Х)).
Формула !0.1 для классификатора К не налагает практически никаких ограничений на вид функционала Р, но в общем случае приводит к довольно медленной процедуре классификации, реализующей минимизацию функционала Р способом перебора на дискретном множестве Зо. П р и м е р 10.5. Предположим, что Р (з) имеет вид 2, Р» (О (о)), где О (и) = з-' (д) и Е» ( ) — критерий одно» ! родности и-го класса, представляющий собой функцию на множестве всех подмножеств из О, такую, что Рд (5,) < ( Рд (Зд), кактолькоЗ, ~ Я,.Тогда классификатор Кможно задать следующим образом. Пусть Л(д, Х)=Р»(О(ч)()Х) — Г»((О(!)()Х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
