1. 度量理论与选举分析的基础框架
在计算社会科学领域，度量偏好理论为选举分析提供了强有力的数学工具。这一理论的核心思想是将候选人和选民都视为某个共同度量空间中的点，通过计算他们之间的距离来衡量偏好关系。这种几何视角不仅能够描述个体偏好，还能揭示选举结果背后的结构性特征。
1.1 度量偏好的基本概念
度量偏好理论建立在三个基本假设之上：
- 存在一个潜在的度量空间，所有候选人和选民都嵌入其中
- 选民对候选人的偏好顺序由他们与该候选人的距离决定（距离越近越偏好）
- 选举的"最优胜者"是使所有选民距离之和最小的候选人
这种框架下，每个度量嵌入都对应一个理论上的最优胜者。然而，现实中我们只能观察到选民的序数偏好（即排名），而无法直接获取底层度量空间。这就引出了度量扭曲(metric distortion)的概念——即实际选举规则选出的胜者与理论最优胜者之间的成本比率。
1.2 选举数据的两种核心度量
在排名数据分析中，Borda距离和Kendall距离是最常用的两种度量：
Borda距离(dB)：
- 基于Borda计分法：将候选人在排名中的位置转换为分数（第j位得分为m-j）
- 定义为两个排名向量L1距离的一半
- 对应于统计学中的Spearman footrule距离
- 在选举理论中，Borda计分法是一种经典的投票规则
Kendall距离(dH)：
- 计算两个排名中不一致的成对比较数量
- 也称为交换距离或冒泡排序距离
- 对应于统计学中的Kendall tau距离
- Kemeny排名规则就是寻找最小化Kendall距离总和的共识排名
这两种距离满足关系：1/2dH ≤ dB ≤ dH，表明它们在度量偏好结构方面具有一致性但又各具特点。
2. 选票图的构建与理论性质
为了有效处理选举数据，我们引入选票图(ballot graph)的概念，将抽象的排名空间转化为具体的图结构，从而可以利用图论工具进行分析。
2.1 基本选票图Gm
基本选票图Gm定义如下：
- 顶点：所有可能的完整或部分排名（即选票）
- 边类型：
- 相邻交换：两个排名仅相差一个相邻候选人的交换，边权重为1
- 截断/扩展：两个排名长度相差1且前k-1位相同，边权重为(m-k)/2
性质：
- 顶点数量为O(m!)，每个顶点度数为O(m²)
- 路径度量精确恢复Kendall距离dH
- 包含对称群Sm的Cayley图作为子图（完整排名构成的子图）
2.2 快捷选票图Gₘ⁺
在基本选票图基础上，增加：
- 一般交换边：允许非相邻候选人的交换，边权重等于他们的排名差
关键性质：
- 路径度量精确恢复Borda距离dB
- 提供了更丰富的连接结构，能够捕捉更全局的排名关系
- 在完整排名情况下，相当于在排列多面体的1-骨架中添加对角线
2.3 广义选票图Ĝm
为处理包含任意平局的选票，我们扩展定义：
- 顶点：允许候选人在任意位置平局的广义排名
- 边：当两个排名仅相差一个相邻组的合并时相连，边权重为1/2×|A|×|B|（A,B为被合并的组）
理论贡献：
- 证明了广义选票图的路径度量仍保持与dH的一致性
- 建立了处理复杂选举数据的统一框架
- 揭示了度量理论与图表示之间的深刻联系
技术细节：在悲观Borda约定下（未提及候选人得0分），选票图能够保持稀疏性；而平均Borda约定会导致度数爆炸性增长，这解释了为何前者更适合大规模选举分析。
3. 选举聚类的算法实现
基于上述理论构建，我们开发了一套完整的选举聚类流程，用于识别选民集团和候选人联盟。
3.1 坐标嵌入与聚类准备
将选票转化为向量表示是应用标准聚类算法的关键步骤：
Borda嵌入(b)：
- 每个候选人对应一个坐标
- 坐标值为m-σ(i)（σ(i)为候选人i的排名位置）
- 例如：在4候选人选举中，选票AD映射为(3,0,0,2)
头对头嵌入(h)：
- 每个候选人对对应一个坐标
- 坐标值为+1（i排在j前）、-1（相反）或0（平局）
- 例如：选票AD映射为(1,1,1,0,-1,-1)（假设候选对顺序为AB,AC,AD,BC,BD,CD）
3.2 Kemeny聚类算法
Kemeny问题可视为单中心聚类特例：
单Kemeny中心：
- 寻找排名π最小化ΣdH(v,π)，v为所有选票
- 经典Kemeny规则，NP难问题
- 对小规模选举（≤10候选人）可精确求解
K均值Kemeny聚类：
- 寻找k个中心{π₁,...,πₖ}最小化Σmin dH(v,πᵢ)
- 描述选举中的多极化结构
- 采用Lloyd型迭代算法：交替进行中心更新和簇分配
优化技巧：
- 利用距离下界进行分支定界剪枝
- 对部分排名采用乐观/悲观界限估计
- 在迭代中使用局部搜索改进中心质量
3.3 极化选举的稳定性理论
我们证明了聚类结果在度量扰动下的稳定性：
定理：对于(R,r)-极化选举（存在两个距离>R的中心，所有选票距离某个中心≤r）：
- 当R > 4r时，存在唯一最优聚类
- 当R > 10r时，该聚类对任何2-biLipschitz等价的度量都保持最优
这一结果为聚类结果的解释提供了理论保障，特别是在分析高度极化的选举时。
4. 实证分析：苏格兰地方政府选举
我们将方法应用于2012-2022年苏格兰地方政府选举数据，包含1070场选举，涉及5个主要政党和数十个小党。
4.1 数据处理流程
数据清洗：
- 处理缺失值和异常排名
- 统一候选人和政党标识
- 验证选票有效性
度量选择：
- 采用悲观Borda约定处理部分排名
- 同时计算dB和dH距离矩阵
- 构建选票图的稀疏表示
聚类验证：
- 使用轮廓系数评估簇内紧密度
- 比较不同k值的解释力
- 进行bootstrap稳健性检验
4.2 主要发现
选民集团识别：
- 在多数选区发现清晰的二聚类结构
- 聚类结果与政党标签有强相关性但不完全一致
- 揭示了传统左-右分野之外的新维度
候选人联盟分析：
- 部分小党候选人表现出与主要政党候选人的意外接近
- 识别出跨党派的地区性联盟模式
- 量化了政党内部的一致性程度
度量比较：
- dB和dH产生的聚类结果高度一致（ARI > 0.9）
- Borda距离对部分排名更稳健
- Kendall距离对顶部排名变化更敏感
4.3 方法优势体现
无监督特性：
- 不依赖政党标签等先验信息
- 能够发现传统分析忽略的模式
- 适用于跨地区、跨时期的比较研究
几何解释性：
- 可视化选票在度量空间中的分布
- 量化不同群体的分离程度
- 为选举制度设计提供洞见
计算效率：
- 稀疏图表示支持大规模选举分析
- 精确算法可处理中等规模选举
- 启发式方法在保持质量的同时降低复杂度
5. 技术细节与实现考量
5.1 部分排名的处理策略
在实际选举中，部分排名（选民未对所有候选人排序）是常见现象。我们采用两种主要策略：
悲观Borda约定：
- 未提及候选人得0分
- 保持计算的简单性
- 适用于策略性投票分析
平均Borda约定：
- 未提及候选人得平均可能分数
- 保持Borda总分不变
- 更符合效用最大化假设
关键发现：只有悲观约定与稀疏选票图表示兼容，这为方法选择提供了理论依据。
5.2 距离计算的优化
原始距离计算复杂度为O(m²)，通过以下技术实现优化：
稀疏向量表示：
- 仅存储非零坐标
- 利用排名位置信息压缩存储
边界估计：
- 对部分排名计算距离上下界
- 在聚类过程中进行早期剪枝
并行计算：
- 将距离矩阵计算分布到多个核心
- 使用SIMD指令加速向量运算
5.3 聚类质量的评估指标
除标准聚类指标外，我们开发了选举特定的评估方法：
解释力分数：
- 比较聚类前后距离总和减少比例
- 量化聚类捕捉选举结构的程度
稳定性指数：
- 通过子采样评估簇一致性
- 衡量方法对数据扰动的鲁棒性
政治一致性：
- 计算簇内政党同质性
- 评估无监督结果与政治现实的吻合度
6. 应用前景与扩展方向
6.1 在选举分析中的潜在应用
选举制度设计：
- 量化不同投票规则下的扭曲程度
- 评估选举制度对极化程度的影响
选民行为研究：
- 识别隐藏的选民维度
- 追踪偏好随时间的演变
选区划分：
- 提供基于偏好相似性的社区定义
- 支持更合理的选区边界划定
6.2 方法学扩展可能
动态选举分析：
- 引入时间序列方法
- 建模选民偏好的演化过程
混合度量学习：
- 结合dB和dH的优势
- 学习特定选举的最合适度量
可解释AI集成：
- 生成聚类结果的语义解释
- 识别影响选民决策的关键维度
6.3 跨领域应用前景
推荐系统：
- 处理用户的部分商品排名
- 识别具有相似偏好的用户群体
生物信息学：
- 分析基因排序数据
- 发现功能相关的基因模块
社会科学研究：
- 量化社会调查中的意见分歧
- 识别文化价值观的潜在维度
在实际应用中，我们观察到选举聚类结果的质量高度依赖于候选人数量和选民人数比例。当候选人过多而选民相对较少时，容易出现过度拟合。一个实用的经验法则是确保平均每个聚类中心至少有50张选票作为支持。
