Технологии обработки информации

Лабораторный практикум

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

 

Технологии обработки информации

к.т.н., доцент

Буряченко Владимир Викторович

 

[e-mail]

Кафедра ИВТ, Л304

 

Красноярск, 2019

ОГЛАВЛЕНИЕ

 

Лабораторная работа №1

Работа в текстовом процессоре с использованием средств LaTeX.. 3

 

Лабораторная работа №2

Нахождение оптимальной стратегии с использованием языков высокого уровня 12

 

Лабораторная работа №3

Применение методов кластерного анализа в программировании. 21

 

Лабораторная работа №4

Методы и алгоритмы сжатия данных. 35

 

Лабораторная работа №5

Машинная арифметика и идиомы численного программирования. Особенности хранения чисел в памяти компьютера. 40

 

Лабораторная работа №1

Работа в текстовом процессоре с использованием средств LaTeX

 

Цель работы

       Целью работы является приобретение практических навыков работы в текстовом процессоре и знакомство с возможностями редактора и основными принципами работы в LaTeX.

Теоретическая часть

Начало работы с LaTeX

В данной работе рассматривается процесс создания LaTeX-документа на примере подготовки курсовой работы.

Знакомство с LaTeX лучше начинать с документов "среднего" масштаба (например, курсовой работы), так как на их примере можно изучить все основные принципы работы с LaTeX, и при этом не оказаться "погребённым" под ворохом технических особенностей и деталей реализации.

Дистрибутив LaTeX

Если у вас уже установлен и настроен дистрибутив LaTeX, то можно пропустить этот раздел. В противном случае дистрибутив LaTeX придётся установить, так без него продвинуться дальше не получится. Установка LaTeX – это простая задача, и для начала рекомендуется установить дистрибутив TeX Live. Устанавливать следует все имеющиеся в наличии пакеты.

Этот дистрибутив присутствует в большинстве популярных дистрибутивах GNU/Linux (пакет для установки texlive-full). У пользователей Windows популярен MikTeX, а пользователю Mac OS, возможно, подойдёт дистрибутив MacTeX.

Текстовый редактор

LaTeX-документ (расширение tex) — это обычный текстовый файл, в котором содержится и некоторый объём команд для LaTeX процессора. В каком-то смысле это программа, по выполнении которой получается качественно оформленная печатная или электронная копия документа.

Поэтому для редактирования tex-файлов используются обычные текстовые редакторы. В принципе, подойдёт любой редактор, но, безусловно, для эффективного набора лучше выбрать специализированный текстовый редактор, например, emacs. Предварительно следует убедиться в том, что выбранный текстовый редактор поддерживает кодировку UTF-8 (общепринятая стандартная кодировка текста для символов Unicode). Этой кодировки следует придерживаться и при создании документов.

Можно также выбрать специализированный LaTeX-редактор, например, Texmaker или TeXstudio.

Ещё один хороший вариант — это LyX. Этот редактор совмещает поддержку команд LaTeX и визуальное редактирование WYSIWYM (W hat Y ou S ee I s W hat Y ou M ean).

Пример LaTeX-документа

В этом разделе мы представим первый LaTeX-документ. Для этого необходимо создать файл HelloWorld.tex, и поместить в него (скопировав или набрав) следующее содержание. Файл HelloWorld.tex и другие примеры можно найти в архиве latex_examples. rar.

 

Листинг 1. Исходный файл HelloWorld.tex

1 2 3 4 5 6 7 8 9 10

\documentclass[12pt,a4paper]{scrartcl} \usepackage[utf8]{inputenc} \usepackage[english,russian]{babel} \usepackage{indentfirst} \usepackage{misccorr} \usepackage{graphicx} \usepackage{amsmath} \begin{document} Здравствуй, Мир!!! \end{document}

 

На первой строке загружается класс документа scrartcl. Этот класс входит в набор KOMA-Script — современный пакет с отличной документацией и богатыми возможностями. На следующих строках загружаются стилевые файлы, необходимые для "русификации" документа:

· inputenc — для выбора кодировки текста;

· babel — пакет для локализации;

· indentfirst — красная строка для первого параграфа;

· misccorr — пакет с дополнительными настройками для соответствия правилам отечественной полиграфии.

Стили graphicx и amsmath отвечают за вставку картинок и отображение математической нотации.

Сам текст документа набирается внутри окружения document, которое начинается с команды \begin{document} и заканчивается конструкцией \end{document}. Параграфы в тексте разделяются друг от друга пустой строкой.

