Дюран Б._ Оделл П. - Кластерный анализ (1977) (Дюран Б._ Оделл П. - Кластерный анализ (1977).djvu), страница 7

Было бы желательно иметь такой метод кластеризации, который был бы иивариантен к изменению масштабов измерения, ется не мера рассеяния, а «мера принадлежности», введенная Хользннгером и Харманом [1681 (см. табл, 1,6). Фортьер и Соломон пришли к выводу, что простой случайный отбор в общем случае не эффективен, если распределение показателя очень скошено и более вероятные его значения находятся на хвостах распределения. В то же время, как отмечают авторы, «модификация стратегии отбора может значительно улучшить ситуацию и эту возможность необходимо исследовать». ГЛАВА 2 КЛАСТЕРИЗАЦИЯ ПОЛНЫМ ПЕРЕБОРОМ 2Л.

Введение Наиболее прямой 'способ решения кластерной проблемы заключается в полном переборе всех возможных разбиений на кластеры и отыскании такого разбиения, которое ведет к оптимальному (минимальному) значе. нию целевой функции. Однако такая процедура практически невыполнима за исключением тех случаев, ког..да и (число объектов) и пч (число кластеров) не велико. Этот способ называют кластеризацией с помощью 'полного перебора. Например, если п=8, а т=4, то число возможных разбиений равно 1701; другими словами, существует 1701 способов разбить 8 объектов на 4 группы. Число разбиений обозначается через о (и, гп) и называется числом Стирлинга второго рода.

Оно мо. жет быть вычислено по формулам, которые будут нами получены в следующем параграфе. Данная глава лишь частично имеет отношение к проблеме кластеризации и поэтому' при первом чтении может быть опущена. 2.2. Число разбиений и объектов на и непуетых подмножеств Процесс разбиения множества из побъектов на пь непустых подмножеств можно представить как распределение и различных шаров по т одинаковым урнам, ни одна нз которых не должна остаться пустой. Обозначим число таких разбиений через ш. Тогда ннп! есть число всех возможных размещений и различ- яых объектов по т разным урнам (ни одна из которых не остается пустой) о. Один из наиболее эффективных методов решения задач, связанных с этой проблемой (т.

е. разбиение п объектов на т непустых . подмножеств), основан на методе производящих функций. Расомотрим функцию (1+х11) (1+хт1)... (1+хпг). (2.1) Раскрывая скобки, мы получим полипом от 1, в котором коэффициент при 1» представляет собой сумму произведений всех комбинаций по й множителей из и. Если, далее, х~ — — хо= ...

=х„=1, то коэффициент при г» равен С," — числу способов отбора (сочетаний) Й объектов из и. Таким образом, последовательность С а можно получить при помощи производящей гРункции (1+1)-= ~С„"Т» ° Этой же функцией можно воспользоватъся в случае, когда порядок элементов в группе существен: н» и» Г» (1+1)"= ~."„С 1»= ~',А„—, ° (2.2) » о » о здесь Ая =й! Са, й=О, 1, „п (число размещений), »» Функция (2.2) называется вхспаненциалоной производяи(ей функ»)ией. Если допускаются повторения, тодля подсчета результата перебора служит ряд, л-й член которого равен 1»!й1, где л — число повторений.

Таким образом, если число повторений не ограничено, то счетчи- ' ком для каждого объекта служит ряд Го 1+1+ — +... =е' 2! Следовательно, число различных перестановок п различныхобъектов в группе из Л объектов равно коэффициенту при 1»/й1 в производящей функции ь Число ш не предполагает разлнченяя н самих урн. Если же учнтывать н его, то, расположив для данного разбвення урны в некотором порядке, будем нх переставлять, обменнвая содержашнеся в ннх группы объектов.

Таких перестановок может бытыа~ Обозначення понятий теории соединений дальше нзменены на привычные для русского читателя.— Прямее. ред. ( — )-— Зз тл да зл 1+1+ — +... ~ =е"з= 2",ав — л 2! И в=о Как видим, это число равно лв. Если число повторений ие ограничено и каждый объект повторяется не менее одного раза, то счетчиком будет ( — ).- -— Зз т п л З-!. — -1-... ( = (ез-1) "= ~ С„( — 1] з е!"-з!'= 2! з=о с Зв л = Š— „! (ЕС (-1)'(а-у)д). (2.3) в=о з-о Тогда число перестановок определяется формулой ,'з С„(-1)з(п-1)в ° (2.4) з=о Производящая функция, применяемая для получения числа способов распределения и различных шаров поги различным урнам '(порядок расположения шаров в урнах несуществен), при котором урна 1 содержит и! шаров, з=1, 2, ...,.т'задается как л! лз лв п (хз+хв+... +х,„)л=~ хз хв ...х,„, (2.5) где суммирование производится по всем т-разбиениям а (так что пз+ав+ ...

