Задача кластеризации, Аппарат нечетких множеств - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом

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

Аппарат нечетких множеств

Метод основан на выборе транзитивно ближайших сообщений [2].

При данном подходе каждому объекту сообщению ставится в соответствие пункт на карте. Пункты характеризуются расстояниями между собой.

Пусть Е = max A(i, j) по всем i, j - максимальный элемент матрицы расстояний А.

Тогда матрица В = [B(i, j)] размерности N x N, где B(i, j) = 1 - А(i, j) / Е

Задает нечеткое отношение сходства. 0 ? B(i, j) ? 1.

Транзитивное замыкание нечеткого отношения сходства задается матрицей D = [D(i, j)] размерности n x n. 0 ? D(i, j) ? 1.

D = В U В2 U В3 U ... U ВN,

Где U - операция объединения нечетких отношений (MAX).

В2 = B o B Представляет собой (Max - min)-композицию нечеткого отношения самого на себя.

B2 (x, z) = MAX [MIN (B(x, y), B(y, z))].

Y

ВK+1 = BK o B - (Max - min)-композиция нечетких отношений BK и B.

B k+1 (x, z) = MAX [MIN (BK(x, y), B(y, z))].

D - матрица задающая нечеткое отношение эквивалентности (подобия). Это отношение рефлексивно, симметрично и транзитивно. Согласно теореме о декомпозиции для отношения подобия, для каждого значения матрицы D (в порядке возрастания их значения) получаем транзитивно ближайшие сообщения (пункты).

Таким образом, в итоге получаем разбиение множества объектов на заранее заданное число компактных (транзитивно-ближайших) групп.

Похожие статьи




Задача кластеризации, Аппарат нечетких множеств - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом

Предыдущая | Следующая