1. 从两个看似无关的算法说起如果你参加过数学建模竞赛或者处理过一些网络优化、数据分类的实际问题大概率会碰到两个名字听起来八竿子打不着的算法Floyd和K-means。前者Floyd算法通常和“最短路径”、“图论”、“网络优化”这些词绑定在一起给人的感觉是严谨、确定、一步一个脚印。后者K-means算法则活跃在“聚类分析”、“数据挖掘”、“机器学习”的领域充满了迭代、试探和不确定性。乍一看一个像是规划城市间最省时路线的交通工程师另一个则像是在一堆杂乱无章的客户数据中寻找相似群体的市场分析师。它们似乎分属两个完全不同的世界。但有意思的是在我参与和评审过的众多数模项目以及一些工业界的解决方案中这两个算法常常会以意想不到的方式组合出现解决一些单一算法束手无策的复杂问题。比如一个经典的场景是你需要对一批城市进行区域划分聚类但划分的依据不是简单的经纬度距离而是城市之间的实际交通时间或物流成本最短路径。这时候单独用K-means按欧氏距离分结果可能完全不符合实际单独用Floyd算出了所有城市间的最短耗时却又不知道怎么科学地分组。它们的结合恰恰能碰撞出火花。今天我们就抛开教科书上孤立的介绍从一个数模实战者和算法应用者的角度深入聊聊Floyd和K-means。我们不止要弄清楚它们各自“是什么”和“怎么用”更要探究它们“为什么”要这么设计以及最关键的一步——如何将它们“串联”或“嵌套”起来去解决那些更贴近现实的、维度丰富的综合性问题。无论你是正在备战数模竞赛的学生还是初涉数据分析的工程师理解这种“算法组合拳”的思路远比死记硬背单个算法的步骤要有价值得多。2. Floyd算法全源最短路径的“暴力美学”首先我们聚焦Floyd算法。它的全称是Floyd-Warshall算法核心任务是解决“全源最短路径”问题。简单说就是给你一个图比如城市交通网图中每个点城市到其他所有点的最短距离是多少它不满足于只求一个起点到其他点的距离那是Dijkstra算法的活儿而是要一口气算出所有点对之间的最短距离结果通常用一个二维矩阵距离矩阵来呈现。2.1 核心思想与动态规划内核Floyd算法最迷人的地方在于其思想的简洁与深刻。它基于一个非常直观的动态规划思想。假设我们有一个图顶点编号为1到n。我们定义d[k][i][j]为从顶点i到顶点j只允许以顶点1, 2, ..., k 作为中间顶点的所有可能路径中的最短路径长度。注意这个定义的精妙之处。当 k0 时意味着不允许任何中间顶点那么d[0][i][j]就是顶点i到j的直接边权如果两点间有直接边或者无穷大如果两点间没有直接边。这就是我们的初始状态。现在考虑如何从d[k-1][i][j]推导出d[k][i][j]。当我们允许使用第k个顶点作为中间点时从i到j的最短路径无非两种可能这条最短路径根本不经过顶点k。那么它的长度就是d[k-1][i][j]。这条最短路径经过顶点k。那么我们可以把路径拆成两段i - k 和 k - j。而这两段路径在只允许使用前k-1个顶点作为中间点时最短长度分别是d[k-1][i][k]和d[k-1][k][j]。因此经过k的路径长度就是这两者之和。我们要找的是所有可能路径中的最短者所以递推公式就出来了d[k][i][j] min( d[k-1][i][j], d[k-1][i][k] d[k-1][k][j] )这个递推关系是Floyd算法的灵魂。在实际编程中为了节省空间我们通常使用同一个二维数组d[i][j]进行滚动更新因为d[k][i][j]只依赖于d[k-1][...]。最终当 kn 时d[i][j]就是允许使用所有顶点作为中间点时从i到j的全局最短路径长度。注意这里有一个非常关键的细节也是初学者容易写错的地方。三层循环for k from 1 to n: for i from 1 to n: for j from 1 to n:的顺序是固定的k必须放在最外层。因为我们的递推式是基于“允许使用前k个点”这个状态定义的必须一层一层地解放这些中间点。如果错把i或j放在外层更新逻辑就完全错误了。2.2 算法实现与“距离矩阵”的构建理论有点绕我们来看一个具体的实现和例子。假设我们有4个城市A、B、C、D它们之间的直接道路距离如下表所示INF代表无穷大即没有直接道路ABCDA0264BINF03INFC7INF01D5INF120这个矩阵就是我们的初始距离矩阵d。现在我们开始Floyd算法的三重循环更新。第一轮 (k1考虑A作为中间点) 主要检查所有i-j的路径是否可以通过“i-A A-j”变得更短。 例如d[B][C]原本是3。检查d[B][A] d[A][C] INF 6不小于3所以不变。 再如d[B][D]原本是INF。检查d[B][A] d[A][D] INF 4不小于INF不变。 这一轮因为A点本身更新可能不多。第二轮 (k2考虑B作为中间点) 检查所有路径是否可以通过B中转。 例如d[A][C]原本是6。检查d[A][B] d[B][C] 2 3 5小于6于是更新d[A][C] 5。这意味着发现了A-B-C这条更短的路径。 再如d[A][D]原本是4。检查d[A][B] d[B][D] 2 INF不小于4不变。第三轮 (k3考虑C作为中间点) 此时矩阵已经部分更新。检查所有路径是否可以通过C中转。 例如d[A][D]此时是4。检查d[A][C] d[C][D] 5 1 6大于4不变。 但d[B][A]原本是INF。检查d[B][C] d[C][A] 3 7 10小于INF于是更新d[B][A] 10。发现了B-C-A的路径。d[D][A]原本是5。检查d[D][C] d[C][A] 12 7 19大于5不变。d[D][B]原本是INF。检查d[D][C] d[C][B] 12 INF不小于INF不变。第四轮 (k4考虑D作为中间点) 最后一遍扫描查漏补缺。 例如d[C][B]原本是INF。检查d[C][D] d[D][B] 1 INF不小于INF不变。d[A][B]原本是2。检查d[A][D] d[D][B] 4 INF不小于2不变。经过四轮更新我们最终得到全源最短路径矩阵。你可以手动验证比如d[B][A]最终是10路径B-C-Ad[A][C]是5路径A-B-C。这个最终的矩阵才是我们心目中真正能反映“任意两城市间实际可达最短距离”的数据。它已经考虑了所有可能的迂回、中转方案。在代码实现上Python版本非常简洁def floyd_warshall(graph): n len(graph) dist [[graph[i][j] for j in range(n)] for i in range(n)] # 初始化距离矩阵副本 for k in range(n): for i in range(n): for j in range(n): if dist[i][k] ! float(inf) and dist[k][j] ! float(inf): if dist[i][j] dist[i][k] dist[k][j]: dist[i][j] dist[i][k] dist[k][j] return dist这段代码就是上述动态规划思想的直接翻译。graph是输入的邻接矩阵。2.3 实战中的关键细节与避坑指南在实际的数模或工程应用中直接套用教科书代码往往不够有几个细节必须注意图的类型与初始化Floyd算法要求图用邻接矩阵表示。对于无向图矩阵是对称的对于有向图则不一定。初始化时对角线自己到自己的距离必须初始化为0。不直接相连的点距离初始化为一个足够大的数如float(inf)但要注意这个“无穷大”不能参与加法运算否则会溢出。所以在代码中我们增加了if dist[i][k] ! inf and dist[k][j] ! inf的判断。负权边与负权环Floyd算法可以处理带有负权边的图这是它相对于Dijkstra算法的一个优势。但是它不能处理包含“负权环”的图。因为如果在i到j的路径上存在一个总权值为负的环那么可以无限次地绕这个环使得最短路径长度趋于负无穷算法将失去意义。如果你的图可能存在负权在算法结束后可以检查对角线元素dist[i][i]。如果任何一个dist[i][i] 0则说明图中存在从i出发又回到i的负权环。路径重建算法只给出了最短距离但很多时候我们需要知道具体是哪条路径。这就需要额外维护一个“后继节点矩阵”或“前驱节点矩阵”。在更新dist[i][j]的同时记录下导致这次更新的中间点k或者记录j的前驱节点。赛后通过回溯法即可重建完整路径。这个步骤在数模论文中是体现工作完整性的重要加分项。性能考量Floyd算法的时间复杂度是O(n³)空间复杂度是O(n²)。这意味着当顶点数n很大时比如上万个点它的计算开销会变得非常巨大。在数模竞赛中通常n不会特别大几百以内所以可以放心使用。但在实际工业场景面对海量节点就需要考虑更高效的算法如针对单源问题的Dijkstra堆优化版、Bellman-Ford算法或者使用分布式计算框架。3. K-means聚类数据分组的“探索之旅”现在我们把视线转向另一个舞台K-means聚类。它的任务是把一堆没有标签的数据点按照它们之间的“相似度”自动划分成K个组簇。这个“相似度”通常用数据点之间的距离来衡量最常用的就是欧几里得距离。3.1 算法流程与形象化理解K-means的思想非常直观甚至有些“简单粗暴”。你可以把它想象成一场“地盘划分”游戏选老大首先我们随机在数据空间里选择K个点作为初始的“簇中心”Centroid也就是每个簇的老大。跟老大然后遍历每一个数据点计算它到K个簇中心的距离并把它归入距离最近的那个簇中心所在的簇。这一步完成后所有数据点都被分到了K个簇里。重新选老大既然小弟们都归队了原来的老大位置可能就不太“居中”了。于是对于每一个簇我们重新计算它的簇中心。方法很简单把这个簇里所有数据点的各个坐标值分别求平均得到一个新的点这个点就是该簇新的中心。迭代与收敛用新的簇中心重复第2步跟老大和第3步重新选老大。如此反复迭代直到满足停止条件。停止条件通常是簇中心的位置不再发生显著变化移动距离小于某个阈值或者数据点的归属不再改变或者达到了预设的最大迭代次数。这个过程本质上是在优化一个目标函数簇内误差平方和Within-Cluster Sum of Squares, WCSS。这个函数计算的是每个数据点到其所属簇中心的距离的平方和。K-means的迭代过程就是在不断地尝试降低这个WCSS的值。虽然不能保证找到全局最优解这是一个NP难问题但通常能找到一个不错的局部最优解。3.2 核心参数K的选择肘部法则与轮廓系数K-means算法有一个必须由我们事先指定的参数簇的数量K。这既是它的优点简单明确也是最大的难点和挑战。选错了K结果可能毫无意义。在数模竞赛和实际分析中有几种常用的方法来确定K肘部法则这是最直观的方法。我们尝试不同的K值比如从1到10分别运行K-means算法并计算每个K值对应的WCSS。然后我们画出K与WCSS的关系曲线。理想情况下这条曲线会像一个“手肘”。当K小于真实簇数时每增加一个簇WCSS会大幅下降相当于把一个大簇切开内部紧凑性大大增加。当K达到或超过真实簇数后再增加KWCSS的下降幅度会突然变得平缓相当于在已经很紧凑的簇里再硬切一刀收益不大。这个拐点就像手肘的关节对应的K值就是我们的候选值。实操心得肘部法则很多时候拐点并不明显尤其是数据分布复杂时。这时需要结合业务理解进行判断。在论文中一定要附上这条曲线图并阐述你选择某个K值的理由。轮廓系数这是一个更量化的指标用于衡量聚类结果的“紧密度”和“分离度”。对于每个数据点i计算a(i)i到同簇内所有其他点距离的平均值簇内不相似度。b(i)i到其他每一个簇中所有点平均距离的最小值簇间不相似度。那么点i的轮廓系数 s(i) (b(i) - a(i)) / max(a(i), b(i))。 s(i)的取值范围在[-1, 1]之间。越接近1说明该点聚类越合理越接近-1说明该点可能被分错了簇接近0则说明点在两个簇的边界上。所有点的s(i)的均值即为该聚类结果的整体轮廓系数。我们可以计算不同K值下的平均轮廓系数选择系数最大的K。实操心得轮廓系数计算量比肘部法则大但结果通常更可靠。Python的sklearn.metrics库里有现成的函数silhouette_score可以直接调用。在论文中同时使用肘部法则和轮廓系数会让你的分析显得更全面、更严谨。业务驱动在有的场景下簇的数量是由业务需求决定的。比如你要把客户分成“高价值”、“中价值”、“低价值”三类那么K3就是给定的。这时聚类的目的是发现这三类客户各自的特征而不是寻找数据本身的自然分组。3.3 算法实现、初始化的陷阱与改进我们来看一个简单的Python实现使用sklearn库from sklearn.cluster import KMeans import numpy as np # 假设X是我们的数据形状为 (n_samples, n_features) X np.array([[1, 2], [1, 4], [1, 0], [10, 2], [10, 4], [10, 0]]) # 选择K2 kmeans KMeans(n_clusters2, random_state42, n_init10) kmeans.fit(X) print(簇中心, kmeans.cluster_centers_) print(数据点标签, kmeans.labels_)这段代码会输出两个簇中心以及每个数据点属于哪个簇0或1。这里引出了K-means最大的一个“坑”对初始簇中心敏感。由于算法开始时是随机选择K个点作为中心不同的随机种子可能导致完全不同的聚类结果尤其是在数据分布不那么“规整”的时候。运气不好时可能会收敛到一个很差的局部最优解。为了解决这个问题在实际应用中我们通常采用以下策略多次初始化这正是上面代码中n_init10参数的作用。算法会使用不同的随机种子运行10次最终选择WCSS最小的那一次结果作为最终输出。sklearn默认n_init10这是一个很好的实践务必保留或设置一个更大的值如20或50以确保稳定性。K-means初始化这是一种更聪明的初始化方法也是sklearn默认的初始化策略 (initk-means)。它的核心思想是让初始的簇中心彼此尽可能远离。具体步骤是随机选择一个数据点作为第一个簇中心。对于每个数据点计算它与已选簇中心的最短距离D(x)。以概率D(x)^2 / sum(D(x)^2)选择下一个簇中心距离越远的点被选中的概率越大。重复直到选出K个中心。 K-means能显著提高找到优质解的概率和算法的收敛速度是现在的标准做法。注意即使使用了K-means和多次初始化K-means仍然可能找到局部最优。在论文中你可以提及采用了这些策略来增强结果的稳定性并说明最终选取的是多次运行中目标函数WCSS最优的结果。数据预处理——标准化至关重要K-means基于距离度量因此各特征的数量级差异会对结果产生决定性影响。如果一个特征的单位是“万元”另一个特征是“百分比”直接聚类就等于让“万元”这个特征完全主导了距离计算。必须进行特征标准化通常使用Z-score标准化减去均值除以标准差使每个特征均值为0方差为1处于同一量纲。sklearn的StandardScaler可以轻松完成这个工作。忘记标准化是新手最常见的错误之一。局限性与适用场景K-means假设簇是凸形的、各向同性的在各个方向方差相近并且大小差不多。它对于非球形簇、密度差异大的簇或者大小悬殊的簇效果会很差。例如它无法很好地区分两个嵌套的环形簇。了解算法的局限性才能知道何时该用它何时该换用DBSCAN、层次聚类等其他方法。4. Floyd与K-means的联合作战从距离到分组前面我们分别深入了解了Floyd和K-means。现在来到最精彩的部分如何让它们联手解决更复杂的问题核心思路在于用Floyd算法计算出更符合业务逻辑的“自定义距离”然后将这个距离矩阵作为K-means的输入进行聚类。4.1 经典场景基于实际交通时间的城市聚类假设我们有一个数模题目某物流公司需要在全国设立K个区域配送中心。选址要求是每个配送中心覆盖一组城市组内城市到该中心城市的实际运输时间尽可能短即组内紧密度高同时不同组之间的城市运输时间尽可能长即组间分离度大。城市之间的直接运输时间已知但可以通过其他城市中转。步骤拆解构建图模型与距离矩阵将每个城市视为图的一个顶点。如果两个城市有直达运输路线则边的权重就是运输时间。如果没有直达路线则初始权重设为无穷大或一个极大值。对角线城市到自身设为0。这就得到了初始的邻接矩阵。应用Floyd算法计算全源最短运输时间运行Floyd算法得到最终的距离矩阵D。此时D[i][j]存储的就是城市i到城市j的实际最短运输时间可能包含中转。这个时间比简单的直线距离或直达时间更能反映真实的物流成本。为K-means准备“特征”现在我们有了一个N x N的距离矩阵N是城市数量。但是K-means的输入通常是一个N x M的特征矩阵N个样本每个样本有M个特征。我们如何把距离矩阵转换成每个城市的“特征向量”呢一个巧妙且常用的方法是将每个城市到其他所有城市的最短时间作为该城市的特征。也就是说对于城市i它的特征向量就是距离矩阵D的第i行或第i列。这样每个城市就被表示为一个N维向量向量中每个元素代表它到另一个城市的“关系”。降维可选但推荐现在每个城市有N个特征N可能很大。直接进行聚类可能面临“维数灾难”且计算效率低。我们可以使用主成分分析PCA或度量多维标度法MDS等降维技术在尽可能保留城市间“距离关系”信息的前提下将N维特征降到较低的维度比如2维或3维。这不仅便于可视化也能提升K-means的效率和效果。MDS尤其适合这种从距离矩阵还原坐标的场景。运行K-means聚类对降维后的数据或原始的高维特征向量运行K-means算法。此时算法依据的“距离”是特征空间中的欧氏距离而这个特征空间是由Floyd算出的实际运输时间关系构建的。因此聚类的结果自然会将“实际运输时间相近”的城市分到同一组。确定中心与解释结果K-means会给出K个簇以及每个簇的中心。在降维后的空间中这些中心点也有坐标。我们可以寻找距离每个簇中心最近的原城市将其作为该区域的“中心城市”或“配送中心”候选。最后结合地理信息、经济数据等对分簇结果进行业务解释。4.2 另一种思路直接使用距离矩阵进行聚类除了将距离矩阵转化为特征向量还有一种更直接的方法使用基于距离矩阵的聚类算法如层次聚类Hierarchical Clustering或谱聚类Spectral Clustering。这些算法可以直接接受一个距离矩阵或相似度矩阵作为输入。特别是谱聚类它首先根据距离矩阵构建一个相似度图例如使用高斯核函数将距离转化为相似度然后对这个图的拉普拉斯矩阵进行特征分解最后对特征向量进行K-means聚类。这种方法在应对复杂的流形数据时往往比直接使用欧氏距离的K-means效果更好。在我们的场景中我们可以将Floyd计算出的最短时间矩阵D通过一个衰减函数如similarity exp(-D^2 / (2*sigma^2))转化为相似度矩阵然后喂给谱聚类算法。这样我们就完成了一个“Floyd - 相似度矩阵 - 谱聚类”的完整 pipeline。在数模论文中尝试并对比“特征向量K-means”和“距离矩阵谱聚类”两种方案能极大地丰富论文的方法论部分。4.3 数模论文中的呈现要点如果你在数模论文中使用了这种组合方法以下几点能让你脱颖而出清晰的流程图绘制一个从原始数据到最终聚类结果的完整流程图标明每个环节使用的算法Floyd, PCA/MDS, K-means/谱聚类及其输入输出。一图胜千言。关键矩阵的可视化将Floyd处理前后的距离矩阵用热力图Heatmap展示出来。处理前矩阵中可能有很多代表“无穷大”的斑块无直接连接处理后矩阵会变得“充实”起来能直观显示城市间的连通性改善。聚类结果的评估与对比不要只给出一个聚类结果。要用轮廓系数、Calinski-Harabasz指数等指标定量评估不同K值下、不同方法如纯坐标K-means vs FloydK-means的聚类质量。通过表格和图表进行对比分析。业务意义的映射将聚类结果在地图上可视化并结合每个簇内城市的经济发展水平、产业结构、人口规模等属性解释为什么这些城市会被分在一起这样的分簇对物流配送、区域规划有何实际指导意义。这是从“模型结果”上升到“解决方案”的关键一步。5. 超越竞赛在更广阔场景下的组合应用Floyd与K-means的组合其威力远不止于数模竞赛或物流规划。它的核心范式是先用一种算法Floyd构建或修正“关系”或“距离”的度量再用另一种算法K-means基于这个修正后的度量进行“分组”或“分类”。这个范式可以迁移到许多领域社交网络分析在社交网络中我们定义用户之间的“距离”可以是他们之间的最短社交路径长度例如间隔了多少个共同好友。直接用Floyd算法可以算出所有用户两两之间的“社交距离”。然后基于这个社交距离矩阵可以对用户进行聚类发现潜在的社区结构。这里的“距离”不再是物理距离而是关系亲疏。蛋白质相互作用网络在生物信息学中蛋白质可以看作节点它们之间的相互作用看作边。Floyd算法可以帮助找到蛋白质间的最短作用路径可能经过其他蛋白质中介。然后基于这种功能距离对蛋白质进行聚类可能发现具有相似功能或处于同一代谢通路的蛋白质模块。故障传播分析在复杂的工业系统或电网中一个组件的故障可能通过依赖关系传播到其他组件。我们可以用图表示组件间的依赖边的权重可以是故障传播的概率或时间。Floyd算法可以计算出任意两个组件间最可能的故障传播路径及其“风险距离”。基于此距离对组件进行聚类可以识别出系统中脆弱性高度关联的子系统便于进行冗余设计和重点防护。推荐系统的冷启动对于新用户或新物品由于缺乏历史行为数据协同过滤等方法难以生效。我们可以利用物品的属性信息如电影的类型、导演、演员构建一个物品关系图用Floyd计算物品间的“属性路径距离”。然后将所有物品基于这个距离进行聚类。当一个新用户对某个簇内的一个物品产生行为后我们可以将整个簇的物品作为潜在的推荐候选集。这为解决冷启动问题提供了一种思路。在这些场景中Floyd扮演了“关系度量构建者”的角色而K-means或其他聚类算法扮演了“模式发现者”的角色。它们的结合使得我们可以基于复杂的、非欧几里得的、网络化的关系数据进行有效的分组分析。6. 实战中的扩展与优化思考当你真正在项目或竞赛中应用这套组合拳时还有一些进阶问题需要考虑Floyd的性能瓶颈与替代方案如前所述Floyd的O(n³)复杂度是硬伤。对于大规模图节点数1000计算全源最短路径可能不现实。此时可以考虑多次运行Dijkstra算法对每个节点作为源点运行一次Dijkstra算法使用二叉堆优化复杂度O((VE)log V)。对于稀疏图边数E远小于V²这比Floyd更高效。sklearn中并没有图算法库但networkx或igraph等图计算库有高效的最短路径实现。Johnson算法对于稀疏图且含有负权边不含负权环的情况Johnson算法是更好的全源最短路径选择。近似算法或分布式计算如果对精度要求不是绝对严格可以考虑使用Landmark-based的近似最短路径算法。对于超大规模图必须借助Spark GraphX或Neo4j等分布式或图数据库的计算能力。距离度量的设计与归一化Floyd输出的最短路径“距离”可能具有特定的物理意义如时间、成本、跳数。直接将其作为K-means的输入距离可能有问题。例如时间距离和跳数距离量纲和范围不同需要归一化。更重要的是要考虑这个距离是否满足K-means的假设欧氏空间。有时需要对距离进行变换例如取对数、平方根或者使用更通用的距离度量如马氏距离。K-means的变体与替代标准K-means有其局限。根据数据特点可以考虑K-medoids使用实际的数据点作为簇中心medoid而不是计算均值点。这对噪声和异常值更鲁棒且中心点一定是存在的样本解释性更强。DBSCAN基于密度的聚类不需要指定K能发现任意形状的簇并能识别噪声点。如果你不确定簇的数量和形状DBSCAN是很好的探索工具。层次聚类可以生成一个树状的聚类结构树状图便于观察不同粒度下的聚类结果也不需要预先指定K。流程的自动化与评估在完整的分析pipeline中从原始图数据到最终聚类标签中间可能包含多个步骤Floyd、降维、聚类、评估。使用像Python的scikit-learn的Pipeline和GridSearchCV可以帮你自动化地尝试不同的参数组合如K-means的KPCA的降维维度并通过轮廓系数等指标自动选择最优的模型参数。这能让你的分析过程更加系统化和可靠。在我处理过的一个区域商圈分析项目中就完整运用了这套流程。原始数据是城市内商业网点间的行车时间部分直接部分需估算。先用Floyd算出所有网点间的最短通行时间矩阵然后用MDS将其降维至2维便于可视化最后用K-means结合轮廓系数确定了5个核心商圈。结果不仅与政府规划高度吻合还发现了一个潜在的新兴商圈区域。整个过程中对Floyd结果的热力图分析、对MDS降维后散点图的观察、以及对不同K值下轮廓系数的对比这些环节都提供了至关重要的洞察。算法的价值不仅在于其本身的计算过程更在于我们如何创造性地将它们组合、适配到具体的问题语境中。Floyd与K-means一个精于计算全局关系一个善于发现局部模式它们的结合正是这种“组合创新”的典型体现。下次当你面对一个既有复杂关联关系又需要清晰分组的难题时不妨想想这对“黄金搭档”。 Floyd与K-means算法组合实战：从最短路径到数据聚类的综合应用
1. 从两个看似无关的算法说起如果你参加过数学建模竞赛或者处理过一些网络优化、数据分类的实际问题大概率会碰到两个名字听起来八竿子打不着的算法Floyd和K-means。前者Floyd算法通常和“最短路径”、“图论”、“网络优化”这些词绑定在一起给人的感觉是严谨、确定、一步一个脚印。后者K-means算法则活跃在“聚类分析”、“数据挖掘”、“机器学习”的领域充满了迭代、试探和不确定性。乍一看一个像是规划城市间最省时路线的交通工程师另一个则像是在一堆杂乱无章的客户数据中寻找相似群体的市场分析师。它们似乎分属两个完全不同的世界。但有意思的是在我参与和评审过的众多数模项目以及一些工业界的解决方案中这两个算法常常会以意想不到的方式组合出现解决一些单一算法束手无策的复杂问题。比如一个经典的场景是你需要对一批城市进行区域划分聚类但划分的依据不是简单的经纬度距离而是城市之间的实际交通时间或物流成本最短路径。这时候单独用K-means按欧氏距离分结果可能完全不符合实际单独用Floyd算出了所有城市间的最短耗时却又不知道怎么科学地分组。它们的结合恰恰能碰撞出火花。今天我们就抛开教科书上孤立的介绍从一个数模实战者和算法应用者的角度深入聊聊Floyd和K-means。我们不止要弄清楚它们各自“是什么”和“怎么用”更要探究它们“为什么”要这么设计以及最关键的一步——如何将它们“串联”或“嵌套”起来去解决那些更贴近现实的、维度丰富的综合性问题。无论你是正在备战数模竞赛的学生还是初涉数据分析的工程师理解这种“算法组合拳”的思路远比死记硬背单个算法的步骤要有价值得多。2. Floyd算法全源最短路径的“暴力美学”首先我们聚焦Floyd算法。它的全称是Floyd-Warshall算法核心任务是解决“全源最短路径”问题。简单说就是给你一个图比如城市交通网图中每个点城市到其他所有点的最短距离是多少它不满足于只求一个起点到其他点的距离那是Dijkstra算法的活儿而是要一口气算出所有点对之间的最短距离结果通常用一个二维矩阵距离矩阵来呈现。2.1 核心思想与动态规划内核Floyd算法最迷人的地方在于其思想的简洁与深刻。它基于一个非常直观的动态规划思想。假设我们有一个图顶点编号为1到n。我们定义d[k][i][j]为从顶点i到顶点j只允许以顶点1, 2, ..., k 作为中间顶点的所有可能路径中的最短路径长度。注意这个定义的精妙之处。当 k0 时意味着不允许任何中间顶点那么d[0][i][j]就是顶点i到j的直接边权如果两点间有直接边或者无穷大如果两点间没有直接边。这就是我们的初始状态。现在考虑如何从d[k-1][i][j]推导出d[k][i][j]。当我们允许使用第k个顶点作为中间点时从i到j的最短路径无非两种可能这条最短路径根本不经过顶点k。那么它的长度就是d[k-1][i][j]。这条最短路径经过顶点k。那么我们可以把路径拆成两段i - k 和 k - j。而这两段路径在只允许使用前k-1个顶点作为中间点时最短长度分别是d[k-1][i][k]和d[k-1][k][j]。因此经过k的路径长度就是这两者之和。我们要找的是所有可能路径中的最短者所以递推公式就出来了d[k][i][j] min( d[k-1][i][j], d[k-1][i][k] d[k-1][k][j] )这个递推关系是Floyd算法的灵魂。在实际编程中为了节省空间我们通常使用同一个二维数组d[i][j]进行滚动更新因为d[k][i][j]只依赖于d[k-1][...]。最终当 kn 时d[i][j]就是允许使用所有顶点作为中间点时从i到j的全局最短路径长度。注意这里有一个非常关键的细节也是初学者容易写错的地方。三层循环for k from 1 to n: for i from 1 to n: for j from 1 to n:的顺序是固定的k必须放在最外层。因为我们的递推式是基于“允许使用前k个点”这个状态定义的必须一层一层地解放这些中间点。如果错把i或j放在外层更新逻辑就完全错误了。2.2 算法实现与“距离矩阵”的构建理论有点绕我们来看一个具体的实现和例子。假设我们有4个城市A、B、C、D它们之间的直接道路距离如下表所示INF代表无穷大即没有直接道路ABCDA0264BINF03INFC7INF01D5INF120这个矩阵就是我们的初始距离矩阵d。现在我们开始Floyd算法的三重循环更新。第一轮 (k1考虑A作为中间点) 主要检查所有i-j的路径是否可以通过“i-A A-j”变得更短。 例如d[B][C]原本是3。检查d[B][A] d[A][C] INF 6不小于3所以不变。 再如d[B][D]原本是INF。检查d[B][A] d[A][D] INF 4不小于INF不变。 这一轮因为A点本身更新可能不多。第二轮 (k2考虑B作为中间点) 检查所有路径是否可以通过B中转。 例如d[A][C]原本是6。检查d[A][B] d[B][C] 2 3 5小于6于是更新d[A][C] 5。这意味着发现了A-B-C这条更短的路径。 再如d[A][D]原本是4。检查d[A][B] d[B][D] 2 INF不小于4不变。第三轮 (k3考虑C作为中间点) 此时矩阵已经部分更新。检查所有路径是否可以通过C中转。 例如d[A][D]此时是4。检查d[A][C] d[C][D] 5 1 6大于4不变。 但d[B][A]原本是INF。检查d[B][C] d[C][A] 3 7 10小于INF于是更新d[B][A] 10。发现了B-C-A的路径。d[D][A]原本是5。检查d[D][C] d[C][A] 12 7 19大于5不变。d[D][B]原本是INF。检查d[D][C] d[C][B] 12 INF不小于INF不变。第四轮 (k4考虑D作为中间点) 最后一遍扫描查漏补缺。 例如d[C][B]原本是INF。检查d[C][D] d[D][B] 1 INF不小于INF不变。d[A][B]原本是2。检查d[A][D] d[D][B] 4 INF不小于2不变。经过四轮更新我们最终得到全源最短路径矩阵。你可以手动验证比如d[B][A]最终是10路径B-C-Ad[A][C]是5路径A-B-C。这个最终的矩阵才是我们心目中真正能反映“任意两城市间实际可达最短距离”的数据。它已经考虑了所有可能的迂回、中转方案。在代码实现上Python版本非常简洁def floyd_warshall(graph): n len(graph) dist [[graph[i][j] for j in range(n)] for i in range(n)] # 初始化距离矩阵副本 for k in range(n): for i in range(n): for j in range(n): if dist[i][k] ! float(inf) and dist[k][j] ! float(inf): if dist[i][j] dist[i][k] dist[k][j]: dist[i][j] dist[i][k] dist[k][j] return dist这段代码就是上述动态规划思想的直接翻译。graph是输入的邻接矩阵。2.3 实战中的关键细节与避坑指南在实际的数模或工程应用中直接套用教科书代码往往不够有几个细节必须注意图的类型与初始化Floyd算法要求图用邻接矩阵表示。对于无向图矩阵是对称的对于有向图则不一定。初始化时对角线自己到自己的距离必须初始化为0。不直接相连的点距离初始化为一个足够大的数如float(inf)但要注意这个“无穷大”不能参与加法运算否则会溢出。所以在代码中我们增加了if dist[i][k] ! inf and dist[k][j] ! inf的判断。负权边与负权环Floyd算法可以处理带有负权边的图这是它相对于Dijkstra算法的一个优势。但是它不能处理包含“负权环”的图。因为如果在i到j的路径上存在一个总权值为负的环那么可以无限次地绕这个环使得最短路径长度趋于负无穷算法将失去意义。如果你的图可能存在负权在算法结束后可以检查对角线元素dist[i][i]。如果任何一个dist[i][i] 0则说明图中存在从i出发又回到i的负权环。路径重建算法只给出了最短距离但很多时候我们需要知道具体是哪条路径。这就需要额外维护一个“后继节点矩阵”或“前驱节点矩阵”。在更新dist[i][j]的同时记录下导致这次更新的中间点k或者记录j的前驱节点。赛后通过回溯法即可重建完整路径。这个步骤在数模论文中是体现工作完整性的重要加分项。性能考量Floyd算法的时间复杂度是O(n³)空间复杂度是O(n²)。这意味着当顶点数n很大时比如上万个点它的计算开销会变得非常巨大。在数模竞赛中通常n不会特别大几百以内所以可以放心使用。但在实际工业场景面对海量节点就需要考虑更高效的算法如针对单源问题的Dijkstra堆优化版、Bellman-Ford算法或者使用分布式计算框架。3. K-means聚类数据分组的“探索之旅”现在我们把视线转向另一个舞台K-means聚类。它的任务是把一堆没有标签的数据点按照它们之间的“相似度”自动划分成K个组簇。这个“相似度”通常用数据点之间的距离来衡量最常用的就是欧几里得距离。3.1 算法流程与形象化理解K-means的思想非常直观甚至有些“简单粗暴”。你可以把它想象成一场“地盘划分”游戏选老大首先我们随机在数据空间里选择K个点作为初始的“簇中心”Centroid也就是每个簇的老大。跟老大然后遍历每一个数据点计算它到K个簇中心的距离并把它归入距离最近的那个簇中心所在的簇。这一步完成后所有数据点都被分到了K个簇里。重新选老大既然小弟们都归队了原来的老大位置可能就不太“居中”了。于是对于每一个簇我们重新计算它的簇中心。方法很简单把这个簇里所有数据点的各个坐标值分别求平均得到一个新的点这个点就是该簇新的中心。迭代与收敛用新的簇中心重复第2步跟老大和第3步重新选老大。如此反复迭代直到满足停止条件。停止条件通常是簇中心的位置不再发生显著变化移动距离小于某个阈值或者数据点的归属不再改变或者达到了预设的最大迭代次数。这个过程本质上是在优化一个目标函数簇内误差平方和Within-Cluster Sum of Squares, WCSS。这个函数计算的是每个数据点到其所属簇中心的距离的平方和。K-means的迭代过程就是在不断地尝试降低这个WCSS的值。虽然不能保证找到全局最优解这是一个NP难问题但通常能找到一个不错的局部最优解。3.2 核心参数K的选择肘部法则与轮廓系数K-means算法有一个必须由我们事先指定的参数簇的数量K。这既是它的优点简单明确也是最大的难点和挑战。选错了K结果可能毫无意义。在数模竞赛和实际分析中有几种常用的方法来确定K肘部法则这是最直观的方法。我们尝试不同的K值比如从1到10分别运行K-means算法并计算每个K值对应的WCSS。然后我们画出K与WCSS的关系曲线。理想情况下这条曲线会像一个“手肘”。当K小于真实簇数时每增加一个簇WCSS会大幅下降相当于把一个大簇切开内部紧凑性大大增加。当K达到或超过真实簇数后再增加KWCSS的下降幅度会突然变得平缓相当于在已经很紧凑的簇里再硬切一刀收益不大。这个拐点就像手肘的关节对应的K值就是我们的候选值。实操心得肘部法则很多时候拐点并不明显尤其是数据分布复杂时。这时需要结合业务理解进行判断。在论文中一定要附上这条曲线图并阐述你选择某个K值的理由。轮廓系数这是一个更量化的指标用于衡量聚类结果的“紧密度”和“分离度”。对于每个数据点i计算a(i)i到同簇内所有其他点距离的平均值簇内不相似度。b(i)i到其他每一个簇中所有点平均距离的最小值簇间不相似度。那么点i的轮廓系数 s(i) (b(i) - a(i)) / max(a(i), b(i))。 s(i)的取值范围在[-1, 1]之间。越接近1说明该点聚类越合理越接近-1说明该点可能被分错了簇接近0则说明点在两个簇的边界上。所有点的s(i)的均值即为该聚类结果的整体轮廓系数。我们可以计算不同K值下的平均轮廓系数选择系数最大的K。实操心得轮廓系数计算量比肘部法则大但结果通常更可靠。Python的sklearn.metrics库里有现成的函数silhouette_score可以直接调用。在论文中同时使用肘部法则和轮廓系数会让你的分析显得更全面、更严谨。业务驱动在有的场景下簇的数量是由业务需求决定的。比如你要把客户分成“高价值”、“中价值”、“低价值”三类那么K3就是给定的。这时聚类的目的是发现这三类客户各自的特征而不是寻找数据本身的自然分组。3.3 算法实现、初始化的陷阱与改进我们来看一个简单的Python实现使用sklearn库from sklearn.cluster import KMeans import numpy as np # 假设X是我们的数据形状为 (n_samples, n_features) X np.array([[1, 2], [1, 4], [1, 0], [10, 2], [10, 4], [10, 0]]) # 选择K2 kmeans KMeans(n_clusters2, random_state42, n_init10) kmeans.fit(X) print(簇中心, kmeans.cluster_centers_) print(数据点标签, kmeans.labels_)这段代码会输出两个簇中心以及每个数据点属于哪个簇0或1。这里引出了K-means最大的一个“坑”对初始簇中心敏感。由于算法开始时是随机选择K个点作为中心不同的随机种子可能导致完全不同的聚类结果尤其是在数据分布不那么“规整”的时候。运气不好时可能会收敛到一个很差的局部最优解。为了解决这个问题在实际应用中我们通常采用以下策略多次初始化这正是上面代码中n_init10参数的作用。算法会使用不同的随机种子运行10次最终选择WCSS最小的那一次结果作为最终输出。sklearn默认n_init10这是一个很好的实践务必保留或设置一个更大的值如20或50以确保稳定性。K-means初始化这是一种更聪明的初始化方法也是sklearn默认的初始化策略 (initk-means)。它的核心思想是让初始的簇中心彼此尽可能远离。具体步骤是随机选择一个数据点作为第一个簇中心。对于每个数据点计算它与已选簇中心的最短距离D(x)。以概率D(x)^2 / sum(D(x)^2)选择下一个簇中心距离越远的点被选中的概率越大。重复直到选出K个中心。 K-means能显著提高找到优质解的概率和算法的收敛速度是现在的标准做法。注意即使使用了K-means和多次初始化K-means仍然可能找到局部最优。在论文中你可以提及采用了这些策略来增强结果的稳定性并说明最终选取的是多次运行中目标函数WCSS最优的结果。数据预处理——标准化至关重要K-means基于距离度量因此各特征的数量级差异会对结果产生决定性影响。如果一个特征的单位是“万元”另一个特征是“百分比”直接聚类就等于让“万元”这个特征完全主导了距离计算。必须进行特征标准化通常使用Z-score标准化减去均值除以标准差使每个特征均值为0方差为1处于同一量纲。sklearn的StandardScaler可以轻松完成这个工作。忘记标准化是新手最常见的错误之一。局限性与适用场景K-means假设簇是凸形的、各向同性的在各个方向方差相近并且大小差不多。它对于非球形簇、密度差异大的簇或者大小悬殊的簇效果会很差。例如它无法很好地区分两个嵌套的环形簇。了解算法的局限性才能知道何时该用它何时该换用DBSCAN、层次聚类等其他方法。4. Floyd与K-means的联合作战从距离到分组前面我们分别深入了解了Floyd和K-means。现在来到最精彩的部分如何让它们联手解决更复杂的问题核心思路在于用Floyd算法计算出更符合业务逻辑的“自定义距离”然后将这个距离矩阵作为K-means的输入进行聚类。4.1 经典场景基于实际交通时间的城市聚类假设我们有一个数模题目某物流公司需要在全国设立K个区域配送中心。选址要求是每个配送中心覆盖一组城市组内城市到该中心城市的实际运输时间尽可能短即组内紧密度高同时不同组之间的城市运输时间尽可能长即组间分离度大。城市之间的直接运输时间已知但可以通过其他城市中转。步骤拆解构建图模型与距离矩阵将每个城市视为图的一个顶点。如果两个城市有直达运输路线则边的权重就是运输时间。如果没有直达路线则初始权重设为无穷大或一个极大值。对角线城市到自身设为0。这就得到了初始的邻接矩阵。应用Floyd算法计算全源最短运输时间运行Floyd算法得到最终的距离矩阵D。此时D[i][j]存储的就是城市i到城市j的实际最短运输时间可能包含中转。这个时间比简单的直线距离或直达时间更能反映真实的物流成本。为K-means准备“特征”现在我们有了一个N x N的距离矩阵N是城市数量。但是K-means的输入通常是一个N x M的特征矩阵N个样本每个样本有M个特征。我们如何把距离矩阵转换成每个城市的“特征向量”呢一个巧妙且常用的方法是将每个城市到其他所有城市的最短时间作为该城市的特征。也就是说对于城市i它的特征向量就是距离矩阵D的第i行或第i列。这样每个城市就被表示为一个N维向量向量中每个元素代表它到另一个城市的“关系”。降维可选但推荐现在每个城市有N个特征N可能很大。直接进行聚类可能面临“维数灾难”且计算效率低。我们可以使用主成分分析PCA或度量多维标度法MDS等降维技术在尽可能保留城市间“距离关系”信息的前提下将N维特征降到较低的维度比如2维或3维。这不仅便于可视化也能提升K-means的效率和效果。MDS尤其适合这种从距离矩阵还原坐标的场景。运行K-means聚类对降维后的数据或原始的高维特征向量运行K-means算法。此时算法依据的“距离”是特征空间中的欧氏距离而这个特征空间是由Floyd算出的实际运输时间关系构建的。因此聚类的结果自然会将“实际运输时间相近”的城市分到同一组。确定中心与解释结果K-means会给出K个簇以及每个簇的中心。在降维后的空间中这些中心点也有坐标。我们可以寻找距离每个簇中心最近的原城市将其作为该区域的“中心城市”或“配送中心”候选。最后结合地理信息、经济数据等对分簇结果进行业务解释。4.2 另一种思路直接使用距离矩阵进行聚类除了将距离矩阵转化为特征向量还有一种更直接的方法使用基于距离矩阵的聚类算法如层次聚类Hierarchical Clustering或谱聚类Spectral Clustering。这些算法可以直接接受一个距离矩阵或相似度矩阵作为输入。特别是谱聚类它首先根据距离矩阵构建一个相似度图例如使用高斯核函数将距离转化为相似度然后对这个图的拉普拉斯矩阵进行特征分解最后对特征向量进行K-means聚类。这种方法在应对复杂的流形数据时往往比直接使用欧氏距离的K-means效果更好。在我们的场景中我们可以将Floyd计算出的最短时间矩阵D通过一个衰减函数如similarity exp(-D^2 / (2*sigma^2))转化为相似度矩阵然后喂给谱聚类算法。这样我们就完成了一个“Floyd - 相似度矩阵 - 谱聚类”的完整 pipeline。在数模论文中尝试并对比“特征向量K-means”和“距离矩阵谱聚类”两种方案能极大地丰富论文的方法论部分。4.3 数模论文中的呈现要点如果你在数模论文中使用了这种组合方法以下几点能让你脱颖而出清晰的流程图绘制一个从原始数据到最终聚类结果的完整流程图标明每个环节使用的算法Floyd, PCA/MDS, K-means/谱聚类及其输入输出。一图胜千言。关键矩阵的可视化将Floyd处理前后的距离矩阵用热力图Heatmap展示出来。处理前矩阵中可能有很多代表“无穷大”的斑块无直接连接处理后矩阵会变得“充实”起来能直观显示城市间的连通性改善。聚类结果的评估与对比不要只给出一个聚类结果。要用轮廓系数、Calinski-Harabasz指数等指标定量评估不同K值下、不同方法如纯坐标K-means vs FloydK-means的聚类质量。通过表格和图表进行对比分析。业务意义的映射将聚类结果在地图上可视化并结合每个簇内城市的经济发展水平、产业结构、人口规模等属性解释为什么这些城市会被分在一起这样的分簇对物流配送、区域规划有何实际指导意义。这是从“模型结果”上升到“解决方案”的关键一步。5. 超越竞赛在更广阔场景下的组合应用Floyd与K-means的组合其威力远不止于数模竞赛或物流规划。它的核心范式是先用一种算法Floyd构建或修正“关系”或“距离”的度量再用另一种算法K-means基于这个修正后的度量进行“分组”或“分类”。这个范式可以迁移到许多领域社交网络分析在社交网络中我们定义用户之间的“距离”可以是他们之间的最短社交路径长度例如间隔了多少个共同好友。直接用Floyd算法可以算出所有用户两两之间的“社交距离”。然后基于这个社交距离矩阵可以对用户进行聚类发现潜在的社区结构。这里的“距离”不再是物理距离而是关系亲疏。蛋白质相互作用网络在生物信息学中蛋白质可以看作节点它们之间的相互作用看作边。Floyd算法可以帮助找到蛋白质间的最短作用路径可能经过其他蛋白质中介。然后基于这种功能距离对蛋白质进行聚类可能发现具有相似功能或处于同一代谢通路的蛋白质模块。故障传播分析在复杂的工业系统或电网中一个组件的故障可能通过依赖关系传播到其他组件。我们可以用图表示组件间的依赖边的权重可以是故障传播的概率或时间。Floyd算法可以计算出任意两个组件间最可能的故障传播路径及其“风险距离”。基于此距离对组件进行聚类可以识别出系统中脆弱性高度关联的子系统便于进行冗余设计和重点防护。推荐系统的冷启动对于新用户或新物品由于缺乏历史行为数据协同过滤等方法难以生效。我们可以利用物品的属性信息如电影的类型、导演、演员构建一个物品关系图用Floyd计算物品间的“属性路径距离”。然后将所有物品基于这个距离进行聚类。当一个新用户对某个簇内的一个物品产生行为后我们可以将整个簇的物品作为潜在的推荐候选集。这为解决冷启动问题提供了一种思路。在这些场景中Floyd扮演了“关系度量构建者”的角色而K-means或其他聚类算法扮演了“模式发现者”的角色。它们的结合使得我们可以基于复杂的、非欧几里得的、网络化的关系数据进行有效的分组分析。6. 实战中的扩展与优化思考当你真正在项目或竞赛中应用这套组合拳时还有一些进阶问题需要考虑Floyd的性能瓶颈与替代方案如前所述Floyd的O(n³)复杂度是硬伤。对于大规模图节点数1000计算全源最短路径可能不现实。此时可以考虑多次运行Dijkstra算法对每个节点作为源点运行一次Dijkstra算法使用二叉堆优化复杂度O((VE)log V)。对于稀疏图边数E远小于V²这比Floyd更高效。sklearn中并没有图算法库但networkx或igraph等图计算库有高效的最短路径实现。Johnson算法对于稀疏图且含有负权边不含负权环的情况Johnson算法是更好的全源最短路径选择。近似算法或分布式计算如果对精度要求不是绝对严格可以考虑使用Landmark-based的近似最短路径算法。对于超大规模图必须借助Spark GraphX或Neo4j等分布式或图数据库的计算能力。距离度量的设计与归一化Floyd输出的最短路径“距离”可能具有特定的物理意义如时间、成本、跳数。直接将其作为K-means的输入距离可能有问题。例如时间距离和跳数距离量纲和范围不同需要归一化。更重要的是要考虑这个距离是否满足K-means的假设欧氏空间。有时需要对距离进行变换例如取对数、平方根或者使用更通用的距离度量如马氏距离。K-means的变体与替代标准K-means有其局限。根据数据特点可以考虑K-medoids使用实际的数据点作为簇中心medoid而不是计算均值点。这对噪声和异常值更鲁棒且中心点一定是存在的样本解释性更强。DBSCAN基于密度的聚类不需要指定K能发现任意形状的簇并能识别噪声点。如果你不确定簇的数量和形状DBSCAN是很好的探索工具。层次聚类可以生成一个树状的聚类结构树状图便于观察不同粒度下的聚类结果也不需要预先指定K。流程的自动化与评估在完整的分析pipeline中从原始图数据到最终聚类标签中间可能包含多个步骤Floyd、降维、聚类、评估。使用像Python的scikit-learn的Pipeline和GridSearchCV可以帮你自动化地尝试不同的参数组合如K-means的KPCA的降维维度并通过轮廓系数等指标自动选择最优的模型参数。这能让你的分析过程更加系统化和可靠。在我处理过的一个区域商圈分析项目中就完整运用了这套流程。原始数据是城市内商业网点间的行车时间部分直接部分需估算。先用Floyd算出所有网点间的最短通行时间矩阵然后用MDS将其降维至2维便于可视化最后用K-means结合轮廓系数确定了5个核心商圈。结果不仅与政府规划高度吻合还发现了一个潜在的新兴商圈区域。整个过程中对Floyd结果的热力图分析、对MDS降维后散点图的观察、以及对不同K值下轮廓系数的对比这些环节都提供了至关重要的洞察。算法的价值不仅在于其本身的计算过程更在于我们如何创造性地将它们组合、适配到具体的问题语境中。Floyd与K-means一个精于计算全局关系一个善于发现局部模式它们的结合正是这种“组合创新”的典型体现。下次当你面对一个既有复杂关联关系又需要清晰分组的难题时不妨想想这对“黄金搭档”。