+л =зз). Коэффициент при хз'хв'...х ~ равен числу таких распределений п шаров, при которых урна 1 содержит и! шаров, урна 2 содержит пв,..., урна т содержит и шаров. Таким образом, ве. личина (2.6) лз! лз!...а,„! зл / в м з" в П ~1+ «+ — + ..+. — ~. 2! ' ' ' и! 1 з з (2.7) В этом случае 1-й множитель есть число способов размещения пз шаров в 1-й урне, з= 1,2,..., зи. Число способов размещения л различных шаров по пз различным урнам может быть найдено с помощьзо производящей функции р я тч 1+х> 1+х> + ° . ° + хс (2.8) соответствует числу способов размещения шаров в 1-й урне.

Раскрывая скобки в (2.7), находим, что коэффициент при ! равен 1 я> яз я Е „,„1, х~ хя ° х,„" > где суммирование производится по всем пт-разбиениям и. Таким образом, коэффициент при 1Я!п! в (2.7) равен. и! я> пз я>, х~ хя хю я>! л>!... я ! =(х~+хз+ . ° +х,„)" ° Как следует из (2.6), число способов размещения и шаров по ги урнам, при которых й-я урна содержит пь ша. ров (й=1,2,..., ти), равно и!/п~! и,!... и 1, так как х1"' хз"'...х " отвечает некоторому частному способу раз мещения. Полагая в (2.7) х~— - ха= ... =х =1, получаем, что коэффициент при 1я/и! в выражении (1.! 1 ! 1а/2!+...

! 1я/и!)ю есть число способов размещения и различных шаров по и различным урнам. Однако этот коэффициент равен коэффициенту при 1Я/и! в выражении (1 ! 1 ! 1272! ! ... )я> ея>з Отсюда следует, что число возможных размещений п шаров по ти урнам равно тине.

Число разбиений множества из п объектов на ит подмножеств, ни одно из которых не будет пустым, определяется в следующей теореме. Теорема 1.!. Число способов размещения п шаров по гп урнам (ни одна из урн не будет пустой, а порядок расположения шаров в урне несуществен) равно >в 2', С~ ( — 1)1(т-'!)" ° 1 0 ' Допускается, что та или иная урна может вообще не содержать шаров, а поэтому этот же результат может быть получен крайне просто: первый шар можно положить в любую из т урн. Так же второй и т.

д. до л-го. Отсюда сразу ясно, что число всех полученных вариантов в целом будет и". — Примеч. ред. 44 Доказательство. Число шаров, содержащихся в 1-й урне, определяется из уравнения (х;1+х; Гз/2!+ ° ° ° ) =е — 1, поскольку каждая урна содержит по крайней мере один шар. Соответствующая экспоненциальная производящая функция, которую обозначим через Е(г,хь..,,х ), равна: »»» оч Е(1,хь хь...,х ) = П (е — 1).

»сы Число способов размещения и шаров по т урнам так, чтобы ни одна урна не была пустой, равно коэффициенту при Р'/а! и при условии х~ — — ха=...=х =1. В этом случае производящая функция (2.9) превращается в (2.9) (2.10) Е(Г 1 1 1) (ес 1)»»» которая совпадает с (2.3). Поэтому »» Са»»» Е(1,1,1,....1)= Š— ( Е СА( — 1)у(т — 1)ь). И ь=о з=о Коэффициент при !"/и! равен тп ~. С (-1)з(и — 1)", Осталось показать, каким образом числа Стирлинга второго рода связаны с соотношением (2.11).

Числа Стирлинга второго рода возникают при вычислении конечных разностей и связаны с нахождением показателя х в факториальных многочленах. Факториальный многочлен определяется-следующим образом: что приводит к требуемому результату.

В теореме 1.1 лт урн предполагаются различными.' Однако при разбиении а объектов на т подмножеств, каждое из которых не пусто,' порядок подмножеств не играет роли. С учетом теоремы 1.! отсюда следует, что число разбиений и объектов на гл подмножеств равно: »»» ш= — Е С ( — !)!(гп-1)а ° (2.!1) в-а . хо! 1, хо„! — — х(х-1) ° ° (х-и+1), п=1,2, ° ° ° и ° Определение 2.1.

Числами Стирлинга второго рода называются числа Я (и, !), удовлетворяющие уравнениям я х"=.~ Б(п,1)хооь 3(п, 0) =О о-! Г Ь~и(к) 0(х)= ~ х<о> [ — 1 (2,! 2) где Ь определяется как Д! О =1( + 1) †!(х) Ь"1(х) =Ь[Д"-' !(х)1 и Ло[(х) =цх) Разлагая У(х)=х" по формуле (2.12), получим: "= й;- ~ — '" 1.. о Из определения 8 (и, 1) имеем: Г Дткп ! ! Е(~,-) = ~ — ~ = — [~-"1.=' т! к=о т! Осталось показать, что п~ 2„,' С ( — 1)!(т-1)"= [Д~х"1, о ° о=о Для этой цели введем оператор смещения Е=1+Л, где Е1 (х) =!о (х+1), ЕЦ (х) =! (х+1) и Ь='Š— 1. Пользуясь введенными обозначениями, получим: тл ь па В ~", Ст ( — 1)о(т й)п ~-' С~ ( 1)'Е~-ьхп~ =о= о о (Š— 1) ~х" [к=о = [Л~х" ~*=о ° Таким образом, имеем ое=5 (п,т).