разделены объекты.
Работа алгоритма состоит из четырех шагов
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
1> Do'stlaringiz bilan baham: |