我正试图编写DBSCAN算法来聚类一组点,但我得到的结果非常糟糕。这可能是因为数据,但不仅仅是因为数据。我得到了大小为<不应该发生的minPoints>不应该发生的minPoints>
我做错了什么?这段代码我看了很多遍,还是不知道问题出在哪里。
我参考了DBSCAN维基百科页面上给出的算法。
private static int[] dbScan(String[] points, int epsilon, int minPts) {
int cluster = 0;
// visited stores if point has been visited
boolean[] visited = new boolean[points.length];
// pointsCluster stores which cluster a point has been assigned to
int[] pointsCluster = new int[points.length];
for(int iii = 0; iii < points.length; iii++) {
// if point iii is already visited, do nothing
if(visited[iii]) continue;
visited[iii] = true; // mark point iii as visited
// get points in neighborhood of point iii
HashSet<Integer> neighbors = epsilonNeighbors(points, iii, epsilon);
if(neighbors.size() < minPts) {
// if number of neighbors < minPts, mark point iii as noise
pointsCluster[iii] = -1;
} else {
++cluster; // else, start new cluster
expandCluster(points, iii, neighbors, pointsCluster, visited, cluster, epsilon, minPts);
}
}
return pointsCluster;
}
/*
* Expands a cluster if a point is not a noise point
* and has > minPts in its epsilon neighborhood
*/
private static void expandCluster(String[] points, int seedPoint, HashSet<Integer> neighbors,
int[] pointsCluster, boolean[] visited, int cluster, int epsilon, int minPts) {
pointsCluster[seedPoint] = cluster; //assign cluster to seed point
// create queue to process neighbors
Queue<Integer> seeds = new LinkedList<Integer>();
seeds.addAll(neighbors);
while(!seeds.isEmpty()) {
int currentPoint = (Integer) seeds.poll();
if(!visited[currentPoint]) {
visited[currentPoint] = true; // mark neighbor as visited
// get neighbors of this currentPoint
HashSet<Integer> currentNeighbors = epsilonNeighbors(points, currentPoint, epsilon);
// if currentPoint has >= minPts in neighborhood, add those points to the queue
if(currentNeighbors.size() >= minPts) {
seeds.addAll(currentNeighbors);
}
}
// if currentPoint has not been assigned a cluster, assign it to the current cluster
if(pointsCluster[currentPoint] == 0) pointsCluster[currentPoint] = cluster;
}
}
/*
* Returns a HashSet containing the indexes of points which are
* in the epsilon neighborhood of the point at index == currentPoint
*/
private static HashSet<Integer> epsilonNeighbors(String[] points, int currentPoint, int epsilon) {
HashSet<Integer> neighbors = new HashSet<Integer>();
String protein = points[currentPoint];
for(int iii = 0; iii < points.length; iii++) {
int score = similarity(points[iii], points[jjj]);
if(score >= epsilon) neighbors.add(iii);
}
return neighbors;
}
当你的结果不好时,可能是因为你的数据不好(对于基于密度的聚类),或者是因为你的参数不好。
实际上,DBSCAN 可以生成小于minpt的集群,如果它们相互接触的话。然后,他们可以"窃取"彼此的边界点。如何使用例如ELKI来验证你的算法输出?