Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 47
Текст из файла (страница 47)
Для размытого подмножества 5 в Х и точки е р )с» положим л 1»(5, е; »р)= ~ «р(з!)1(Х! — е((», «=. ! где з, = 5 (Х!) Лля обычного подмножества 5 (когда з; =-О либо 1) выражение для 1» (5, е; <р) не зависит от выбора »р и называется разбросом этого подмножества относительно точки е. По аналогии общее выражение для 0 (5, е; »р) назовем «р-взвешенным разбросом размытого множества 5. Центрразмыпогомножестеа 5 определим, естественно, как решение задачи е(5; «р)=ага»п!и 1:»(5, е; <р). «ел Имеем л е(5; ф) = ~~~ ' Х».
~ е(»») ! Внутриклассовый разбросразмытого множества 3 определим как разброс этого множества относительно его центра, т. е. 0 (5; !р) = 0 (5, е (5, <р); ф). Теперь пусть 5 = (5„., 5») — некоторое разбиение на нечеткие классы. Положим » )(5)= .0(5,; !). ! =- ! В задаче классификации, отвечающей этому критерию, весовые функции !р„..., <Сд являются параметрами, которые можно фиксировать либо подбирать в ходе классификации.
Широкий класс критериев качества разбиения на нечеткие множества получается, если использовать подход метода динамических сгущений (см. и. 7.4). Выберем некоторую меру сходства 0 (Х, е). Тогда, как и выше, для монотонной функции <р (з), з 6 [О, 1[, <р (О) = О, ф (1) = 1 вводится разброс размытого .подмножества 5 относительно представителя 1 по формуле: 0(3, 1' !2) = ~~' Ф(з!) 0(Хо 1). ! 1 Пусть теперь 5=(5„..., 5д) — некоторое разбиение на нечеткие классы н 1= (1м ..., 1д) с 1.» с: (1.) — некоторое представительство (см. 7.4.1).
Положим Ф'(5, 1)= ~ч~~ Р(3„1;; !р!). ! ! Критерий качества разбиения, соответствующий [д! (5, 1) в МДС, имеет вид Я (5) = [Р" (5, й' (5)), где я (5) — функция представительства. В рассматриваемом случае, при 1.» = =- (1.)», д (5) = (1„..., 1»), где 1! — — агк ш!и Улр! (ф 0 (Хв, 1), з! = 5, (Х!). !е! 7.5.2. Алгоритмы нечеткой классификации.
Специфику этих алгоритмов покажем на алгоритме я-средних [!92,193). Пусть Х = (Х„..., Х„), где Х! Е )хе. Управляющие параметры: и — число классов; М вЂ” симметрическая положительно определенная матрица, задающая расстояние в гс» р (Х, У)=(Х вЂ” У) М(Х вЂ” У) 242 (далее для простоты будем предполагать, что М = 1о— единичная матрица); а — число, 1(а ( ео, определякицее весовую функцию <р (з) = зо (см. п. 7.5.1). Схема алгоритма 1. Выберем начальное разбиение 5<о> = (5)о>, ..., 51о>) на <<с нечетких классов, т.
е. массив з<о> из п й-мерных векторов з(с> з<о> з)о> (а<ос> з<оо>) з<оо> ~ (> ~з~ з(ос> 1 с с=< для всех с' = 1...„п. 2. Пусть построено т-е разбиение 5<"'> в видемассиваФ"о из и А-мерных векторов з<"'>, ..., з<"'>. Вычислим набор центров е<"'>, ..., е)'">, где л с= с ~ с,< с>)о /=.! 3. Построим (т + 1)-е разбиение 5<'"+'> в виде массива (з","+'>, ..., з<'"+'>), порождаемое центрами е<'">, ..., е<'">, где з<,'"+'>= агин>(п~ ~ (з<с>)о((Х< — е',"((о:з=(з<», ..., з<">), т.е.
если7',"=((~1<(< й:'>)Хс — з)о(>=(>), то /~ -й 8 з<<~ + >> с> <1 ( ~ 7ссс и т с <<о~.ь с> с> 1 сес) 4. Если 5,' + ' чь 5<< ' для некоторого с', 1 ~ с' ~ л, то переходим к 2; если 5<'"+"> = 5<'">, то полагаем 5<"'> = -= 5о и заканчиваем работу алгоритма. При фиксированных й и М описанный алгоритм й-средних представляет собой параметрическое семейство по сх, где 1 ( сх( оь.
Построение нечеткого разбиения, порождаемого набором центров (см. 3), определено при сх- 1 и а-+ со. Пусть сх-с-1. Положим 3",' = (Г, 1 ~1 ~А,: )) Хс— — е',")! = ппп (! Хс — е',",)(). Тогда З(Схс+ Сс!)— С другой стороны, непосредственно из определения нечет- кого класса з'с'+ с следует, что при а = 1 он имеет вид: Х цг(Х 1Х,— ЧГ,,в»О, ХХ~=С). 1с=- с с=с Решением этой задачи линейного программирования является любой й-мерньссс вектор, лежащий на грани симплекса (зс )с": зссс > О,;~ Фсс = 1), выделяемого условиями с=с Фс> = О, если 1~!,'". В частности, любая из вершин этого симплекса, у которои все координаты, кроме одной с номером из множества 7,'", равны О.
Таким образом получается, что минимальное дистанционное разбиение, порождаемое набором центров е',", ..., е"' — это одна из допустимых классификации в алгоритме Беждека при а = 1. 1 ПуСтЬ СХ-~ осс. ТОГда ЗСС'"+ссС1 = —, т. Е. КЛаССИфИКацИя с х' вырождается. Таким образом, в алгоритме Беждека брать слишком большие значения параметра сх не имеет смысла, Точно так же, как расписан алгоритм нечеткой классификации по методу сс-средних, можно расписать соответствующие алгоритмы по всем методам, основанным на описании классов «ядрами», рассмотренным в й 7.2 и 7.4.
Например, полностью сохраняется общая схема алгоритмов классификации по методу динамических сгущений (см. 7,4.2). В случае нечеткой классификации необходимо только использовать следующий способ построения функции назначения 1 при выбранных ядрах классов (1„..., 1ь) и мерах сходства Р (Х, 1с): с объектом Хс сопоставляется А-мерный вектор зт = (з>>, ..., з,'ь) принадлежности к классам, такой, что з7=-агагпш ~ чь >р>(з') й(Х>, 1,):з= !>=> =(зы>, ..., з>а>), з<о- 0 ~~ з«> — 1 >=1 Например, в качестве весовых функций хр (з) можно, как и выше, взять функции ьо, 1 - а ~ оо.
Тогда такие алгоритмы нечеткой классификации по МЛС при а-ч- 1 перейдут в алгоритмы, вариантами которых являются алгоритмы, описанные в $ 7.4. Детальное описание алгоритмов нечеткой классификации и исследование их можно найти в П931. Алгоритмы, основанные на методе просеивания (решета) 7.В, Общим для всего этого семейства алгоритмов является наличие следующих трех блоков [351: 1) парное сравнение объектов Оп ..., О„и составление для каждого объекта О, кортежа (О;, ..., О;„>) «похожих» на него объектов; 2) упорядочение (оцифровка) выборки в соответствии с целью классификации; 3) классификация, моделирующая принцип решета Эратосфена ': на вход классификатора поступает выборка, упорядоченная в блоке 2. Первый объект объявляется типичным представителем первого таксоиа, в который включается кортеж похо>ьил на него объектов, составленный в блоке 1, после чего этот кортеж удаляется (вычеркивается) из выборки 1 ипичным представите,дем следующего таксоиа объявляется первый из оставшихся объектов упорядоченной выборки, а кортеж похожих на него объектов включается во второй таксон, те же из них, ко~орые не были удалены на предыдущем шаге, удаляются из выборки.
Такая процедура классификации продолжается до тех пор, пока > Одна из формулировок решета Эратосфена (!!! в. до н. в.): если в множестве натуральных чисел 2. 3, 4,. зачеркнуть числа, кратные первым т простым числам 2, 3. 5 ... рт, то первое !наименьшее) иеаачеркнутое число будет прос)ым вся выборка или наперед заданная доля ее не будет расклассифицирована. Классификация, проведенная алгоритмами семейства, в общем случае приводит к покрытию классами, а не разбиению, так как таксоны могут пересекаться. Это связано с тем, что хотя элементы выборки на этапе 3 последовательно исключаются из рассмотрения, тем не менее они оказывают существенное влияние на последующую классификацию, поскольку на этапе 2 они участвовали в упорядочении выборки и порядок этот после их исключения ие пересматривается.
Переход внутри семейства от одного алгоритма к другому осуществляется настройкой управляющих параметров. В блоке 1 такие параметры определяются видом входной информации. Так, если выборка характеризуется матрицей «объект — свойство», то оценка похожести происходит с помощью той или иной меры близости, которая тем самым становится параметром алгоритма. Если же входная информация представлена в виде матрицы попарных взаимных расстояний,то кортеж похожих объектов рассчитывается с использованием пороговых значений, которые либо задаются, либо оцениваются на основе анализа матрицы взаимосвязей.
В блоке 2 упорядочение элементов выборки, как правило, проводится при помощи функционала, который сопоставляет с каждым объектом О, выборки число, характеризующее, насколько этот объект типичен для совокупности похожих нанего (О,,, ...,О, )сточки зрения целей классификации. Для выбранного функционала г" (0,) =-- г (О;; О,,„ ..., О, ) полагаем О, «-' 0»ч если г" (0,) ) г (Ог); в случае г (0,) =- Г(0~), если нет дополнительной информации, то полагаем О, = 0; при ( ( /. Блок 3 не содержит управляющих параметров, поэтому далее при описании конкретных алгоритмов классификации методом Эратосфена (АКМЭ) опускаем его.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
