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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


курсовая работа Методы кластеризации. Алгоритм Forel

Информация:

Тип работы: курсовая работа. Добавлен: 06.09.2012. Сдан: 2012. Страниц: 8. Уникальность по antiplagiat.ru: < 30%

Описание (план):


     СОДЕРЖАНИЕ 

     ВВЕДЕНИЕ……………………………………………………………….4
     1 ПРЕДМЕТ КЛАСТЕРНОГО АНАЛИЗА…………………………..…5
     2 ПРИМЕНЕНИЕ КЛАСТЕРНОГО АНАЛИЗА…………………….…9
     3 МЕТОДЫ КЛАСТЕРНОГО АНАЛИЗА…………….…………….…16

     4 АЛГОРИТМ FOREL……………………………………………….…..18

         4.1 Принцип работы алгоритма FOREL……………………...…19

         4.2 Процедура, реализующая алгоритм  FOREL………………..25
      ЗАКЛЮЧЕНИЕ………………………………………………….……....28
     СПИСОК  ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ……………………….29 
 
 
 
 
 

 


     ВВЕДЕНИЕ
     Кластерный  анализ  (англ. Data clustering) –задача разбиения заданной выборки объектов (ситуаций) на подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались. Задача кластеризации относится к статистической обработке, а также к широкому классу задач обучения без учителя.
     В настоящее время кластерный анализ является наиболее актуальным направлением статистических исследований. С помощью  методов кластерного анализа  происходит обнаружение новизны  в данных, понимание данных и сжатие данных.
     В данном курсовом проекте рассмотрены  общие методы кластеризации и  подробно рассмотрен и реализован алгоритм кластеризации FOREL.
 


     1 ПРЕДМЕТ КЛАСТЕРНОГО АНАЛИЗА
     Кластерный  анализ – это многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы (кластеры) (Q-кластеризация, или Q-техника, собственно кластерный анализ). Кластер –группа элементов, характеризуемых общим свойством, главная цель кластерного анализа–нахождение групп схожих объектов в выборке. Спектр применений кластерного анализа очень широк: его используют в археологии, медицине, психологии, химии, биологии, государственном управлении, филологии, антропологии, маркетинге, социологии и других дисциплинах. «Тематика исследований варьирует от анализа морфологии мумифицированных грызунов в Новой Гвинее до изучения результатов голосования сенаторов США, от анализа поведенческих функций замороженных тараканов при их размораживании до исследования географического распределения некоторых видов лишая в Саскачеване». Однако универсальность применения привела к появлению большого количества несовместимых терминов, методов и подходов, затрудняющих однозначное использование и непротиворечивую интерпретацию кластерного анализа.
     Задачи и условия
     Кластерный  анализ выполняет следующие основные задачи:
    Разработка типологии или классификации.
    Исследование полезных концептуальных схем группирования объектов.
    Порождение гипотез на основе исследования данных.
    Проверка гипотез или исследования для определения, действительно ли типы (группы), выделенные тем или иным способом, присутствуют в имеющихся данных.
     Независимо  от предмета изучения применение кластерного  анализа предполагает следующие этапы:
    Отбор выборки для кластеризации.
    Определение множества переменных, по которым будут оцениваться объекты в выборке.
    Вычисление значений той или иной меры сходства между объектами.
    Применение метода кластерного анализа для создания групп сходных объектов.
    Проверка достоверности результатов кластерного решения.
     Кластерный анализ предъявляет следующие требования к данным:
    показатели не должны коррелировать между собой;
    показатели должны быть безразмерными;
    распределение показателей должно быть близко к нормальному;
    показатели должны отвечать требованию «устойчивости», под которой понимается отсутствие влияния на их значения случайных факторов;
    выборка должна быть однородна, не содержать «выбросов».
     Если  кластерному анализу предшествует факторный анализ, то выборка не нуждается в «ремонте» – изложенные требования выполняются автоматически самой процедурой факторного моделирования (есть ещё одно достоинство–z-стандартизация без негативных последствий для выборки; если её проводить непосредственно для кластерного анализа, она может повлечь за собой уменьшение чёткости разделения групп). В противном случае выборку нужно корректировать.
     Задача  кластерного анализа заключается  в том, чтобы на основании данных, содержащихся во множестве Х, разбить  множество объектов G на m (m – целое) кластеров (подмножеств) Q1, Q2, …, Qm, так, чтобы каждый объект Gj принадлежал одному и только одному подмножеству разбиения и чтобы объекты, принадлежащие одному и тому же кластеру, были сходными, в то время, как объекты, принадлежащие разным кластерам были разнородными.
     Например, пусть G включает n стран, любая из которых характеризуется ВНП на душу населения (F1), числом М автомашин на 1 тысячу человек (F2), душевым потреблением электроэнергии (F3), душевым потреблением стали (F4) и т.д. Тогда Х1 (вектор измерений) представляет собой набор указанных характеристик для первой страны, Х2 - для второй, Х3 для третьей, и т.д. Задача заключается в том, чтобы разбить страны по уровню развития.
     Решением  задачи кластерного анализа являются разбиения, удовлетворяющие некоторому критерию оптимальности. Этот критерий может представлять собой некоторый  функционал, выражающий уровни желательности  различных разбиений и группировок, который называют целевой функцией. Например, в качестве целевой функции  может быть взята внутригрупповая  сумма квадратов отклонения:
     
     где xj - представляет собой измерения j-го объекта.
     Для решения задачи кластерного анализа необходимо определить понятие сходства и разнородности.
     Понятно то, что объекты i-ый и j-ый попадали бы в один кластер, когда расстояние (отдаленность) между точками Хi и Хj было бы достаточно маленьким и попадали бы в разные кластеры, когда это расстояние было бы достаточно большим. Таким образом, попадание в один или разные кластеры объектов определяется понятием расстояния между Хi и Хj из Ер, где Ер - р-мерное евклидово пространство. Неотрицательная функция d(Хi , Хj) называется функцией расстояния (метрикой), если:
     а) d(Хi , Хj) ? 0, для всех Хi и Хj из Ер
     б) d(Хi, Хj) = 0, тогда и только тогда, когда Хi = Хj
     в) d(Хi, Хj) = d(Хj, Хi)
     г) d(Хi, Хj) ? d(Хi, Хk) + d(Хk, Хj), где Хj; Хi и Хk - любые три вектора из Ер.
     Значение d(Хi, Хj) для Хi и Хj называется расстоянием между Хi и Хj и эквивалентно расстоянию между Gi и Gj соответственно выбранным характеристикам (F1, F2, F3, ..., Fр).
     Наиболее  часто употребляются следующие  функции расстояний:
     1. Евклидово расстояние   d2(Хi , Хj) =
     2. l1 - норма    d1(Хi , Хj) =
     3. Сюпремум - норма   d? (Хi , Хj) = sup
     k = 1, 2, ..., р
     4. lp - норма    dр(Хi , Хj) =
     Евклидова метрика является наиболее популярной. Метрика l1 наиболее легкая для вычислений. Сюпремум-норма легко считается  и включает в себя процедуру упорядочения, а lp - норма охватывает функции расстояний 1, 2, 3,.
     Пусть n измерений Х1, Х2,..., Хn представлены в виде матрицы данных размером p ? n:
     
     Тогда расстояние между парами векторов d(Хi , Хj) могут быть представлены в виде симметричной матрицы расстояний:
     
     Понятием, противоположным расстоянию, является понятие сходства между объектами Gi. и Gj. Неотрицательная вещественная функция S(Хi ; Хj) = Sij называется мерой сходства, если :
     1) 0? S(Хi , Хj)<1 для Хi ? Хj
     2) S(Хi , Хi) = 1
     3) S(Хi , Хj) = S(Хj , Хi)
     Пары  значений мер сходства можно объединить в матрицу сходства: 

     
     Величину Sij называют коэффициентом сходства.
     2 ПРИМЕНЕНИЕ КЛАСТЕРНОГО АНАЛИЗА
     Рассмотрим  некоторые приложения кластерного  анализа.
     Деление стран на группы по уровню развития.
     Изучались 65 стран по 31 показателю (национальный доход на душу населения, доля населения  занятого в промышленности в %, накопления на душу населения, доля населения, занятого в сельском хозяйстве в %, средняя  продолжительность жизни, число  автомашин на 1 тыс. жителей, численность  вооруженных сил на 1 млн. жителей, доля ВВП промышленности в %, доля ВВП  сельского хозяйства в %, и т.д.)
     Каждая  из стран выступает в данном рассмотрении как объект, характеризуемый определенными  значениями 31 показателя. Соответственно они могут быть представлены в  качестве точек в 31-мерном пространстве. Такое пространство обычно называется пространством свойств изучаемых  объектов. Сравнение расстояния между этими точками будет отражать степень близости рассматриваемых стран, их сходство друг с другом. Социально-экономический смысл подобного понимания сходства означает, что страны считаются тем более похожими, чем меньше различия между одноименными показателями, с помощью которых они описываются.
     Первый  шаг подобного анализа заключается  в выявлении пары народных хозяйств, учтенных в матрице сходства, расстояние между которыми является наименьшим. Это, очевидно, будут наиболее сходные, похожие экономики. В последующем  рассмотрении обе эти страны считаются  единой группой, единым кластером. Соответственно исходная матрица преобразуется  так, что ее элементами становятся расстояния между всеми возможными парами уже  не 65, а 64 объектами – 63 экономики  и вновь преобразованного кластера – условного объединения двух наиболее похожих стран. Из исходной матрицы сходства выбрасываются  строки и столбцы, соответствующие  расстояниям от пары стран, вошедших в объедение, до всех остальных, но зато добавляются строка и столбец, содержащие расстояние между кластером, полученным при объединении и прочими  странами.
     Расстояние  между вновь полученным кластером  и странами полагается равным среднему из расстояний между последними и двумя странами, которые составляют новый кластер. Иными словами, объединенная группа стран рассматривается как целое с характеристиками, примерно равными средним из характеристик входящих в него стран.
     Второй  шаг анализа заключается в  рассмотрении преобразованной таким  путем матрицы с 64 строками и столбцами. Снова выявляется пара экономик, расстояние между которыми имеет наименьшее значение, и они, так же как в  первом случае, сводятся воедино. При  этом наименьшее расстояние может оказаться как между парой стран, так и между какой-либо страной и объединением стран, полученным на предыдущем этапе.
     Дальнейшие  процедуры аналогичны описанным  выше: на каждом этапе матрица преобразуется  так, что из нее исключаются два  столбца и две строки, содержащие расстояние до объектов (пар стран  или объединений – кластеров), сведенных воедино на предыдущей стадии; исключенные строки и столбцы  заменяются столбцом и строкой, содержащими расстояния от новых объединений до остальных объектов; далее в измененной матрице выявляется пара наиболее близких объектов. Анализ продолжается до полного исчерпания матрицы (т. е. до тех пор, пока все страны не окажутся сведенными в одно целое). Обобщенные результаты анализа матрицы можно представить в виде дерева сходства (дендограммы), подобного описанному выше, с той лишь разницей, что дерево сходства, отражающее относительную близость всех рассматриваемых нами 65 стран, много сложнее схемы, в которой фигурирует только пять народных хозяйств. Это дерево в соответствии с числом сопоставляемых объектов включает 65 уровней. Первый (нижний) уровень содержит точки, соответствующие каждых стране в отдельности. Соединение двух этих точек на втором уровне показывает пару стран, наиболее близких по общему типу народных хозяйств. На третьем уровне отмечается следующее по сходству парное соотношение стран (как уже упоминалось, в таком соотношении может находиться либо новая пара стран, либо новая страна и уже выявленная пара сходных стран). И так далее до последнего уровня, на котором все изучаемые страны выступают как единая совокупность.
     В результате применения кластерного  анализа были получены следующие  пять групп стран:
      афро-азиатская группа;
      латино-азиатская группа;
      латино-среднеземнаморская группа;
      группа развитых капиталистических стран (без США)
      США
     Введение  новых индикаторов сверх используемого  здесь 31 показателя или замена их другими, естественно, приводят к изменению  результатов классификации стран.
     2. Деление стран по критерию  близости культуры.
     Как известно маркетинг должен учитывать  культуру стран (обычаи, традиции, и  т.д.).
     Посредством кластеризации были получены следующие  группы стран:
      арабские;
      ближневосточные;
      скандинавские;
      германоязычные;
      англоязычные;
      романские европейские;
      латиноамериканские;
      дальневосточные.
     3. Разработка прогноза конъюнктуры  рынка цинка. 
     Кластерный  анализ играет важную роль на этапе редукции экономико-математической модели товарной конъюнктуры, способствуя облегчению и упрощению вычислительных процедур, обеспечению большей компактности получаемых результатов при одновременном сохранении необходимой точности. Применение кластерного анализа дает возможность разбить всю исходную совокупность показателей конъюнктуры на группы (кластеры) по соответствующим критериям, облегчая тем самым выбор наиболее репрезентативных показателей.
     Кластерный  анализ широко используется для моделирования  рыночной конъюнктуры. Практически  основное большинство задач прогнозирования  опирается на использование кластерного анализа.
     Например, задача разработки прогноза конъюнктуры  рынка цинка.
     Первоначально было отобрано 30 основных показателей  мирового рынка цинка:
      Х1 - время
      Показатели производства:
      Х2 - в мире
      Х3 - США
      Х4 - Европе
      Х5 - Канаде
      Х6 - Японии
      Х7 - Австралии
      Показатели потребления:
      Х8 - в мире
      Х9 - США
      Х10 - Европе
      Х11 - Канаде
      Х12 - Японии
      Х13 - Австралии
      Запасы цинка у производителей:
      Х14 - в мире
      Х15 - США
      Х16 - Европе
      Х17 - других странах
      Запасы цинка у потребителей:
      Х18 - в США
      Х19 - в Англии
      Х10 - в Японии
     Импорт  цинковых руд и концентратов (тыс. тонн)
      Х21 - в США
      Х22 - в Японии
      Х23 - в ФРГ
     Экспорт цинковых руд и концентратов (тыс. тонн)
      Х24 - из Канады
      Х25 - из Австралии
     Импорт  цинка (тыс. тонн)
      Х26 - в США
      Х27 - в Англию
      Х28 - в ФРГ
     Экспорт цинка (тыс. Тонн)
      Х29 - из Канады
      Х30 - из Австралии
     Для определения конкретных зависимостей был использован аппарат корреляционно-регрессионного анализа. Анализ связей производился на основе матрицы парных коэффициентов корреляции. Здесь принималась гипотеза о нормальном распределении анализируемых показателей конъюнктуры. Ясно, что rij являются не единственно возможным показателем связи используемых показателей. Необходимость использования кластерного анализа связано в этой задаче с тем, что число показателей влияющих на цену цинка очень велико. Возникает необходимость их сократить по целому ряду следующих причин:
     а) отсутствие полных статистических данных по всем переменным;
     б) резкое усложнение вычислительных процедур при введении в модель большого числа  переменных;
     в) оптимальное использование методов  регрессионного анализа требует  превышения числа наблюдаемых значений над числом переменных не менее, чем  в 6-8 раз;
     г) стремление к использованию в  модели статистически независимых  переменных и пр.
     Проводить такой анализ непосредственно на сравнительно громоздкой матрице коэффициентов  корреляции весьма затруднительно. С  помощью кластерного анализа  всю совокупность конъюнктурных  переменных можно разбить на группы таким образом, чтобы элементы каждого  кластера сильно коррелировали между  собой, а представители разных групп  характеризовались слабой коррелированностью.
     Для решения этой задачи был применен один из агломеративных иерархических  алгоритмов кластерного анализа. На каждом шаге число кластеров уменьшается  на один за счет оптимального, в определенном смысле, объединения двух групп. Критерием  объединения является изменение  соответствующей функции. В качестве функции такой были использованы значения сумм квадратов отклонений вычисляемые по следующим формулам:
     
     (j = 1, 2, …, m),
     где j - номер кластера, n - число элементов в кластере.
     rij - коэффициент парной корреляции.
     Таким образом, процессу группировки должно соответствовать последовательное минимальное возрастание значения критерия E.
     На  первом этапе первоначальный массив данных представляется в виде множества, состоящего из кластеров, включающих в  себя по одному элементу. Процесс группировки  начинается с объединения такой  пары кластеров, которое приводит к  минимальному возрастанию суммы  квадратов отклонений. Это требует  оценки значений суммы квадратов  отклонений для каждого из возможных объединений кластеров. На следующем этапе рассматриваются значения сумм квадратов отклонений уже для кластеров и т.д. Этот процесс будет остановлен на некотором шаге. Для этого нужно следить за величиной суммы квадратов отклонений. Рассматривая последовательность возрастающих величин, можно уловить скачок (один или несколько) в ее динамике, который можно интерпретировать как характеристику числа групп «объективно» существующих в исследуемой совокупности. В приведенном примере скачки имели место при числе кластеров равном 7 и 5. Далее снижать число групп не следует, т.к. это приводит к снижению качества модели. После получения кластеров происходит выбор переменных наиболее важных в экономическом смысле и наиболее тесно связанных с выбранным критерием конъюнктуры - в данном случае с котировками Лондонской биржи металлов на цинк. Этот подход позволяет сохранить значительную часть информации, содержащейся в первоначальном наборе исходных показателей конъюнктуры.
 


     3 МЕТОДЫ КЛАСТЕРНОГО АНАЛИЗА
     Сегодня существует достаточно много методов  кластерного анализа. Остановимся  на некоторых из них (ниже приводимые методы принято называть методами минимальной  дисперсии).
     Пусть Х - матрица наблюдений: Х = (Х1, Х2,..., Хu) и квадрат евклидова расстояния между Хi и Хj определяется по формуле:
     

     Метод полных связей.
     Суть  данного метода в том, что два  объекта, принадлежащих одной и  той же группе (кластеру), имеют коэффициент  сходства, который меньше некоторого порогового значения S. В терминах евклидова  расстояния d это означает, что расстояние между двумя точками (объектами) кластера не должно превышать некоторого порогового значения h. Таким образом, h определяет максимально допустимый диаметр подмножества, образующего кластер.
     Метод максимального локального расстояния.
     Каждый  объект рассматривается как одноточечный кластер. Объекты группируются по следующему правилу: два кластера объединяются, если максимальное расстояние между  точками одного кластера и точками  другого минимально. Процедура состоит  из n - 1 шагов и результатом являются разбиения, которые совпадают со всевозможными разбиениями в  предыдущем методе для любых пороговых  значений. 

