Расшифровка : Наука в целом (информационные технологии 004) icon

Расшифровка : Наука в целом (информационные технологии 004)


Смотрите также:
Расшифровка : Наука в целом (информационные технологии 004)...
Расшифровка : Наука в целом (информационные технологии 004)...
Расшифровка : Наука в целом (информационные технологии 004)...
Расшифровка : Наука в целом (информационные технологии 004)...
Расшифровка : Наука в целом (информационные технологии 004)...
Расшифровка : Наука в целом (информационные технологии 004)...
Расшифровка : Наука в целом (информационные технологии 004)...
Расшифровка: Наука в целом (информационные технологии 004)Информационные технологии...
Расшифровка : Наука в целом (информационные технологии 004)...
Расшифровка : Наука в целом (информационные технологии 004)...
Название Предмет Направление...
Программа вступительного испытания по предмету «Информационные технологии»...



ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОУВПО «Самарский государственный архитектурно-строительный университет»

Факультет информационных систем и технологий

Кафедра прикладной математики и вычислительной техники


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


по дисциплине

МЕТОДОЛОГИЯ ПРОФЕССИОНАЛЬНОЙ ДЕЯТЕЛЬНОСТИ


на тему


«Реализация и сравнительный анализ двух методов кластеризации на примере информации по ФИСТ»


7 СЕМЕСТР 4 КУРС


Преподаватель (Ворошилов)

Методический руководитель (Пиявский С.А)

Научный руководитель (Куманяйкина)





Выполнил:

студент ГИП-106а Малов А.Г




подпись дата















Оценка преподавателя _______________


Оценка комиссии по результатам защиты_______________


2009 г.


УДК 004.021+378.14.015.62


Расшифровка:

Наука в целом (информационные технологии — 004)

Методы решения задач

Алгоритмы

А также:
^

Народное образование. Воспитание. Обучение. Организация досуга


Высшее образование. Высшая школа. Подготовка научных кадров

Организация высшего образования. Организация работы высшего учебного заведения

Организация учебной работы

Результаты обучения


^ Ключевые слова

анализ, кластеризация,рейтинг, учебный процесс


Реферат

В данной работе автор реализовал и использовал два различных по своей сути метода кластеризации: метод k-means (k-средних) и метод Гарантирующей Многоцелевой Системы (ГМС). В ходе работы были использованы такие средства как: офисные пакеты, отличные от наиболее используемых, встроенные функции табличного процессора, язык программирования Macros Basic и др.

В ходе исследования выявлено: 1) При количестве кластеров, немногим меньшем количества кластеризумых объектов, метод k-средних выказывает свою неэффективность, тогда как метод ГМС, успешно справляется, и не имеет объектов , входящих в разные кластера. 2) Среди радиусов кластеров метода k-средних есть как намного меньшие , так и на много превышающие ,значение радиуса в методе ГМС. 3) В отличие от метода k-средних в кластерах метода ГМС примерно одинаковое количество объектов.

Из этого можно сделать вывод, что для данной задачи метод ГМС предпочтительнее.


^ Экран оценки творческого уровня работы




Аннотация


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

Задачей автора было выбрать и реализовть два метода, наиболее подходящих для кластеризации информации по ФИСТ. В качестве источника информации взят рейтинг студентов одной группы. За первый метод кластеризации взят метод k-means (k-средних); за второй кластеризация методом Гарантирующей Многоцелевой Системы (ГМС). Эти метододы выбраны за счёт относительной простоты их математической модели и нересурсоёмкости вычислений . Объектом кластеризации яаляется комплексный рейтинг студентов факультета, взятый по трём критериям: учебный рейтинг, внеучебный рейтинг и процент пропущенных часов. Обеими методами производится кластеризация данных с последующим выделением по каждому методу 3, 4 и 5 кластеров. Для метода k-средних высчитывается радиус кластера, а для метода ГМС, путём задания гарантирующего радиуса , подбираются необходимые количесва кластеров. Автор производит сравнительный анализ полученных результатов.

