Python聚类算法之DBSACN实例分析

这篇文章主要介绍了Python聚类算法之DBSACN,结合实例形式详细分析了DBSACN算法的原理与具体实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下

本文实例讲述了Python聚类算法之DBSACN。分享给大家供大家参考，具体如下：

DBSCAN：

是一种简单的，基于密度的聚类算法。本次实现中，DBSCAN使用了基于中心的方法。在基于中心的方法中，每个数据点的密度通过对以该点为中心以边长为2*EPs的网格(邻域)内的其他数据点的个数来度量。根据数据点的密度分为三类点:

核心点：该点在邻域内的密度超过给定的阀值MinPs。

边界点：该点不是核心点，但是其邻域内包含至少一个核心点。

噪音点：不是核心点，也不是边界点。

有了以上对数据点的划分，聚合可以这样进行：各个核心点与其邻域内的所有核心点放在同一个簇中，把边界点跟其邻域内的某个核心点放在同一个簇中。

1. # scoding=utf-8 
2. import pylab as pl 
3. from collections import defaultdict,Counter 
4. points = [[int(eachpoint.split("#")[0]), int(eachpoint.split("#")[1])] for eachpoint in open("points","r")] 
5. # 计算每个数据点相邻的数据点，邻域定义为以该点为中心以边长为2*EPs的网格 
6. Eps = 10 
7. surroundPoints = defaultdict(list) 
8. for idx1,point1 in enumerate(points): 
9. for idx2,point2 in enumerate(points): 
10. if (idx1 < idx2): 
11. if(abs(point1[0]-point2[0])<=Eps and abs(point1[1]-point2[1])<=Eps): 
12. surroundPoints[idx1].append(idx2) 
13. surroundPoints[idx2].append(idx1) 
14. # 定义邻域内相邻的数据点的个数大于4的为核心点 
15. MinPts = 5 
16. corePointIdx = [pointIdx for pointIdx,surPointIdxs in surroundPoints.iteritems() if len(surPointIdxs)>=MinPts] 
17. # 邻域内包含某个核心点的非核心点，定义为边界点 
18. borderPointIdx = [] 
19. for pointIdx,surPointIdxs in surroundPoints.iteritems(): 
20. if (pointIdx not in corePointIdx): 
21. for onesurPointIdx in surPointIdxs: 
22. if onesurPointIdx in corePointIdx: 
23. borderPointIdx.append(pointIdx) 
24. break 
25. # 噪音点既不是边界点也不是核心点 
26. noisePointIdx = [pointIdx for pointIdx in range(len(points)) if pointIdx not in corePointIdx and pointIdx not in borderPointIdx] 
27. corePoint = [points[pointIdx] for pointIdx in corePointIdx]  
28. borderPoint = [points[pointIdx] for pointIdx in borderPointIdx] 
29. noisePoint = [points[pointIdx] for pointIdx in noisePointIdx] 
30. # pl.plot([eachpoint[0] for eachpoint in corePoint], [eachpoint[1] for eachpoint in corePoint], 'or') 
31. # pl.plot([eachpoint[0] for eachpoint in borderPoint], [eachpoint[1] for eachpoint in borderPoint], 'oy') 
32. # pl.plot([eachpoint[0] for eachpoint in noisePoint], [eachpoint[1] for eachpoint in noisePoint], 'ok') 
33. groups = [idx for idx in range(len(points))] 
34. # 各个核心点与其邻域内的所有核心点放在同一个簇中 
35. for pointidx,surroundIdxs in surroundPoints.iteritems(): 
36. for oneSurroundIdx in surroundIdxs: 
37. if (pointidx in corePointIdx and oneSurroundIdx in corePointIdx and pointidx < oneSurroundIdx): 
38. for idx in range(len(groups)): 
39. if groups[idx] == groups[oneSurroundIdx]: 
40. groups[idx] = groups[pointidx] 
41. # 边界点跟其邻域内的某个核心点放在同一个簇中 
42. for pointidx,surroundIdxs in surroundPoints.iteritems(): 
43. for oneSurroundIdx in surroundIdxs: 
44. if (pointidx in borderPointIdx and oneSurroundIdx in corePointIdx): 
45. groups[pointidx] = groups[oneSurroundIdx] 
46. break 
47. # 取簇规模最大的5个簇 
48. wantGroupNum = 3 
49. finalGroup = Counter(groups).most_common(3) 
50. finalGroup = [onecount[0] for onecount in finalGroup] 
51. group1 = [points[idx] for idx in xrange(len(points)) if groups[idx]==finalGroup[0]] 
52. group2 = [points[idx] for idx in xrange(len(points)) if groups[idx]==finalGroup[1]] 
53. group3 = [points[idx] for idx in xrange(len(points)) if groups[idx]==finalGroup[2]] 
54. pl.plot([eachpoint[0] for eachpoint in group1], [eachpoint[1] for eachpoint in group1], 'or') 
55. pl.plot([eachpoint[0] for eachpoint in group2], [eachpoint[1] for eachpoint in group2], 'oy') 
56. pl.plot([eachpoint[0] for eachpoint in group3], [eachpoint[1] for eachpoint in group3], 'og') 
57. # 打印噪音点，黑色 
58. pl.plot([eachpoint[0] for eachpoint in noisePoint], [eachpoint[1] for eachpoint in noisePoint], 'ok')  
59. pl.show() 

运行效果截图如下：

希望本文所述对大家Python程序设计有所帮助。