Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 32
Текст из файла (страница 32)
При этом интерпретация функционала 1, может быть различной. Под 1. понимается иногда и некоторая мера взаимной удаленности (близости) классов, и мера тех потерь, которые приходится нести исследователю при излишней детализации рассматриваемого массива исходных наблюдений, и величина, обратная так называемой «мере концентрации» всей структуры точек, полученной при разбиении исследуемого множества наблюдений на й классов. В (218), например, предлагается брать 1,(5)= ~ ~ 1(Хь Х(1)) 1 ! Х~ез~ 1в (5) = сй (5), где й (5) — число клаесов, получающихся при разбиении 5, а с — некоторая положительная постоянная, характеризующая потери исследователя при увеличении числа классов на единицу.
159 Другой вариант функционалов качества такого типа можно найти, например, в (57), где полагают 1.(5) ! ч~ч ( 2 ) ~ К(Х Х), (! 1 и! (п! — 1) 1 г= ! х!езо х/ез! 2 12 (5) = У чь г (5ь 52) ° й(а — !) $= ! ! )! Здесь К (Х, У') — упомянутая выше потенциальная функция, а г(5„5,) — мера близости !кго и 1-го классов, основанная на потенциальной функции (5.6).
Очевидно, в первом случае будем искать разбиение 5е, минимизирующее значение функционала ()(5) -1 (5)+1з(5) (5.15) в то время как во втором случае требуется найти разбиение 5в, которое максимизировало бы значение функционала Я' (5) =1!(5) +1!(5). (5.! 6) Весьма !ибким и достаточно общим подходом, реализующим идею одновременного учета двух функционалов, является подход, основанный на схеме, предложенной А.Н. Колмогоровым. Эта схема опирается на понятия меры кон!(ентрации Л, (5) точек, соответствующей разбиению 5, и средней меры внутриклассового рассаиия 1! '(5), характери<к> зующей то же разбиение 5.
Под мерой концентрации Л„(5) предлагается понимать степенное среднее (см. 2 5.3) вида (5.17) где т (Х,) — число элементов в кластере, содержащем точку Х„а выбор числового параметра т находится в распоряжении исследователя и зависит от конкретных целей разбиения. При выборе т полезно иметь в виду следующие частные случаи Л, (5): г,(5)= 1, к где й — число различных кластеров в разбиении 5; ал; л, !ойкал(5) = Х вЂ” 1ой — — естественная информационная ,.=! л л мера концентрации; 2 (5) = !пах ~ — "' ); п х Я!(5) = — '~ ~ — ~= — '~ и,.
(Хй 1 л (, л 1 ла с=! ю=! Заметим, что при любом т предложенная мера концентрации имеет минимальное значение, равное 1/и, при разбиении исследуемого множества на п одноточечных кластеров, и максимальное значение, равное 1, при объединении всех исходных наблюдений в один общий кластер. При конструировании и сравнении различных кластер- процедур полезно иметь в виду, что объединение двух кластеров 5, и 5 в один дает прирост меры концентрации Я! (5), равный АХ!= — [(и!+л )а — л!а — а'1= — ' л' ла Определение средней меры енугприклассоеого рассеяния 1! ! (5) также опирается на понятие степенного среднего. В частности, полагают (8.18) где под ! еГ'!аа-( — ', ~ д а !х„х!1' [ "! к,ез! х,ез, понимается обобщенная средняя мера рассеяния, характеризующая класс 5п Числовой параметр т здесь, как и прежде„выбирается по усмотрению исследователя.
Полагая ! аГ'!х!= ( — „х а а!х, х!~ '. х!ез (к) 6 Заказ Ма 29! где, как и прежде, 5 (Х) — кластер, в который входит наб- людение Х, а т (Х) — число элементов в кластере 5 (Х), формулу (5.18) можно переписать в виде К'»(5) =М,(Ф'(Х,>, ..., Фк>(Х.)) =- 1 — — ~ >Хи Х~~ ' ( '1 х,ев(х,) (5.19) Очевидно, если ориентироваться на сокращение числа кластеров при наименьших потерях в отношении внутриклассового рассеивания, не обращая внимания на меру концентрации, то естественно объединять два кластера, для которых минимальна величина Л (и [1>">)').
Если же одновременноориентироваться и иа рост взвешенной концентрации Я> (5), то объединение кластеров следует подчинить требованию минимизации величины а '(в(!~~к>)') ьл, (51 (я(»>к>д х )1т (>7>к>(х>11т 1о<к 1з 11т)т в>+ч„, 5.4.3. формулировка экстремальных задач разбиения исходного множества объектов на классы при неизвестном числе классов. Возможно множество вариантов таких формулировок. Рассмотрим два из них, относящиеся к наиболее естественным и часто используемым.
В а р и а н т 1: комбинирование функционалов качества. Требуется найти такое разбиение 5*, для которого некоторая алгебраическая комбинация функционала, характеризующего среднее внутриклассовое рассеяние (5.19), и функционала, характеризующего меру концентрации полученной структуры (5.17), достигала бы своего экстремума. В качестве примеров можно привести комбинации Я (5) и Я' (5), При конструировании и сравнении различных кластер- процедур полезно иметь в виду, что объединение двух кластеров 5, и 5 в один дает прирост величины а (1~~~> (5)1', непосредственно характеризующей срединно меру внутриклассового рассеяния, равный Л(а ((~~Р~)~~ > (2 ~р>к>(5ь 5 )~'— в> Е℠— [()Г'(5,)à — )ЕГ'(5.)Г)- задаваемые формулами (5.16) и (5.16), а также более общие выражения вида а 7,(5)+]У»(3) и [1,(5)]«[1»(5)]в, (6.20) где l,(5) =- У, ' (5); »»(5) =- †; а и ]1 — некоторые положительные константы, например и =- р =.= 1.
В а р и а н т 2: двойственная формулировка. Требуется найти разбиение 5", которое, обладая концентрацией 2,(5*), не меньшей заданного порогового значения Е„ давало бы наименьнгее внутриклассовое рассеяние /~к'(5*), или, в двойственной подстановке: при заданном пороговом значении 1, найти разбиение 5" с внутриклассовым рассеянием т'~~'(5") ( /» и наибольшей концентрацией Е, (5'), 6.4.4. Общий вид функционала качества разбиения как функции ряда параметров, характеризующих межклассовую и внутриклассовую структуру наблюдений. Зададимся вопросом. нельзя ли выделить такой достаточно полный набор величин и, (5), и» (5), ..., характеризующих как межклассовую, так и внутриклассовую структуру наблюдений при каждом фиксированном разбиении на классы 5, чтобы существовала некоторая функция Я (и,, и„...) от этих величин, которую мы могли бы считать в каком-то смысле универсальной характеристикой качества разбиения.
В частности, вкачестветаких величин и, =- и, (5), и» = и«(5),... можно рассмотреть, например, некоторые числовые характеристики: степени близости элементов внутри классов (и,); степени удаленности классов друг от друга (и»); степени «одинаковости» распределения многомерных наблюдений внутри классов (и»); степени равномерности распределения общего числа классифицируемых наблюдений п по классам (и«).
Что касается установления общего вида функции Я (и„ и„и», и«), то без введения дополнительной априорной информации о наблюдениях Х, (характере и общем виде их закона распределения внутри классов и т п ) единственным возможным подходом в решении этой задачи, как нам представляется, является экспертно-экспериментальное исследование Именно с этих позиций в [63] сделана попытка определения общего вида функции Я. Чтобы определить рассмотренные в этой работе величины и„и„и» и им введем понятие кратчайшего незамкнутого пути (КНП), соединяющего все п точек исходной совокупности в связный неориентированный граф с минимальной суммарной длиной ре- 163 бер '.
Под длиной ребра понимается расстояние между соответствующими точками совокупности в смысле выбранной метрики. Построение такого графа можно начать с пары наиболее близких точек. Если таких пар несколько, то выбирается любая из этих пар. Пусть это будут наблюдения с номерами >, и у,.
Затем с помощью сравнения расстояний гу(Х>„Х>) (у = 1, 2, ..., и; у чьуз, у Фуо) и гу(Х>„Х«), где гу = 1, 2, ..., и; гу чяь ге и гу ~ г, определяются точки >л Х „,> н Х,„1„>, наименее уда- ленные соответственно от то- з Ш чек Х,, и Х;„и выбирается ближайшая йз них Х„„т. е. Хм, = Хюг,,>, если >У(Х>„ Х 1;,>) ( гу(Х»м Х 1;,>), и > Х, = Х 1„>, если гУ (Х;ю 'х Х 1,.>) < >У (Х>м Х 1,,>)'.
За- .1 > тем точка Х, «пристраивает- и ся» к той из точек Х, и Х>„ гь > к которой она ближе. Дадзг лее сравниваются расстояния «У(Хгм Х;), «У(Хьн Х«) и Рас. 5.2. Графическое изо >У (ХР. Хя) (у, гу м Фу»! у >у бражение кратчайшего ие- ч чауа и у, гу, ч чь и> ) и т. д, замкнуто'о пути Очевидно, «разрубая» з ребер такого графа, будем делить совокупность на з + 1 классов. Пусть р, (1) — 1-е ребро части графа, отнесенной к 1-му классу. Всего таких ребер, как легко видеть, будет и> — 1. И пусть р>>,'„(р) — минимальное из ребер, непосредственно примыкающих к ребру р и относящихся к 1-му классу, если таковое имеется.
Пронумеруем в определенном порядке граничные, («разрубленные») ребра )ч, Х, ..., Хь, таким образом, чтобы имелось взаимно однозначное соответствие между номерами граничных ребер н номерами примыкающих к ним классов, за исключением одного, геометрически представленного одним из «хвостов» графа. Выбрасывая ребра 1, П, П1 (рнс. 5.2), получаем четыре связных графа, что ' Методы классификанин, основалные на К!!П, используются для решения задач в области антропологии. биологии, сельского хозяйства, лингвистики усм . например: Саекапочзйд Л. Лог Р!ПегепНа>б!айпозе бег Меапбег1а!агирре О Ког — Ь>а11 Рен>з«Ь. Сез.
Ап1- гор. — !909.— Х$. — 5. 44 — 47; Е>оге!г К., ! ниазкеч !с«Л., Рег>га! Н., 7нЬ«исы 8. 8нг !а !!а>зоп е1 !а б!ч!з!оп без ро!п>з 6'нп епзегпые Пп>1> Сои. Ма>Ь. — !95!. — 2. — Р. 282 — 288), » Если и (Х,, Х » ) =- и 1Х> Хю >), го в качестве Х можно выбрать любую из точек Х,„г, > и Х,„1 >. 164 соответствует разбиению совокупности на четыре группы. Обозначим с помощью Х! одно из таких ребер 1-го класса. Теперь, следуя [ бЗ!, определим величины и, таким образом: и и, = — ч р(1), а сы 1=! где р (1) = (~ р, (1))/(и, — [) — средняя длина ребер 1-го с=! класса; ) и — ! и,= — ~ )!!; ь — ) >ю 1= ! Эмпирический перебор различных вариантов общего вида функции в сочетании с анализом результатов экспертных оценок качества всевозможных разбиений привели авторов [63) к следующей формуле для функционала: [и!(5)[" [и,(5)[ [()-,-[и! (Х))')()+[и,,(З)[') где а, [), с и 
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