В результате исследования было выявлено:

-При количестве кластеров, немногим меньшем количества кластеризумых объектов, метод k-средних выказывает свою неэффективность(некоторые кластеры содержат один объект), тогда как метод ГМС, успешно справляется, и не имеет объектов , входящих в разные кластера (однако это происходит при ещё большем увеличение количества кластеров, то есть уменьшении максимального радиуса для ГМС).

- Среди радиусов кластеров метода k-средних есть как намного меньшие , так и на много превышающие ,значение радиуса в методе ГМС (поэтому метод ГМС более удобен для выделения более близких по в кластер).

- В отличие от метода k-средних в кластерах метода ГМС примерно одинаковое количество объектов.

Работа выполнена на основе офисного пакета IBM Lotus Symphony. Для реализации метода k-средних был написан макрос во встроенной среде Macros Basic. А для реализации ГМС использовался аналог поиска решений - Solve Equation.

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


Введение


В рамках работы был поставлена задача провести кластеризацию на примере двух методов, взяв в качестве исходных данных информацию по факультету-рейтинг студентов. В качетсве первого метода был выбран метод k-средних, в качестве второго метод Гарантирующей Многоцелевой Системы (ГМС). Эти метододы выбраны за счёт относительной простоты их математической модели и нересурсоёмкости вычислений . Кластеризация проводилась на примере комплексного рейтинга учащихся 4 курса ИСТ. Для реализации наиболее оптимальным было выбрать электронные таблицы. Выбор Mikrosoft Exсel сразу отпал изза ограничений в реализации поиска решений. Разумным решением было использовать OpenOffice Calc, однако после выполнения части работы были обнаружены трудности в использование VBA, в связи с чем было принято решение использовать офисный пакет IBM Lotus Symphony, а именно табличный процессор Spreadsheet. Для реализации метода k-средних был написан макрос во встроенной среде Macros Basic. А для реализации ГМС использовался аналог поиска решений - Solve Equation.


^ Описание методов.

Метод k-средних.

k-средних - наиболее популярный метод кластеризации. Он разбивает множество элементов векторного пространства на заранее известное число кластеров k.



где k - число кластеров, Si - полученные кластеры, и μi - центры масс векторов

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


ГМС.

Пусть исходными данными являются Xi . Где i=n число кластеризумых элементов. Получим таблицу расстояний между элементами -Yi,j , где i=j, так матрица квадратичная.

Введем булевы переменные признаки того, включен ли элемент в стратегию A. Тогда число M элементов стратегии определяется как



Для исключения «грубых ошибок» необходимо при оптимизации ГМС предоставить возможность оптимального (по основному критерию) исключения из множества Y определенного числа элементов q.

Решая эту задачу для заданной таблицы расстояний, мы находим центры кластеров (они соответствуют найденным единичным значениям Ui ). На основе найденных центров, и заданном f, перебирая все элементы, можно разделить их на кластеры. Причем, если один элемент может быть отнесен к нескольким кластерам, то он отправляется в кластер, ближе к центру которого он расположен.


^ Исходные данные


В качестве критериев оценки объектов кластеризации были выбраны: Процент пропусков, Процент пропущенных контрольных точек, вне учебный рейтинг.

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




^ Рис.1 Исходные данные по всем группам


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


Рис. 2 Исходные данные по кластеризумой группе


Реализация метода k-средних.


Так как метод многоитеррационный (и сходимость его не доказана), то невозможно было обойтись одними встроенными функциями табличного процессора. Поэтому метод был реализован на встроенном в Lotus Symphony языке Macros Basic.

При числе кластеров 4 метод выдал следующие результаты:




^ Рис 3. Разбиение группы на 4 кластера методом k-средних.

По горизонтали кластера, по вертикали объекты.

Единицей и жёлтым цветом обозначен факт вхождения объекта в данный кластер.


