Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

164
Глава 6.
Кластеризация методом k-средних
формулу.и.вывели.ее.версию.для.двумерных.пространств.в.главе.2,.где.с.ее.по-
мощью.искали.расстояние.между.любыми.двумя.точками.в.лабиринте..Версия.
для.
DataPoint
.должна.быть.более.сложной,.поскольку.
DataPoint
.может.включать.
в.себя.любое.количество.измерений.
Квадраты.каждой.из.разностей.суммируются,.и.окончательное.значение,.воз-
вращаемое.функцией.
distance()
,.является.квадратным.корнем.из.данной.суммы.
6.2. АЛГОРИТМ КЛАСТЕРИЗАЦИИ 
МЕТОДОМ k-СРЕДНИХ
Метод.
k
-средних.—.это.алгоритм.кластеризации,.который.стремится.сгруппи-
ровать.единицы.данных.в.некое.заранее.определенное.количество.кластеров..
В.каждом.периоде.
k
-средних.вычисляется.расстояние.между.каждой.единицей.
данных.и.каждым.центром.кластера.—.единицей.данных,.известной.как.
центроид
..
Единицы.данных.присваиваются.кластеру,.к.центроиду.которого.они.ближе.всего..
Затем.алгоритм.пересчитывает.все.центроиды,.находя.среднее.значение.единиц.
данных,.назначенных.каждому.кластеру,.и.заменяя.старый.центроид.новым.сред-
ним..Процесс.назначения.единиц.данных.и.пересчета.центроидов.продолжается.
до.тех.пор,.пока.центроиды.не.перестанут.передвигаться.или.не.будет.выполнено.
определенное.количество.итераций.
Все.измерения.начальных.точек,.представленных.
k
-средними,.должны.быть.со-
поставимыми.по.величине..Иначе.
k
-средние.будут.отклоняться.в.сторону.класте-
ризации.на.основе.измерений.с.наибольшим.отличием..Процесс.сопоставления.
разных.типов.данных.(в.нашем.случае.разных.измерений).называется.
нормали-
зацией
..Одним.из.распространенных.способов.нормализации.данных.является.
приближенная.оценка.каждого.значения.на.основе.его.
z-оценки
,.известной.также.
как.
стандартная
.
оценка
,.относительно.других.значений.того.же.типа..
Z
-оценка.
рассчитывается.путем.вычитания.среднего.всех.значений.из.данного.значе-
ния.и.деления.результата.на.стандартное.отклонение.всех.значений..Функция.
zscores()
,.разработанная.в.начале.предыдущего.раздела,.делает.именно.это.для.
каждого.значения.итерируемого.объекта,.состоящего.из.значений.типа.
doubles
.
Основная.сложность,.связанная.с.алгоритмом.
k
-средних,.заключается.в.опреде-
лении.способа.выбора.начальных.центроидов..В.простейшей.форме.алгоритма,.
которую.мы.будем.реализовывать,.начальные.центроиды.размещаются.случай-
ным.образом.в.пределах.диапазона.данных..Сложно.также.решить,.на.сколько.
кластеров.разделить.данные.(
k
.в.
k
-средних)..В.классическом.алгоритме.это.
число.определяет.пользователь,.но.он.может.не.знать.правильного.числа,.и.его.
определение.потребует.некоторого.количества.экспериментов..Мы.позволим.
пользователю.определить.
k
.

---

6.2. Алгоритм кластеризации методом k-средних
165
Объединяя.все.эти.этапы.и.соображения,.получим.следующий.алгоритм.класте-
ризации.методом.
k
-средних.
1.. Инициализировать.все.единицы.данных.и.
k
.пустых.кластеров.
2.. Нормализовать.все.единицы.данных.
3.. Создать.случайные.центроиды,.связанные.с.каждым.кластером.
4.. Назначить.каждую.единицу.данных.кластеру.того.центроида,.к.которому.она.
расположена.ближе.всего.
5.. Пересчитать.каждый.центроид,.чтобы.он.был.центром.(средним).кластера,.
с.которым.связан.
6.. Повторять.пункты.4.и.5.до.тех.пор,.пока.не.будет.выполнено.максимально.
допустимое.количество.итераций.или.пока.центроиды.не.перестанут.пере-
двигаться.(сходиться).
Концептуально.метод.
k
-средних,.в.сущности,.очень.прост:.на.каждой.итерации.
каждая.единица.данных.связана.с.тем.кластером,.к.центру.которого.она.располо-
жена.ближе.всего..По.мере.того.как.в.кластер.вносятся.новые.единицы.данных,.
этот.центр.перемещается.(рис..6.1).
Поколение 1
Поколение 2
Поколение 3