聚类|2022年MathorCup数学建模竞赛（基站聚类思路）算法|python|机器学习

辐射归并算法和聚类实践

算法运作基本原理
算法的 Python 实现
聚类结果

算法运作基本原理 【聚类|2022年MathorCup数学建模竞赛（基站聚类思路）】题中给出的弱覆盖点聚类原理是一种“传染机制”：距离不大于 20 的两点属于同一类别，因此通过点和点之间的“传染标记”得到一个完整的类别，算法原理如同病毒扩散。因此，我们将“类别传染者”命名为“辐射点”，未归类点命名为“待归类点”。
因此，如果想得到一类，应当从一个辐射点开始在所有待归类点中寻找与其距离不超过 20 的点后将它们标记为相同类别，并将每次迭代后类中的新增点作为下一次迭代的辐射点，将每次迭代后剩下的为归类点作为下一次迭代的待归类点……在某一次迭代后如果没有出现新增点（即下一次迭代无辐射点），则本轮迭代结束。依照这种迭代规则，每一轮迭代停止后可以得到一类；下一轮迭代将重新从所有剩下的“待归类”点中进行。
算法的 Python 实现首先，撰写用于分出聚类单类别的函数SingleClass(*args, **kwargs)

''' df 代表用 DataFrame 格式存放的点集 classtype 为人工输入的类编号 dis_square 为距离阈值的平方（题中为 20 ** 2 即 400） ''' def SingleClass(df, classtype, dis_square): # 初始迭代，“class”字段存放点被归入的类别编号，因此没有被归类的点该字段存放空值 newdf = df.loc[df['class'].isnull()].copy() startindex = newdf.index[0] # “dis”字段存放两点间欧氏距离的平方，而并非欧氏距离 df.loc[:, 'dis'] = (df.loc[startindex, 'x'] - df['x']) ** 2 + (df.loc[startindex, 'y'] - df['y']) ** 2 df.loc[df['dis'] <= dis_square, 'class'] = classtype index_update = df.loc[df['dis'] <= dis_square].index # 完成了从空到有类的步骤，然后进入循环 while True: newdf = df.loc[df['class'].isnull()].copy() last_increased_index = [] for i in index_update: newdf.loc[:, 'dis'] = (newdf.loc[:, 'x'] - df.loc[i, 'x']) ** 2 + (newdf.loc[:, 'y'] - df.loc[i, 'y']) ** 2 last_increased_index.extend(newdf[newdf['dis'] <= dis_square].index) # 去除重复的点索引 last_increased_index = list(set(last_increased_index))if last_increased_index == []: # 如果没有找到满足要求的点则跳出循环 break else: # 更改类值添加分类 df.loc[last_increased_index, 'class'] = classtype index_update = last_increased_index return df

第二步，撰写利用SingleClass(*args, **kwargs)函数进行迭代的总聚类函数Cluster(*args, **kwargs）

''' df 为输入的点集 dis_square 为距离阈值的平方（本题中即为400） ''' def Cluster(df, dis_square): count = 1 while True: df_null = df[df['class'].isnull()] if df_null.shape[0] == 0: return df else: df = SingleClass(df, f'Classed-{count}', dis_square) print(f'类别{count}, 完成！') count += 1

使用两个函数进行聚类的前提是预处理数据集，使其具有“class”字段和“dis_square”字段。因此，在调用函数Cluster(*args, **kwargs)之前，要对原数据集进行预处理。

if __name__ == '__main__': # 使用文件路径读取数据集 df = pd.read_csv('*****.csv') df[['dis', 'class']] = np.nan df = Cluster(df, dis_square = 400) df.drop(['dis'], axis = 1, inplace = True) # df.to_csv('聚类结果.csv', index=False)

聚类结果最后，通过作图，可以直观看出聚类结果。下方两张图分别为聚类前和聚类后的点簇图。经过聚类，一共得到898类，所有弱覆盖栅格点均被归类