Программный комплекс кластеризации студенческого коллектива

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

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к дипломному проекту на тему:

Программный комплекс кластеризации студенческого коллектива

РЕФЕРАТ

Дипломный проект.

Пояснительная записка: 113 с., 21 рис., 12 табл., 2 приложения

Графическая документация: 8 листов А 4

ПРОГРАММНЫЙ КОМПЛЕКС, КЛАСТЕР, КЛАСТЕРИЗАЦИЯ, РАЗБИЕНИЕ НА КЛАСТЕРЫ, МЕТОДЫ КЛАСТЕРИЗАЦИИ, СТУДЕНЧЕСКИЙ КОЛЛЕКТИВ, МОНИТОРИНГ, УЧЕБНАЯ ДЕЯТЕЛЬНОСТЬ, ПРОГНОЗИРОВАНИЕ, АНАЛИЗ,

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

Программный комплекс разработан на языке программирования С#.

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

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

ВВЕДЕНИЕ

программный информация учебный деятельность

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

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

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

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

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

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

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

1. СИСТЕМОТЕХНИЧЕСКАЯ ЧАСТЬ

1.1 Описание и системный анализ эволюции предметной области

Задачи высшего профессионального образования России связаны

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

Развитие рынка труда востребует профессионалов, владеющих

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

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

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

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

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

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

Первое применение кластерный анализ нашел в социологии. Название кластерный анализ происходит от английского слова cluster - гроздь, скопление. Впервые в 1939 был определен предмет кластерного анализа и сделано его описание исследователем Трионом. Главное назначение кластерного анализа - разбиение множества исследуемых объектов и признаков на однородные в соответствующем понимании группы или кластеры. Это означает, что решается задача классификации данных и выявления соответствующей структуры в ней. Методы кластерного анализа можно применять в самых различных случаях, даже в тех случаях, когда речь идет о простой группировке, в которой все сводится к образованию групп по количественному сходству.

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

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

Важное значение кластерный анализ имеет применительно

к совокупностям временных рядов, характеризующих развитие объектов

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

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

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

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

В кластерном анализе считается, что:

а) выбранные характеристики допускают в принципе желательное разбиение на кластеры;

б) единицы измерения (масштаб) выбраны правильно.

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

Задача кластерного анализа заключается в том, чтобы на основании данных, содержащихся во множестве Х, разбить множество объектов G на m (m - целое) кластеров (подмножеств) Q1, Q2, …, Qm, так, чтобы каждый объект Gj принадлежал одному и только одному подмножеству разбиения и чтобы объекты, принадлежащие одному и тому же кластеру, были сходными, в то время, как объекты, принадлежащие разным кластерам были разнородными.

Например, пусть G включает n студентов, любой из которых характеризуется склонностью к точным наукам (F1), склонностью к гуманитарным наукам (F2), возрастом (F3). Тогда Х1 (вектор измерений) представляет собой набор указанных характеристик для первого студента, Х2 - для второго, Х3 для третьего, и т.д. Задача заключается в том, чтобы разбить студентов по уровню развития.

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

,

где x_j - представляет собой измерения j-го объекта.

Для решения задачи кластерного анализа необходимо определить понятие сходства и разнородности.

Понятно то, что объекты i-ый и j-ый попадали бы в один кластер, когда расстояние (отдаленность) между точками Х и Хj было бы достаточно маленьким и попадали бы в разные кластеры, когда это расстояние было бы достаточно большим. Таким образом, попадание в один или разные кластеры объектов определяется понятием расстояния между Х и Хj из Ер, где Ер - р-мерное евклидово пространство. Неотрицательная функция d(Х, Хj) называется функцией расстояния (метрикой), если:

а) d(Хi , Хj) 0, для всех Х и Хj из Ер;

б) d(Хi, Хj) = 0, тогда и только тогда, когда Х = Хj;

в) d(Хi, Хj) = d(Хj, Х);

г) 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(Х , Хj) могут быть представлены в виде симметричной матрицы расстояний:

.

Понятием, противоположным расстоянию, является понятие сходства между объектами G. и Gj. Неотрицательная вещественная функция

