Учебное пособие для студентов магистерских программ москва Екатеринбург 014 удк ббк п

разделены объекты.
Работа алгоритма состоит из четырех шагов
48
.
На первом шаге задается число 
k
исходных центров кластеров.
48
Паклин Н.Б., Орешков В.И. Бизнес-аналитика: от данных к знаниям (+CD).─ Спб.: Питер, 2009. ─ 624 с.: ил. 

---

177 
На втором шаге в качестве центров кластеров случайным обра-
зом выбираются 
k
объектов исходного множества.
На третьем шаге для каждого объекта производится расчет рас-
стояний до каждого из 
k
центров, и объект относится к тому кластеру, 
для которого это расстояние оказывается наименьшим. 
На четвертом шаге вычисляются центры полученных на преды-
дущем шаге кластеров. В качестве центров используются центры тя-
жести кластеров, или центроиды. Старый центр кластера переносится 
в его центроид.
Затем для новых центров кластеров повторяются шаги 3 и 4 до 
тех пор, пока расположение центров кластеров не перестанет изме-
няться. Обычно для этого достаточно нескольких десятков итераций. 
В качестве критерия сходимости алгоритма k-средних обычно 
используется сумма квадратов отклонений между центром каждого 
кластера и входящими в этот кластер объектами.
В заключение отметим, что для исследователя важным вопросом 
является выбор «лучшего» алгоритма, «лучшей» меры близости. Од-
нако если кластеры естественны и четко отделены друг от друга, то 
они будут выделены любым алгоритмом кластер-анализа. Поэтому 
критерием естественности классификации может быть устойчивость 
относительно выбора алгоритма кластер-анализа. 
Для проверки устойчивости можно применить для одних и тех же 
данных различные алгоритмы. Если в результате выделяются сходные 
кластеры, то можно полагать, что полученная классификация отражает 
существующие в природе объектов классы. Если же различные проце-
дуры выделяют непохожие кластеры, то, скорее всего, задача кластер-
анализа не имеет решения, и для исследуемой совокупности объектов 
можно проводить только операции группирования. 
Рассмотрим пример решения задачи классификации для базы 
данных помещений с использованием классификационной техники 
«Деревья решений» (деревья классификаций), в ходе которой 
решающие правила извлекаются непосредственно из исходных 
данных в процессе обучения. Дерево решений – это иерархическая 
модель, где в каждом узле производится проверка определенного 
атрибута(признака) с помощью правила (рисунок 5.14). Каждая 
выходящая из узла ветвь есть результат проверки, она содержит 
объекты, для которых значения данного атрибута удовлетворяют 

---

178 
правилу в узле. Каждый конечный узел дерева (лист) содержит 
объекты, относящиеся к одному классу
49
. 
 
Х = ?
Y = ?
Класс 1
Класс 2
Класс 3
X<1
X >=1
Y = A
Y = B