聚类算法
聚类算法介绍
（1）系统聚类法
系统聚类法的基本思想是：距离近的样品先聚成类，距离远的后聚成类。
根据类间定义的不同，系统聚类法又可以分成最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法、离差平方和法8种。
需要注意的是：
（1）该方法不需要事先指定聚类个数，而是根据最终的分类过程确定。
（2）为了直观的反映，可以把分类系统画成一张谱系图，所以系统聚类也称谱系分析。
（2）K-means聚类法
K-means聚类法是非常经典的聚类算法，有关资料很丰富，故本文不再赘述。
需要注意的是：
（1）该方法通过计算欧氏距离，比较样品间的相似度进行聚类。不过我也有看过，通过计算相关系数来聚类的。
（2）该法需要指定聚类个数，而K的确定是个难点，有很多针对K优化的方法。
（3）single-pass聚类法
含义适用
Single-pass clustering，中文名一般译作”单遍聚类”，它是一种简洁且高效的文本聚类算法。相比于常用的K-means聚类法，它的计算速度非常快，且不需要指定聚类个数，而是通过设定相似度阈值来限定。
Single-pass聚类算法同时是一种增量聚类算法（Incremental Clustering Algorithm），每个文档只需要流过算法一次，常用与文本主题的聚类中。它可以很好的应用于话题监测与追踪、在线事件监测等社交媒体大数据领域，特别适合流式数据（Streaming Data），比如微博的帖子信息等。
流数据:一组顺序、大量、快速、连续到达的数据序列。一般情况下，流数据可被视为一个随时间延续而无限增长的动态数据集合。
来源：百度百科
处理步骤
Single-pass算法顺序处理文本，以第一篇文档为种子，建立一个新主题。之后再进行新进入文档与已有主题的相似度，将该文档加入到与它相似度最大的、且大于一定阈值的主题中。如果与所有已有话题相似度都小于阈值，则以该文档为聚类种子，建立新的主题类别。其算法流程如下：
（1）以第一篇文档为种子，建立一个主题；
（2）将文档X向量化；
（3）将文档X与已有的所有话题均做相似度计算，可采用 欧氏距离或 余弦距离等距离度量方法
（4）找出与文档X具有最大相似度的已有主题；
（5）若相似度值大于阈值θ ，则把文档X加入到有最大相似度的主题中，跳转至 （7）；
（6）若相似度值小于阈值θ ， 则文档X不属于任一已有主题， 需创建新的主题类别，同时将当前文本归属到新创建的主题类别中；
（7）聚类结束，等待下一篇文档进入
注：上述中讲相似度最大的划为一类，在实际代码中，所谓相似度最大大于某个阈值，也可以理解为距离最近（小）小于某个阈值。
样本描述
将样本信息保存至TXT文件中，截图后如上所示。
有多少行我没数，用python中describe()一下就知道了，列数是十列。
日期后面两类是最高温和最低温，最后两列表示该地的经度和纬度。
; 代码实现
定义类和函数
首先定义了一个簇单元 ClusterUnit ，定义了一个单类 OnePassCluster ，定义了向量a与b间的欧式距离euclidian_distance。
import numpy as np
from math import sqrt
import time
import matplotlib.pylab as pl
class ClusterUnit:
def __init__(self):
self.node_list = []
self.node_num = 0
self.centroid = None
def add_node(self, node, node_vec):
"""
为本簇添加指定节点，并更新簇心
node_vec:该节点的特征向量
node:节点
return:null
"""
self.node_list.append(node)
try:
self.centroid = (self.node_num * self.centroid + node_vec) / (self.node_num + 1)
except TypeError:
self.centroid = np.array(node_vec) * 1
self.node_num += 1
def remove_node(self, node):
try:
self.node_list.remove(node)
self.node_num -= 1
except ValueError:
raise ValueError("%s not in this cluster" % node)
def move_node(self, node, another_cluster):
self.remove_node(node=node)
another_cluster.add_node(node=node)
def euclidian_distance(vec_a, vec_b):
diff = vec_a - vec_b
return sqrt(np.dot(diff, diff))
class OnePassCluster:
def __init__(self, t, vector_list):
self.threshold = t
self.vectors = np.array(vector_list)
self.cluster_list = []
t1 = time.time()
self.clustering()
t2 = time.time()
self.cluster_num = len(self.cluster_list)
self.spend_time = t2 - t1
def clustering(self):
self.cluster_list.append(ClusterUnit())
self.cluster_list[0].add_node(0, self.vectors[0])
for index in range(len(self.vectors))[1:]:
min_distance = euclidian_distance(vec_a=self.vectors[index],
vec_b=self.cluster_list[0].centroid)
min_cluster_index = 0
for cluster_index, cluster in enumerate(self.cluster_list[1:]):
distance = euclidian_distance(vec_a=self.vectors[index],
vec_b=cluster.centroid)
if distance < min_distance:
min_distance = distance
min_cluster_index = cluster_index + 1
if min_distance < self.threshold:
self.cluster_list[min_cluster_index].add_node(index, self.vectors[index])
else:
new_cluster = ClusterUnit()
new_cluster.add_node(index, self.vectors[index])
self.cluster_list.append(new_cluster)
del new_cluster
def print_result(self, label_dict=None):
print("*********** single-pass的聚类结果展示 ***********")
for index, cluster in enumerate(self.cluster_list):
print("cluster:%s" % index)
print(cluster.node_list)
if label_dict is not None:
print(" ".join([label_dict[n] for n in cluster.node_list]))
print("node num: %s" % cluster.node_num)
print( "-------------")
print( "所有节点的个数为： %s" % len(self.vectors))
print("簇类的个数为：%s" % self.cluster_num)
print("花费的时间为： %.9fs" % (self.spend_time / 1000))
运行之后，一共聚类十类，聚类个数从0-9。
如下图为第八个类别所包含的城市以及他们对应的索引：
整体运行结果如下：
调用与画图
之后通过实例化类和调用函数，来实现聚类
temperature_all_city = np.loadtxt('data1.txt', delimiter=",", usecols=(3, 4),encoding='utf-8')
xy = np.loadtxt('data1.txt', delimiter=",", usecols=(8, 9),encoding='utf-8')
f = open('data1.txt', 'r',encoding='utf-8')
lines = f.readlines()
zone_dict = [i.split(',')[1] for i in lines]
f.close()
clustering = OnePassCluster(vector_list=temperature_all_city, t=9)
clustering.print_result(label_dict=zone_dict)
print(temperature_all_city)
fig, ax = pl.subplots()
fig = zone_dict
c_map = pl.get_cmap('jet', clustering.cluster_num)
c = 0
for cluster in clustering.cluster_list:
for node in cluster.node_list:
ax.scatter(xy[node][0], xy[node][1])
c += 1
pl.savefig('./map.jpg')
pl.show()
根据样本中经纬度的信息，并结合聚类算法的结果，可画图如下：
总结
本文主要给出single-pass聚类算法的实例，该例很好复现。希望对各位兄弟姐妹们有所帮助。
参考：https://blog.csdn.net/maqian5/article/details/107333316
本文数据与代码均引用他处，如未标注来源，请联系我更改加上。
需要本文数据和代码，可在本文评论区留言。希望对各位兄弟姐妹们有所帮助。
Original: https://blog.csdn.net/golden_knife/article/details/124434270
Author: 不想秃头的夜猫子
Title: single-pass聚类算法实现天气聚类
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/662092/
转载文章受原作者版权保护。转载请注明原作者出处！