S(Х ; Хj) = Sj называется мерой сходства, если :

1) 0 S(Хi , Хj)1 для Х Хj;

2) S(Хi , Хi) = 1;

3) S(Хi , Хj) = S(Хj , Х).

Пары значений мер сходства можно объединить в матрицу сходства:

.

Величину Sij называют коэффициентом сходства.

Сегодня существует достаточно много методов кластерного анализа. Остановимся на некоторых из них (ниже приводимые методы принято называть методами минимальной дисперсии).

Пусть Х - матрица наблюдений: Х = (Х1, Х2,..., Хu) и квадрат евклидова расстояния между Х и Хj определяется по формуле:

.

1) Метод полных связей.

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

2) Метод максимального локального расстояния.

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

3) Метод Ворда.

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

4) Центроидный метод.

Расстояние между двумя кластерами определяется как евклидово расстояние между центрами (средними) этих кластеров:

d2ij = (X -Y)Т(X -Y).

Кластеризация идет поэтапно на каждом из n-1 шагов объединяют два кластера G и , имеющие минимальное значение d2ij Если n1 много больше n2, то центры объединения двух кластеров близки друг к другу и характеристики второго кластера при объединении кластеров практически игнорируются. Иногда этот метод иногда называют еще методом взвешенных групп.

1.2 Обзор алгоритмов кластеризации

Для себя я выделил две основные классификации алгоритмов кластеризации.

Иерархические и плоские.

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

Плоские алгоритмы строят одно разбиение объектов на кластеры.

Четкие и нечеткие.

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

Алгоритмы иерархической кластеризации

Среди алгоритмов иерархической кластеризации выделяются два основных типа: восходящие и нисходящие алгоритмы. Нисходящие алгоритмы работают по принципу «сверху-вниз»: в начале все объекты помещаются в один кластер, который затем разбивается на все более мелкие кластеры. Более распространены восходящие алгоритмы, которые в начале работы помещают каждый объект в отдельный кластер, а затем объединяют кластеры во все более крупные, пока все объекты выборки не будут содержаться в одном кластере. Таким образом, строится система вложенных разбиений. Результаты таких алгоритмов обычно представляют в виде дерева - дендрограммы. Классический пример такого дерева

- классификация животных и растений.

Для вычисления расстояний между кластерами чаще все пользуются двумя расстояниями: одиночной связью или полной связью.

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

Алгоритмы квадратичной ошибки

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

где cj -- «центр масс» кластера j (точка со средними значениями характеристик для данного кластера).

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

1. Случайно выбрать k точек, являющихся начальными «центрами масс» кластеров.

2. Отнести каждый объект к кластеру с ближайшим «центром масс».

3. Пересчитать «центры масс» кластеров согласно их текущему составу.

4. Если критерий остановки алгоритма не удовлетворен, вернуться

5. к п. 2.

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

переместившихся из кластера в кластер.

К недостаткам данного алгоритма можно отнести необходимость задавать количество кластеров для разбиения.

Нечеткие алгоритмы

Наиболее популярным алгоритмом нечеткой кластеризации является алгоритм c-средних (c-means). Он представляет собой модификацию метода k-средних. Шаги работы алгоритма:

Выбрать начальное нечеткое разбиение n объектов на k кластеров путем выбора матрицы принадлежности U размера n x k.

Используя матрицу U, найти значение критерия нечеткой ошибки:,

где c_k -- «центр масс» нечеткого кластера k:

.

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

Возвращаться в п. 2 до тех пор, пока изменения матрицы U не станут незначительными.

Этот алгоритм может не подойти, если заранее неизвестно число кластеров, либо необходимо однозначно отнести каждый объект к одному кластеру.

Алгоритмы, основанные на теории графов

Суть таких алгоритмов заключается в том, что выборка объектов представляется в виде графа G=(V, E), вершинам которого соответствуют объекты, а ребра имеют вес, равный «расстоянию» между объектами.

Достоинством графовых алгоритмов кластеризации являются наглядность, относительная простота реализации и возможность вносения различных

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

Алгоритм выделения связных компонент

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

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

Алгоритм минимального покрывающего дерева

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

Рисунок 1 - Покрывающее дерево

