Code Coverage |
||||||||||
Classes and Traits |
Functions and Methods |
Lines |
||||||||
| Total | |
0.00% |
0 / 1 |
|
75.00% |
3 / 4 |
CRAP | |
96.67% |
29 / 30 |
| DBSCAN | |
0.00% |
0 / 1 |
|
75.00% |
3 / 4 |
13 | |
96.67% |
29 / 30 |
| __construct | |
100.00% |
1 / 1 |
2 | |
100.00% |
6 / 6 |
|||
| cluster | |
100.00% |
1 / 1 |
4 | |
100.00% |
10 / 10 |
|||
| getSamplesInRegion | |
100.00% |
1 / 1 |
3 | |
100.00% |
5 / 5 |
|||
| expandCluster | |
0.00% |
0 / 1 |
4.02 | |
88.89% |
8 / 9 |
|||
| <?php | |
| declare (strict_types = 1); | |
| namespace Phpml\Clustering; | |
| use Phpml\Math\Distance; | |
| use Phpml\Math\Distance\Euclidean; | |
| class DBSCAN implements Clusterer | |
| { | |
| /** | |
| * @var float | |
| */ | |
| private $epsilon; | |
| /** | |
| * @var int | |
| */ | |
| private $minSamples; | |
| /** | |
| * @var Distance | |
| */ | |
| private $distanceMetric; | |
| /** | |
| * @param float $epsilon | |
| * @param int $minSamples | |
| * @param Distance $distanceMetric | |
| */ | |
| public function __construct($epsilon = 0.5, $minSamples = 3, Distance $distanceMetric = null) | |
| { | |
| if (null === $distanceMetric) { | |
| $distanceMetric = new Euclidean(); | |
| } | |
| $this->epsilon = $epsilon; | |
| $this->minSamples = $minSamples; | |
| $this->distanceMetric = $distanceMetric; | |
| } | |
| /** | |
| * @param array $samples | |
| * | |
| * @return array | |
| */ | |
| public function cluster(array $samples) | |
| { | |
| $clusters = []; | |
| $visited = []; | |
| foreach ($samples as $index => $sample) { | |
| if (isset($visited[$index])) { | |
| continue; | |
| } | |
| $visited[$index] = true; | |
| $regionSamples = $this->getSamplesInRegion($sample, $samples); | |
| if (count($regionSamples) >= $this->minSamples) { | |
| $clusters[] = $this->expandCluster($regionSamples, $visited); | |
| } | |
| } | |
| return $clusters; | |
| } | |
| /** | |
| * @param array $localSample | |
| * @param array $samples | |
| * | |
| * @return array | |
| */ | |
| private function getSamplesInRegion($localSample, $samples) | |
| { | |
| $region = []; | |
| foreach ($samples as $index => $sample) { | |
| if ($this->distanceMetric->distance($localSample, $sample) < $this->epsilon) { | |
| $region[$index] = $sample; | |
| } | |
| } | |
| return $region; | |
| } | |
| /** | |
| * @param array $samples | |
| * @param array $visited | |
| * | |
| * @return array | |
| */ | |
| private function expandCluster($samples, &$visited) | |
| { | |
| $cluster = []; | |
| foreach ($samples as $index => $sample) { | |
| if (!isset($visited[$index])) { | |
| $visited[$index] = true; | |
| $regionSamples = $this->getSamplesInRegion($sample, $samples); | |
| if (count($regionSamples) > $this->minSamples) { | |
| $cluster = array_merge($regionSamples, $cluster); | |
| } | |
| } | |
| $cluster[] = $sample; | |
| } | |
| return $cluster; | |
| } | |
| } |