После создания файла HelloWorld.tex, его можно скомпилировать с помощью программы MikTex путем нажатия на кнопку зеленой стрелки, либо комбинацией клавиш ctrl + T.

В принципе любой правильно настроенный современный специализированный LaTeX-редактор позволяет компилировать tex-файлы и просматривать полученный результат. Для просмотра PDF-документов в системе должна быть установлена соответствующая программа просмотра. В данном примере предполагалось, что доступна программа okular, но всегда можно скачать стандартную программу просмотра Adobe Reader. Готовый PDF-файл HelloWorld.pdf также можно найти в архиве latex_examples. rar.

 

Модифицируем исходный файл добавив к нему рисунок.

Ответственным за создание «бокса» для размещения картинки является пакет graphicx, а точнее команда \includegraphics:

 

11	\includegraphics[width=0.49\textwidth]{helloworld.jpg}

 

Параметр «width =0.5\ textwidth» отвечает за ширину добавляемой картинки и определяет её, как половину от ширины страницы. Для более удобного оформления графических объектов необходимо упаковать рисунок в общий блок figure, для которого можно задать общие правила оформления:

 

\begin{figure} [ ht] \centering \hspace{0.5cm} \includegraphics[width=0.49\textwidth]{helloworld.jpg} \caption{Название рисунка} \end{figure}

Создание титульного листа

Перед началом работы следует попытаться найти готовый класс LaTeX, который учитывает все правила к оформлению научных публикаций, установленные в ВУЗе. Если такой файл найдётся (у других студентов или в администрации ВУЗа), то задачу по вёрстке документа можно считать решённой, что позволит сразу перейти к набору текста.

В листинге 2 представлен пример оформления титульного листа, который можно использовать после внесения специфических изменений (файл KursTitle.tex также находится в архиве latex_examples. rar).

 

Листинг 2. Исходный код титульного листа курсовой работы

\begin{titlepage} \begin{center} \large МИНИСТЕРСТВО ВЫСШЕГО ОБРАЗОВАНИЯ И НАУКИ\\ РОССИЙСКОЙ ФЕДЕРАЦИИ   \textbf{ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ\\ ВЫСШЕГО ОБРАЗОВАНИЯ} \vspace{0.5cm}   Сибирский государственный университет\\ науки и технологий имени академика М.Ф. Решетнева \vspace{0.25cm}   Институт информатики и телекоммуникаций   Кафедра информатики и вычислительной техники \vfill     \textsc{Курсовая работа}\\[5mm]   {\LARGE Название курсовой\\ работы\\[2mm] } \bigskip   Название дисциплины \end{center} \vfill   \newlength{\ML} \settowidth{\ML}{«\underline{\hspace{0.7cm}}» \underline{\hspace{2cm}}} \hfill\begin{minipage}{0.4\textwidth} Выполнил\\ Студент 2-го курса, группа БИС17-01 Фамилия Имя Отчество Проверил\\ \underline{\hspace{\ML}} И.\,О.~преподавателя\\ «\underline{\hspace{0.7cm}}» \underline{\hspace{2cm}} 2019 г. \end{minipage}% \bigskip     \begin{center} Красноярск, 2019 г. \end{center} \end{titlepage}

 

Титульный лист оформляется внутри окружения titlepage. Окружение center используется для выравнивания содержимого по центру. Окружение minipage представляет собой бокс фиксированной ширины и используется для формирования шапки с подписями.

Размер текста можно увеличивать с помощью команд \huge, \LARGE, \Large и \large (от большего к меньшему). Чтобы выделить текст можно применить следующие инструкции:

• \textbf{текст} — жирный текст;
• \textit{текст} — наклонный текст;
• \textsc{текст} — капитель;
• \underline{текст} — подчёркивание.

Вертикальные и горизонтальные пробелы можно выставить с помощью команд \vspace{} и \hspace{}. Принудительный перевод строки производится с помощью команды \\. Инструкции \vfill и \hfill ставят растяжимые пробелы бесконечной длины по вертикали и горизонтали. Если слева от бокса minipage указать команду \hfill, то бокс будет прижат к правой границе текста.

Команда \textwidth определяет ширину текста, что позволяет указывать долю от него, если нужно. Аналогично можно использовать и высоту текста \textheight.

В примере присутствует и элемент программирования. С помощью команды \newlength{\ML} была определена переменная длина \ML, которой была присвоена длина, нужная для вставки даты и месяца. Это позволило точно выровнять место, оставленное под подпись. Хотя это и мелочь, но именно такие незаметные аспекты и определяют восприятие документа читателем.

 

