Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Алгорифм нечёткой кластеризации fuzzy c-means на PHP

Anna | 31.05.2014 | нет комментариев

Пост и код приведённый ниже, предуготовлен не столько для применения алгорифма в рабочих целях, сколько для того, Дабы осознать, как алгорифм fuzzy c-means работает и допустимо, дать толчок к реализации этого алгорифма на других языках либо для модернизации приведённого кода и его последующего применения в рабочих целях.

Всеобщие данные

Для начала стоит дюже стремительно рассказать, что такое кластеризация и что особенного в нечёткой кластеризации.

Кластеризация, как описывает это слово Викисловарь,

группировка, разбиение множества объектов на непересекающиеся подмножества, кластеры, состоящие из аналогичных объектов

Данное определение абсолютно внятное и я думаю не нуждается в дополнительном объяснении.

Что же тогда такое «нечёткая кластеризация»?
Нечёткую кластеризацию от легко кластеризации отличает то, что объекты, которые подвергаются кластеризации, относятся к определенному кластеру с некой принадлежностью, а не однозначно, как это бывает при обыкновенной кластеризации. Скажем, при нечёткой кластеризации объект A относится к кластеру K1 с принадлежностью 0.9, к кластеру K2 — с принадлежностью 0.04 и к кластеру К3 — с принадлежностью 0.06. При обыкновенной же (чёткой) кластеризации объект А был бы отнесён к кластеру K1.

Математическое изложение данного алгорифма Вы можете обнаружить в данном програпосте.

Реализация fuzzy c-means на PHP.

Давайте перейдём непринужденно к реализации алгорифма. Для этого я бы разглядел реализацию на больше-менее настоящем примере. Таким примером может быть дальнейший — давайте кластеризируем пиксели по их RGB-значению, т.е. реально по цвету. В результате, мы сумеем увидеть итог выполнения алгорифма наглядно.

Ниже приведён код алгорифма, тот, что дальше я разберу чуть подробнее.

Реализация алгорифма fuzzy c-means для кластеризации точек по их RGB-значению

define('EPLSION', 0.1);
define('MAX_EXECUTION_CYCLES', 150);
define('POINTS_COUNT', 100);
define('CLUSTERS_NUM', 3);
define('FUZZ', 1.5);

class Point
{
  public $r;
  public $g;
  public $b;
}

// Random values 0 - 1
function random_float ($min,$max) {
   return ($min lcg_value()*(abs($max-$min)));
}

//  Fuzzy C Means Algorithm
function distributeOverMatrixU($arr, $m, &$centers)
{
    $centers = generateRandomPoints(CLUSTERS_NUM);
    $MatrixU = fillUMatrix(count($arr), count($centers));

    $previousDecisionValue = 0;
    $currentDecisionValue = 1;

    for($a = 0; $a < MAX_EXECUTION_CYCLES && (abs($previousDecisionValue - $currentDecisionValue) > EPLSION); $a  ){
        $previousDecisionValue = $currentDecisionValue;
        $centers = calculateCenters($MatrixU, $m, $arr);

        foreach($MatrixU as $key=>&$uRow){
            foreach($uRow as $clusterIndex=>&$u){
                $distance = evklidDistance3D($arr[$key], $centers[$clusterIndex]);
                $u = prepareU($distance, $m);
            }

            $uRow = normalizeUMatrixRow($uRow);
        }
        $currentDecisionValue = calculateDecisionFunction($arr, $centers, $MatrixU);
    }

    return $MatrixU;
}

function fillUMatrix($pointsCount, $clustersCount)
{
    $MatrixU = array();
    for($i=0; $i<$pointsCount; $i  ){
        $MatrixU[$i] = array();
        for($j=0; $j<$clustersCount; $j  ){
            $MatrixU[$i][$j] = random_float(0, 1);
        }
        $MatrixU[$i] = normalizeUMatrixRow($MatrixU[$i]);
    }

    return $MatrixU;
}

function calculateCenters($MatrixU, $m, $points)
{
    $MatrixCentroids = array();

    for($clusterIndex=0; $clusterIndex < CLUSTERS_NUM; $clusterIndex  ){
        $tempAr = 0;
        $tempBr = 0;
        $tempAg = 0;
        $tempBg = 0;
        $tempAb = 0;
        $tempBb = 0;

        foreach($MatrixU as $key=>$uRow){
            $tempAr  = pow($uRow[$clusterIndex],$m);
            $tempBr  = pow($uRow[$clusterIndex],$m) * $points[$key]->r;

            $tempAg  = pow($uRow[$clusterIndex],$m);
            $tempBg  = pow($uRow[$clusterIndex],$m) * $points[$key]->g;

            $tempAb  = pow($uRow[$clusterIndex],$m);
            $tempBb  = pow($uRow[$clusterIndex],$m) * $points[$key]->b;
        }

        $MatrixCentroids[$clusterIndex] = new Point();
        $MatrixCentroids[$clusterIndex]->r = $tempBr / $tempAr;
        $MatrixCentroids[$clusterIndex]->g = $tempBg / $tempAg;
        $MatrixCentroids[$clusterIndex]->b = $tempBb / $tempAb;
    }

    return $MatrixCentroids;
}

