Space::iterate() - Code Metrics - Inspection of "permutable point distance algorithm #12" - bdelespierre/php-kmeans - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Pull Request — master (#13)

by Benjamin

created 2021-05-19 11:38 UTC

Space::iterate() B

↳ Parent: Space

Complexity

Conditions	9
Paths	56

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
dl	0
loc	48
rs	7.5789
c	0
b	0
f	0
cc	9
nc	56
nop	1

<?php

/**
 * This file is part of PHP K-Means
 *
 * Copyright (c) 2014 Benjamin Delespierre
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is furnished
 * to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

namespace KMeans;

use KMeans\Algorithms\CallbackDistance;
use KMeans\Algorithms\EuclidianDistance;
use KMeans\Interfaces\DistanceAlgorithmInterface;
use KMeans\Interfaces\SpaceInterface;

class Space extends \SplObjectStorage implements SpaceInterface
{
    protected $dimention;
    protected $distanceAlgo;

    protected static $rng = 'mt_rand';

    public function __construct($dimention)
    {
        if ($dimention < 1) {
            throw new \LogicException("a space dimention cannot be null or negative");
        }

        $this->dimention = $dimention;
        $this->setDistanceAlgorithm(new EuclidianDistance());
    }

    public static function setRng(callable $fn): void
    {
        static::$rng = $fn;

    }

    public function setDistanceAlgorithm($algo): void
    {
        if (is_callable($algo) && ! $algo instanceof DistanceAlgorithmInterface) {
            $algo = new CallbackDistance($algo);
        }

        if (! $algo instanceof DistanceAlgorithmInterface) {
            throw new \RuntimeException(
                "distance algorithm must implement KMeans\Interfaces\DistanceAlgorithmInterface"
            );
        }

        $this->distanceAlgo = $algo;

        foreach ($this as $point) {
            $point->setDistanceAlgorithm($algo);
        }
    }

    public function toArray(): array
    {
        $points = [];
        foreach ($this as $point) {
            $points[] = $point->toArray();
        }

        return ['points' => $points];
    }

    public function newPoint(array $coordinates): Point
    {
        if (count($coordinates) != $this->dimention) {
            throw new \LogicException("(" . implode(',', $coordinates) . ") is not a point of this space");
        }

        return new Point($this, $coordinates, $this->distanceAlgo);
    }

    public function addPoint(array $coordinates, $data = null): Point
    {
        $this->attach($point = $this->newPoint($coordinates), $data);

        return $point;
    }

    public function attach($point, $data = null): void
    {
        if (!$point instanceof Point) {
            throw new \InvalidArgumentException("can only attach points to spaces");
        }

        parent::attach($point, $data);
    }

    public function getDimention(): int
    {
        return $this->dimention;
    }

    public function getBoundaries(): array
    {
        if (!count($this)) {
            return [];
        }

        $min = $this->newPoint(array_fill(0, $this->dimention, null));
        $max = $this->newPoint(array_fill(0, $this->dimention, null));

        foreach ($this as $point) {
            for ($n = 0; $n < $this->dimention; $n++) {
                if ($min[$n] === null || $min[$n] > $point[$n]) {

                    $min[$n] = $point[$n];
                }

                if ($max[$n] === null || $max[$n] < $point[$n]) {

                    $max[$n] = $point[$n];
                }
            }
        }

        return [$min, $max];
    }

    public function getRandomPoint(Point $min, Point $max): Point
    {
        $point = $this->newPoint(array_fill(0, $this->dimention, null));
        $rng = static::$rng;

        for ($n = 0; $n < $this->dimention; $n++) {
            $point[$n] = $rng($min[$n], $max[$n]);
        }

        return $point;
    }

    public function solve(int $nbClusters, callable $iterationCallback = null): array
    {
        // initialize K clusters
        $clusters = $this->initializeClusters($nbClusters);

        // there's only one cluster, clusterization has no meaning
        if (count($clusters) == 1) {
            return $clusters;
        }

        // until convergence is reached
        do {
            if ($iterationCallback) {
                $iterationCallback($this, $clusters);
            }
        } while ($this->iterate($clusters));

        // clustering is done.
        return $clusters;
    }

    protected function initializeClusters(int $nbClusters): array
    {
        if ($nbClusters <= 0) {
            throw new \InvalidArgumentException("invalid clusters number");
        }

        $clusters = [];

        // get the space boundaries to avoid placing clusters centroid too far from points
        list($min, $max) = $this->getBoundaries();

        // initialize N clusters with a random point within space boundaries
        for ($n = 0; $n < $nbClusters; $n++) {
            $clusters[] = new Cluster($this, $this->getRandomPoint($min, $max)->getCoordinates());
        }

        // assign all points to the first cluster
        $clusters[0]->attachAll($this);

        return $clusters;
    }

    protected function iterate(array $clusters): bool
    {
        $continue = false;

        // migration storages
        $attach = new \SplObjectStorage();
        $detach = new \SplObjectStorage();

        // calculate proximity amongst points and clusters
        foreach ($clusters as $cluster) {
            foreach ($cluster as $point) {
                // find the closest cluster
                $closest = $point->getClosest($clusters);

                // move the point from its old cluster to its closest
                if ($closest !== $cluster) {
                    if (! isset($attach[$closest])) {
                        $attach[$closest] = new \SplObjectStorage();
                    }

                    if (! isset($detach[$cluster])) {
                        $detach[$cluster] = new \SplObjectStorage();
                    }

                    $attach[$closest]->attach($point);
                    $detach[$cluster]->attach($point);

                    $continue = true;
                }
            }
        }

        // perform points migrations
        foreach ($attach as $cluster) {
            $cluster->attachAll($attach[$cluster]);
        }

        foreach ($detach as $cluster) {
            $cluster->detachAll($detach[$cluster]);
        }

        // update all cluster's centroids
        foreach ($clusters as $cluster) {
            $cluster->updateCentroid();
        }

        return $continue;
    }
}


1		<?php
2
3		/**
4		* This file is part of PHP K-Means
5		*
6		* Copyright (c) 2014 Benjamin Delespierre
7		*
8		* Permission is hereby granted, free of charge, to any person obtaining a copy
9		* of this software and associated documentation files (the "Software"), to deal
10		* in the Software without restriction, including without limitation the rights
11		* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12		* copies of the Software, and to permit persons to whom the Software is furnished
13		* to do so, subject to the following conditions:
14		*
15		* The above copyright notice and this permission notice shall be included in all
16		* copies or substantial portions of the Software.
17		*
18		* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19		* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20		* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21		* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22		* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23		* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
24		* THE SOFTWARE.
25		*/
26
27		namespace KMeans;
28
29		use KMeans\Algorithms\CallbackDistance;
30		use KMeans\Algorithms\EuclidianDistance;
31		use KMeans\Interfaces\DistanceAlgorithmInterface;
32		use KMeans\Interfaces\SpaceInterface;
33
34		class Space extends \SplObjectStorage implements SpaceInterface
35		{
36		protected $dimention;
37		protected $distanceAlgo;
38
39		protected static $rng = 'mt_rand';
40
41		public function __construct($dimention)
42		{
43		if ($dimention < 1) {
44		throw new \LogicException("a space dimention cannot be null or negative");
45		}
46
47		$this->dimention = $dimention;
48		$this->setDistanceAlgorithm(new EuclidianDistance());
49		}
50
51		public static function setRng(callable $fn): void
52		{
53		static::$rng = $fn;
		0 ignored issues – show Documentation Bug introduced 2020-08-23 19:24 UTC by Report Bug Copy Issue Report It seems like `$fn` of type `callable` is incompatible with the declared type `string` of property `$rng`. Our type inference engine has found an assignment to a property that is incompatible with the declared type of that property. Either this assignment is in error or the assigned type should be added to the documentation/type hint for that property.. Loading history...
54		}
55
56		public function setDistanceAlgorithm($algo): void
57		{
58		if (is_callable($algo) && ! $algo instanceof DistanceAlgorithmInterface) {
59		$algo = new CallbackDistance($algo);
60		}
61
62		if (! $algo instanceof DistanceAlgorithmInterface) {
63		throw new \RuntimeException(
64		"distance algorithm must implement KMeans\Interfaces\DistanceAlgorithmInterface"
65		);
66		}
67
68		$this->distanceAlgo = $algo;
69
70		foreach ($this as $point) {
71		$point->setDistanceAlgorithm($algo);
72		}
73		}
74
75		public function toArray(): array
76		{
77		$points = [];
78		foreach ($this as $point) {
79		$points[] = $point->toArray();
80		}
81
82		return ['points' => $points];
83		}
84
85		public function newPoint(array $coordinates): Point
86		{
87		if (count($coordinates) != $this->dimention) {
88		throw new \LogicException("(" . implode(',', $coordinates) . ") is not a point of this space");
89		}
90
91		return new Point($this, $coordinates, $this->distanceAlgo);
92		}
93
94		public function addPoint(array $coordinates, $data = null): Point
95		{
96		$this->attach($point = $this->newPoint($coordinates), $data);
97
98		return $point;
99		}
100
101		public function attach($point, $data = null): void
102		{
103		if (!$point instanceof Point) {
104		throw new \InvalidArgumentException("can only attach points to spaces");
105		}
106
107		parent::attach($point, $data);
108		}
109
110		public function getDimention(): int
111		{
112		return $this->dimention;
113		}
114
115		public function getBoundaries(): array
116		{
117		if (!count($this)) {
118		return [];
119		}
120
121		$min = $this->newPoint(array_fill(0, $this->dimention, null));
122		$max = $this->newPoint(array_fill(0, $this->dimention, null));
123
124		foreach ($this as $point) {
125		for ($n = 0; $n < $this->dimention; $n++) {
126	View Code Duplication	if ($min[$n] === null \|\| $min[$n] > $point[$n]) {
		0 ignored issues – show Duplication introduced 2020-08-23 19:24 UTC by Report Bug Copy Issue Report This code seems to be duplicated across your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
127		$min[$n] = $point[$n];
128		}
129
130	View Code Duplication	if ($max[$n] === null \|\| $max[$n] < $point[$n]) {
		0 ignored issues – show Duplication introduced 2020-08-23 19:24 UTC by Report Bug Copy Issue Report This code seems to be duplicated across your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
131		$max[$n] = $point[$n];
132		}
133		}
134		}
135
136		return [$min, $max];
137		}
138
139		public function getRandomPoint(Point $min, Point $max): Point
140		{
141		$point = $this->newPoint(array_fill(0, $this->dimention, null));
142		$rng = static::$rng;
143
144		for ($n = 0; $n < $this->dimention; $n++) {
145		$point[$n] = $rng($min[$n], $max[$n]);
146		}
147
148		return $point;
149		}
150
151		public function solve(int $nbClusters, callable $iterationCallback = null): array
152		{
153		// initialize K clusters
154		$clusters = $this->initializeClusters($nbClusters);
155
156		// there's only one cluster, clusterization has no meaning
157		if (count($clusters) == 1) {
158		return $clusters;
159		}
160
161		// until convergence is reached
162		do {
163		if ($iterationCallback) {
164		$iterationCallback($this, $clusters);
165		}
166		} while ($this->iterate($clusters));
167
168		// clustering is done.
169		return $clusters;
170		}
171
172		protected function initializeClusters(int $nbClusters): array
173		{
174		if ($nbClusters <= 0) {
175		throw new \InvalidArgumentException("invalid clusters number");
176		}
177
178		$clusters = [];
179
180		// get the space boundaries to avoid placing clusters centroid too far from points
181		list($min, $max) = $this->getBoundaries();
182
183		// initialize N clusters with a random point within space boundaries
184		for ($n = 0; $n < $nbClusters; $n++) {
185		$clusters[] = new Cluster($this, $this->getRandomPoint($min, $max)->getCoordinates());
186		}
187
188		// assign all points to the first cluster
189		$clusters[0]->attachAll($this);
190
191		return $clusters;
192		}
193
194		protected function iterate(array $clusters): bool
195		{
196		$continue = false;
197
198		// migration storages
199		$attach = new \SplObjectStorage();
200		$detach = new \SplObjectStorage();
201
202		// calculate proximity amongst points and clusters
203		foreach ($clusters as $cluster) {
204		foreach ($cluster as $point) {
205		// find the closest cluster
206		$closest = $point->getClosest($clusters);
207
208		// move the point from its old cluster to its closest
209		if ($closest !== $cluster) {
210		if (! isset($attach[$closest])) {
211		$attach[$closest] = new \SplObjectStorage();
212		}
213
214		if (! isset($detach[$cluster])) {
215		$detach[$cluster] = new \SplObjectStorage();
216		}
217
218		$attach[$closest]->attach($point);
219		$detach[$cluster]->attach($point);
220
221		$continue = true;
222		}
223		}
224		}
225
226		// perform points migrations
227		foreach ($attach as $cluster) {
228		$cluster->attachAll($attach[$cluster]);
229		}
230
231		foreach ($detach as $cluster) {
232		$cluster->detachAll($detach[$cluster]);
233		}
234
235		// update all cluster's centroids
236		foreach ($clusters as $cluster) {
237		$cluster->updateCentroid();
238		}
239
240		return $continue;
241		}
242		}
243

bdelespierre / php-kmeans

Pull Request — master (#13)

Space::iterate() B

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like