|
.2.4 Алгоритмы прямой классификации. Подавляющая часть практических исследований выполнена с помощью этих алгоритмов.В качестве примера одного из способов точного определения кластеров приведем класс типа сгущения (типа ядра) - компактная группа. Все расстояния между объектами внутри класса меньше любого расстояния между объектами класса и остальной частью множества. С помощью такого определения нельзя различать классы, представленные на рисунке 1-3: разнотипные (B и C), пересекающиеся (К и H), большие и малые (R и Q).1.2.5 Алгоритм иерархической классификации. Пусть X={X1, ...,Xn}, где Xi=( xi(1), ..., xi(p)) Rp. Пусть Si - i-я группа (класс, кластер) объектов, ni - число объектов, образующих группу Si, - среднее арифметическое векторных наблюдений, входящих в Si-ую группу. На вход агломеративного иерархического алгоритма подается разбиение S(0)= (S1(0),..., Sn(0)), где Si(0)={Xi}. Разбиение k-го уровня имеет вид S(k)= (S1(k),..., Sn-k(k)) и строится из разбиения S(k-1), k>1, путем объединения пары классов (S1*, S2*), где (S1*, S2*)=( S1, S2) (1.25) Итоговую иерархию s образует система вложенных разбиений . Здесь S(n-1)=X. Отметим, что иерархическая классификация при помощи бинарного алгоритма всегда дает бинарную иерархию. Чаще всего используются в агломеративных алгоритмах следующие меры близости между классами. Расстояние, измеряемое по приращению статистического разброса при объединении классов (S1, S2)= Q (S1) - Q (S1) - Q (S2), (1.26) где Q(S)=, Z=-центр класса S, - квадрат евклидова расстояния между X и Z. Расстояние, измеряемое по принципу «ближнего соседа» (Sl, Sm)= (1.27) Расстояние, измеряемое по принципу «дальнего соседа» (Sl, Sm)= (1.28) Расстояние, измеряемое по «центрам тяжести групп» (Sl, Sm)= d (), (1.29) Отметим, что мера близости (1.26) обладает рядом важных свойств, которые обеспечивают широкое использование ее при решении задач классификации. В то же время расстояние по центрам тяжести (1.29) не обладает такими свойствами. Результаты работы всех иерархических процедур оформляется в виде дендрограммы (см. рисунок 1.4). По горизонтали показаны номера объектов, а по вертикали - значения межклассовых расстояний. Рисунок 1.4 - Дендограмма 1.2.6 Алгоритм k-средних. При решении практических задач полезно иметь набор простых быстродействующих алгоритмов классификации для выработки первых представлений о структуре данных в признаковом пространстве. Пусть исходная информация о классифицируемых объектах представлена матрицей «объект-свойство», столбцы которой задают точки p-мерного евклидова пространства.Опишем один из наиболее известных алгоритмов, использующий понятие центра тяжести, являющийся процедурой параллельной классификации. Единственным управляющим параметром алгоритма k-средних является число классов, на которые проводится разбиение S={S1 , ... , Sk} выборки X. В результате получается несмещенное разбиение S*={S1* , ... , Sk*}.Схема алгоритмаВыберем начальное разбиение S0=(S10,..., Sn0), где Si0- {Xi10,..., Xini0}, =0, Пусть построено m-е разбиение Sm=(S1m,..., Snm). Вычислим набор средних em ={e1m,..., ekm}, ei m=.Построим минимальное дистанционное разбиение, порождаемое набором em и возьмем его в качестве Sm+1=(S1m+1,..., Snm+1), т.е......................................................где - расстояние в p-мерном пространстве Rp.Если , то переходим к пункту 2, заменив m на m+1, если , то полагаем Sm=S* и заканчиваем работу алгоритма.Содержательно процедура алгоритма k-средних направлена на поиск разбиения S* выборки X с минимальным разбросом.В ряде случаев начальное разбиение S0 как минимальное дистанционное разбиение, порожденное некоторым набором точек e0={e10,..., ek0}. Результат классификации зависит от выбора e0. Обычно для проверки устойчивости результата рекомендуется варьировать выбор e0. 2 Алгоритмы методов статистического описания выборки2.1 Алгоритмы непараметрической аппроксимации функции плотности распределения вероятностейДля реализации непараметрической аппроксимации оценки функции плотности вероятностей в среде встроенного пакета анализа данных Excel разработан макрос.Алгоритм последовательности действий, которые выполняются при запуске макроса для построения равноинтервальной гистограммы и полигона частот, описывается следующей схемой (см. рисунок 2.1).Рисунок 2.1 - Схема последовательности действий, производимых макросом для равноинтервальной гистограммы и полигона частот Алгоритм последовательности действий, которые выполняются при запуске макроса для построения равнонаполненной гистограммы и полигона частот, описывается схемой, приведенной на рисунке 2.2. Алгоритм последовательности действий, которые выполняются при запуске макроса для построения «ядерной» аппроксимации функции плотности распределения, описывается следующей схемой на рис 2.3. Рисунок 2.2 - Схема последовательности действий, производимых макросом для равнонаполненной гистограммы и полигона частот Рисунок 2.3 - Схема последовательности действий, производимых макросом для «ядерной» аппроксимации функции плотности распределения 2.2 Алгоритм параметрической аппроксимации функции плотности распределения вероятностей на основе нормальной вероятностной бумагиДля реализации лабораторной работы «Оценка функции распределения с помощью нормальной вероятностной бумаги» в среде встроенного пакета анализа Excel разработан макрос.Алгоритм последовательности действий, которые выполняются при запуске макросов, описывается следующей схемой (см. рисунок 2.4).Рисунок 2.4 - Схема последовательности действий, производимых макросом для нормальной вероятностной бумаги 2.3 Упрощенная схема алгоритма прямой классификацииНа основе изученного материала разработано схематическое описание алгоритма прямой классификации упрощенным методом K - ближайших соседей (см. рисунок 2.5). Рисунок 2.5 - Схематическое описание алгоритма прямой классификации 3 Статистическое описание выборки на основе Visual Basic for Application3.1 Описание средств автоматизации непараметрической аппроксимации функции плотности распределения вероятностейПервоначально перед пользователем стоит выбор решаемой задачи: гистограмма и полигон частот для статистических данных с разбиением на интервалы равной длины (задача 1), гистограмма и полигон частот для статистических данных с разбиением на равнонаполненные интервалы (задача 2), непараметрическая оценка функции плотности распределения вероятности для статистических данных методом прямоугольных вкладов (задача 3).3.1.1 Описание средств автоматизации равноинтервальной гистограммы и полигона частот. Действия, которые производит построенный макрос для гистограммы и полигона частот для статистических данных с разбиением на интервалы равной длины, разбиты на 4 этапа.Этап 1. Ввод объема выборки и количества интервалов. Первоначально пользователю следует ввести информацию об объеме выборки и количестве интервалов, на которое следует разбить отрезок, в ячейки С16 и С17 соответственно. В случае если пользователь не произвел эти действия, выводится предупреждающее сообщение о необходимости ввода этих данных.Этап 2. Сортировка данных по возрастанию. Для определения концов отрезка, в который попадают все элементы выборки, необходима сортировка выборки по возрастанию. Для продолжения дальнейшего исследования в макросе предусмотрена реализация этих действий.Этап 3. Нахождение шага разбиения отрезка. После определения концов отрезка в макросе происходит нахождение шага разбиения отрезка на отрезки равной длины по формуле h=(b-a)/N, где b- конец отрезка, a - начало отрезка, N - число отрезков.Этап 3. Нахождение значений для функции распределения. Значения для функции распределения в макросе находятся по формуле , где mi-- число наблюдений, попавших в интервал .Этап 4. Занесение значения для абсцисс и ординат равноинтервальной гистограммы и полигона частот на рабочий лист. Для наглядного изображения равноинтервальной гистограммы и полигона частот на рабочий лист выводятся данный по значению абсцисс и ординат, по которым ведутся дальнейшие построения.3.1.2 Описание средств автоматизации равнонаполненной гистограммы и полигона частот. Действия, которые производит построенный макрос гистограмма и полигон частот для статистических данных с разбиением на равнонаполненные интервалы, разбиты на 4 этапа.Этап 1. Проверка выполнений условий, необходимых для построения гистограммы и полигона частот. После ввода элементов выборки следует проверить условия, при которых невозможно дальнейшее исследование. Это случаи, когда выборка однородна и количество элементов выборки нечетно. В случае если эти условия имеют место быть, программа выдаст сообщение о невозможности продолжения исследования. После этого исследователь может исправить недочеты и продолжить вычисления.Этап 2. Сортировка данных по возрастанию. Для определения концов отрезка, в который попадают все элементы выборки, необходима сортировка выборки по возрастанию. Для продолжения дальнейшего исследования в макросе предусмотрена реализация этих действий.Этап 3. Нахождение значений для функции распределения. Значения для функции распределения в макросе находятся по формуле, где - интервал, а k - целое число из интервала [3,7].Этап 4. Занесение значения для абсцисс и ординат равноинтервальной гистограммы и полигона частот на рабочий лист. Для наглядного изображения равноинтервальной гистограммы и полигона частот на рабочий лист выводятся данные по значению абсцисс и ординат, по которым ведутся дальнейшие построения.3.1.3 Описание средств автоматизации «ядерной» функции плотности. Действия, которые производит построенный макрос непараметрической оценки функции плотности распределения вероятности для статистических данных методом прямоугольных вкладов, разбиты на 5 этапов.Этап 1. Нахождение d - ширины функции вклада. На первоначальном этапе данного метода следует найти d - ширину функции вклада по формуле d=, где b - конец отрезка, a - начало отрезка, значение k берется из интервала [3; 7]. Этап 2. Сортировка данных по возрастанию. Для определения концов отрезка, в который попадают все элементы выборки, необходима сортировка выборки по возрастанию. Для продолжения дальнейшего исследования в макросе предусмотрена реализация этих действий. Этап 3. Нахождение множества абсцисс для оценки функции плотности распределения. Для дальнейшего исследования в макросе производится разбиение отрезка точками, которые высчитываются по формулам Этап 4. Определение «ядерной» аппроксимации функции плотности распределения. Значения для «ядерной» аппроксимации функции плотности распределения в макросе находятся по формуле
Страницы: 1, 2, 3, 4, 5, 6, 7, 8
|
