這篇文章主要介紹了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程序設計有所幫助。