function calculateDecisionFunction($MatrixPointX, $MatrixCentroids, $MatrixU)
{
    $sum = 0;
    foreach($MatrixU as $index=>$uRow){
        foreach($uRow as $clusterIndex=>$u){
            $sum  = $u * evklidDistance3D($MatrixCentroids[$clusterIndex], $MatrixPointX[$index]);
        }
    }

    return $sum;
}

function evklidDistance3D($pointA, $pointB)
{
    $distance1 = pow(($pointA->r - $pointB->r),2);
    $distance2 = pow(($pointA->g - $pointB->g),2);
    $distance3 = pow(($pointA->b - $pointB->b),2);
    $distance = $distance1   $distance2   $distance3;
    return sqrt($distance);
}

function normalizeUMatrixRow($MatrixURow)
{
    $sum = 0;
    foreach($MatrixURow as $u){
        $sum  = $u;
    }

    foreach($MatrixURow as &$u){
        $u = $u/$sum;
    }

    return $MatrixURow;
}

function prepareU($distance, $m)
{
    return pow(1/$distance , 2/($m-1));
}

function generateRandomPoints($count){
    $points = array_fill(0, $count, false);
    array_walk($points, function(&$value, $key){
        $value = new Point();
        $value->r = rand(20, 235);
        $value->g = rand(20, 235);
        $value->b = rand(20, 235);
    });

    return $points;
}

$points = generateRandomPoints(POINTS_COUNT);
$centers = array();

$matrixU = distributeOverMatrixU($points, FUZZ, $centers);

Начнём рассмотрение алгорифма с функции, которая собственно и запускает сам алгорифм кластеризации —distributeOverMatrixU
Входными параметрами для неё являются массив кластеризируемых объектов(в нашем случае рандомно заполненный массив, содержащий об]екты класса Point) и показатель неопределённости. Возвращаемое значение — матрица принадлежности. Также был добавлен в функцию in/out параметр centers, в котором позже выполнения алгорифма будут центры наших кластеров.

Шаги по нахождению новых центров кластеров и пересчёте матрицы принадлежности ограничены константами MAX_EXECUTION_CYCLES и EPSILON, где MAX_EXECUTION_CYCLES — ограничивает число шагов, EPSILON — ограничивает точность нахождения матрицы принадлежности.

Всякий шаг алгорифма таков:
1) рассчитываем центры кластеров с поддержкой функции calculateCenters
2) дальше для всякого объекта рассчитываем Евклидово расстояние до центра всякого кластера (функцияevklidDistance3D — пространство 3х мерное у нас)
3) рассчитываем показатель принадлежности для данного объекта (функция prepareU)
4) нормализуем показатели u для данного объекта (функция normalizeUMatrixRow)
5) рассчитываем значение решающей функции (функция calculateDecisionFunction)
6) дальше сравнивается нынешнее значение решающей функции с предыдущим её значением и если их разница поменьше установленного EPSILON, то алгорифм прекращает работу.

Сейчас чуть подробнее о всяком шаге:
1) центры рассчитываются по дальнейшей формуле
image
где wk(x) — показатель принадлежности, m — показатель неопределённости, x — объект (в самом алгорифме в качестве х выступают составляющие R, G, B)

2) Евклидово расстояние мы рассчитываем для 3х измерений, т.е. формула дальнейшая:
r = sqrt((r2-r1)^2 (g2-g1)^2 (b2-b1)^2);
где r,g,b — составляющие RGB

3) показатель принадлежности рассчитывается по формуле
u = (1/d)^(2/(m-1)),
где d — расстояние от объекта до центра кластера, m — показатель неопределённости.

4) нормализация всех показателей принадлежности объекта — преобразуем показатели, Дабы в сумме они давали 1, т.е. реально разделяем всякий показатель на сумму всех показателей данного объекта

5) решающая функция возвращает сумму всех Евклидовых расстояний всякого объекта к всякому центру кластера умноженному на показатель принадлежности

6) по модулю вычитаем предыдущее и нынешнее значение решающей функции, и если это разница поменьше EPSILON — алгорифм прекращает и возвращается обнаруженная матрица принадлежности.

В конце хотелось бы добавить пару скриншотов, демонстрирующих итоги работы алгорифма.
На рисунках видно, что алгорифм отработал правильно и отнём схожие по цветам точки к одним и тем же класстерам

Демонстрация работы алгорифма



Таким образом, я представил Вам базовую реализацию алгорифма нечёткой кластеризации fuzzy c-means. Верю, она будет Вам пригодна.
Спасибо за внимание.

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB