Задача кластеризации зерен пшеницы

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева»

Институт информатики и телекоммуникаций

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

Курсовая работа

по дисциплине «Кластерный анализ»

на тему:

Выполнил: студенты группы БС-91

очной формы обучения

Ломаев Юрий Сергеевич

Куприн Артём Геннадьевич

Проверил: профессор кафедры САиИО

Попов Евгений Александрович

Красноярск 2012 г.

Содержание

1. Постановка задачи

2. Описание алгоритмов

3. Реализация

4. Результаты исследований

5. Список литературы

1. Постановка задачи

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

Рассматриваемая группа содержала зёрна, принадлежащие к различным сортам пшеницы. Высокое качество визуализации внутренней структуры зёрен было получено при помощи рентгеновской техники. Этот метод значительно дешевле, чем другие более сложные методы визуализации, такие как сканирующая микроскопия или лазерные технологии. Изображения зёрен пшена были записаны на рентгеновские пластины KODAK размерностью 13х18 см. Исследования проводились с использованием объединенного рассмотрения собранных зёрен пшеницы, произрастающих на опытных полях в Институте Агрофизики Польской академии наук в Люблине. Набор данных может быть использован для задач классификации и кластерного анализа.

Рис.1. Зёрна пшена на рентгеновской пластине

Характеристики (атрибуты):

Для формирования данных были измерены 7 геометрических параметров зёрен пшена:

1) область расположения зёрен;

2) длина зерна;

3) ширина зерна;

4) периметр P;

5) компактность C = ;

6) коэффициент асимметрии;

7) длина зернового просвета.

Все эти параметры - вещественные и непрерывные.

2. Описание алгоритмов

А) Агломеративный алгоритм иерархической классификации

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

где (S₁^*, S₂^*) = (S₁^*, S₂^*).

Результатом работы агломеративного алгоритма является система вложенных разбиений S⁽⁰⁾ S⁽¹⁾ S⁽²⁾ … S^(n-1) множества объектов X, где S^(n-1) = X и S^(k) = (S₁^(k), S₂^(k), …, S_n-k^(k)) - разбиение k-го уровня.

В случае иерархической классификации подходящий результат классификации можно выбрать, анализируя дендрограмму - графическую иллюстрацию иерархии. Дендрограмма - оцифрованный граф иерархии. На одной из осей графика отложено значение индексации графа иерархии, вдоль другого направления отображается структура образовывающихся в результате попарного слияния подмножеств разбиений. При этом любое сечение линией v = const, где v - индексация, есть разбиение. Хорошей классификацией можно считать разбиение, которое получается в области значений v, соответствующее большому его скачку до получения нового разбиения. Иерархическая классификация с помощью бинарного алгоритма всегда даёт бинарную иерархию.

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

Б) Параллельный алгоритм k-средних

Параллельные процедуры - это процедуры, в которых вся выборка сразу поступает на классификацию.

В алгоритме k-средних единственным управляющим параметром является число классов, на которые производится разбиение S = (S₁, S₂, …, S_k) выборки Х. В результате получается несмещённое разбиение S^* = (S₁^*, S₂^*, …, S_k^*).

I) Выберем начальное разбиение S⁰ = (S₁⁰, S₂⁰, …, S_k⁰), где S_l⁰ = (), , = , l ?l'.

II) Пусть построено m-е разбиение S^m = (S₁^m, S₂^m, …, S_k^m). Вычислим набор средних e^m = (e₁^m, e₂^m, …, e_k^m), где

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

……………………………………………

, где d(X, e) = ||X - e|| - расстояние в R^p.

IV) Если S^m+1? S^m, то переходим к пункту 2, заменив m на m+1.

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

Введём расстояние d(X, e) от точки X R^p до множества e = (e₁, …, e_k), где e_j R^p по формуле: Тогда можно рассмотреть статистический выброс выборки X относительно множества

e = (e₁, …, e_k): F(X,e) = .

Определим статистический выброс F(S) разбиения S = (S₁, …, S_k) выборки X как разброс этой выборки относительно множества

e(S) = (e₁(S), …, e_k(S)), где e_j(S) - средний вектор класса S_j, т.е. полагается, что F(S) = F(X, e(S)). Непосредственно из построения минимального дистанционного разбиения следует формула:

F(S) = .

Так как на последовательности разбиений S⁰, S¹, …, S^m, …, которая строится в алгоритме k-средних, функционал F(S) не возрастает, то для любого начального разбиения алгоритм через конечное число шагов заканчивает работу.

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

В) Параллельный эвристический алгоритм k-эталонов

Пусть для классификации имеется выборка O₁, O₂,…, O_n, причем i-ый объект характеризуется вектором признаков Х_i = (x₁, x₂, …, x_p). Рассмотрим р-мерное признаковое пространство вместе с функцией d(X_i, X_l), задающей в R^p расстояние (либо степень близости).

I) Выберем k эталонов X₁^*, X₂^*,…, X_k^* и порог d₀.

II) Поставим в соответствие объекту О_i код из k двоичных символов е_i = (е_i¹, е_i², …, е_i^k), где е_i^l = 1, если d(X_i, X_l) ? d₀, и е_i^l = 0 в противном случае.

Разобьем выборку на классы, отнесся к одному из классов объекты с одинаковым кодом. В зависимости от порога d₀ и геометрии выборки число классов может варьироваться от 1 до 2^k. После анализа разбиения выборки на классы исследователь может уточнить выбор эталонов и перейти к следующей итерации алгоритма. Набор эталонов можно составлять из случайно выбранных точек.

