Labs 5–7：集群、Cholesky 与 Spark 机器学习

1. 从镜像到分布式查询：系统图景

课程原文：Docker 使用操作系统级虚拟化，把应用及依赖装入容器。镜像包含代码、库、工具和依赖；容器以轻量方式运行应用。Lab 5 使用 Docker 部署 Hadoop、Spark 与 Drill，并以 Docker Swarm 的 overlay 网络连接多个 Docker daemon 主机。

• Image：只读分层模板。一个镜像可以创建多个容器。
• Container：镜像的运行实例，具有独立进程视图与可写层。
• Swarm manager：初始化 Swarm、签发 join token、维护节点成员关系。
• Worker：使用 manager 给出的 token 与地址加入 Swarm。
• Overlay network：让不同 Docker 主机上的容器进入同一逻辑二层网络。

可验证推导：“容器能启动”只说明本机运行时可用；“容器能按名称访问另一主机的容器”还依赖 Swarm 成员关系、overlay 网络和网络端口。排障必须分层观察。

1. 用 docker ps -a 检查容器状态。
2. 在 manager 用 docker node ls 检查 Swarm 节点。
3. 用 docker network ls 检查 hadoop-net。
4. 在容器内部测试名称解析与 ping。
5. 最后检查应用进程、端口和日志。

2. Lab 5 启动顺序与观察点

课程原文：manager 与 worker 必须先能互相 ping。manager 初始化 Swarm 后创建可附加的 hadoop-net；worker 使用生成的 token 加入；随后启动 Hadoop 容器、Hadoop daemon、ZooKeeper 与 Drillbit。

Manager

docker system prune
master/init_swarm.sh
master/init_network.sh
docker node ls
docker network ls

export WORKER_NUMBER=N
master/start.sh
master/start_hadoop.sh
jps
./run-wordcount.sh

每个 worker

docker system prune
worker/join_swarm.sh <JOIN_TOKEN> <MANAGER_IP>

export WORKER_NUMBER=N
export WORKER_ID=X
worker/start.sh
docker ps -a

考试陷阱：N 表示 worker 总数，X 表示当前 worker 的编号。源材料没有规定任意集群都使用同一个具体数值。

风险提示：docker system prune 会删除未使用的 Docker 对象。课程步骤包含该命令，但真实环境中应先检查待删除对象；不要把清理命令当作无副作用的“重启”。

3. Hadoop 四层角色

课程原文：Lab 5 在 master 容器启动 NameNode、DataNode、ResourceManager 与 NodeManager。课程的 Hadoop 材料进一步区分 HDFS、YARN 与 MapReduce。

hdfs dfs -mkdir /input
hdfs dfs -put local.csv /input
hdfs dfs -ls /input
hdfs dfs -cat /input/local.csv
hdfs dfs -get /output ./local_output

考试陷阱：HDFS 路径不是本机路径。hdfs dfs -put 从本机复制到 HDFS，-get 的方向相反。Hadoop Streaming 的输出目录必须事先不存在。

hadoop jar "$HADOOP_HOME/share/hadoop/tools/lib/hadoop-streaming-3.5.0.jar" \
  -files mapper.py,reducer.py \
  -input /user/hadoop/input \
  -output /user/hadoop/output \
  -mapper mapper.py \
  -reducer reducer.py

4. Drill：无须预先固定表模式的分布式 SQL

课程原文：Apache Drill 是面向大数据探索的低延迟分布式 SQL 查询引擎，可查询 JSON、Parquet、CSV 与 Avro 等数据。分布式模式中，Drillbit 是查询执行服务，ZooKeeper 用于协调与服务发现。

./build/docker-build-drill-image.sh
drill/start_zookeeper.sh
drill/start_drillbit.sh 1

# 同一主机再启动一个 Drillbit 时，宿主机端口必须不同
DRILL_HTTP_PORT=8048 DRILL_USER_PORT=31020 drill/start_drillbit.sh 2

docker exec hadoop-drillbit-1 /usr/local/drill/bin/sqlline \
  -u jdbc:drill:drillbit=localhost \
  --outputformat=tsv --silent=true \
  -e 'SELECT * FROM sys.drillbits;'

课程原文：sys.drillbits 的正常示例中，各 Drillbit 状态为 ONLINE，且恰有一个节点的 current 为 true，表示当前连接的 Drillbit；它不表示集群 leader。上面的命令在容器 hadoop-drillbit-1 内以 jdbc:drill:drillbit=localhost 建立直连，因此该示例的运行实例就是 hadoop-drillbit-1；换用 ZooKeeper 连接串时，应以查询返回的 current=true 行识别实际实例。

CSV 的显式字段解释