Практическое задание 1

1. Замените необходимые элементы оформления и текст на соответствующие для вашей группы и изучаемой дисциплины.
2. Измените шрифт текста на Times New Roman.
3. Измените положение строки текста «Красноярск, 2019 г.» так, чтобы оно соответствовало последней строке документа.

Набор текста

После оформления титульного листа можно переходить к набору текста. Пакет LaTeX берёт на себя работу по оформлению заголовков разделов и их автоматической нумерации. Достаточно только указать, что в данном месте начался новый раздел с помощью команд \section (раздел), \subsection (подраздел) и \subsubsection (подподраздел).

Создайте новый документ kurs. tex

Листинг 3. Пример форматирования текста

\section{Введение} \label{sec:intro} % Что должно быть во введении \begin{enumerate} \item Актуальность \item Определение предмета исследования \item Определение цели работы \item Постановка задач работы \item Структура работы \end{enumerate} В заключении подводятся итоги по результатам разработки и тестирования программного продукта. Структура программы подробно описана в разделе~\ref{sec:program:structure} на стр.~\pageref{sec:program:structure}. \section{Анализ предметной области} \label{sec:teor} В данном разделе проводится анализ основной задачи и области исследования. \subsection{Обзор предметной области} \label{sec:teor:overview} \subsubsection{Анализ программного обеспечения} \label{sec:teor:prog} \subsubsection{Выводы по главе} \label{sec:teor:res1} \section{Программная реализация} \label{sec:program} В данном разделе описывается процесс разработки программного продукта, а также используемых средств проектирования. \subsection{Структура программного продукта} \label{sec:program:structure}

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

Кроме символа процента необходимо экранировать символы { } $ & # _. Также специальным является и символ \.

Окружение enumerate формирует нумерованное перечисление. Аналогично ненумерованное перечисление создаётся с помощью окружения itemize.

Обратите внимание на метки, поставленные с помощью команды \label вслед за заголовками. Используя эти метки, можно с помощью команд \ref и \pageref сослаться на номер и страницу соответствующего раздела. Для выставления правильной нумерации в ссылках компилятору потребуется выполнить два прохода при построении документа.

Практическое задание 2

1. Замените необходимые элементы оформления и текст на соответствующие для вашей группы и изучаемой дисциплины. Можно воспользоваться примерной структурой выпускной квалификационной работы бакалавра Руководство к написанию ВКР 2016.pdf либо использовать любую вашу курсовую работу.
2. Измените шрифт текста на Times New Roman.
3. Уберите нумерацию глав введения и заключения.

 

Вставка картинок

Файлы с изображениями следует готовить за пределами LaTeX, используя специализированные графические редакторы. Если в качестве компилятора используется pdflatex из актуальных дистрибутивов LaTeX, то в документ можно вставлять как векторные картинки в форматах eps и pdf, так и растровые в форматах jpeg и png. По возможности лучше использовать векторные форматы, так как они позволяют себя масштабировать без ухудшения качества изображения.

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

Для вставки файла Sibsau_Logo. jpg его нужно положить в каталог, где уже находится исходный tex-файл (Kurs.tex). Вставка изображения в документ выполняется, как показано в листинге 5.

Листинг 5. Вставка изображения в LaTeX-документ

Логотип Сибирского государственного университета науки и технологий представлен на Рис.~\ref{fig:Sibsau_Logo}.   \begin{figure}[htbp] \centering \includegraphics[width=0.2\textwidth]{Sibsau_Logo} \caption{СибГУ им. М.Ф. Решетнева}\label{fig:Sibsau_Logo} \end{figure}

Команда \includegraphics вставляет картинку, а команда \caption формирует подпись к ней. Окружение figure является "плавающим", и поэтому может расположить картинку с подписью наиболее удачным способом. Но если картинок много, то LaTeX может с этим не справиться и тогда лучше формировать связки из нескольких команд \includegraphics в пределах одного элемента figure.

Практическое задание 4

1. Вставьте рисунок в главу «Анализ предметной области», при этом задайте расположение рисунку (изменяя параметр окружения figure) так, чтобы он разместился вверху страницы.

2. Задайте расположение рисунка справа от текста в главе 2.1.1, размер 0,3 от ширины страницы.

Вставка кода

Для добавления неформатируемых фрагментов текста (например, программного кода) в LaTeX-лучше всего использовать окружение verbatim, как показано в листинге 6.

