1

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования

«Гомельский государственный университет имени Франциска Скорны»

Математический факультет

Кафедра математических проблем управления

Допущена к защите

Зав. кафедрой_____________Максимей И.В.

«____»_____________ 200 _ г.

Разработка программно-технологического обеспечения статистического описания объектов посредством Visual Basic for Application Excel

ДИПЛОМНАЯ РАБОТА

Исполнитель:

студентка группы М-52 ______Бондарева Юлия Викторовна

Научный руководитель:

кандидат физико-

математических наук

доцент кафедры МПУ____________Осипенко Наталья Борисовна

Рецензент:

доктор технических наук,

профессор, профессор

кафедры ВМП____________Можаровский В.В.

Гомель 2007

РЕФЕРАТ

Ключевые слова: кластер - анализ, близость между объектами, расстояние, нормировка, алгоритм прямой классификации, нормальная вероятностная бумага, математическое ожидание, дисперсия, макрос, средства автоматизации, лабораторная работа.

Объект исследования: статистическое описание экспериментальных данных.

Методы исследования: метод K - ближайших соседей, метод нормальной вероятностной бумаги, непараметрические методы оценки плотности распределения

Цель дипломной работы: разработка комплекса обучающих средств для студентов, помогающих в изучении и освоении проблематики:

ѕ теории классификации на примере алгоритма прямой классификации упрощенным методом K - ближайших соседей;

ѕ оценки функции плотности распределения вероятностей с помощью непараметрических методов;

ѕ параметрической аппроксимации функции плотности распределения вероятностей с помощью нормальной вероятностной бумаги;

ѕ интерпретации полученных результатов эмпирической статистической обработки данных.

Выводы: разработаны обучающие средства, позволяющие:

ѕ преподавателю упростить процедуру проверки правильности выполнения работ;

ѕ студентам упростить решение задачи статистического описания;

ѕ студентам предоставить наглядные обучающие средства для изучения влияния нормировки, начального разбиения выборки, выбора расстояния на результаты классификации.

СОДЕРЖАНИЕ

• Введение 5
• 1 Типы задач статистической обработки 7
• 1.1 Статистическая аппроксимация законов распределения 7
• 1.1.1 Гистограмма и полигон частот 7
• 1.1.2 Оценка плотности распределения вероятностей «ядерного» типа 8
• 1.2 Основные теоретические сведения по теории классификации 10
• 1.2.1 Основные понятия кластерного анализа и проблема измерения близости между объектами 10
• 1.2.2 Типы методов кластер - анализа 13
• 1.2.3 Систематизация алгоритмов 14
• 1.2.4 Алгоритмы прямой классификации 15
• 1.2.5 Алгоритм иерархической классификации. 16
• 1.2.6 Алгоритм k-средних 17
• 2 Алгоритмы методов статистического описания выборки 18
• 2.1 Алгоритмы непараметрической аппроксимации функции плотности распределения вероятностей 18
• 2.2 Алгоритм параметрической аппроксимации функции плотности распределения вероятностей на основе вероятностной бумаги 20
• 2.3 Упрощенная схема алгоритма прямой классификации 20
• 3 Статистическое описание выборки на основе VBA 22
• 3.1 Описание средств автоматизации непараметрической аппроксимации функции плотности распределения вероятностей 22
• 3.1.1 Описание средств автоматизации равноинтервальной гистограммы и полигона частот 22
• 3.1.2 Описание средств автоматизации равнонаполненной гистограммы и полигона частот. 22
• 3.1.3 Описание средств автоматизации «ядерной» функции плотности 23
• 3.2 Описание средств автоматизации параметрической аппроксимации функции плотности распределения вероятностей на основе нормальной вероятностной бумаги 24
• 3.3 Описание средств автоматизации алгоритма прямой классификации 25
• 4 Апробация средств автоматизации в виде макросов 28
• 4.1 Апробация программного обеспечения средствами встроенного пакета анализа данных Excel 28
• 4.1.1 Апробация программного обеспечения алгоритма прямой классификации 28
• 4.1.2 Апробация программного обеспечения параметрической аппроксимации функции плотности распределения вероятностей на основе нормальной вероятностной бумаги 31
• 4.1.3 Апробация программного обеспечения непараметрических методов статистической аппроксимации законов распределения 33
• Заключение 35
• Список использованных источников 36

Приложение А Апробация программного обеспечения алгоритма прямой классификации средствами пакета анализа данных STATISTICA………. 37

Приложение Б Текст программы макроса для параметрической аппроксимации функции плотности распределения вероятностей на основе нормальной вероятностной бумаги………………………………………. 45

Приложение В Текст программы макроса для алгоритма прямой классификации ……………………………………………………………….. 47

