1.3.1 Аппроксимация

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

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

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

Полиномиальная аппроксимация - наиболее часто используется аппроксимация с помощью полинома степени n:

где - коэффициенты многочлена,

- степень аппроксимирующего полинома.

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

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

Так, через три точки (M = 3) методом наименьших квадратов можно провести только прямую - полином 1-й степени (), через 4 точки - полином 1-й или 2-й степени, через 5 точек - полином 1-й, 2-й или 3-й степени и т.д. Если , то соответствующий полином проходит точно через аппроксимируемые точки и условие выполняется автоматически (точно через две точки проходит прямая, через три точки - парабола и т.д.). Если , задача становится неопределенной (например, через две точки можно точно провести бесчисленное множество парабол).

1.3.2 Обзор существующих методов кластеризации

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

Задачу кластеризации в том или ином виде формулировали в таких научных направлениях, как статистика, распознавание образов, оптимизация, машинное обучение. Отсюда многообразие синонимов понятию кластер - класс, таксон, сгущение. На сегодняшний момент число методов разбиения групп объектов на кластеры довольно велико - несколько десятков алгоритмов и еще больше их модификаций. Большинство алгоритмов кластеризации предполагают сравнение объектов между собой на основе некоторой меры близости (сходства). Мерой близости называется величина, имеющая предел и возрастающая с увеличением близости объектов. Меры сходства «изобретаются» по специальным правилам, а выбор конкретных мер зависит от задачи, а также от шкалы измерений. В качестве меры близости для числовых атрибутов очень часто используют евклидово расстояние, вычисляемое по формуле:

Чтобы придать большие веса более отдаленным друг от друга объектам вычисляют квадрат евклидова расстояния:

Манхэттенское расстояние вычисляется по формуле:

Расстояние Чебышева вычисляется по формуле:

Степенное расстояние вычисляется по формуле:

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

Алгоритмы кластеризации можно классифицировать на масштабируемые и не масштабируемые. Масштабируемые алгоритмы отвечают следующим условиям:

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

– работа в ограниченном объеме оперативной памяти компьютера;

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

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

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

Неиерархические алгоритмы основаны на оптимизации некоторой целевой функции, определяющей оптимальное в определенном смысле разбиение множества объектов на кластеры. В этой группе популярны алгоритмы семейства k-средних (c-means, fuzzy c-means, Густафсон-Кесселя), которые в качестве целевой функции используют сумму квадратов взвешенных отклонений координат объектов от центров искомых кластеров. Кластеры ищутся сферической либо эллипсоидной формы. В канонической реализации минимизация функции производится на основе метода множителей Лагранжа и позволяет найти только ближайший локальный минимум. Использование методов глобального поиска (генетические алгоритмы) значительно увеличит вычислительную сложность алгоритма.

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

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

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

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

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

1.3.3 Методы разработки информационных систем

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

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

– основные цели, которые можно достичь посредством автоматизации процессов;

– перечень участков и последовательность внедрения модулей ИС;

– фактическая потребность в объемах программного и аппаратного обеспечения;

– реальные оценки сроков развертывания и запуска;

– ключевые пользователи ИС.

Можно условно выделить основные этапы жизненного цикла ИС:

1. Определение требований к системе и их анализ - определение того, что должна делать система.

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

3. Разработка - создание функциональных компонентов и отдельных подсистем, соединение подсистем в единое целое.

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

5. Внедрение - установка и ввод системы в действие.

6. Функционирование - штатный процесс эксплуатации в соответствии с основными целями и задачами ИС.

7. Сопровождение - обеспечение штатного процесса эксплуатации системы на предприятии заказчика.

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

1.4 Выводы по главе

2.1 Основные понятия и гипотезы модели