Путём удаления связи, помеченной CD, с длиной равной 6 единицам (ребро с максимальным расстоянием), получаем два кластера: {A, B, C} и {D, E, F, G, H, I}. Второй кластер в дальнейшем может быть разделён ещё на два кластера путём удаления ребра EF, которое имеет длину, равную 4,5 единицам.

Послойная кластеризация

Алгоритм послойной кластеризации основан на выделении связных компонент графа на некотором уровне расстояний между объектами (вершинами). Уровень расстояния задается порогом расстояния c. Например, если расстояние между объектами , то .

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

,

где Gt = (V, Et) -- граф на уровне сt,

,

с_t - t-ый порог расстояния,

m - количество уровней иерархии,

G0 = (V, o), o - пустое множество ребер графа, получаемое при t0 = 1,

Gm = G, то есть граф объектов без ограничений на расстояние (длину ребер графа), поскольку tm = 1.

Посредством изменения порогов расстояния {с0, …, сm}, где 0 = с0 < с1 < …< сm = 1, возможно контролировать глубину иерархии получаемых кластеров. Таким образом, алгоритм послойной кластеризации способен создавать как плоское разбиение данных, так и иерархическое.

Сравнение алгоритмов

Вычислительная сложность алгоритмов

Таблица 1 - Вычислительная сложность алгоритмов

Алгоритм кластеризации	Вычислительная сложность
Иерархический	O(n2)
k-средних	O(nkl), где k - число кластеров, l - число итераций
c-средних
Выделение связных компонент	зависит от алгоритма
Минимальное покрывающее дерево	O(n2 log n)

Сравнительная таблица алгоритмов

Таблица 2 - Сравнительная таблица алгоритмов

Алгоритм кластеризации	Форма кластеров	Входные данные	Результаты
Иерархический	Произвольная	Число кластеров или порог расстояния для усечения иерархии	Бинарное дерево кластеров
k-средних	Гиперсфера	Число кластеров	Центры кластеров
c-средних	Гиперсфера	Число кластеров, степень нечеткости	Центры кластеров, матрица принадлежности
Выделение связных компонент	Произвольная	Порог расстояния R	Древовидная структура кластеров
Минимальное покрывающее дерево	Произвольная	Число кластеров или порог расстояния для удаления ребер	Древовидная структура кластеров
Послойная кластеризация	Произвольная	Последовательность порогов расстояния	Древовидная структура кластеров с разными уровнями иерархии

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

Разработанная система относится к классу программных комплексов, так как она позволяет:

1) повышать производительность работы преподавателей за счет простоты и доступности программного комплекса;

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

1.4 Постановка задачи проектирования

Встала задача разработать такой программный комплекс, который мог бы исследовать закономерности и кластеризовать студенческий коллектив

по динамике изменения исследовательских компетенций.

1.4.1 Цели проектирования

1) ввод информации по студенту;

2) сортировка студентов по семестру, суммарной функции или курсу;

5) выдача рекомендаций каждой студенческой группе

и преподавателям.

1.4.2 Критерии эффективности, планируемые значения показателей эффективности проектируемой системы

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

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

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

- Информационное обеспечение должно восстанавливаться в течение 0,5 часа после отказа НМД.

1.4.3 Ограничения применимости

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

1.5 Математическая модель

Исходная формулировка рангового метода кластеризации представляет собой два требования к искомому разбиению: 1) точки каждого кластера близки к прямой lnw = -? ln R + c ; 2) параметры ? и c меняются при переходе от кластера к кластеру.

Возникают две задачи:

1) оценка заданного разбиения данных на кластеры;

2) нахождение разбиения.

В ранговом методе кластеризации кластер - это совокупность точек с последовательными рангами r = a, ..., b, т.е. промежуток [a...b]. Требуется формализовать приближённое соотношение для кластера [a...b]. Введём меру отклонения точки (ln R, ln w) от прямой lnw = -? ln R + c :

d (ln R,ln w,?? ,c) = |lnw - (-? ln R + c)| .

Зададим пороговое значение ? ₀ и потребуем, чтобы для всех точек кластера [a...b] выполнялось условие:

? (lnR_r ,ln w_r ,?? ,c) ??? ₀ , r = a, ..., b.

Будем считать, что на кластере [a...b] справедлив модифицированный В.П. Масловым закон Ципфа c параметрами ?? c при пороговом значении ?0, если

max???lnR_r ,ln , w_r??? c? ???0

a???r? b

Введем величину

??min???0ln R_r ln w_r ,?? ,c).

???????????????????????????????

Будем считать, что на кластере [a...b] справедлив модифицированный

В.П. Масловым закон Ципфа при пороговом значении ?0, если

???min ?0,??????0 .

Точку, для которой не выполняется неравенство

???ln Rr ,ln wr ,??,c) ???0 ,

будем называть аномальной. Потребуем, чтобы для всех точек кластера [a...b] выполнялось неравенство, при этом допускается ₀ аномальных точек, для которых, однако, должно выполняться неравенство

???ln Rr ,ln wr ,??,c) ???₀?.

Тройку ?L ?????0 ,??0 ,???₀₎?назовём уровнем качества кластера. Будем считать, что на кластере [a...b] справедлив модифицированный В.П. Масловым закон Ципфа на уровне L, если при некоторых значениях параметров

?, c выполняется указанное требование.

Введём величину ???min (??₀ ,???0)?- минимальное значение порогового значения ?0, при котором на кластере [a...b] справедлив модифицированный В.П. Масловым закон Ципфа на уровне ?L ?????₀ ,??₀ ,???₀??. Введём величину ??min ?????₀,???₀?????минимальное количество аномальных точек ,??₀, при котором на кластере [a...b] справедлив модифицированный В.П. Масловым закон Ципфа на уровне ? L ?????₀ ,??₀ ,???₀??

Рассмотрим множество промежутков, на которых справедлив модифицированный В.П. Масловым закон Ципфа на уровне L. Те из них, которые нельзя расширить так, чтобы на расширенном промежутке также был справедлив этот закон, образуют множество максимальных промежутков на уровне L.

Пусть задан кластер [a...b] и задана некоторая точка (ln R₀, ln w₀), не принадлежащая этому кластеру. Введём расстояние от точки (ln R₀, ln w₀) до кластера [a...b]. Рассмотрим множество значений параметров (?, c), таких, что на кластере [a...b] справедлив модифицированный В.П. Масловым закон Ципфа с такими значениями параметров. Выберем из этого множества

те значения (?, c), при которых величина ???ln R₀,ln w₀,??,c?? принимает наименьшее значение. Это значение и будет расстоянием от точки

(ln R₀, ln w₀) до кластера [a...b] (измеренным как отклонение точки

от прямой). Также введём расстояние от точки до кластера, измеренное в количестве точек кластера. Зададим пороговое значение ?0 и рассмотрим множество значений параметров (?, c), для которых ???ln R₀ ,ln w₀ ,??,c?????0 . Выберем из этого множества такие значения (?,c), что неравенство не выполняется для наименьшего количества точек кластера [a...b]. Это количество точек и будет расстоянием от точки ?ln R₀ ,ln w₀) до кластера [a...b].

Рассмотрим задачу оценки заданного разбиения данных на кластеры.

Требуется оценить разбиение, т.е. определить, удовлетворяет ли оно двум требованиям. Во-первых, для оценки каждого кластера в отдельности применим величины ?min и ?min (эти величины характеризуют качество кластера). Во-вторых, проанализируем, как изменяются данные величины при расширении и сужении каждого из кластеров разбиения. Для этого построим таблицу, содержащую значения величины ?min (или ?min) для всех возможных промежутков [a...b]. В-третьих, для каждого кластера разбиения вычислим расстояния от нескольких точек слева и справа от кластера до этого кластера.

Рассмотрим задачу нахождения разбиения. Процесс кластеризации эмпирических данных ранговым методом мы будем рассматривать как процесс расширения кластеров. То есть если выделен некоторый кластер и он может быть расширен (в него можно включить соседствующие с ним точки), то он расширяется. В результате такого расширения кластеры, как правило, будут пересекаться, и это есть особенность кластеризации эмпирических данных ранговым методом. Итак, чтобы построить разбиение, найдём множество максимальных промежутков. Кроме того, для нахождения разбиения пользователю может быть полезна таблица, содержащая значения величины ?min (или ?min) для всех возможных промежутков [a...b].

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