Приложение Г Текст программы макроса для непараметрических методов статистического описания выборки............................................................... 57

• ВВЕДЕНИЕ
• Всё множество задач статистической обработки данных сводится к задачам описания и прогноза. На начальном этапе статистического исследования ставится цель определения объекта и его описания. В том случае, если объектом исследования является выборка, то методами разведочного (предмодельного) статистического анализа данных необходимо определить вероятностную и геометрическую природу обрабатываемых данных, а также выяснить, однородны ли имеющиеся эмпирические данные, т.е. целесообразно ли разбиение совокупности на части, представляющие собой кластеры. В последствии на основе этих заключений формируются адекватные реальности рабочие допущения, на основе которых осуществляется дальнейшее исследование. Поэтому стала актуальной проблема разработки средств автоматизации, позволяющих построить статистическую модель в виде эмпирического описания структуры данных, которую необходимо в ходе статистического исследования верифицировать.
• Если объектом исследования является выборка, которая принадлежит к нормальному распределению, то задача статистической обработки сводится к оценке её параметров. Для оценки параметров выборки можно воспользоваться методом нормальной вероятностной бумаги. В том же случае, когда конкретный вид функции распределения неизвестен, и о виде распределения можно сделать лишь самые общие предположения, то при таких условиях можно воспользоваться аппроксимациями неизвестной функции распределения на основе выборки , называемыми непараметрическими, а именно - гистограммой и полигоном частот для статистических данных с разбиением на интервалы равной длины, или с разбиением на равнонаполненные интервалы, непараметрической оценкой функции плотности распределения вероятности для статистических данных методом прямоугольных вкладов.
• Эти методы предусматривают однообразные и рутинные вычисления, поэтому стала актуальной разработка средств автоматизации проверки правильности производимых расчётов.
• Работа посвящена созданию обучающих средств, помогающих студентам в изучении и освоении метода оценки параметров выборки с помощью нормальной вероятностной бумаги, непараметрических методов аппроксимации функции распределения и метода классификации экспериментальных данных упрощенным алгоритмом K - ближайших соседей.
• В качестве среды реализации алгоритма был выбран встроенный пакет анализа данных Excel, потому что он является базовым компонентом Microsoft Office и доступен большинству обычных пользователей.
• Постановка задачи:
• Изучить литературу о типах методов кластерного анализа, об алгоритмах прямой классификации.
• Изучить литературу о статистической аппроксимации законов распределения, гистограмме и полигоне частот, оценке плотности распределения вероятностей «ядерного» типа, о параметрических методах оценки плотности распределения вероятностей.
• Разработать алгоритмы программной реализации: алгоритма прямой классификации упрощенным методом K - ближайших соседей, метода нормальной вероятностной бумаги и непараметрических методов аппроксимации функции плотности распределения.
• Разработать макросы, позволяющие реализовать алгоритм прямой классификации упрощенным методом K - ближайших соседей.
• Разработать макрос для оценки параметров выборки методом нормальной вероятностной бумаги.
• Разработать макросы для непараметрических методов оценки функции плотности распределения.
• Разработать обучающие средства по первичной статистической обработке данных на основе созданных макросов.
• В первой главе дипломной работы сделан обзор задач статистического описания.
• Во второй главе приведены алгоритмы прямой классификации упрощенным методом K - ближайших соседей, оценки параметров выборки методом нормальной вероятностной бумаги и алгоритмы непараметрической оценки функции плотности распределения.
• Третья глава посвящена статистическому описанию выборки на основе Visual Basic for Application.
• В четвертой главе работы описана апробация средств автоматизации в виде макросов.
• 1 Типы задач статистической обработки

1.1 Статистическая аппроксимация законов распределения

Первичные данные, полученные при наблюдении, обычно трудно обозримы. Для того чтобы начать анализ, в них надо внести некоторый порядок и придать им удобный для исследователя вид. В частности, для начала желательно получить представление об одномерных распределениях случайных величин, входящих в данные.

Существуют два типа задач аппроксимации распределений [2,4]. Если вид функции распределения известен, но не известны ее параметры, тогда задача сводится к параметрическому оцениванию. Бывают ситуации, когда конкретный вид функции распределения неизвестен, и о виде распределения можно сделать лишь самые общие предположения. При таких условиях аппроксимацию неизвестной функции распределения на основе выборки называют непараметрической.

1.1.1 Гистограмма и полигон частот. Классическими методами статистической аппроксимации функции плотности являются гистограмма (равноинтервальная и равнонаполненная) и полигон частот.