Г) Метод главных компонент: аппроксимация данных линейными многообразиями

Метод главных компонент применяется к данным, записанным в виде матрицы X - прямоугольной таблицы чисел размерностью I строк и J столбцов.

Рис.2. Матрица данных

Традиционно строки этой матрицы называются образцами. Они нумеруются индексом i, меняющимся от 1 до I. Столбцы называются переменными, и они нумеруются индексом j= 1, …, J.

Цель МГК - извлечение из этих данных нужной информации. Что является информацией, зависит от сути решаемой задачи. Данные могут содержать нужную нам информацию, они даже могут быть избыточными. Однако, в некоторых случаях, информации в данных может не быть совсем.

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

Передадим суть метода главных компонент, используя интуитивно-понятную геометрическую интерпретацию. Начнем с простейшего случая, когда имеются только две переменные x₁ и x₂. Такие данные легко изобразить на плоскости.

Рис. 3. Графическое представление двумерных данных

Каждой строке исходной таблицы (т.е. образцу) соответствует точка на плоскости с соответствующими координатами. Они обозначены пустыми кружками на Рис. 3. Проведем через них прямую, так, чтобы вдоль нее происходило максимальное изменение данных. На рисунке эта прямая выделена синим цветом; она называется первой главной компонентой. Затем спроецируем все исходные точки на эту ось. Получившиеся точки закрашены красным цветом. Теперь можно сделать предположение, что на самом деле все экспериментальные точки и должны были лежать на этой новой оси. Просто какие-то неведомые силы отклонили их от правильного, идеального положения. Тогда все отклонения от новой оси можно считать шумом, т.е. ненужной нам информацией. Проверить шум ли это, или все еще важная часть данных, можно поступив с этими остатками так же, как поступили с исходными данными - найти в них ось максимальных изменений. Она называется второй главной компонентой. И так надо действовать, до тех пор, пока шум уже не станет действительно шумом, т.е. случайным хаотическим набором величин.

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

1. Ищется центр облака данных, и туда переносится новое начало координат - это нулевая главная компонента (синяя точка на рис.4).

2. Выбирается направление максимального изменения данных - это первая главная компонента.

3. Если данные описаны не полностью (шум велик), то выбирается еще одно направление - перпендикулярное к первому, так чтобы описать оставшееся изменение в данных и т.д.

Рис. 4. Графическое представление метода главных компонент

МГК начинался с задачи наилучшей аппроксимации конечного множества точек прямыми и плоскостями. Пусть дано конечное множество векторов x₁, x₂,…, x_m Rⁿ. Для каждого k = 0, 1, …, n - 1 среди всех k-мерных линейных многообразий в Rⁿ найти такое L_k Rⁿ, что сумма квадратов уклонений x_I от L_k минимальна:

где - евклидово расстояние от точки до линейного многообразия. Всякое k-мерное линейное многообразие в Rⁿ может быть задано множеством линейных комбинаций L_k = , где b_i пробегают вещественную прямую R, a₀ Rⁿ , - ортонормированный набор векторов. В координатной форме:

Решение задачи аппроксимации для k = 0,1, …, n - 1 даётся набором вложенных линейных многообразий L₀ L₁ L₂ … L_n-1. Эти линейные многообразия определяются ортонормированным набором векторов (векторами главных компонент) и вектором a₀:

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

1) централизуем данные: . Теперь ;

2) находим первую главную компоненту как решение задачи:

Если решение не единственно, то выбираем одно из них.

3) Вычитаем из данных проекцию на первую главную компоненту:

;

4) Находим вторую главную компоненту как решение задачи:

Если решение не единственно, то выбираем одно из них.

2k-1) Вычитаем проекцию на (k-1)-ую главную компоненту:

;

2k) находим k-ую главную компоненту:

геометрический зерно пшеница кластеризация

Если решение не единственно, то выбирается одно из них.

Д) Полный градиентный алгоритм кластеризации

Первоначально считаем, что существует набор m-элементов n-мерного пространства: x₁, x₂, …, x_m Rⁿ. Будем считать, что случайная выборка получена из n-мерной случайной величины X с плотностью распределения f. Оценка плотности распределения рассматривается как:

,

где h - коэффициент размытости, x_i - экспериментальная точка из выборки, - гауссово ядро.

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

, для j = 1,…, m.

,

где k = 0, …, k^*, b > 0, , z - шаг, k^* - число шагов.

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

· построить оценку ;

· сформулировать критерий остановки(число k^*);

· определить процедуры для создания кластеров и назначение им конкретных элементов множества;

· анализ влияния значений параметров на полученный результат.

Критерий остановки - алгоритм должен быть остановлен после того, как выполняется условие на k-м шаге:

, где a₀ > 0 и

,

, где d(.) - Евклидова метрика в Rⁿ.

D₀, D_k-1, D_k - сумма расстояний между отдельными элементами множества.

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

, состоящего из элементов множества после k-го шага.

После этого формируется набор взаимных расстояний из вышеперечисленных элементов:

, где i = 1, …, m-1; j = 1, …, m.

Их размерность задаётся как .

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

D = max , i = 1, …, m-1; j = 1, …, m.

Для этой цели рассчитывается величина стандартного отклонения на основе найденного набора взаимных расстояний, после чего значение элемента выбирается из множества, где - целая часть числа 100D до нахождения первого (наименьшего) из них, удовлетворяющего условию:

> и

Размещено на Allbest.ru