Листинг 6. Пример включения неформатируемого текста в LaTeX-документ

\begin{verbatim} for alpha:=-90 step 3 until 0: label(btex IBM developerWorks etex scaled (5*(1+alpha/100)) rotated alpha,(0,0)) withcolor (max(1+alpha/45,0)*red+ min(-alpha/45,2+alpha/45)*green+ max(-alpha/45-1,0)*blue); endfor; \end{verbatim}

 

Практическое задание 5

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

 

Библиография

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

Листинг 7. Создание библиографии

1 2 3 4 5 6 7

\begin{thebibliography}{9} \bibitem{Knuth-2003}Кнут Д.Э. Всё про \TeX. \newblock --- Москва: Изд. Вильямс, 2003. 550~с. \bibitem{Baldin-2008}Балдин Е.М. Компьютерная типография \LaTeX. \newblock --- Санкт-Петербург: Изд. БХВ-Петербург, 2008. 302~с. \end{thebibliography}

Команды \bibitem формируют библиографические ссылки, на которые можно ссылаться с помощью команды \cite, как показано ниже (ссылаться можно даже из тех фрагментов текста, которые располагаются выше определения ссылки):

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

Практическое задание 6

1. Добавьте новый источник в список литературы.

2. Осуществите ссылку на один из использованных источников.

 

 

Задание на лабораторную работу

1. Ознакомиться с теоретическим материалом.

2. Выполнить практические задания, указанные по ходу работы.

3. Подготовить файлы HelloWorld.tex, kursTitle.tex, Kurs.tex, а также соответствующие скомпилированные pdf-файлы для защиты работы.

4. Собрать при помощи средств LaTeX текст со всех трех исходных файлов в один с названием Lab1_Фамилия_Группа.tex

 

 

Рекомендуемая листература

 

Документация LaTeX

https://ru.wikibooks.org/wiki/LaTeX

https://www.intuit.ru/studies/courses/1137/137/info

http://www.inp.nsk.su/~baldin/LaTeX/lurs.pdf

 

Дистрибутив для работы с LaTeX документами

https://miktex.org/     

 

 

5. Контрольные вопросы

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

2. Понятие тегов. Способы задания форматирования документа.

3. Основные теги для форматирования уровней текста в документе.

4. Основные способы вставки изображений в документ.

5. Основные теги для работы с формулами.

6. Способы создания библиографии. Достоинства при использовании библиографии.

7. Способы создания разделов в документе.

 

Лабораторная работа №2

Нахождение оптимальной стратегии с использованием
языков высокого уровня

 

Цель работы

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

 

Теоретическая часть

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

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

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

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

С точки зрения информированности лица, принимающего решения (ЛПР), относительно зависимости исходов операции от условий ее проведения и принимаемых решений различают следующие варианты задач принятия решений:

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

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

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

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

Остановимся подробнее на принятии решений в условиях неопределенности.

 

Критерий Лапласа

При j = 1,2,3,4 вероятности

Тогда ожидаемые значения затрат для различных возможных решений вычисляются следующим образом:

Минимаксный критерий

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

 

Таблица 2 – Модифицированная матрица затрат

 

Критерий Сэвиджа

Определим матрицу потерь, путем вычитания чисел 5,7,12 и 15 из элементов столбцов от первого до четвертого соответственно (табл. 3).

 

Таблица 3 – Модифицированная матрица потерь

16

 

Критерий Гурвица

Расчет по критерию Гурвица приведен в табл. 4.

Таблица 4 – Выполнение расчетов по критерию Гурвица

Подставив α определим оптимальную стратегию. При α=0,5 оптимальными являются либо стратегия a1, либо а2. При α=0,25 оптимальным является решение а3.

 

Методика выполнения работы

1. Изучить теоретический материал.

2. Найти оптимальную стратегию для различных критериев аналитическим методом.

3. Написать программу на любом языке программирования для расчёта оптимальной стратегии с использованием четырех критериев.

4. Предоставить пользователю выбор одного из критериев для расчёта оптимальной стратегии.

5. Выбрать входные данные в соответствии с вариантом задания по номеру обучающегося в группе либо предоставить пользователю возможность ввода исходных данных.

5. Описать словесную формулировку принятия решений в условиях неопределенности в отчете.

6. Составить отчет.

 

Таблица 4 - Варианты заданий