SELECT *
FROM (
  SELECT
    columns[0] AS name,
    columns[1] AS id,
    CAST(columns[2] AS INT) AS grade
  FROM dfs.`/path/grades.csv`
)
WHERE name = 'Tad Wyze'
ORDER BY grade DESC;

考试陷阱：Drill 能进行 schema-on-read，不等于所有字段自动具有正确类型。文本 CSV 的 columns[n] 常需显式 CAST，否则数值排序或聚合可能按字符串语义执行。

5. 三道航班 Drill 题：仓库中的实际 SQL

仓库事实：labs/l5/src/lab5_drill.sql 查询 HDFS 上的 dfs.root.`/user/hadoopuser/lab5/flights_parquet`。实际列名是 UniqueCarrier、DepDelay、Origin 与 WeatherDelay；第一题按正的出发延误次数排名，第二题按天气延误分钟总和排名，第三题求各承运人的最大出发延误。

-- 1：正的出发延误次数最多的承运人（仓库保留前 10）
SELECT UniqueCarrier, COUNT(*) AS late_count
FROM dfs.root.`/user/hadoopuser/lab5/flights_parquet`
WHERE DepDelay > 0
GROUP BY UniqueCarrier
ORDER BY late_count DESC
LIMIT 10;

-- 2：天气延误分钟总和最大的三个出发地
SELECT Origin, SUM(WeatherDelay) AS weather_delay
FROM dfs.root.`/user/hadoopuser/lab5/flights_parquet`
WHERE WeatherDelay > 0
GROUP BY Origin
ORDER BY weather_delay DESC
LIMIT 3;

-- 3：每个承运人的最大出发延误
SELECT UniqueCarrier, MAX(DepDelay) AS max_dep_delay
FROM dfs.root.`/user/hadoopuser/lab5/flights_parquet`
GROUP BY UniqueCarrier
ORDER BY UniqueCarrier;

仓库结果：第一题首位是 DL（8,064,705 次）；第二题前三名为 ATL、DFW、ORD，对应天气延误总和 2,875,797、2,420,428、1,981,125。注意“最常晚点”也可被解释为晚点比例，但本仓库明确实现的是 DepDelay > 0 的次数。

6. 故障定位清单

• worker 无法加入：先测试 manager 的 TCP 2377。课程材料建议允许 2377，overlay 还需要 7946 与 4789。
• Drillbit 退出：运行 docker ps --filter name=hadoop-drillbit 和 docker logs hadoop-drillbit-1。
• Drill 内存不足：课程示例用 DRILL_HEAP=512M DRILL_MAX_DIRECT_MEMORY=1G 降低限制后启动。
• ZooKeeper 异常：运行 docker ps --filter name=hadoop-zookeeper 与相应 docker logs。

可验证推导：宿主机端口映射冲突与容器内部服务端口不是同一个问题。同一主机运行多个 Drillbit 时，应改宿主机端口；不同主机可复用同一宿主机端口号。

1. 为什么分解，不直接求逆

课程原文：线性系统 Ax = b 通常不通过显式计算 A⁻¹ 求解。先做分解的代价是 O(n³)；同一 A 对多个右端项求解时，每次三角求解只需 O(n²)。

若 A = LU，则先解 Ly = b（前代），再解 Ux = y（回代）。Doolittle 约定 L 的对角线全为 1，从而固定 LU 缩放自由度。

2. SPD 的判定与反例

定义：实矩阵 A 是对称正定矩阵（symmetric positive definite, SPD），当且仅当：

课程原文：对实对称矩阵，以下两种方法可检查正定性：

1. 全部特征值严格大于 0；
2. Sylvester 判据：从左上角开始的所有顺序主子式严格大于 0。

可验证推导：若 A = LL^T 且 L 可逆，则对 x ≠ 0，

因此正对角的非奇异 Cholesky 因子直接证明 A 正定。

考试陷阱：

• A = A^T 只证明对称，不能证明正定。例如 diag(1, -1) 对称但不定。
• 所有对角元素为正也不够。例如 [[1,2],[2,1]] 的行列式为 −3，不正定。
• A^TA 总是半正定；只有当 A 满列秩时才正定。

3. 从 Doolittle 到 LDLᵀ，再到 Cholesky

课程原文与可验证推导：以下等式逐步给出 Cholesky 的来源。

1. 从 Doolittle 分解开始：A = LU，其中 L 为单位下三角，U 为上三角。
2. 因为 A 对称，LU = A = A^T = U^TL^T。
3. 把 U 的对角抽出：U = DÛ，其中 D = diag(U₁₁,…,U_nn)，Û 为单位上三角。
4. 于是 LDÛ = Û^TDL^T。Doolittle 分解的唯一性给出 L = Û^T。
5. 因此 A = LDL^T。
6. 若 A 为正定，则每个枢轴 D_ii > 0，实数平方根 D^1/2 存在。
7. 令 C = LD^1/2，得到 A = CC^T。通常把 C 重新记作 L。