Выборочная функция плотности распределения или гистограмма (равноинтервальная) строится следующим образом. Делим промежуток [a,b], на котором сосредоточены данные выборки на S интервалов , равной длины h=(b-a)/S. Подсчитываем число наблюдений , попавших в интервал , соответственно. Полагаем

, (1.1)

Полигон частот получают путем сглаживания гистограммы

, , (1.2)

где - середина промежутка , -правый конец промежутка .

Очевидно, что .

Выборочная функция плотности распределения или гистограмма (равнонаполненная) строится исходя из предположения, что вся площадь под графиком оценки функции разбивается на k равных частей. Тогда площадь каждой части равна , . Для конкретной выборки рассчитываются длины интервалов , а затем, опираясь на формулу

, (1.3)

определяется . На основании полученных значений длины и высоты каждого прямоугольника гистограммы получаем оценку .

1.1.2 Оценка плотности распределения вероятностей «ядерного» типа.

Для малых выборок (N<30) гистограмма и полигон частот оказываются обычно искаженными за счет тех или иных случайных локальных отклонений, связанных с отсутствием необходимого числа объектов. Одним из способов частично ликвидировать этот пробел явилась «ядерная» аппроксимация, которая путем «размазывания» имеющихся точек заполняет на гистограмме «впадины» и срезает «пики». Отметим, что «ядерное» сглаживание учитывает особенность функции плотности распределения и потому из всех методов сглаживания является наиболее корректным.

Оценка плотности распределения для большинства методов «ядерного» типа обобщенно может быть выражена линейной суммой двух компонент: априорной и эмпирической:

(1.4)

где - априорная компонента; - составляющая эмпирической компоненты, связанная с i- той реализацией выборки; - вес априорной компоненты.

Различным методам исследования соответствуют разные значения и разные виды функции . Широко известны оценки f(x) типа (1.3) при значении . В методе прямоугольных вкладов.

(1.5)

(1.6)

(1.7)

где [a,b] -интервал изменения случайной величины x; d - ширина функции вклада.

В качестве d может быть взято, например:

(1.8)

Алгоритм ядерной аппроксимации функции плотности распределения имеет следующий вид:

1 Задается множество точек ;

2 Полученное множество точек упорядочивается по возрастанию: ;

3 Определяется «ядерная» аппроксимация функции плотности распределения:

(1.9)

где - количество точек исходной выборки, попавших в интервал .

Замечание: значение k берется из интервала [3; 7].

1.1.3 Оценка функции распределения с помощью нормальной вероятностной бумаги. Пусть даны N наблюдений x₁,...,x_N, извлеченные из генеральной совокупности с функцией распределения F(t).

Этап 1. Исходная выборка значений упорядочивается по возрастанию. В результате получается последовательность x(1) ,..., x(N).

Этап 2. Для каждого значения x(i), на плоскости отмечается точка (x(i), i/N) (см. рисунок 1.1). Для того чтобы определить расположение этой точки, находится значение V_i=Ф^-1(i / N), которое откладывается по оси V.



Рисунок 1.1 - Нормальная вероятностная бумага

Этап 3. Если точки (х(i) ,i/N) в какой-то мере ложатся вдоль некоторой прямой, то можно грубо считать генеральную совокупность, из которой извлечена данная выборка, нормальной. В противном случае надо подыскать преобразование переменной, например, логарифмирование, извлечение корня и тому подобное, в результате которого выборка бы соответствовала нормальному распределению.

Этап 4. В случае принятия гипотезы о нормальности распределения осуществляется оценка параметров распределения. В качестве оценки центра берется медиана выборки, которая соответствует вероятности р=0.5. Оценка стандартного отклонения , где - оценка 0.84 квантиля распределения, полученного при V=1.

1.2 Основные теоретические сведения по теории классификации

1.2.1 Основные понятия кластерного анализа и проблема измерения близости между объектами. В общем виде задачу классификации исследуемой совокупности объектов O={O_i}, , где для каждого объекта замерены значения p параметров, т.е. каждый объект O_i описан вектором X_i = (x_i1,...,x_i), можно сформулировать как задачу поиска такого разбиения S заданной совокупности на непересекающиеся классы S₁,....,S_k:

, S_i S_j = , ij , (1.10)

при котором функционал качества Q(S) достигает экстремального значения на множестве A допустимых правил классификации [6]. В качестве Q(S) используют критерии, минимизирующие межгрупповое сходство и одновременно максимизирующее внутригрупповое сходство. Состав множества A зависит от предварительной (априорной) выборочной информации об этих классах. Итак, задача классификации формально сводится к нахождению разбиения S*.

Q(S*) =min Q(S), S A (1.11)

Заметим, что при этом число k может быть и неизвестно.