№ варианта	Задача	№ варианта	Задача
1	S1 S2 S3 S4 X1 6 12 20 24 X2 9 7 9 28 X3 23 18 15 19 X4 27 24 21 15	9	S1 S2 S3 S4 S5 X1 6 2 4 10 14 X2 9 7 14 9 18 X3 13 18 16 15 9 X4 17 14 12 11 15 X5 15 10 15 17 12
2	S1 S2 S3 S4 X1 16 12 10 14 X2 19 17 9 18 X3 13 18 15 9 X4 17 14 11 15	10	S1 S2 S3 S4 X1 16 12 10 24 X2 19 17 29 18 X3 13 28 15 9 X4 27 14 11 15
3	S1 S2 S3 S4 S5 X1 16 22 20 14 20 X2 19 27 29 18 25 X3 13 28 25 19 27 X4 17 24 21 15 22	11	S1 S2 S3 S4 X1 6 12 20 4 X2 9 7 9 8 X3 23 18 15 9 X4 27 24 21 5
4	S1 S2 S3 S4 X1 6 2 10 14 X2 9 7 9 18 X3 13 18 15 9 X4 17 14 11 15	12	S1 S2 S3 S4 S5 X1 20 24 23 26 22 X2 19 28 25 29 27 X3 25 19 30 23 28 X4 21 25 19 27 24
5	S1 S2 S3 S4 X1 26 22 20 24 X2 29 27 19 28 X3 23 28 25 19 X4 27 24 21 25	13	S1 S2 S3 S4 X1 6 2 9 4 X2 9 17 9 8 X3 3 18 15 9 X4 7 4 9 5
6	S1 S2 S3 S4 S5 X1 6 18 12 20 24 X2 9 7 7 9 28 X3 23 13 18 15 19 X4 27 19 24 21 15	14	S1 S2 S3 S4 X1 26 12 20 24 X2 9 27 9 28 X3 23 18 25 19 X4 27 24 21 25
7	S1 S2 S3 S4 X1 26 12 20 24 X2 9 27 9 28 X3 23 18 25 19 X4 12 30 17 25 X5 27 24 21 15	15	S1 S2 S3 S4 S5 X1 26 22 20 24 20 X2 29 7 9 28 15 X3 23 18 15 29 12 X4 27 24 21 25 22
8	S1 S2 S3 S4 X1 16 12 10 14 X2 18 23 20 16 X3 19 17 9 18 X4 13 18 15 9 X5 17 14 11 15	16	S1 S2 S3 S4 X1 26 12 10 24 X2 29 17 19 28 X3 23 18 15 29 X4 27 14 11 25 X5 27 24 21 5

Содержание отчета

Отчет по лабораторной работе должен содержать:

а) название и цель работы;

б) вариант задания;

в) описание хода работы;

г) выводы по работе.

 

6. Контрольные вопросы

1. Назовите особенности принятия решений в условиях неопределенности.

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

3. Дайте характеристику критериев принятия решений в условиях неопределенности.

4. Охарактеризуйте особенности использования табличного редактора MS Excel для решения задачи принятия решений в условиях неопределенности.

5. Какую роль имеет значение показателя α на принятие решения с использованием критерия Гурвица?

Лабораторная работа №3

Цель работы

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

 

Теоретическая часть

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

 

Области применения

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

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

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

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

Разработка типологии или классификации.

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

Представление гипотез на основе исследования данных.

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

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

 

Рассмотрим пример процедуры кластерного анализа.

Допустим, мы имеем набор данных А, состоящий из 14-ти примеров, у которых имеется по два признака k ₁ и k ₂. Данные по ним приведены в таблице 1.

Таблица 1. Исходные данные

№ примера	признак k 1	признак k 2
1	27	19
2	11	46
3	25	15
4	36	27
5	35	25
6	10	43
7	11	44
8	36	24
9	26	14
10	26	14
11	9	45
12	33	23
13	27	16
14	19	47

 

Данные в табличной форме не носят информативный характер. Представим переменные X и Y в виде диаграммы рассеивания, изображенной на рис. 1.

Рис. 1. Диаграмма рассеивания переменных X и Y

 

На рисунке мы видим несколько групп «похожих» примеров. Примеры (объекты), которые по значениям X и Y «похожи» друг на друга, принадлежат к одной группе (кластеру); объекты из разных кластеров не похожи друг на друга.

Критерием для определения схожести и различия кластеров является расстояние между точками на диаграмме рассеивания. Это сходство можно «измерить», оно равно расстоянию между точками на графике. Способов определения меры расстояния между кластерами, называемой еще мерой близости, существует несколько. Наиболее распространенный спосо<