考试陷阱：LDL^T 对某些非正定对称矩阵仍可能存在；从 D 取实平方根并得到标准 Cholesky 时才使用“正定”。

4. 元素公式：必须会从矩阵乘法还原

由 A = LL^T，对任意 i,j：

先算第 j 列对角元，再算其下方元素：

def cholesky(A):
    n = len(A)
    L = [[0.0] * n for _ in range(n)]
    for j in range(n):
        diagonal_residual = A[j][j] - sum(L[j][k] ** 2 for k in range(j))
        if diagonal_residual <= 0:
            raise ValueError("matrix is not SPD")
        L[j][j] = diagonal_residual ** 0.5
        for i in range(j + 1, n):
            cross = sum(L[i][k] * L[j][k] for k in range(j))
            L[i][j] = (A[i][j] - cross) / L[j][j]
    return L

可验证推导：循环不变量是：开始第 j 列前，L 的前 j−1 列已经满足对应的 LL^T 元素等式。对角残差必须严格大于 0。

5. 3×3 完整手算

课程原文：

1. l₁₁ = √25 = 5
2. l₂₁ = 15/5 = 3，l₃₁ = −5/5 = −1
3. l₂₂ = √(18−3²) = 3
4. l₃₂ = (0−(−1)(3))/3 = 1
5. l₃₃ = √(11−(−1)²−1²) = 3

验算：第 (2,3) 项为 3(−1)+3(1)+0(3)=0；第 (3,3) 项为 (−1)²+1²+3²=11。故 LL^T=A。

同一分解如何解方程

可验证推导：若取 b=[35,33,6]^T，则先解 Ly=b：

1. 5y₁=35 ⇒ y₁=7
2. 3y₁+3y₂=33 ⇒ y₂=4
3. −y₁+y₂+3y₃=6 ⇒ y₃=3

再解 L^Tx=y，得到 x=[1,1,1]^T。直接乘 Ax 可验证结果。

6. 复杂度与适用范围

课程原文：Cholesky 的主导运算量约为一般 LU 的一半。它只计算一个三角因子，并利用对称性省去另一半。

1. Scala：考试所需最小语法

课程原文：Scala 是静态类型、多范式语言，可与 Java 互操作，同时支持面向对象和函数式编程。

val fixed: Int = 10                 // 不可重新赋值
var mutable: String = "Hello"       // 可以重新赋值
mutable = "World"

def add(a: Int, b: Int): Int = a + b
val doubled = List(1, 2, 3).map(_ * 2)
val total = List(1, 2, 3).reduce(_ + _)

case class Point(x: Int, y: Int)
val sameValue = Point(1, 2) == Point(1, 2)  // true

val description = fixed match {
  case 1 => "one"
  case _ => "other"
}

object HelloWorld {
  def main(args: Array[String]): Unit = {
    println("Hello, world!")
  }
}

scalac HelloWorld.scala
scala HelloWorld

2. Spark：driver、RDD 与 DataFrame

课程原文：每个 Spark 应用都有 driver program，driver 运行用户的 main 并组织集群上的并行操作。RDD 是可容错、分区的分布式元素集合；现代 Spark 更强调带 schema 的 DataFrame，并由 Spark SQL 的 Catalyst 优化器处理。

val textFile = spark.sparkContext.textFile("path/to/text.txt")
val wordCounts = textFile
  .flatMap(line => line.split(" "))
  .map(word => (word, 1))
  .reduceByKey(_ + _)

wordCounts.collect().foreach(println)

可验证推导：map 与 flatMap 等 transformation 建立计算血缘；collect 等 action 触发执行。collect 把全部结果拉回 driver，只适用于能装入 driver 内存的结果。

考试陷阱：reduceByKey 在 shuffle 前可做本地合并，通常比 groupByKey 后再求和更节省网络传输。

3. PBMC 数据预处理

课程原文：Lab 7 使用预处理后的 PBMC mRNA 表。数据有 1882 个特征；目标是用 PCA 降维，并用细胞类型标签做分类实验。

spark_df = (
    spark.read
    .options(header="true", inferSchema="true")
    .csv("datasets/PBMC_16k_RNA.csv")
)

spark_df.agg({"KLHL17": "max"}).show()
spark_df.createOrReplaceTempView("data")
spark.sql("SELECT max(KLHL17) FROM data").show()

课程原文：KLHL17 的范围约为 −0.11 到 10，HES4 的范围约为 −1.33 到 9.47。课程答案认为两者范围相近，可以跳过标准化，也可以为了稳妥执行标准化。