Реализация метода ГМС.


Для начала была получена таблица расстояний. Она высчитывается по формуле евклидова расстояния: расстояние(x,y) = sqrt(Si (xi - yi )^2) . В нашем случае S=sqrt((Xi-Yi)^2+(Xg-Yg)^2+(Xt-Yt)^2).




Рис. 4 Таблица расстояний, используемая в методе ГМС


Зададим в Solve Equation атрибуты подбора оптимальных значений, задав

ограничения в виде условий самих ячеек, так как в Solve Equation ограничения не поддерживаются. Так, если вектор принадлежности кластеру не равен 0 или 1, то значение его устанавливается на неопределённое, таким образом Solve Equation не сосчитает оптимальное решение с не бинарным вектором принадлежности.


^ Анализ результатов




Рис.5

^ Результаты разбиения на 4 кластера по методу k-средних(слева) и на 5 кластеров по ГМС(справа).. Одинаковым цветом выделены объекты, входящие в один кластер.


Сравним радиусы методов для различных количеств кластеров. Возьмём количества кластеров 3,4,5. С методом k-средних проблем не возникнет, так как количество кластеров в нём задаётся. Однако в методе ГМС нужно сделать это путем подбора значений максимального радиуса. Значения максимального радиуса получаются такие: K=3: 1.1; K=4: 0.7 ; K=5: 0.4 . Так как метод k-средних итерационный, и сходимость его не доказана, то посчитать радиус кластера путём математических выкладок, для него является нетривиальной задачей. Поэтому посчитаем его, используя таблицу расстояний.


Результаты анализа работы методов:


Кол-во кластеров

Радиус по k-средних

Радиус по ГМС

5

0.62 | 0.21 | 0.21 | 0.00 | 0.48

0,4

4

0.58 | 0.72 | 0.51 | 1.0

0,7

3

0.62 | 0.21 | 0.21

1,1

Рис. 6 Таблица радиусов кластеров


Изучив эти данные можно прийти к выводам:

1) При количестве кластеров, немногим меньшем количества кластеризумых объектов, метод k-средних выказывает свою неэффективность(некоторые кластеры содержат один объект), тогда как метод ГМС, успешно справляется, и не имеет объектов , входящих в разные кластера (однако это происходит при ещё большем увеличение количества кластеров, то есть уменьшении максимального радиуса для ГМС).

2) Среди радиусов кластеров метода k-средних есть как намного меньшие , так и на много превышающие ,значение радиуса в методе ГМС (поэтому метод ГМС более удобен для выделения более близких по субъектов в кластер).

3) В отличие от метода k-средних в кластерах метода ГМС примерно одинаковое количество объектов.


^ Из этого можно сделать вывод, что для данной задачи метод ГМС предпочтительнее.


Направления дальнейшего развития:

  • Перенос методов в нативную программу.

  • Проверка результатов на более репрезентативной выборке

  • Изменение метода ГМС, путём задания не только гарантирующего радиуса радиуса, но и гарантирующего расстояния между объектами.

  • Реализация других методов кластерного анализа

  • Применение результатов кластеризации для оптимизации образовательного процесса



Библиографический список


  1. Учебник по математической статистике с упражнениями в системе STATISTICA” – www.statsoft.ru

  2. С.А. Пиявский Методы оптимизации и оптимального управления. Учебное пособие. Самарский государственный архитектурно-строительный университет. Самара, 2005. 184с.

  3. Ким Дж.-О., Мьюллер Ч.У., Клекка У.Р. Факторный, дискриминантный и кластерный анализ. Финансы и статистика, 1989 – 215с.

  4.  Гиршов Евгений. Алгоритмы кластеризации. Ebook, 1997-11с.




Скачать 119.25 Kb.
оставить комментарий
Дата20.04.2012
Размер119.25 Kb.
ТипРасшифровка, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Документы

Рейтинг@Mail.ru
наверх