在 Apple ][+ 上运行机器学习:用 APPLESOFT BASIC 实现 K-means 的复古实践

区块链技术

在现代硬件上训练模型几乎已经成为常识,但把机器学习带回到 1980 年代的复古主机上,不仅是一种怀旧挑战,也可以成为深入理解算法本质的绝佳教学工具。Apple ][+ 作为史上最具影响力的家用计算机之一,虽然运算能力和内存都有限,但使用 APPLESOFT BASIC 实现经典的 K-means 聚类仍然可行,并且能直观地展示迭代、收敛与决策边界的演化。 K-means 是最直观的聚类算法之一,其核心思想是将观测点划分到离其最近的质心簇,并反复更新质心直到收敛。算法可拆分为两步:分配步骤(Assignment)把每个点分配到最近的质心;更新步骤(Update)根据分配结果重新计算各簇的均值。用数学语言描述就是在欧氏距离度量下最小化组内平方误差。由于思路简单,K-means 非常适合在资源受限的环境中实现,也正因此成为在 Apple ][+ 上动手实践的优选。

在 Apple ][+ 上实现 K-means 面临几类限制:APPLESOFT BASIC 的执行速度远低于现代解释器或编译语言;图形绘制通过 HPLOT 等原始指令,坐标和色彩控制有限;内存和数组声明需要小心规划,DIM 一旦声明便不可改变;浮点运算代价高,需要尽量避免不必要的开销。基于这些限制,实践中采用了若干工程策略来保证程序可运行且易于观察算法行为。 数据生成方面,可以用高斯分布生成两类点以便演示聚类效果。需要注意的是,伪随机函数 RND 与浮点运算配合会产生极端值作为异常点,作者选择保留这些离群点而不裁剪,以展示聚类算法在极端样本存在时的鲁棒性问题。为了调试与可视化方便,示例中每类样本数被缩小到 5 个左右,这样能够清晰地在图形界面上观察每次迭代质心的移动与决策边界的变化。 初始化质心是 K-means 效果好坏的关键环节之一。

在 APPLESOFT BASIC 中,作者通过随机选取数据点作为初始质心实现,并用数据表的某一列标记已被选取的点以避免重复选择。KM 数组用于存放每个簇的质心坐标及计数,KO 用来保存上一轮迭代的质心以便判断收敛。初始化完成后,程序绘制质心之间的连线,作为调试视觉辅助。由于图形指令在越界时会报错,代码对越界情形需要做额外处理或直接忽略不画,这类实现权衡在复古平台上尤为常见。 分配步骤的实现核心是计算每个数据点到所有质心的欧氏距离并取最小值。为了减少开销,程序只计算平方距离而不取平方根,因为比较大小时平方根操作是多余的。

APPLESOFT BASIC 的数组访问和运算会影响速度,因此用二维数组 DI 存储每个点到每个质心的距离以便比较并记录预测标签。为便于观察和调试,代码会打印每个点的坐标与分配结果。 在演示环境下,还要计算聚类与真实标签的一致率以衡量算法表现。由于 K-means 的无监督本质,类别标签本身没有顺序信息,两个簇的编号可能与真实标签相反,导致所谓的标签翻转问题。当簇数量为二时,可以通过若干简单判断将精度调整为其对称值来避免 0% 的误报。但当簇数量超过二时,需要更通用的匹配方法,比如匈牙利算法或基于簇中心与真实类中心的最近匹配策略,这些在 APPLESOFT BASIC 上实现会增加复杂度。

更新步骤通过累加簇内样本坐标并除以样本数量得到新的质心。为检测收敛,程序保存旧质心并计算质心位移平方和,当位移小于某个容差(例如 0.01)时认为收敛。这里同样避免取平方根以节省计算量。收敛后会清空图形并重新绘制所有点和最终决策边界,给出直观的收敛效果展示。 绘制决策边界是一个有趣的额外工程任务,尤其在 Apple ][+ 的图形模型下更具挑战。对于两个质心,决策边界是连接两质心中点的垂直线。

绘制时需要计算中点坐标、斜率(垂直于连接线)并求出该直线与屏幕可视矩形的交点,然后用 HPLOT 在两个交点之间绘制线段。代码需要处理斜率为无穷大的垂直线情形,以及线与矩形边界的四条边分别求交并判断是否在边界范围内。作者利用一个小数组 P% 保存中点与交点信息,并用 NX 计数交点个数,当交点为两个时绘制线段。该过程虽然繁琐,但在最终视觉呈现上非常直观,尤其适合教学演示聚类的决策边界如何随质心移动而变化。 在资源受限环境下,若要提升聚类质量与稳定性,可以考虑若干改进方向。首先,多次随机重启并选择最低组内平方误差的结果能够缓解 K-means 容易陷入局部最优的问题。

其次,当数据近似高斯分布时,采用基于期望最大化的高斯混合模型(GMM)会带来更强的表达能力。EM 框架通过软分配概率替代硬分配,可以估计每个簇的均值和协方差矩阵,从而在簇形状和方差不等时表现更好。不过在 Apple ][+ 上实现 EM 会增加计算和内存负担,例如需要对协方差矩阵求逆与计算指数函数,这在 APPLESOFT BASIC 中既慢又易出精度问题,需要精心简化与优化才能可行。 另一个实际优化点是用整型近似或表查方式替代昂贵的浮点运算。由于 APPLESOFT BASIC 的浮点处理开销大,可将坐标放大为整数并只在必要时做浮点除法。随机数生成和断点控制也可以通过简单的线性同余发生器在整数域内实现以提高可控性。

图形绘制方面,可以限制刷新频率,只在关键迭代或质心显著移动时更新屏幕,以避免因为频繁绘制而拖慢算法运行。 实现机器学习算法于复古硬件的意义不仅在于完成一个工程挑战,更在于教育与理解。将抽象的迭代过程以可视化方式呈现,可以让学习者直观感受为什么质心会移动、为什么算法可能停在局部最优、异常值如何影响分类边界。这种手工实现的过程促使开发者亲自处理随机初始化、收敛判定与数值稳定性等问题,是现代高层库封装所掩盖的宝贵经验。 作者在社交平台上分享这段 Apple ][+ 上的 K-means 实验,在线社区反响不一。在 Hacker News 上得到了有思考性和建设性的反馈,指出了若干实现细节与改进建议;而在面向复古电脑兴趣的小众社群中,传播效果受限于群组审核规则与受众差异。

无论如何,这类跨时代的实验能够将复古硬件爱好者和机器学习研究者连接起来,激发出新的交流与灵感。 总的来说,将 K-means 移植到 Apple ][+ 并用 APPLESOFT BASIC 实现,不只是一次对代码技巧的锻炼,也是一堂实践机器学习基本原理的公开课。对于希望深入算法细节的读者,建议尝试实现更多改进:增加多次重启机制、扩展到 k>2 的决策边界绘制、实现基于矩阵的协方差估计以准备 EM 的简化实现,或将部分计算预先离线完成以减轻主机实时负担。无论最终选择何种路径,这样的复古实践都能帮助开发者在受限环境中培养出更强的工程直觉和算法理解。 。