可验证推导：仅检查两个特征不足以证明全部 1882 个特征尺度相近。PCA 对尺度敏感；严谨流程应统计所有输入列，或在含义允许时使用 StandardScaler。

from pyspark.ml.feature import VectorAssembler, StandardScaler

feature_cols = [c for c in spark_df.columns if c != "index"]
assembled = VectorAssembler(
    inputCols=feature_cols,
    outputCol="features"
).transform(spark_df)

scaler = StandardScaler(
    inputCol="features",
    outputCol="standardized_features",
    withMean=True,
    withStd=True
)
standardized_df = scaler.fit(assembled).transform(assembled)

未给定：源材料没有完整列清单，也没有确认索引列的精确名称。上例的 "index" 是占位判断，实际执行必须检查 schema 后决定排除列。

4. PCA：目标、公式与课程结果

可验证推导：对中心化数据矩阵 X，协方差矩阵可写为 S = X^TX/(n−1)。第一主成分方向 w₁ 解约束优化：

拉格朗日条件给出 Sw = λw，因此主成分是协方差矩阵按特征值从大到小排列的特征向量。第 j 个解释方差比为 λ_j/Σλ_i。

from pyspark.ml.feature import PCA

pca = PCA(
    k=2,
    inputCol="standardized_features",
    outputCol="pca_features"
)
pca_model = pca.fit(standardized_df)
pca_df = pca_model.transform(standardized_df)
print(pca_model.explainedVariance.toArray())

课程原文：前两个解释方差比分别约为 0.02942326 与 0.01307317，合计约 0.04249643，即 4.25%。课程答案随后写“2% 的方差”；这与前述两个数值之和不一致。复习时应优先按给定数值求和，并指出原文表述冲突。

课程原文：按标签着色的前两个主成分散点图中，同类细胞通常聚集；随机选择两个原始列时，同类细胞更分散。PCA 因而对低维可视化有用。

考试陷阱：低解释方差不等于 PCA “错误”。它只说明二维投影丢失了大部分总方差。分类效果还取决于被丢弃方向是否包含判别信息。

5. 逻辑回归、BFGS 与 L-BFGS

课程原文：Lab 7 把样本分为 type A 与 non-type A，并要求用两个主成分训练逻辑回归。课程计数结果显示 CD4+ T 数量最多（5262），因此它是 type A。训练集与测试集按 70%/30% 划分。

可验证推导：二分类逻辑回归令

• 梯度下降：只用一阶梯度，沿负梯度方向更新。
• Newton：使用 Hessian 的逆，单步信息强，但高维存储和求解昂贵。
• BFGS：通过梯度差和步长更新逆 Hessian 近似，不显式计算真实 Hessian。
• L-BFGS：只保留最近有限次 (s_k,y_k) 历史，降低高维内存成本。

from pyspark.mllib.classification import LogisticRegressionWithLBFGS
from pyspark.mllib.linalg import Vectors as OldVectors
from pyspark.mllib.regression import LabeledPoint

# 前置条件：classified_df 已含数值 label 与 ML Vector 类型的 pca_features
labeled_points = classified_df.select("label", "pca_features").rdd.map(
    lambda row: LabeledPoint(
        float(row["label"]),
        OldVectors.dense(row["pca_features"].toArray())
    )
)

training, test = labeled_points.randomSplit([0.7, 0.3], seed=42)

model = LogisticRegressionWithLBFGS.train(
    training,
    iterations=100,
    numClasses=2
)

prediction_and_label = test.map(
    lambda point: (model.predict(point.features), point.label)
)
test_error = prediction_and_label.filter(
    lambda pair: pair[0] != pair[1]
).count() / float(test.count())

课程原文：一次实验在 100 次迭代后得到 25.59% 测试错误率。课程答案认为二维图上 CD4+ T 与其他类型很接近，并建议加入更多主成分。

未给定：25.59% 不是可复现的固定标准答案。源材料没有给出随机种子、精确预处理、特征组装、正则化参数和数据版本。结果应作为一次实验观测，而不是算法常数。

如何改进并验证

1. 在验证集上选择主成分数 k，不要只比较训练误差。
2. 固定随机种子并报告训练/测试样本量。
3. 标准化特征；只在训练集上拟合 scaler 与 PCA，防止测试信息泄漏。
4. 调节正则化强度与迭代次数，并检查目标函数是否收敛。
5. 类别不平衡时同时报告 precision、recall、F1、ROC-AUC 与混淆矩阵，不能只看 accuracy。
6. 若二维线性边界不足，增加主成分或比较非线性模型。

考试陷阱：先对全数据拟合 PCA、再切训练/测试，会让测试集参与特征空间学习。即使 PCA 不用标签，这仍属于数据泄漏。