При любых трактовках кластеров и для различных методов классификаций неизбежно возникает проблема измерения близости объектов. С этой проблемой связаны следующие трудности: неоднозначность выбора способа нормировки и определения расстояния между объектами.

Нормировка представляет собой переход к некоторому единообразному описанию всех признаков и связана с введением новых единиц измерения, допускающих формальное сопоставление объектов. Перечислим наиболее распространенные способы нормирования показателей (переход от исходных значений x к нормированным z):

z¹ = (x -) / , (1.12)

z²= x /, (1.13)

z³=x / x , (1.14)

z⁴=x / x_max, (1.15)

z⁵=(x-)/ (x_max - x_min), (1.16)

где , - среднее и среднеквадратичное отклонение x, соответственно;

x - некоторое эталонное (нормативное) значение x;

x_min , x_max - наименьшее и наибольшее значения x.

(1.17)

Расстоянием (метрикой) d между объектами a и b в пространстве параметров называется такая величина d(a,b), которая удовлетворяет аксиомам:

A1.d(a,b)>0, d(a,a)=0 (рефлексивность); (1.18)

A2.d(a,b)=d(b,a) (симметричность); (1.19)

A3.d(a,b)+d(b,d) d(a,b) (правило треугольника) (1.20)

Рассмотрим основные способы определения близости между объектами для количественных шкал.

1 Линейное расстояние:

(1.21)

2 Евклидово расстояние:

(1.22)

3 Обобщенное степенное расстояние Минковского:

(1.23)

4 Расстояние Махаланобиса:

, (1.24)

где X_i = (x_i1,...,x_ip);

W = (_ij), элементами которой являются:

- ковариационная матрица.

Содержательно линейное расстояние (1.21) оправдано, например, при многокритериальной оценке качества продукции, при нормировке по эталонам типа z³ (1.14), при определении расстояния между домами по кварталам. С его помощью лучше всего выделяют «плоские» классы, расположенные почти на гиперплоскостях, особенно, если они ортогональны каким-либо координатным осям.

Евклидово расстояние (1.22) является самой популярной метрикой в кластер-анализе. Оно отвечает интуитивным представлениям о близости. Геометрически оно лучше всего объединяет объекты в шарообразных скоплениях, которые типичны для слабо коррелированных совокупностей.

Обобщенное степенное расстояние (1.23) представляет интерес, как математическая универсальная метрика.

Расстояние Махаланобиса является своеобразной конструкцией. Если считать, что все признаки не коррелированны (т.е. _ij=0, ij), то

, где - разница значений i-го признака у 2-х объектов, т.е. на каждой оси расстояние уменьшается пропорционально дисперсии. Это приводит к своеобразному уравниванию признаков, напоминающему процедуру нормирования z¹ (1.12). Другая особенность этого расстояния в его «контекстном» характере. Матрица ковариаций W в формуле (1.23) делает расстояние между двумя точками зависимым от расстояний между другими точками.

Рисунок 1.2 - Общая схема выбора способа измерения близости между объектами

На рисунке 1.2 приведена общая схема определения способа измерения близости между объектами.

1.2.2 Типы методов кластер - анализа. Существует огромное количество алгоритмов кластер - анализа. Они отличаются вычислительными приемами и концепциями [1,6].

Точной постановки задачи кластер - анализа нет. Единая теория находится в стадии становления. Для создания теории необходимо уметь учитывать разные конфигурации точек и предъявляемые к разбиениям требования.

Требования к хорошей классификации формируются двумя способами: в терминах определений отдельных кластеров; в виде некоторого функционала, оптимальное значение которого соответствует лучшей классификации.

Ниже на рисунке приведены сочетания классов на плоскости, которые трудно четко разделить, так как необходимо учитывать разнообразные обстоятельства: расстояние между точками класса C больше, чем межклассовые расстояния некоторых точек в классах В и С, среднее значение в классах Е и F, K и H одинаковы; классы P и Q соединены цепочкой, которую надо выделить.

Рисунок 1.3- Сочетания классов на плоскости

Прежде чем строить теорию, учитывающую подобные конфигурации точек, надо осознать природу требований, предъявленных к разбиениям. Границы классов на рисунке 1.3 приведены именно такими в соответствии с интуитивными представлениями о том, что кластер - скопление точек - представляет собой некоторую целостность (образ), чем-то отличающийся от другого скопления точек. Причем кластеры могут касаться друг друга (B и C, L и M) и пересекаться (K и H). Различать подобные кластеры формальным образом трудно. Это означало бы машинную реализацию чисто человеческого процесса распознавания образов.

40-летние попытки решить задачу «структурной классификации» привели к тому, что традиционную для статистики проблему выделения однородных групп стали называть распознаванием образов без учителя (самообучением).

