安徽省交通运输厅网站,网络品牌营销策略,永登县建设局网站,沈阳软件定制开发公司4.1 k-means算法简介 聚类分析#xff0c;作为机器学习领域中的一种无监督学习方法#xff0c;在数据探索与知识发现过程中扮演着举足轻重的角色。它能够在没有先验知识或标签信息的情况下#xff0c;通过挖掘数据中的内在结构和规律#xff0c;将数据对象自动划分为多个类… 4.1 k-means算法简介 聚类分析作为机器学习领域中的一种无监督学习方法在数据探索与知识发现过程中扮演着举足轻重的角色。它能够在没有先验知识或标签信息的情况下通过挖掘数据中的内在结构和规律将数据对象自动划分为多个类别或簇。每个簇内的对象具有高度的相似性而不同簇间的对象则表现出明显的差异性。 在众多聚类算法中K-means算法因其简单高效而备受青睐。K-means算法的基本思想是通过迭代的方式将数据划分为K个不同的簇并使得每个数据点与其所属簇的质心或称为中心点、均值点之间的距离之和最小。 K-means算法的优点在于其直观易懂、计算速度快且易于实现。然而它也存在一些局限性如对初始簇质心的选择敏感、可能陷入局部最优解以及需要预先设定聚类数K等。因此在实际应用中我们需要根据具体的问题和数据特点来选择合适的聚类算法并可能需要对算法进行优化或改进以适应特定的需求。 4.2 算法的基本原理 1类和分类 类指的是具有相似性的集合。而分类是根据给定的已知类别的样本训练出来一个模型使该模型能够对未知类别的样本进行分类。故分类属于有监督学习。有监督学习是指提前由人工对训练数据做好了分类训练样本同时包含有特征和类别信息。有监督学习类似于先学习带有标准答案的复习题学习到知识规律以后再去参加考试。 2聚类 对于一些给定的样本不知道样本之间的关系不知道他们是否属于同一类也不知道到底可以分为多少类。此时通过聚类把未知类别的数据分为多个类别。聚类目的在于把相似的东西聚在一起因此聚类属于无监督学习。 3K-均值聚类思想 K-均值K-Means是发现给定数据集的K个簇的算法。簇个数K是用户给定的每一个簇通过其质心即簇中所有点的中心来描述。其核心思想是将数据集中的n个对象划分为K个聚类使得每个对象到其所属聚类的中心或称为均值点、质心的距离之和最小。这里所说的距离通常指的是欧氏距离但也可以是其他类型的距离度量。通过迭代的方式不断优化聚类结果使得每个聚类内的对象尽可能紧密而不同聚类间的对象则尽可能分开。 4算法步骤 K-means算法作为一种强大的无监督学习工具具有简单易懂、计算效率高和易于实现等优点在多个领域有着广泛的应用下面我们将详细探讨K-means算法的实现步骤。K-means算法的执行过程通常包括以下四个步骤。 a.初始化选择K个初始聚类中心。在算法开始时需要随机选择K个数据点作为初始的聚类中心。这些初始聚类中心的选择对最终的聚类结果有一定的影响因此在实际应用中通常会采用一些启发式的方法来选择较好的初始聚类中心如K-means算法。 b.分配将每个数据点分配给最近的聚类中心。对于数据集中的每个数据点计算其与每个聚类中心的距离并将其分配给距离最近的聚类中心。这一步通常使用欧氏距离作为距离度量计算公式如下1。其中x是数据点ci是第i个聚类中心d是数据的维度xj和cij分别是x和ci在第j维上的值。 c.更新重新计算每个聚类的中心。对于每个聚类重新计算其聚类中心新的聚类中心是该聚类内所有数据点的均值计算公式如下2。其中Si是第i个聚类的数据点集合|Si|是该集合中数据点的数量。 d.迭代重复分配和更新步骤直到满足终止条件。重复执行分配和更新步骤直到满足某种终止条件。常见的终止条件包括聚类中心不再发生显著变化即新的聚类中心与旧的聚类中心之间的距离小于某个预设的阈值。达到最大迭代次数为了避免算法陷入无限循环通常会设置一个最大迭代次数作为终止条件。在迭代过程中算法会不断优化聚类结果使得每个聚类内的对象更加紧密而不同聚类间的对象更加分散。最终当满足终止条件时算法停止迭代并输出最终的聚类结果。 4.3 算法实例 K-means算法作为一种强大的无监督学习工具在多个领域有着广泛的应用。本实验以对俄勒冈州的波特兰地区地图上的点进行聚类为例基于k-means算法实现将这些地方进行聚类的最佳策略这样就可以安排交通工具抵达这些簇的质心然后步行到每个内地址。实例操作可分为以下五个过程。 收集数据 通过调用geoGrab函数来实现收集数据geoGrab函数的作用是收集数据通过调用雅虎地理编码 APIYahoo Geocoding API将输入的街道地址和城市名称转换为对应的地理坐标经纬度等位置信息返回 API 响应的 JSON 格式数据包含地址对应的地理编码信息如坐标、地址匹配度等。 相关代码如下 def geoGrab(stAddress, city): apiStem http://where.yahooapis.com/geocode? #create a dict and constants for the goecoder params {} params[flags] J#JSON return type params[appid] aaa0VN6k params[location] %s %s % (stAddress, city) url_params urllib.parse.urlencode(params) yahooApi apiStem url_params #print url_params print (yahooApi) curllib.parse.urlopen(yahooApi) return json.loads(c.read()) 准备数据 准备数据中只保留经纬度信息。我们可以通过调用massPlaceFind函数。该函数其作用是批量处理地址数据通过调用geoGrab函数获取地理坐标经纬度并将结果写入文件。该函数适用于批量处理地址数据生成带地理坐标的数据集常用于地理信息系统GIS、数据分析或地图可视化等场景。 相关代码如下 def massPlaceFind(fileName): fw open(places.txt, w) for line in open(fileName).readlines(): line line.strip() lineArr line.split(\t) retDict geoGrab(lineArr[1], lineArr[2]) if retDict[ResultSet][Error] 0: lat float(retDict[ResultSet][Results][0][latitude]) lng float(retDict[ResultSet][Results][0][longitude]) print(%s\t%f\t%f % (lineArr[0], lat, lng)) fw.write(%s\t%f\t%f\n % (line, lat, lng)) else: print (error fetching) sleep(1) fw.close() 分析数据 使用Matplotlib来构建一个二维数据图其中包含簇与地图。我们通过调用clusterClubs函数来实现。clusterClubs函数其核心功能是对地点的经纬度数据进行聚类分析并在地图背景上可视化聚类结果。该函数适用于地理数据的聚类分析与可视化常用于城市规划、商业选址、轨迹分析等场景帮助快速识别数据中的空间分布模式。 图1 调用函数 图2 二维数据图 相关代码如下 def clusterClubs(numClust5): datList [] for line in open(places.txt).readlines(): lineArr line.split(\t) datList.append([float(lineArr[4]), float(lineArr[3])]) datMat matrix(datList) myCentroids, clustAssing biKmeans(datMat, numClust, distMeasdistSLC) fig plt.figure() rect[0.1,0.1,0.8,0.8] scatterMarkers[s, o, ^, 8, p, \d, v, h, , ] axprops dict(xticks[], yticks[]) ax0fig.add_axes(rect, labelax0, **axprops) imgP plt.imread(Portland.png) ax0.imshow(imgP) ax1fig.add_axes(rect, labelax1, frameonFalse) for i in range(numClust): ptsInCurrCluster datMat[nonzero(clustAssing[:,0].Ai)[0],:] markerStyle scatterMarkers[i % len(scatterMarkers)] ax1.scatter(ptsInCurrCluster[:,0].flatten().A[0], ptsInCurrCluster[:,1].flatten().A[0], markermarkerStyle, s90) ax1.scatter(myCentroids[:,0].flatten().A[0], myCentroids[:,1].flatten().A[0], marker, s300) plt.show() 测试算法 通过调用biKmeans()函数来测试算法。该函数实现了二分K均值算法Bisecting K-Means用于对数据集进行聚类分析。其核心作用是通过 “逐步分裂簇” 的策略将数据集划分为指定数量的簇k个。 图3 测试算法 相关代码如下 def biKmeans(dataSet, k, distMeasdistEclud): m shape(dataSet)[0] clusterAssment matrix(zeros((m,2))) centroid0 mean(dataSet, axis0).tolist()[0] centList [centroid0] #create a list with one centroid for j in range(m):#calc initial Error clusterAssment[j,1] distMeas(matrix(centroid0), dataSet[j,:])**2 while (len(centList) k): lowestSSE inf for i in range(len(centList)): ptsInCurrCluster dataSet[nonzero(clusterAssment[:,0].Ai)[0],:]#get the data points currently in cluster i centroidMat, splitClustAss kMeans(ptsInCurrCluster, 2, distMeas) sseSplit sum(splitClustAss[:,1])#compare the SSE to the currrent minimum sseNotSplit sum(clusterAssment[nonzero(clusterAssment[:,0].A!i)[0],1]) print(sseSplit, and notSplit: ,sseSplit,sseNotSplit) if (sseSplit sseNotSplit) lowestSSE: bestCentToSplit i bestNewCents centroidMat bestClustAss splitClustAss.copy() lowestSSE sseSplit sseNotSplit bestClustAss[nonzero(bestClustAss[:,0].A 1)[0],0] len(centList) #change 1 to 3,4, or whatever bestClustAss[nonzero(bestClustAss[:,0].A 0)[0],0] bestCentToSplit print (the bestCentToSplit is: ,bestCentToSplit) print (the len of bestClustAss is: , len(bestClustAss)) centList[bestCentToSplit] bestNewCents[0,:].tolist()[0]#replace a centroid with two best centroids centList.append(bestNewCents[1,:].tolist()[0]) clusterAssment[nonzero(clusterAssment[:,0].A bestCentToSplit)[0],:] bestClustAss#reassign new clusters, and SSE return matrix(centList), clusterAssment 使用算法 我们通过使用clusterClubs函数来输出包含簇及簇中心的地图。clusterClubs函数其核心功能是对地点的经纬度数据进行聚类分析并在地图背景上可视化聚类结果。操作过程与3分析数据相同。 图4 簇及簇中心图 相关代码如下 def clusterClubs(numClust5): datList [] for line in open(places.txt).readlines(): lineArr line.split(\t) datList.append([float(lineArr[4]), float(lineArr[3])]) datMat matrix(datList) myCentroids, clustAssing biKmeans(datMat, numClust, distMeasdistSLC) fig plt.figure() rect[0.1,0.1,0.8,0.8] scatterMarkers[s, o, ^, 8, p, \ d, v, h, , ] axprops dict(xticks[], yticks[]) ax0fig.add_axes(rect, labelax0, **axprops) imgP plt.imread(Portland.png) ax0.imshow(imgP) ax1fig.add_axes(rect, labelax1, frameonFalse) for i in range(numClust): ptsInCurrCluster datMat[nonzero(clustAssing[:,0].Ai)[0],:] markerStyle scatterMarkers[i % len(scatterMarkers)] ax1.scatter(ptsInCurrCluster[:,0].flatten().A[0], ptsInCurrCluster[:,1].flatten().A[0], markermarkerStyle, s90) ax1.scatter(myCentroids[:,0].flatten().A[0], myCentroids[:,1].flatten().A[0], marker, s300) plt.show()
