真实面经题目 · 原创解析
这题考的是把百万级经纬度点在 Hive 环境里做成可落地的空间聚类方案，而不是只说一个算法名。好的回答要先明确聚类目标和距离口径，再选择网格、Geohash、KMeans 或 DBSCAN 等方法，并说明 Hive 里如何用分区分桶、邻域裁剪、两阶段距离计算和结果验证控制成本。核心原则是避免全量两两距离，把空间问题转成可分区、可局部比较、可抽样核验的数据处理流程。
我会先澄清业务目标：是想把一个城市里的点按空间位置聚成热点区域，还是想找异常点、服务圈、商圈边界或固定数量的簇。目标不同，算法选择不同。如果只是做热点统计，网格或 Geohash 聚合就足够；如果要固定 K 个区域，可以用 KMeans；如果希望识别任意形状的密集区域并保留噪声点，DBSCAN 更合适。放在 Hive 里，我不会直接做所有点之间的两两距离，因为百万级点的笛卡尔积会到万亿级比较，基本不可接受。更合理的方案是先把经纬度预处理成可索引的空间单元，例如按经纬度网格、Geohash 或近似投影坐标生成 cell_id，再按城市、日期、cell_id 做分区或分桶。距离计算上，先用经纬度范围或相邻网格做粗过滤，只比较同一 cell 和周边 cell 的点；候选集变小后再用 Haversine、局部平面投影距离或预计算三角函数做精确距离。算法落地上，如果面试要求纯 Hive，可以用 UDF 生成 geohash、邻接 cell，再用有限自连接和聚合完成近邻统计；如果允许工程化选择，我会把 Hive 作为离线存储和预处理层，把真正迭代的 KMeans 或 DBSCAN 放到 Spark、Flink 或专门空间计算库里。性能方面要关注 ORC/Parquet、统计信息、谓词下推、分桶键、数据倾斜和热点网格拆分。验证上不能只看跑完了，要看簇数量、簇半径、簇内平均距离、噪声比例、参数敏感性、抽样地图可视化，以及是否提升下游业务指标，比如热点覆盖率、服务半径合理性或人工标注一致性。
经纬度聚类不是一个固定答案。热点发现适合网格或 Geohash 聚合，固定区域划分适合 KMeans，发现不规则密集区域和噪声点适合 DBSCAN。面试时先问清楚输出要服务什么业务，否则容易把算法说对但方案不匹配。
百万级点如果做全量 pairwise distance，会产生接近 10 的 12 次方量级比较，Hive 上会变成巨大的 shuffle 和 join。空间聚类的第一原则是先做空间索引或网格裁剪，把比较限制在局部邻域内。
可以按经纬度切网格、生成 Geohash，或者在城市尺度下投影到平面坐标后按固定边长切 cell。Hive 表可以按城市、日期等高层字段分区，再按 cell_id 或 geohash 分桶，聚类时只扫描目标城市和目标时间范围的数据。
第一阶段用 bounding box、同 cell 和相邻 cell 做粗筛；第二阶段对候选点用 Haversine 或局部平面近似计算真实距离。城市尺度下平面近似通常更快，但要用抽样和误差评估确认不会影响边界点归属。
Hive 更适合批处理、聚合和有限 join，不擅长大量迭代。纯 Hive 场景下可以做网格聚合、相邻网格合并、近邻计数和简单密度聚类；如果要多轮 KMeans 或完整 DBSCAN，通常把 Hive 作为数据准备层，再交给 Spark 或空间计算框架执行。
优化点包括减少扫描列、使用 ORC/Parquet、开启统计信息和谓词下推、控制 geohash 精度、只展开必要邻接 cell、对超热点 cell 加盐拆分、限制单 reducer 数据量，并用 explain 或作业日志观察 shuffle、map 数量和 reducer 倾斜。
验证可以看簇数量、簇内平均距离、最大半径、噪声比例、边界点稳定性、不同 cell 精度和 eps 参数下的稳定性，还要抽样画到地图上核验。若有下游业务，还要看热点覆盖、服务范围、人工标注一致性或运营决策效果。
可以先按 eps 相关的尺度切网格或 Geohash，把每个点展开到自己 cell 和相邻 cell，只在这些候选 cell 内做自连接计算距离。然后统计每个点 eps 半径内的邻居数，判断核心点、边界点和噪声点，再用连通分量或多轮合并近似形成簇。纯 Hive 做完整连通合并比较笨重，所以通常会限制迭代轮数或把合并步骤交给更合适的计算引擎。
精度要和业务半径或 DBSCAN 的 eps 匹配。cell 太大，候选点过多，join 成本高；cell 太小，需要展开更多邻接 cell，边界处理复杂。常见做法是让 cell 尺度略小于或接近 eps，再通过抽样比较候选召回率、运行时间和簇稳定性。
KMeans 适合想要固定 K 个中心或近似圆形区域的场景，速度和解释性较好，但需要指定 K，且对异常点敏感。DBSCAN 不需要预设簇数，能发现不规则密集区域并识别噪声，但参数 eps 和 minPts 敏感，对密度不均的城市数据可能效果不稳定。
经纬度是球面坐标，经度对应的实际距离会随纬度变化，直接欧氏距离会有误差。城市尺度下可以先做局部投影或小范围近似，但需要说明误差边界；如果要求更严谨，就用 Haversine 或其他球面距离公式做精算。
看扫描数据量、候选 pair 数、shuffle 数据量、任务耗时、reducer 倾斜、热点 cell 占比和失败重试情况。还可以和简单网格聚合、抽样跑完整算法、Spark 版本做对照，确认 Hive 方案不是用过高计算成本换来很小收益。