Основой 1-го направления решения задачи структурной классификации является:

ѕ формулировка понятия кластера в смысле такого скопления точек, которое обладает некоторым свойством, например, в котором среднее межточечное расстояние меньше среднего расстояния от данных точек до остальных;

ѕ разбиение совокупности на части, представляющие собой кластер.

Алгоритмы, ориентированные на кластеры с заранее заданными свойствами, называют процедурами прямой классификации. Сам подход называют эвристическим, но некоторые алгоритмы находят локальный экстремум определенному функционалу.

Требования к хорошей классификации предъявляют не только в терминах определения отдельных кластеров.

Они могут быть сформулированы в виде некоторого функционала, экстремальное значение которого соответствует наилучшей классификации. Это второе - оптимизационное направление. Здесь возникает чисто математические проблемы, определение свойства функционала, путем достижения оптимума, трудоемкости алгоритма. Редко в этих задачах нужен глобальный оптимум.

В кластер - анализе нет четкой связи между функционалом и действительной целью исследователя, так как она не может быть точно сформулирована в условиях исходной неопределенности в данных.

Эти два подхода: прямой и оптимизационный являются разными способами формализации представления о хорошей классификации.

Было выявлено, что некоторые эвристические процедуры оптимизируют определенные функционалы. Резкой границы между подходами нет, наоборот есть предположение, что каждая прямая процедура на самом деле доставляет экстремум какой-то функции, которую надо отыскать. И каждому функционалу соответствует свое определение кластера.

1.2.3 Систематизация алгоритмов. Ее приходится вести по нескольким качественным признакам.

1 Характер отношений, которые отыскиваются как результат классификации.

1.1 Разбиение с непересекающимися классами (отношение эквивалентности). Объекты внутри класса тождественны, объекты разных классов нет.

1.2 Разбиение с пересекающимися классами. Задаются по-разному: введение степени принадлежности объекта к классу в духе теории размытых множеств, определением вероятности принадлежности объекта к классу или перечнем объектов в зоне пересечения.

1.3 Иерархическое дерево

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

2 Степень участия человека в процедуре выделения кластеров.

2.1 Человек не принимает участия в работе алгоритма, т. е. машинным способом получается готовый результат, в процессе работы алгоритма он не вмешивается.

2.2 Человек участвует в процессе получения разбиения. ЭВМ выдает информацию, по которой человек принимает решение о разбиении (Это метод визуализации).

3 Характер априорных сведений (задаваемых параметров) для работы алгоритма.

3.1 Априорные сведения отсутствуют (свободная классификация). Их отсутствие необходимо для выделения естественной, а не навязанной структуры исходных данных. Очень мало таких алгоритмов, они имеют человеко-машинный характер.

3.2 Задано число классов.

3.3 Заданы пороговые значения величины близости объектов (классов).

3.4 Заданы комбинированные сведения (число классов и пороги разных типов).

4 Характер работы алгоритма. По способу построения классов: эталонный и неэталонный. По зависимости от порядка просмотра точек: последовательные и параллельные.

4.1 Остановимся на делении алгоритмов по способу построения кластеров: эталонные и неэталонные. В процедурах эталонного типа на множестве объектов задается несколько эталонов - исходных зон, полей, с которых начинает работу алгоритм. После задания (машинного или человеко-машинного) эталонов алгоритм проводит классификацию, иногда меняя эталоны определенным способом.

Существует множество процедур кластеризации, работающих по иному принципу: иерархические алгоритмы, процедуры диагонализации, разрезание графов.

4.2 Другая особенность алгоритмов - зависимость результатов от порядка просмотра точек. Она характерна для эталонных алгоритмов.

Есть процедуры, зависящие от порядка просмотра, например иерархическая. Задача определения трудоемкости алгоритмов изучена слабо. Общую классификацию процедур на быстры и медленные, требующие большой и малой памяти можно заменить делением на параллельные и последовательные процедуры.

1.2.4 Алгоритмы прямой классификации. Подавляющая часть практических исследований выполнена с помощью этих алгоритмов.

В качестве примера одного из способов точного определения кластеров приведем класс типа сгущения (типа ядра) - компактная группа. Все расстояния между объектами внутри класса меньше любого расстояния между объектами класса и остальной частью множества. С помощью такого определения нельзя различать классы, представленные на рисунке 1-3: разнотипные (B и C), пересекающиеся (К и H), большие и малые (R и Q).

1.2.5 Алгоритм иерархической классификации. Пусть X={X₁, ...,X_n}, где X_i=( xi_(1), ..., xi_(p)) Rp.

Пусть S_i - i-я группа (класс, кластер) объектов, n_i - число объектов, образующих группу S_i, - среднее арифметическое векторных наблюдений, входящих в S_i-ую группу.

