1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
# -*- coding: utf-8 -*-
"""
DBSCAN: Density-Based Spatial Clustering of Applications with Noise
"""
# Author: Robert Layton <robertlayton@gmail.com>
#
# License: BSD
import warnings
import numpy as np
from ..base import BaseEstimator
from ..metrics import pairwise_distances
from ..utils import check_random_state
def dbscan(X, eps=0.5, min_samples=5, metric='euclidean',
random_state=None):
"""Perform DBSCAN clustering from vector array or distance matrix.
Parameters
----------
X: array [n_samples, n_samples] or [n_samples, n_features]
Array of distances between samples, or a feature array.
The array is treated as a feature array unless the metric is given as
'precomputed'.
eps: float, optional
The maximum distance between two samples for them to be considered
as in the same neighborhood.
min_samples: int, optional
The number of samples in a neighborhood for a point to be considered
as a core point.
metric: string, or callable
The metric to use when calculating distance between instances in a
feature array. If metric is a string or callable, it must be one of
the options allowed by metrics.pairwise.calculate_distance for its
metric parameter.
If metric is "precomputed", X is assumed to be a distance matrix and
must be square.
random_state: numpy.RandomState, optional
The generator used to initialize the centers. Defaults to numpy.random.
Returns
-------
core_samples: array [n_core_samples]
Indices of core samples.
labels : array [n_samples]
Cluster labels for each point. Noisy samples are given the label -1.
Notes
-----
See examples/plot_dbscan.py for an example.
References
----------
Ester, M., H. P. Kriegel, J. Sander, and X. Xu, “A Density-Based
Algorithm for Discovering Clusters in Large Spatial Databases with Noise”.
In: Proceedings of the 2nd International Conference on Knowledge Discovery
and Data Mining, Portland, OR, AAAI Press, pp. 226–231. 1996
"""
X = np.asarray(X)
n = X.shape[0]
# If index order not given, create random order.
random_state = check_random_state(random_state)
index_order = np.arange(n)
random_state.shuffle(index_order)
D = pairwise_distances(X, metric=metric)
# Calculate neighborhood for all samples. This leaves the original point
# in, which needs to be considered later (i.e. point i is the
# neighborhood of point i. While True, its useless information)
neighborhoods = [np.where(x <= eps)[0] for x in D]
# Initially, all samples are noise.
labels = -np.ones(n)
# A list of all core samples found.
core_samples = []
# label_num is the label given to the new cluster
label_num = 0
# Look at all samples and determine if they are core.
# If they are then build a new cluster from them.
for index in index_order:
if labels[index] != -1 or len(neighborhoods[index]) < min_samples:
# This point is already classified, or not enough for a core point.
continue
core_samples.append(index)
labels[index] = label_num
# candidates for new core samples in the cluster.
candidates = [index]
while len(candidates) > 0:
new_candidates = []
# A candidate is a core point in the current cluster that has
# not yet been used to expand the current cluster.
for c in candidates:
noise = np.where(labels[neighborhoods[c]] == -1)[0]
noise = neighborhoods[c][noise]
labels[noise] = label_num
for neighbor in noise:
# check if its a core point as well
if len(neighborhoods[neighbor]) >= min_samples:
# is new core point
new_candidates.append(neighbor)
core_samples.append(neighbor)
# Update candidates for next round of cluster expansion.
candidates = new_candidates
# Current cluster finished.
# Next core point found will start a new cluster.
label_num += 1
return core_samples, labels
class DBSCAN(BaseEstimator):
"""Perform DBSCAN clustering from vector array or distance matrix.
DBSCAN - Density-Based Spatial Clustering of Applications with Noise.
Finds core samples of high density and expands clusters from them.
Good for data which contains clusters of similar density.
Parameters
----------
eps : float, optional
The maximum distance between two samples for them to be considered
as in the same neighborhood.
min_samples : int, optional
The number of samples in a neighborhood for a point to be considered
as a core point.
metric : string, or callable
The metric to use when calculating distance between instances in a
feature array. If metric is a string or callable, it must be one of
the options allowed by metrics.pairwise.calculate_distance for its
metric parameter.
If metric is "precomputed", X is assumed to be a distance matrix and
must be square.
random_state : numpy.RandomState, optional
The generator used to initialize the centers. Defaults to numpy.random.
Attributes
----------
`core_sample_indices_` : array, shape = [n_core_samples]
Indices of core samples.
`components_` : array, shape = [n_core_samples, n_features]
Copy of each core sample found by training.
`labels_` : array, shape = [n_samples]
Cluster labels for each point in the dataset given to fit().
Noisy samples are given the label -1.
Notes
-----
See examples/plot_dbscan.py for an example.
References
----------
Ester, M., H. P. Kriegel, J. Sander, and X. Xu, “A Density-Based
Algorithm for Discovering Clusters in Large Spatial Databases with Noise”.
In: Proceedings of the 2nd International Conference on Knowledge Discovery
and Data Mining, Portland, OR, AAAI Press, pp. 226–231. 1996
"""
def __init__(self, eps=0.5, min_samples=5, metric='euclidean',
random_state=None):
self.eps = eps
self.min_samples = min_samples
self.metric = metric
self.random_state = check_random_state(random_state)
def fit(self, X, **params):
"""Perform DBSCAN clustering from vector array or distance matrix.
Parameters
----------
X: array [n_samples, n_samples] or [n_samples, n_features]
Array of distances between samples, or a feature array.
The array is treated as a feature array unless the metric is
given as 'precomputed'.
params: dict
Overwrite keywords from __init__.
"""
if params:
warnings.warn('Passing parameters to fit methods is '
'depreciated', stacklevel=2)
self.set_params(**params)
self.core_sample_indices_, self.labels_ = dbscan(X,
**self.get_params())
self.components_ = X[self.core_sample_indices_].copy()
return self
|
