# scoding=utf-8import pylab as plfrom collections import defaultdict,Counterpoints = [[int(eachpoint.split("#")[0]), int(eachpoint.split("#")[1])] for eachpoint in open("points","r")]# 計算每個數據點相鄰的數據點，鄰域定義為以該點為中心以邊長為2*EPs的網格Eps = 10surroundPoints = defaultdict(list)for idx1,point1 in enumerate(points):  for idx2,point2 in enumerate(points):    if (idx1 < idx2):      if(abs(point1[0]-point2[0])<=Eps and abs(point1[1]-point2[1])<=Eps):        surroundPoints[idx1].append(idx2)        surroundPoints[idx2].append(idx1)# 定義鄰域內相鄰的數據點的個數大于4的為核心點MinPts = 5corePointIdx = [pointIdx for pointIdx,surPointIdxs in surroundPoints.iteritems() if len(surPointIdxs)>=MinPts]# 鄰域內包含某個核心點的非核心點，定義為邊界點borderPointIdx = []for pointIdx,surPointIdxs in surroundPoints.iteritems():  if (pointIdx not in corePointIdx):    for onesurPointIdx in surPointIdxs:      if onesurPointIdx in corePointIdx:        borderPointIdx.append(pointIdx)        break# 噪音點既不是邊界點也不是核心點noisePointIdx = [pointIdx for pointIdx in range(len(points)) if pointIdx not in corePointIdx and pointIdx not in borderPointIdx]corePoint = [points[pointIdx] for pointIdx in corePointIdx] borderPoint = [points[pointIdx] for pointIdx in borderPointIdx]noisePoint = [points[pointIdx] for pointIdx in noisePointIdx]# pl.plot([eachpoint[0] for eachpoint in corePoint], [eachpoint[1] for eachpoint in corePoint], 'or')# pl.plot([eachpoint[0] for eachpoint in borderPoint], [eachpoint[1] for eachpoint in borderPoint], 'oy')# pl.plot([eachpoint[0] for eachpoint in noisePoint], [eachpoint[1] for eachpoint in noisePoint], 'ok')groups = [idx for idx in range(len(points))]# 各個核心點與其鄰域內的所有核心點放在同一個簇中for pointidx,surroundIdxs in surroundPoints.iteritems():  for oneSurroundIdx in surroundIdxs:    if (pointidx in corePointIdx and oneSurroundIdx in corePointIdx and pointidx < oneSurroundIdx):      for idx in range(len(groups)):        if groups[idx] == groups[oneSurroundIdx]:          groups[idx] = groups[pointidx]# 邊界點跟其鄰域內的某個核心點放在同一個簇中for pointidx,surroundIdxs in surroundPoints.iteritems():  for oneSurroundIdx in surroundIdxs:    if (pointidx in borderPointIdx and oneSurroundIdx in corePointIdx):      groups[pointidx] = groups[oneSurroundIdx]      break# 取簇規模最大的5個簇wantGroupNum = 3finalGroup = Counter(groups).most_common(3)finalGroup = [onecount[0] for onecount in finalGroup]group1 = [points[idx] for idx in xrange(len(points)) if groups[idx]==finalGroup[0]]group2 = [points[idx] for idx in xrange(len(points)) if groups[idx]==finalGroup[1]]group3 = [points[idx] for idx in xrange(len(points)) if groups[idx]==finalGroup[2]]pl.plot([eachpoint[0] for eachpoint in group1], [eachpoint[1] for eachpoint in group1], 'or')pl.plot([eachpoint[0] for eachpoint in group2], [eachpoint[1] for eachpoint in group2], 'oy')pl.plot([eachpoint[0] for eachpoint in group3], [eachpoint[1] for eachpoint in group3], 'og')# 打印噪音點，黑色pl.plot([eachpoint[0] for eachpoint in noisePoint], [eachpoint[1] for eachpoint in noisePoint], 'ok')  pl.show()