Метод Ворда.
     В этом методе в качестве целевой функции  применяют внутригрупповую сумму  квадратов отклонений, которая есть ни что иное, как сумма квадратов  расстояний между каждой точкой (объектом) и средней по кластеру, содержащему  этот объект. На каждом шаге объединяются такие два кластера, которые приводят к минимальному увеличению целевой  функции, т.е. внутригрупповой суммы  квадратов. Этот метод направлен  на объединение близко расположенных  кластеров.
       Центроидный метод.
     Расстояние  между двумя кластерами определяется как евклидово расстояние между  центрами (средними) этих кластеров:
     d2ij = (`X –`Y)Т(`X –`Y)
     Кластеризация идет поэтапно на каждом из n–1 шагов  объединяют два кластера G и p, имеющие минимальное значение d2ij.Если n1 много больше n2, то центры объединения двух кластеров близки друг к другу и характеристики второго кластера при объединении кластеров практически игнорируются. Иногда этот метод иногда называют еще методом взвешенных групп. 

 

     

     4 АЛГОРИТМ FOREL

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

     Минимизируемый алгоритмом функционал качества

     

     где первое суммирование ведется по всем кластерам выборки, второе суммирование — по всем объектам x, принадлежащим текущему кластеру Kj, а W— центр текущего кластера, ?(x,y) — расстояние между объектами.

     Необходимые условия работы алгоритма:

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

     Входные данные:

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

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

     Выходные данные

     Кластеризация на заранее неизвестное число  таксонов

     4.1 Принцип работы алгоритма FOREL

     На  каждом шаге мы случайным образом  выбираем объект из выборки, раздуваем  вокруг него сферу радиуса R, внутри этой сферы выбираем центр тяжести  и делаем его центром новой  сферы. Т.о. мы на каждом шаге двигаем  сферу в сторону локального сгущения объектов выборки, то есть стараемся  захватить как можно больше объектов выборки сферой фиксированного радиуса. После того как центр сферы  стабилизируется, все объекты внутри сферы с этим центром мы помечаем как кластеризованные и выкидываем их из выборки. Этот процесс мы повторяем  до тех пор, пока вся выборка не будет кластеризована.
     Алгоритм  FOREL является примером эвристического дивизимного алгоритма классификации. В основе работы алгоритма FOREL лежит использование гипотезы компактности: близким в содержательном смысле объектам в геометрическом пространстве признаков соответствуют обособленные множества точек, так называемые «сгустки». Если расстояние между центром -го таксона и точкой этого таксона обозначить , то сумма расстояний между центром и всеми точками этого таксона будет равна:
     

     где:
    – расстояние между центром -го таксона и всеми точками этого таксона;
    – расстояние между центром -го таксона и точкой этого таксона.
     Сумма таких внутренних расстояний для  всех таксонов равна:
     

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

                 Алгоритм выполнения:

    Случайно  выбираем текущий объект из выборки;
    Помечаем объекты выборки, находящиеся на расстоянии менее, чем R от текущего;
    Вычисляем их центр тяжести, помечаем этот центр как новый текущий объект;
    Повторяем шаги 2-3, пока новый текущий объект не совпадет с прежним;
    Помечаем объекты внутри сферы радиуса R вокруг текущего объекта как кластеризованные, выкидываем их из выборки;
    и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.