1.5.1 Описание ключевых алгоритмов

Обозначим x = ln R, y = ln w.

Рассмотрим задачу вычисления величины

??min???0lnR_r ln w_r ,?? ,c).

???????????????????????????????

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

наилучшего равномерного приближения существует и единствен. Если ?????x ??c????- многочлен наилучшего равномерного приближения, то существуют 3 узла x r0 ??x r1 ??x r2 , в которых разность y _rk ???????^?x rk ??c???

достигает максимального по модулю значения с последовательной переменой знака (условие альтернанса). Из условия альтернанса вытекает, что прямая y ?????^?x ??c^???параллельна одному из рёбер выпуклой оболочки множества точек ?? xr ,?yr????.

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

Таким образом, для вычисления ??min ?0,???нужно построить выпуклую оболочку, перебрать все её рёбра и для каждого ребра провести прямую, ему параллельную, такую, что максимальное из отклонений точек от этой прямой минимально.

Рассмотрим задачу вычисления ??min ?0,???с точки зрения проектирования точек на ось ординат во всех возможных направлениях.

Введём оператор проектирования p???x, y?. Проведём через точку (x, y) прямую с угловым коэффициентом (-?), тогда проекция точки (x, y) на ось ординат - это точка пересечения данной прямой с осью ординат.

Пусть p???x, y??- координата проекции:

p???x, y????x????y .

Тогда

??min ?0,??p??? xr ,?yr??? c??min min min | p??? xr ,?yr??|- c

??????????? a???r? b a???r? b

= min (? xr ,?yr?? min? xr ,?yr???

?a???r? b a???r? b

Рассмотрим следующие функции:

? r( ?????p???xr , yr) ??xr????yr ,

? max?????? max????r ????

a?r?b

? min???????? min???r ????

a?r?b

Требуется найти минимум функции ??????????max ???????min ????. Функции

??max ?????и ??min ?????кусочно-линейные, следовательно, ???????-

кусочно-линейная функция. Значит, минимум ???????достигается в одной из точек излома. Возникает задача нахождения точек излома функций ??max ?????и ??min ????. Графики этих функций - это ломаные.

Рассмотрим алгоритм построения ломаной - графика функции

??max ??????Начинаем строить ломаную с прямой - графика функции

??b (g ) (эта прямая - текущий максимум). Находим точки пересечения этой прямой с прямыми - графиками функций ?b?1????, …, ??a ????. Выбираем точку пересечения с наименьшей абсциссой ?1. Пусть это точка пересечения с графиком функции ???????k1 . Прямая - график функции ???????k1 - становится текущим максимумом. Далее находим точки пересечения этой прямой с прямыми - графиками функций ??1?????k1??, …,??a ????. Выбираем точку пересечения с наименьшей абсциссой ?2. Пусть это точка

пересечения с графиком функции ? _k2??????. Прямая - график функции

? _k2??????- становится текущим максимумом. Этот процесс продолжается, пока текущим максимумом не станет прямая - график функции ??a ????.

Рисунок 2 - Алгоритм Джарвиса (пунктиром выделен график функции ??max ????).

Описанный алгоритм представляет собой алгоритм Джарвиса построения выпуклой оболочки. Прямые, образующие ломаную, соответствуют вершинам выпуклой оболочки, а абсциссы вершин ломаной соответствуют угловым коэффициентам прямых, содержащих рёбра выпуклой оболочки. Время выполнения алгоритма - O?hM?,

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

1.5.2 Сокращение размера ОМВП с использованием алгоритма кластеризации k-медоидов

• Алгоритм k-медоидов - разновидность алгоритма k-средних;

• Центром кластера признается элемент с наименьшим средним расстоянием до остальных элементов кластера;

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

Производится минимизация функции F расстояний между элементами внутри кластера:

где NС - число кластеров;

ni - число элементов в i-том кластере;

DjCi - расстояние между j-м

элементом i-го кластера и центром данного кластера;

Критерий достаточной оптимальности разбиения:

Di < Dmax для i = 1…NС,

Рисунок 3 - Блок схема

1.6 Используемые средства разработки

1.6.1 Краткое описание методологии UML

Унифицированный язык моделирования (UML) является стандартным инструментом для создания "чертежей" программного обеспечения. С помощью UML можно визуализировать, специфицировать, конструировать и документировать артефакты программных систем[9].

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

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

1.6.2 Краткое описание средства разработки Microsoft Visual Studio 2012.

Microsoft Visual Studio 2012 - многообещающая версия популярной платформы разработки, в которой реализованы новейшие достижения Microsoft. Интерфейс программы и редактор кода были переработаны и реализованы на Windows Presentation Foundation (WPF). Это позволило сделать рабочую среду более функциональной и гибкой. Среди новых функций, стоит отметить возможность использования нескольких мониторов, а также возможность отображения информации о коде в разных представлениях. Программа также имеет усовершенствованный редактор для Silverlight.

1.7 Разработка модели анализа

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

- модель вариантов;

- модель анализа;

- модель проектирования;

- модель развертывания;

- модель реализации;

- модель тестирования.

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

1.7.1 Диаграмма вариантов использования

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

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

Например, у актанта «Секретарь» есть возможность вести справочники системы:

- справочник пользователей;

- справочник студентов;

- справочник групп;

- справочник факультетов;

У актанта «Преподаватель», есть следующие возможности:

- проведение кластерного анализа

Для актанта «Студент» доступно:

- пройти тестирование

Рисунок 4 - Диаграмма вариантов использования

1.7.2 Сценарий вариантов использования «Пройти тестирование»

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

Вариант использования: Пройти тестирование.

Краткое описание. Дает Студенту возможность прохождения тестирования по выбранной дисциплине.

Актант. Студент.

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

Основной поток событий.

1) Студент выбирает пункт из выпадающего списка «Тесты», и нажимает кнопку «Начать».

