DBSCAN和K-means的区别。
思考：
- 如何判断高密度的对象点？
- 如何判断离群/噪声点？
- 如何发现簇？簇：稠密对象趋于，被噪声分隔开，是密度相连的点的最大集合。
概念
邻域 Neighborhood
给定对象半径 ε 内的邻域称为该对象的 ε 邻域。
密度 Density
邻域内的对象点个数。
高密度 High Density
邻域至少包含 MinPts 个对象。称对应的对象为核心对象。
把所有的核心对象着色，但是这不是我们想要的簇。
边界对象 Border Points
虽然邻域小于 MinPts，但是在某个核心对象的邻域中。
离群点/噪声 Noise Or Outlier
对象的邻域小于 MinPts 个对象，而且不是边界点。
我们把簇定义为密度相连的点的最大集合。
直接密度可达 Direct Density Reachable
在邻域中有核心对象。
密度可达 Reachability
从核心点出发，一个点链中间都是直接密度可达的，而且除了末端点，都是核心对象。
密度相连
o→p,o→q 都是密度可达的，则 p,q 密度相连。
代码实现
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
| #include "matrix.h"
#include "euclid.h"
#define MAXN 1005
using namespace std;
Matrix<long double>pt[MAXN];
long double dis[MAXN][MAXN];
int belong[MAXN];
bool core[MAXN],vis[MAXN];
int cluster;
vector<int>adj[MAXN];
void dfs_paint(int u,int color){
vis[u]=true;
belong[u]=color;
for (int v:adj[u]){
if (!vis[v]) dfs_paint(v,color);
}
}
int main(){
int n,m;
cin>>n>>m;
for (int i=1;i<=n;++i){
pt[i].resize(1,m);
for (int j=1;j<=m;++j){
cin>>pt[i][1][j];
}
}
long double eps=1000;
int MinPts=5;
for (int i=1;i<=n;++i){
int cnt=0;
for (int j=1;j<=n;++j){
dis[i][j]=length(pt[i]-pt[j]);
if (dis[i][j]<=eps) cnt++;
}
if (cnt>=MinPts) core[i]=true;
}
for (int i=1;i<=n;++i){
if (core[i]){
for (int j=i+1;j<=n;++j){
if (dis[i][j]<=eps && core[j]){
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
}
for (int i=1;i<=n;++i){
if (core[i] && !vis[i]){
dfs_paint(i,++cluster);
}
}
for (int i=1;i<=n;++i){
cout<<belong[i]<<" ";
}
cout<<endl;
}
|
