Презентация на тему Алгоритм Forel. Выделение устойчивых таксонов

алгоритмов таксономии.
Пример 1.
Примеры прикладных задач таксономии:
прогнозирование успеваемости;
ранжирование

объектов.

объектов в таких условиях, когда:
все характеристики объектов однородны,
число

таксонов N задано,
обладает таксонами, которые имеют форму гиперсферы.

нормируются так, чтобы их значения были в диапазоне 0

- 1.
Шаг 2. R0=+∞
Шаг 3. Все точки считаем непомеченными.
Шаг 4. На множестве непомеченных точек выбирается произвольная xi, после чего осуществляется переход к шагу 5. Если таковых точек нет, то перейти к шагу 8.
Шаг 5. Ищется максимальное расстояние R от xi до остальных точек.

= min {R0;R} .
Шаг 7. Точка xi помечается. Если

помечены все точки, то перейти к шагу 8, нет - к шагу 4.
Шаг 8. R=R0-ε
Шаг 9. Если множество точек пусто, то перейти к шагу 16, нет - к шагу 10.
Шаг 10. Все точки считаем непомеченными.
Шаг 11. На множестве непомеченных точек выбирается произвольная точка xi.
Шаг 12. Определяется число точек P(xi), расстояние которых до xi не превышает R.

Точку xi считаем помеченной. Если помечены все точки, то

перейти к шагу 14, нет - к шагу 11.
Шаг 14. Выбирается j-я точка , для которой справедливо: P(xi)≤P(xj), i=1,2,3,…n.
Шаг 15. Все точки, расстояние от которых до не превышает R, удаляются. Перейти к шагу 9.
Шаг 16. Если число таксонов меньше N, то перейти к шагу 17, иначе к шагу 19.
Шаг 17. R=R-ε .
Шаг 18. Все точки возвращаются на «свои места», перейти к шагу 10.

число таксонов равно N, то перейти к шагу 22,

нет - к шагу 20.
Шаг 20. ε=ε/2.
Шаг 21. R=R+ε, перейти к шагу 18.
Шаг 22. Конец алгоритма.

λ-расстояния между объектами приведены ниже в таблице М, ε

= 0,1.



М=

1

0,85
0,5

0,8
0,6

0,9

0,5 0,6 0,8

Таксон № 1;

R=0,6.






Таксон № 2

2

3

4

1

0,5 0,6 0,8

Таксон № 2






Таксон № 3

2

3

4

1

0,5 0,6 0,8

два столбца:

где k – порядковый номер студента.
2. Полагая, что строки отвечают объектам, а столбцы – критериям, выделить, пользуясь Forel 1, таксоны при условии, что Ɛ = 0,5.
3. Разбить все объекты на 3 таксона, пользуясь Forel 2.

объектов с помощью FOREL-1.
Шаг 2. Используя центры таксонов в

S, как новые стартовые точки для FOREL-1, определяются таксономии S1,S2,…Sn.
Шаг 3. Выбор устойчивых таксонов.
Шаг 4. Конец алгоритма.

FOREL 1, выделить устойчивые таксоны в таблице:

1-й таксон: 1, 2; 2-й таксон: 3.
2)

Таксономия S2 при обратной нумерации объектов (строк):
1-й таксон: 2, 3; 2-й таксон: 1.
3) Вывод: таксоны неустойчивы.

построив график зависимости времени счета от размерности исходной матрицы.

объекты возникают по одному или группами и на каждой

итерации осуществляется таксономия. В этом случае используется алгоритм DINA, описание которого приводится ниже.

i=1.
Шаг 3. Ввод i-го объекта.
Шаг 4. Если i>1, то

перейти к шагу 6.
Шаг 5. Введённый объект отвечает центру первого таксона.
Шаг 6. Определяется расстояние от i-й точки до центров всех созданных таксонов.
Шаг 7. Если кратчайшее из этих расстояний меньше R, то i-й объект принадлежит соответствующему таксону, в противном случае i-й объект - центр нового таксона.
Шаг 8. i=i+1.
Шаг 9. Если ввод объектов завершён, то перейти к шагу 10, нет - к шагу 3.
Шаг 10. Конец алгоритма.

возникающих объектов: круга, квадрата и треугольника, характеризующихся Таблицей, представленной

на следующем слайде, R=1.

квадратом и кругом больше R: r1=1.1657, следовательно квадрат -

центр второго таксона.
Расстояние между треугольником и квадратом r2=0.7541 меньше, чем между треугольником и кругом r3=1.013422 и меньше R, следовательно треугольник принадлежит ко второму таксону.

Таксон № 2