материалдар жинағы, 25 қараша, 2022 жыл

Университеттің 85 жылдығына арналған «Қазіргі заманғы математика: 
проблемалары және қолданыстары» III халықаралық Тайманов оқуларының 
материалдар жинағы, 25 қараша, 2022 жыл 
328 
0,8 
0,7 
0,5 
0,6 
Алгоритм к-средних (k-means) 
Пусть имеется множество объектов 
I 
. Сначала 
каким-либо образом выбираются 
K 
начальных точек (центров). Затем осуществляется 
последовательность итераций, каждая из которых состоит их двух шагов: 
1.
Обновление кластеров. При заданных 
K 
центрах 
C
k
 
, 
k 
= (1,2,.., 
K 
) 
каждый объект 
i 
I 
приписывается к ближайшему из центров 
C
k
 
. Таким образом, 
образуются кластеры 
S
k
 
, 
k 
= (1,2,.., 
K 
) 
. 
2.
 
Обновление центров. Для каждого кластера 
S
k
 
вычисляется его центр 
тяжести (внутри классовое среднее), который объявляется новым центром
C
k
. 
Процесс останавливается, когда кластеры на шаге 
t 
совпадут с кластерами 
на шаге 
t 
[10]. 
Алгоритм к-средних для кластеризации множества формул Ł
n
 
Рассмотрим конечное множество логических формул Ł
n
. Центрами будут являться 
некоторые 
K 
формул из данного множества. Сначала определяем количество кластеров, 
затем выбираем центры кластеров, анализируя матрицу расстояний. Будем исходить из 
следующих предположений:— центры должны быть почти равноудалены друг от друга; 
— расстояния между кластерами должны быть максимально возможными, с учѐтом 
предыдущего пункта. 
Например, исходя из вышесказанного, из двух имеющихся вариантов (рис. 2) мы 
выберем второй. 
φ
1
φ
1
Итерация: 
φ
3
φ
2
0,4 
φ
3
φ
2
0,5 
Рис. 2. 
Шаг 1. Приписываем каждую формулу из множества к ближайшему центру. 
Шаг 2. Центр масс — столбец значений логики Ł
n
. Для определения этого столбца 
учитывается специфика многозначных логических формул: 
Вычисляется среднее арифметическое 
S
a
 
каждой модели. 
значений элементов одного кластера на 
Если 
S 
принадлежит множеству логических значений 
V 
=
1 
,..., 
n 
2 
, то 
a 
 
оно записывается в столбец значений. 
n 
1, 
n 
1 
n 
1 
,1
Если 
S
a 
V
n 
, то в столбец значений записывается ближайшее снизу (или 
ближайшее сверху, это определяется до начала работы алгоритма) значение из 
V
n
 
оставаться в том же множестве моделей, и в той же логике Ł
n
). 
Итерации продолжаются, пока кластеры не перестанут изменяться. 
(чтобы 
Пример: 
Рассмотрим множество из восьми формул из предыдущего примера. 
Допустим, нам нужно получить три кластера. Анализируя матрицу расстояний, выбираем 

Университеттің 85 жылдығына арналған «Қазіргі заманғы математика: 
проблемалары және қолданыстары» III халықаралық Тайманов оқуларының 
материалдар жинағы, 25 қараша, 2022 жыл 
329 
2 
2 
2 
4 
центрами формулы 
2
4
, 
5
) = 0,4032 
). 
, 
4
, 
5
. ( 
2
, 
4
) = 0,5472 
, 
2
, 
5
) = 0,5000 
, 
Распределяем оставшиеся формулы по центрам. Получаются кластеры: 
2
; 
1 
, 
3 
, 
4 
, 
6 
, 
7 
; 
5
, 
8
. 
Ищем центры масс. Рассмотрим наглядно, как это происходит: 
C 
= 
1 
+ 
1
/ 2 = 
1 
1 1 3 
1
0, , 
2 
4 
, ,1
2 4 
C 
= 
1 
+ 
3
/ 2 = 
5 
1 1 3 
2
0, 
8 
, , 
4 2 4 
,1
Допустим, в качестве значения мы определились брать ближайшее сверху 
значение. Тогда 
C
2
= 
3 
. Остальное — аналогично. Таким образом, мы вычисляем центры 
4 
тяжести кластеров. 
Снова распределяем формулы по обновлѐнным центрам. Получаются следующие 3 
кластера: 
2
; 
1 
, 
3 
, 
4 
, 
6 
, 
7 
; 
5
, 
8
. 
Кластеры не изменились. Следовательно, алгоритм останавливается и выдаѐт 
получившиеся кластеры в качестве результата. 
Заметим, что при таком начальном выборе центров получившиеся кластеры 
совпадают с кластерами на пятой итерации иерархического алгоритма. 
Наблюдения и выводы для различных N 
2 
Был создан банк из 500 различных 
логических формул, откуда случайным образом выбирались подмножества формул. С 
помощью адаптированных алгоритмов, описанных в предыдущей главе, было проведено 
более 150 кластеризаций таких подмножеств при различных n, где n — это размерность, 
например, логики Лукасевича Ł
n
. 
Исходя из рассмотренных примеров, были сделаны следующие выводы: 
1.
Для n = 2,…,7 наблюдается различие в составе кластеров. Начиная с n = 8 
кластеры и последовательность итераций практически не меняются (8 — это 
максимальное такое значение n для рассмотренных примеров. Для некоторых множеств 
состав кластеров не меняется даже после n = 4, для других — после n = 5. и т. д.). 
Таким образом, возникает гипотеза о нецелесообразности использования логики 
большой значности в реальных задачах от небольшого числа переменных. Частично это 
подтверждается самой конструкцией введѐнного того или иного расстояния. 
2.
Для алгоритма к-средних при вычислении центров масс наблюдаются одни и те 
же результаты как при замене среднего арифметического ближайшим сверху значением из 
V
n
 
, так и ближайшим снизу. Для данных вычислений расстояния и адаптированные 
алгоритмы кластеризации были программно реализованы. 
Заключение. 
В работе выполнены следующие задачи. Расстояния между 
логическими формулами и меры нетривиальности высказываний обобщены на случай 
произвольной n-значной логики, в частности с полной мерой учета многозначности; 
доказаны свойства этих величин, схожие со свойствами расстояния и меры как в случае 
классической логики, как и в случае произвольной многозначной логики. Также 
определѐн общий случай расстояния между логическими формулами, когда некоторые 
значения переменных заранее известны, что также является актуальным для реальных 
задач, когда некоторая информация уже задана. 
x 
y 
z w θ
5
θ
8
C
58 
0 
1 
2 
0 0 
1 
2 
1 
2 
C
1
1 
4 
1 
2 
0 0 
1 
2 
3 
4 
C
2
… 

жүктеу/скачать 12,2 Mb.

Достарыңызбен бөлісу: