Компьютерные решения задач многомерной статистики. Часть 1. Кластерный и дискриминантный анализ. Давнис В.В - 8 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

гом, строится связное дерево кратчайших расстояний. Формально про -
цедура построения такого дерева выглядит следующим образом .
На нулевом шаге формируются три вектор-строки по правилам:
1-ая строка – это строка из взаимных расстояний первого объекта со
всеми остальными
(
)
k
k
xx ,
1
1
ρρ = , nk ,1= ; (2.8)
2-ая строка – это строка , элементы которой равны расстояниям между
вершинами дерева и расположенные в той последовательности, в которой
вершины подсоединялись к дереву (на нулевом шаге, когда дерево состоит
из одной вершины, единственным элементом этой строки является 0)
{
}
0
1
=R ; (2.9)
3-я строка – это строка из номеров вершин (объектов), расположенных
в той последовательности, в которой строилось дерево кратчайших рас-
стояний (на нулевом шаге в этой строке стоит только один элемент – номер
первой вершины дерева )
{
}
1
1
=
K . (2.10)
На
i
-ом шаге определяется вершина, ближайшая к фрагменту уже по-
строенного дерева путем вычисления минимального элемента строки
{
}
1−i
k
ρ ,
{
}
1
0
min
−
≠
∗
=
i
k
k
k
Argk ρ
ρ
, nk ,1= . (2.11)
Используя найденный номер ближайшей вершины, формируются три
вектор-строки по следующим правилам:
1-ая строка формируется из минимальных расстояний путем сопостав-
ления текущей строки расстояний построенного фрагмента дерева до вер-
шин , не включенных в этот фрагмент, со строкой взаимных расстояний,
ближайшего к фрагменту элемента
∗
},(,min{
k
k
kk
xx ∗
=
ρ
ρ
ρ
, nk ,1= ; (2.12)
2-ая строка пополняется номером объекта, ближайшего к построенному
фрагменту дерева
∗
−
∪= kKK
i
i
1
; (2.13)
3-я строка пополняется значением расстояния от построенного фраг-
мента дерева до ближайшей вершины, которая на
i
-ом шаге включается в
состав фрагмента дерева
∗∪=
−
k
i
i
RR ρ
1
. (2.14)
Процесс продолжается до полного исчерпания всего множества клас-
сифицируемых объектов.
После построения дерева вычисляется среднее значение расстояний
между его вершинами 
гом , ст роит ся связн ое дере во кратчай ши х ра сстоян и й . Ф орм а л ь н о про-
цед у ра построен ия т а кого д ерева выгл яд ит сл ед у ющ им обра зом .
      Н а н у л евом ш а ге ф орм иру ют ся три вект ор-ст роки по пра вил а м :
      1-а я строка –это ст рока из вза им н ых ра сстоян ий первого объект а со
всем и оста л ь н ым и
                             ρ 1k = ρ (x1 , x k ) , k = 1, n ;                  (2.8)
     2-а я ст рока –эт о ст рока , эл ем ен т ы которой ра вн ы ра сст оян иям м еж д у
верш ин а м и д ерева и ра спол ож ен н ые в т ой посл ед ова т ел ь н ост и, в которой
верш ин ы под соед ин ял ись к д ереву (н а н у л евом ш а ге, когд а д ерево состоит
из од н ой верш ин ы, ед ин ст вен н ым эл ем ен т ом эт ой строки явл яет ся 0)
                                   R1 = {0};                                       (2.9)
     3-я строка –эт о ст рока из н ом еров верш ин (объектов), ра спол ож ен н ых
в т ой посл ед ова т ел ь н ост и, в которой ст роил ось д ерево кра тча йш их ра с-
ст оян ий (н а н у л евом ш а ге в эт ой строке ст оит т ол ь ко од ин эл ем ен т –н ом ер
первой верш ин ы д ерева )
                                    K1 = {1}.                                    (2.10)
     Н а i -ом ш а ге опред ел яет ся верш ин а , бл иж а йш а я к ф ра гм ен т у у ж е по-
                                                                                    { }
ст роен н ого д ерева пу т ем вычисл ен ия м ин им а л ь н ого эл ем ен т а ст роки ρ ki −1 ,

                                          k
                                              { }
                             k ∗ = Arg min ρ ki −1 ,             k = 1, n .      (2.11)
                                         ρk ≠0
      Испол ь зу я н а йд ен н ый н ом ер бл иж а йш ей верш ин ы, ф орм иру ют ся т ри
вектор-ст роки по сл ед у ющ им пра вил а м :
      1-а я ст рока ф орм иру ет ся из м ин им а л ь н ых ра сст оян ий пу т ем сопост а в-
л ен ия т еку щ ей ст роки ра сстоян ий построен н ого ф ра гм ен та д ерева д о вер-
ш ин , н е вкл ючен н ых в этот ф ра гм ен т, со ст рокой вза им н ых ра сст оян ий,
бл иж а йш его к ф ра гм ен т у эл ем ен т а k ∗
                     ρ k = min{ρ k , ρ ( x k ∗ , x k } , k = 1, n ;             (2.12)
      2-а я строка попол н яет ся н ом ером объект а , бл иж а йш его к построен н ом у
ф ра гм ен т у д ерева
                               K i = K i −1 ∪ k ∗ ;                          (2.13)
      3-я ст рока попол н яет ся зн а чен ием ра сст оян ия от пост роен н ого ф ра г-
м ен т а д ерева д о бл иж а йш ей верш ин ы, кот ора я н а i -ом ш а ге вкл юча ет ся в
сост а в ф ра гм ен т а д ерева
                               Ri = Ri −1 ∪ ρ k ∗ .                        (2.14)
      П роцесс прод ол ж а ет ся д о пол н ого исчерпа н ия всего м н ож ества кл а с-
сиф ициру ем ых объектов.
      П осл е построен ия д ерева вычисл яет ся сред н ее зн а чен ие ра сст оян ий
м еж д у его верш ин а м и

Страницы