Пояснительная записка (1218768), страница 3

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

Текст из файла (страница 3)

где – исправленная выборочная дисперсия, и

Описанную случайную величину заключим в следующий интервал:

где – процентная точка (процентиль) t-распределения Стьюдента с степенями свободы [12].

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

Таким образом, можно построить интервал для математического ожидания:

В случае, если генеральная совокупность состоит из элементов, и объем извлекаемой из нее выборки больше, чем , то при вычислении границ доверительного интервала математического ожидания необходимо ввести поправочный коэффициент [12].

2.5 Кластерный анализ

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

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

Кластер представляет подмножество объектов или переменных, которое выделяется из общих данных наличием среди его элементов некоторой однородности (некоторого сходства). В простейшем случае речь идет о похожести элементов, в идеальном случае – о совпадающих значениях основных переменных или иного рода близости [13].

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

Кластерный анализ позволяет выполнять следующие задачи [14]:

– создание классификации, типологии;

– изучение оптимальных схем группировки объектов;

– разработка гипотез, основанная на изучении данных;

– проверка разработанных гипотез или результатов исследования.

В рамках проведения кластеризации данных выделяется несколько этапов, схожих для различных задач:

– создание выборки объектов, которые необходимо разбить на отдельные группы;

– создание пространства признаков, на основе которых будет приниматься решение о принадлежности того или иного объекта выделяемым кластерам;

– оценка количественного значения выбранной меры сходства объектов (в некоторых случаях – меры различия);

– использование выбранного метода кластеризации для группировки сходных объектов;

– оценка качества результирующего решения.

К данным, к которым применяется какой-либо метод кластеризации, предъявляются два основных требования: все объекты, подвергаемые кластеризации, должны описываться единым набором характеристик, иметь одну природу, и совокупность этих объектов должна обладать свойством полноты, то есть ее составляющие должны отражать все или же наиболее важные свойства описываемого ими явления или сущности [15].

Алгоритмы кластеризации работают с данными, которые можно разделить на следующие типы [15]:

– признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками. Признаки могут быть числовыми или нечисловыми;

– матрица расстояний между объектами. Каждый объект описывается расстояниями до всех остальных объектов метрического пространства;

– матрица сходства между объектами. Учитывается степень сходства объекта с другими объектами выборки в метрическом пространстве.

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

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

– уменьшение количества данных: в случае избыточности входной выборки, кластеризация позволяет сократить количество входящих в нее объектов, оставив наиболее типичных представителей выделенных кластеров;

– обнаружение нетипичных объектов: их не удается отнести к какому-либо кластеру.

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

2.6 Формальная постановка задачи кластеризации

Для формализации задачи кластеризации необходимо ввести несколько обозначений: множество кластеризуемых объектов обозначим как , а множество меток кластеров – . Расстояние между объектами оценивается посредством функции . – это обучающая выборка объектов, которую необходимо разбить на кластеры. При этом, каждый итоговый кластер должен состоять из объектов, близких по метрике . Объекты разных кластеров должны существенно различаться по той же метрике. В результате разбиения каждому объекту ставится в соответствие номер кластера [16].

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

Отличие кластеризации от классификации заключается в том, что при кластеризации метки изначально не заданы [17].

Для установления меры близости точек-данных друг к другу при кластеризации могут быть использованы следующие функции расстояния:

– метрика Хэмминга:

где Данная метрика отражает количество несовпадающих координат векторов;

– евклидова метрика:

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

– взвешенная евклидова метрика:

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

– метрика Минковского:

где – это порядок функции.

Следует отметить, что если параметр в приведенной выше функции расстояния будет равен 1, то эта функция будет называться расстоянием городских кварталов или же Манхэттенским расстоянием [17]:

где – векторы.

Если же параметр будет равен 2, то функция, описывающая метрику Минковского, примет вид евклидового расстояния (8).

Неоднозначность решения задачи кластеризации определяется рядом причин, среди которых выделяют [17]:

– отсутствие критерия, который бы однозначно определял наилучшее качество кластеризации. Несмотря на наличие целого ряда эвристических критериев, а также алгоритмов, в основе которых не определен ни один четкий критерий, и которые, при этом осуществляют достаточно разумную кластеризацию. Данная задача все еще требует наличия эксперта в исследуемой предметной области для анализа полученных результатов;

– заранее неизвестное число кластеров. Количество кластеров, необходимое для решения той или иной задачи, устанавливается исследователем на основе определенного субъективного критерия;

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

2.7 Методы кластеризации

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

По способу обработки данных выделяют:

– иерархические методы;

– неиерархические методы.

Суть иерархической кластеризации состоит в последовательном объединении меньших кластеров в большие или разделении больших кластеров на меньшие. Существует ряд недостатков методов этой группы [17]:

– ограниченный объем входных данных;

– необходимость выбора меры близости.

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

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

По способу анализа данных выделяют:

– нечеткие методы;

– четкие методы.

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

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

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

2.7.1 Метод k-means

Метод k-means (k-средних) – один из наиболее популярных алгоритмов кластеризации, является неиерархическим.

Данный метод позволяет разделить объекты на заранее определенное количество кластеров в соответствии с критерием, который представляет статистику Фишера: отношение межкластерной дисперсии к внутрикластерной [18].

Разделение объектов на кластеры методом k-means осуществляется таким образом, чтобы объекты, принадлежащие одному и тому же кластеру, были расположены близко друг к другу в пространстве переменных, а принадлежащие разным кластерам – далеко.

В процессе работы алгоритм стремится минимизировать суммарное отклонение точек кластеров от центроидов этих кластеров:

Характеристики

Список файлов ВКР