На вход агломеративного иерархического алгоритма подается разбиение S⁽⁰⁾= (S₁⁽⁰⁾,..., S_n⁽⁰⁾), где S_i⁽⁰⁾={X_i}. Разбиение k-го уровня имеет вид S^(k)= (S₁^(k),..., S_n-k^(k)) и строится из разбиения S^(k-1), k>1, путем объединения пары классов (S₁^*, S₂^*), где

(S₁^*, S₂^*)=( S₁, S₂) (1.25)

Итоговую иерархию s образует система вложенных разбиений . Здесь S^(n-1)=X.

Отметим, что иерархическая классификация при помощи бинарного алгоритма всегда дает бинарную иерархию. Чаще всего используются в агломеративных алгоритмах следующие меры близости между классами.

Расстояние, измеряемое по приращению статистического разброса при объединении классов

(S₁, S₂)= Q (S₁) - Q (S₁) - Q (S₂), (1.26)

где Q(S)=, Z=-центр класса S, - квадрат евклидова расстояния между X и Z.

Расстояние, измеряемое по принципу «ближнего соседа»

(S_l, S_m)= (1.27)

Расстояние, измеряемое по принципу «дальнего соседа»

(S_l, S_m)= (1.28)

Расстояние, измеряемое по «центрам тяжести групп»

(S_l, S_m)= d (), (1.29)

Отметим, что мера близости (1.26) обладает рядом важных свойств, которые обеспечивают широкое использование ее при решении задач классификации. В то же время расстояние по центрам тяжести (1.29) не обладает такими свойствами.

Результаты работы всех иерархических процедур оформляется в виде дендрограммы (см. рисунок 1.4). По горизонтали показаны номера объектов, а по вертикали - значения межклассовых расстояний.

Рисунок 1.4 - Дендограмма

1.2.6 Алгоритм k-средних. При решении практических задач полезно иметь набор простых быстродействующих алгоритмов классификации для выработки первых представлений о структуре данных в признаковом пространстве. Пусть исходная информация о классифицируемых объектах представлена матрицей «объект-свойство», столбцы которой задают точки p-мерного евклидова пространства.

Опишем один из наиболее известных алгоритмов, использующий понятие центра тяжести, являющийся процедурой параллельной классификации. Единственным управляющим параметром алгоритма k-средних является число классов, на которые проводится разбиение S={S₁ , ... , S_k} выборки X. В результате получается несмещенное разбиение S^*={S₁^* , ... , S_k^*}.

Схема алгоритма

Выберем начальное разбиение S⁰=(S₁⁰,..., S_n⁰), где S_i⁰- {X_i1⁰,..., X_ini⁰}, =0,

Пусть построено m-е разбиение S^m=(S₁^m,..., S_n^m). Вычислим набор средних e^m ={e₁^m,..., e_k^m}, e_i ^m=.

Построим минимальное дистанционное разбиение, порождаемое набором e^m и возьмем его в качестве S^m+1=(S₁^m+1,..., S_n^m+1), т.е.

.....................................................

где - расстояние в p-мерном пространстве R^p.

Если , то переходим к пункту 2, заменив m на m+1, если , то полагаем S^m=S^* и заканчиваем работу алгоритма.

Содержательно процедура алгоритма k-средних направлена на поиск разбиения S^* выборки X с минимальным разбросом.

В ряде случаев начальное разбиение S⁰ как минимальное дистанционное разбиение, порожденное некоторым набором точек e⁰={e₁⁰,..., e_k⁰}. Результат классификации зависит от выбора e⁰. Обычно для проверки устойчивости результата рекомендуется варьировать выбор e⁰.

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 Application

3.1 Описание средств автоматизации непараметрической аппроксимации функции плотности распределения вероятностей

Первоначально перед пользователем стоит выбор решаемой задачи: гистограмма и полигон частот для статистических данных с разбиением на интервалы равной длины (задача 1), гистограмма и полигон частот для статистических данных с разбиением на равнонаполненные интервалы (задача 2), непараметрическая оценка функции плотности распределения вероятности для статистических данных методом прямоугольных вкладов (задача 3).

3.1.1 Описание средств автоматизации равноинтервальной гистограммы и полигона частот. Действия, которые производит построенный макрос для гистограммы и полигона частот для статистических данных с разбиением на интервалы равной длины, разбиты на 4 этапа.

Этап 1. Ввод объема выборки и количества интервалов. Первоначально пользователю следует ввести информацию об объеме выборки и количестве интервалов, на которое следует разбить отрезок, в ячейки С16 и С17 соответственно. В случае если пользователь не произвел эти действия, выводится предупреждающее сообщение о необходимости ввода этих данных.