А1: Нажата кнопка «Закрыть»

2) Система выводит форму тестирования, в окне для текстового комментария отображает вопрос, ниже - варианты ответов. Также на форме располагаются кнопки «Предыдущий вопрос», «Следующий вопрос» и «Завершить тестирование».

3) Студент выбирает вариант ответа курсором мыши и нажимает кнопку «Следующий вопрос».

А 2: Студент нажимает кнопку «Предыдущий вопрос».

А 3: Вопрос в тесте был последним.

4) Система анализирует действия студента и отображает следующий вопрос.

5) Выполняет пункт 3 основной последовательности. Вариант использования завершается успешно

Альтернативы.

А 1: Нажата кнопка «Закрыть»

А 1.1. Система закрывает форму приветствия и осуществляет выход в ОС. Вариант использования завершается.

А 2: Нажата кнопка «Предыдущий вопрос»

А 2.1. Система анализирует действия студента и отображает предыдущий вопрос.

А 2.2 Выполняется пункт 3 основной последовательности.

А3: Вопрос в тесте был последним.

А 3.1: Система выводит сообщение об окончании тестирования с данными о результате прохождения.

А 3.2 Студент просматривает сообщение и нажимает «ОК»

А 3.3 Система закрывает сообщение и форму тестирования, Выход в ОС. Вариант использования завершен

1.7.3 Диаграммы сущностных классов (class diagram)

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

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

- отношения зависимости (dependency relationship);

- отношения ассоциации (association relationship);

- отношения обобщения (generalization relationship);

- отношения реализации (realization relationship).

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

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

Рисунок 5 - Диаграмма сущностных классов

Диаграмма сущностных классов АИС, показанная на рисунке 5, содержит 8 сущностей, каждая из которых хранит определенный массив данных, с которыми работает система.

Рассмотрим основные сущности диаграммы:

- студент. В данной сущности хранятся данные о студенте. Атрибутами сущности являются: идентификатор студента, ФИО и идентификатор группы;

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

Диаграмма состояний представлена на рисунке 4.

1) авторизация от имени администратора БД;

2) выход из формы администратора БД;

3) выход из меню преподавателя;

4) авторизация от имени преподавателя;

5) авторизация от имени студента;

6) выход из меню студента;

7) щелчок вкладки редактируемой таблицы;

8) щелчок кнопки (“Добавить”);

9) щелчок кнопки (“Удалить”);

10) щелчок кнопки (“Редактировать”);

11) щелчок кнопки (“Выход”);

12) выбор пункта выпадающего меню(“Группа”);

13) щелчок кнопки (“Кластеризация”);

14) щелчок кнопки (“Назад”);

15) щелчок кнопки (“Выход”);

16) выбор пункта выпадающего меню (“Период”);

17) щелчок кнопки (“Оценить”);

18) щелчок кнопки (“Выход”).

19)



Рисунок 6 - Диаграмма состояний

Рисунок 7 - Диаграмма граничных классов

На диаграмме классов управления (рисунок 8) отображается взаимодействие основных менеджеров, используемых в системе. В данном случае это менеджер приложения, менеджер СУБД и менеджер печати.

Рисунок 8 - Диаграмма классов управления системы

1.8 Описание логической структуры БД

1.8.1 Уровни представления данных

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

Существует три уровня представления данных:

1) 1-й уровень - концептуальный, связан с частным представлением данных группы пользователей в виде внешней схемы, объединяемых общностью используемой информации. Каждый конкретный пользователь работает с частью БД и представляет ее в виде внешней модели. Характеризуется разнообразием используемых моделей (модель “сущность - связь” (ER-модель, модель Чена), бинарные и инфологические модели, семантические сети).

2) 2-й уровень - логический, является обобщенным представлением данных всех пользователей в абстрактной форме. Используется три вида моделей: иерархические, сетевые и реляционные. Сетевая модель является моделью объектов-связей, допускающей только бинарные связи “многие к одному” и использует для описания модель ориентированных графов. Иерархическая модель является разновидностью сетевой, являющейся совокупностью деревьев (лесом). Реляционная модель использует представление данных в виде таблиц (реляций), в основе лежит математическое понятие теоретико-множественного отношения которое базируется на реляционной алгебре и теории отношений.

3) 3-й уровень - физический (внутренний), связан со способом фактического хранения данных в физической памяти ЭВМ. Во многом определяется конкретным типом СУБД.

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

обработки нетипичных запросов.

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

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

1.8.2 Выбор модели данных

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

Реляционная модель данных - разработанная Э.Коддом в 1970г. логическая модель данных, описывающая:

- структуры данных в виде (изменяющихся во времени) наборов отношений;

- теоретико-множественные операции над данными: объединение, пересечение, разность и декартово произведение;

- специальные реляционные операции: селекция, проекция, соединение и деление; а также

- специальные правила, обеспечивающие целостность данных.

Основной структурой в иерархических моделях данных является «дерево». Особенности такого представления в наличии корня - единственной точки входа в дерево, и что каждый порожденный узел имеет только одного родителя. Недостатком этой системы является высокая избыточность. Одна запись БД - это совокупность деревьев. Через эту структуру нельзя построить отношение N:N (многие ко многим).

Основной структурой в сетевых моделях данных является «сеть». При таком представлении существует несколько входов в сеть - неоднозначность доступа к данным. Особенности такого представления: один или несколько узлов могут иметь больше одного родителя; время доступа изменяется в зависимости от исходного входа. Время доступа в сетевой структуре может быть больше, чем в иерархической структуре.

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

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

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

1.8.3 Логическое проектирование

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

Работа с базой данных начинается с построения модели. Наиболее распространенной является ER-модель (entity-relationship model). Это модель данных, позволяющая описывать концептуальные схемы. Она предоставляет графическую нотацию, основанную на блоках и соединяющих их линиях, с помощью которых можно описывать объекты и отношения между ними какой-либо другой модели данных. В этом смысле ER-модель является мета-моделью данных, то есть средством описания моделей данных.

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

ER-модель является одной из самых простых визуальных моделей данных (графических нотаций). Она позволяет обозначить структуру «крупными мазками», в общих чертах. Это общее описание структуры называется ER-диаграммой или онтологией выбранной предметной области (area of interest).

...