Этап 2. Сортировка данных по возрастанию. Для определения концов отрезка, в который попадают все элементы выборки, необходима сортировка выборки по возрастанию. Для продолжения дальнейшего исследования в макросе предусмотрена реализация этих действий.

Этап 3. Нахождение шага разбиения отрезка. После определения концов отрезка в макросе происходит нахождение шага разбиения отрезка на отрезки равной длины по формуле h=(b-a)/N, где b- конец отрезка, a - начало отрезка, N - число отрезков.

Этап 3. Нахождение значений для функции распределения. Значения для функции распределения в макросе находятся по формуле , где m_i-- число наблюдений, попавших в интервал .

Этап 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. Определение «ядерной» аппроксимации функции плотности распределения. Значения для «ядерной» аппроксимации функции плотности распределения в макросе находятся по формуле

где - количество точек исходной выборки, попавших в интервал .

Этап 5. Занесение значения для абсцисс и ординат равноинтервальной гистограммы и полигона частот на рабочий лист. Для наглядного изображения равноинтервальной гистограммы и полигона частот на рабочий лист выводятся данные по значению абсцисс и ординат, по которым будет вестись дальнейшее построение.

Полный текст макроса приведен в приложении Г.

3.2 Описание средств автоматизации параметрической аппроксимации функции плотности распределения вероятностей на основе нормальной вероятностной бумаги

Действия, которые производит построенный макрос, разбиты на 4 этапа.

Этап 1. Очищение ячеек с ранее полученными оценками значений для м и у. Макрос необходим для проверки правильности выполнения работ с различными первоначальными данными ряда наблюдений, по которым в дальнейшем производится оценка значений для м и у. Поэтому разработанный макрос для удобства использования производит очищение ячеек с ранее полученными значениями.

Этап 2. Заполнение столбца с порядковым номером i членов вариационного ряда наблюдений. Первоначально дан упорядоченный по возрастанию ряд наблюдений . Для каждого члена исходного ряда в ячейки (C2:CN+1) заносится значение i, соответствующее порядковому номеру данного элемента.

Этап 3. Заполнение столбца с оценкой для функции распределения F(t). За оценку функции распределения F(t) принимают:. Значение для функции распределения членов ряда наблюдений, принятой данной оценкой, заносится в ячейки (D2:DN+1).

Этап 4. Вывод уравнения прямой, вдоль которой ложатся точки (x_i,V_i). Для построения прямой программа находит значение максимального и минимального элементов ряда наблюдений и, для более простого обращения к ним в случае необходимости, происходит размещение этих значений в ячейки G2 и G3 соответственно.

Для максимального и минимального элементов находятся соответствующие значения функции , где Ф()-стандартная функция нормального распределения. Для простоты дальнейших вычислений полученные значения функции для максимального и для минимального элемента заносятся в ячейки G3 и в G4 соответственно.

По двум известным точкам происходит вывод уравнения прямой, вдоль которой ложатся точки (x_i,V_i). Таким образом, искомое уравнение имеет вид:

,

где max,min - максимальный и минимальный элементы ряда наблюдений, v_min, v_max - соответствующие им значения функции V.

Этап 5. Оценка для параметров м и у. В качестве оценки м берётся медиана выборки, соответствующая вероятности p=0,5. Для определения значения м в полученное уравнение прямой подставляем значение y=0,5, и получаем точку x_0,5, дающую нам искомую оценку для математического ожидания м. Найденное значение м для лучшей наглядности помещается в ячейку G7.

Оценка для стандартного отклонения выглядит следующим образом:

,

где x_0,84 - оценка 0,84 квантиля распределения, полученного при V=1. Она производится следующими действиями.

Первоначально находится значение x_0,84 в результате подстановки в полученное уравнение прямой y=0,84. у в данном случае определяется как разность между x_0,84 и ранее полученным значением математического ожидания м. Найденное в результате значение для лучшего восприятия заносится в ячейку G8.

Полный текст макроса приведен в приложении Б.

3.3 Описание средств автоматизации алгоритма прямой классификации

Разработанные средства автоматизации алгоритма прямой классификации предназначены для использования в процессе изучения студентами азов теории классификации. Они ориентированы на выработку у студентов интуиции о влиянии характера исходных данных, а также способов измерения близости между объектами и типе нормировки на результат классификации.

Диалог с пользователем осуществляется при помощи пользовательской формы. При нажатии на соответствующие кнопки формы, происходит выполнение необходимых вычислений. Действия, которые производят разработанные макросы для кнопок, разбиты на 5 этапов.

Этап 1. Генерация выборки. Для изучения влияния характера исходных данных на результат классификации используется генерация псевдослучайных величин средствами Excel.

С помощью генератора случайных чисел можно построить последовательности с нормальным распределением. Очень многие модели, построенные с помощью этого распределения, хорошо соответствуют действительности. Чтобы построить последовательность значений нормально распределенной случайной величины, необходимо задать математическое ожидание и дисперсию.

Чтобы сгенерировать последовательность, необходимо воспользоваться функцией из встроенного пакета анализа данных:

1 Выбрать команду Сервис, Анализ данных (Tools, Data Analysis). Появляется диалоговое окно Анализ данных

2 Выбрать пункт Генерация случайных чисел (Random Number Generation). Появляется диалоговое окно Генерация случайных чисел.

3 Выбрать Нормальное распределение в списке Распредеение (Distribution).

4 Ввести число 3 в поле Число переменных (Number of Variables), что означает число столбцов, которые заполнены последовательностью.

5 Ввести число 20 в поле Число случайных чисел (Number Random Numbers), т. е. последовательность занимает 20 строк.

6 Нажать кнопку ОК. Если указанный на рабочем листе диапазон содержит другие данные, появится окно сообщения, где необходимо будет подтвердить замену данных.

Excel создаст последовательность.

Первая половина выборки в разработанном макросе сгенерирована случайным образом из нормального распределения с параметрами математическое ожидание 0 и дисперсия 1 (м = 0, у = 1).

Вторая половина выборки сгенерирована случайным образом из нормального распределения с параметрами математическое ожидание 2 и дисперсия 1 (м = 2, у = 1).

Замечание. Для изменения исходных параметров в теле макроса делаются корректировки. Например, для математического ожидания со значением 0 дисперсии со значением 1 данный фрагмент реализации в макросе выглядит следующим образом:

For i = 1 To m

Randomize

Cells(i + 1, 1) = RndN(0, 1)

Next i

For i = 1 To m

Randomize

Cells(i + 1, 2) = RndN(0, 1)

Next i

For i = 1 To m

Randomize

Cells(i + 1, 3) = RndN(0, 1)

Next i

Этап 2. Рабочие расчеты. Для классификации необходимо провести дополнительные рабочие расчеты, как-то: вычисление максимальных и средних элементов выборки, нормировка выборки.

Первоначально каждый объект заданной совокупности описан тремя признаками по двадцать элементов каждый.

Для каждых членов исходных рядов в ячейки D4, E4, F4 заносятся значения, соответствующие средним значениям.

Для каждых членов исходных рядов в ячейки D7, E7, F7 заносятся значения, соответствующие максимальным значениям.

В процессе исследования в качестве нормировок были выбраны две.

Первая из них вычисляется по формуле , вторая по формуле .

Этап 3 Расчет матриц расстояний. В качестве определения расстояния между объектами выбраны линейное и евклидово расстояния.

Этап 4 Выделение 2 классов, вывод промежуточных результатов. На этом этапе производится выделение двух классов для построенных на первом этапе исходных данных.

Начальное разбиение выборки задается двумя способами. Первый способ заключается в том, что первая половина элементов выборки принимается за первый класс, а вторая - за второй. Второй способ разбиения заключается в том, что в первый класс будут входить нечетные элементы выборки, а во второй - четные. На рабочем листе при помощи макроса реализованы следующие действия: отображено первоначальное разбиение выборки на 2 класса, промежуточные результаты по работе макроса, будет отображение конечного результата разбиения выборки на два класса. По полученным разбиениям построены графики, наглядно изображающие два класса.

Этап 5 Очищение ячеек. Начальные данные, вводимые для исследования, всегда различны. Поэтому на пользовательской форме предусмотрена кнопка, выполняющая полную очистку ячеек с ранее полученными результатами.

Полный текст макроса приведен в приложении В.

4 Апробация средств автоматизации в виде макросов

4.1 Апробация программного обеспечения средствами встроенного пакета анализа данных Excel

4.1.1 Апробация программного обеспечения алгоритма прямой классификации. Входные данные для апробации алгоритма классификации генерируются с помощью макроса, реализованного в виде кнопок: «Генерация 1 выборки», «Генерация 2 выборки» (рисунок 4.1). При необходимости изменения параметров выборок их можно изменить внутри макроса.

Рисунок 4.1 - Кнопки «Генерация 1 выборки» и «Генерация 2 выборки»

На начальном этапе построения алгоритма простой классификации в кластерном анализе ставится задача определения средних и максимальных значений среди элементов выборки и способа нормировки [1]. Для этой цели в Excel разработана кнопка «Рабочие расчеты» на пользовательской форме (см. рисунок 4.2). Для этой кнопки написан макрос, который выполняет поставленную задачу.