1. Overview of Harmony algorithm
Harmony 可以将多个单细胞RNA测序数据集整合到同一空间中，消除不同数据集之间的技术差异，并更好地比较和分析细胞之间的差异和相似性。
在应用Harmony之前，首先通过主成分分析（Principal Components Analysis，PCA）将细胞嵌入到一个降维后的空间中。然后，Harmony接受在这个降维空间中的细胞坐标，并运行一个迭代算法来调整数据集中特定效应。
具体来说，这段话描述了Harmony的步骤：
A. 使用模糊聚类将每个细胞分配到多个簇，同时通过罚项确保每个簇中数据集的多样性最大化。
B. 为每个簇计算全局质心以及每个数据集在每个簇中的特定质心。
C. 在每个簇内，根据质心计算每个数据集的矫正因子。
D. 最后，通过将数据集在步骤A中进行软簇分配的方式，Harmony校正每个细胞with a cell-specific factor：根据数据集的矫正因子的线性组合加权。Harmony重复执行A到D的步骤直到收敛。簇分配和数据集之间的相互依赖性在每一轮中都会减弱。
2. Performance on both integration and accuracy
In order to quantify integration and accuracy of this embedding we defined an objective metric:
the Local Inverse Simpson's Index (LISI, online methods) in the local neighborhood of each cell.
评估Harmony方法在整合性（数据集混合）和准确性（细胞类型不混合）方面的表现。
评估整合性(mixing of datasets)，他们使用了 “integration LISI” (iLISI），它定义了邻域中数据集的有效数量。只有一个数据集表示的邻域具有iLISI值为1，而由两个数据集中相等数量的细胞组成的邻域具有iLISI值为2。需要注意的是，即使在理想的混合情况下，如果数据集具有不同数量的细胞，iLISI也会小于2。
评估准确性(no mixing of cell types)，他们使用了 “cell-type LISI”(cLISI），这是同样的数学度量，但应用于细胞类型而不是数据集标签上。准确的整合应该保持cLISI值为1，反映嵌入中独特细胞类型的分离。
3. Algorithm
1) Input and output
The Harmony algorithm inputs a PCA embedding (Z) of cells, along with their batch assignments (ϕ), and returns a batch corrected embedding (Z^).
2) Maximum Diversity Clustering
对原始的软K均值聚类目标函数进行了修改，增加了一个正则化项，旨在促使聚类结果中的批次之间具有更大的多样性。
批次之间具有更大的多样性， namely, 聚类结果中不同批次的数据点分布在不同的聚类簇中，并且每个聚类簇包含来自不同批次的数据点。
3) Entropy regularization for Soft K-means
Entropy regularization for Soft K-means是对软K均值聚类进行的一种熵（Entropy）正则化。
在软K均值聚类中，每个数据点都被分配到每个聚类簇的隶属度（membership degree）上。这些隶属度通常是基于数据点与聚类中心之间的距离计算得到的。软K均值聚类的目标是通过最小化每个数据点与聚类中心的距离的加权平方和来确定最佳的聚类。
然而，为了进一步促使每个数据点在聚类结果中具有较大的多样性，可以引入熵正则化。熵是对不确定性或信息量的度量，而将熵正则化应用于软K均值聚类的隶属度可以使分配更加均匀。
具体而言，通过在目标函数中添加一个熵的惩罚项，并结合与隶属度相关的概率分布，可以增加隶属度的分散性，从而增强聚类结果的多样性。这将导致数据点在聚类中更均匀地分布，而不是集中在特定的聚类簇中。
总之，通过引入熵正则化项，软K均值聚类的目标是同时考虑数据点与聚类簇之间的距离和隶属度的均衡分布。
4) Objective Function for Maximum Diversity Clustering
For each batch variable, we add a new parameter θ. θ decides the degree of penalty for dependence between batch membership and cluster assignment. When ∀fθ=0, the problem reverts back to (2), with no penalty on dependence. As θ increases, the objective function favors more independence between batch f and cluster assignment. As θ approaches infinity, it will yield a degenerate solution. In this case, each cluster has an equivalent distribution across batch f. However, the distances between cells and centroids may be large. Finally, σ is added to this term for notational convenience in the gradient calculations.
"Objective Function for Maximum Diversity Clustering"是用于最大多样性聚类的目标函数。该目标函数基于之前的部分构建，除了软分配正则化外，还对具有低批次多样性的聚类进行惩罚。
对于每个批次变量，我们引入了一个新的参数θ。θ决定了批次成员和聚类分配之间依赖关系的惩罚程度。
当对所有批次变量都设置θ=0（∀fθ=0）时，问题退化为之前的目标函数（记为(2)），在聚类和批次之间没有依赖关系的惩罚。实际上，这意味着不考虑批次和聚类之间的独立性。
随着θ值的增加，目标函数更倾向于批次变量和聚类分配之间的独立性。这意味着聚类解决方案将被鼓励具有更小的批次变量和聚类分配之间的相关性或依赖性。目的是促进多样性，避免聚类解决方案对特定批次存在偏差。
当θ趋近于无穷大时，可能会出现退化解。在这种情况下，每个聚类将在批次变量上具有相同的分布。然而，这也可能导致细胞与聚类中心之间的距离较大，表示聚类可能不太紧密或定义不明确。
5）当向量进行L2归一化时，平方欧氏距离等于余弦距离
a)) 对Z和Y向量进行L2归一化，它们的平方欧氏距离等于余弦距离
We found that this clustering works best when we compute the cosine, rather than Euclidean distance, between Z and Y. Haghverdi et al showed that the squared Euclidean distance is equivalent to cosine distance when the vectors are L2 normalized. Therefore, assuming that all Zi and Yk have a unity L2 norm, the squared Euclidean distance above can be re-written as a dot product.
在进行聚类时，通过计算Z和Y之间的余弦距离而不是欧氏距离，可以获得更好的聚类效果。Haghverdi等人在研究中表明，当向量进行L2归一化时，平方欧氏距离等效于余弦距离。因此，假设所有的Zi和Yk都具有单位的L2范数（即归一化），上述的平方欧氏距离可以重新表示为点积。
这里的L2范数是指向量的欧氏长度，归一化即将向量除以其L2范数，使其长度变为1。通过对Z和Y向量进行L2归一化，可以将它们的平方欧氏距离转化为余弦距离的形式。
通过将平方欧氏距离转化为点积形式，可以简化计算，并且利用点积运算的性质，可以更高效地处理向量之间的相似性比较。
b)) 举个例子：
当向量进行L2归一化时，平方欧氏距离可以等效于余弦距离。具体的计算过程如下，假设有两个向量A和B：
1. 归一化向量A和B，使它们的长度变为1。通过将向量除以其L2范数，即可进行L2归一化。
归一化后的向量A' = A / ∥A∥₂，在归一化后的向量B' = B / ∥B∥₂。
2. 计算归一化后的向量A'和B'的余弦相似度。余弦相似度可以通过计算两个向量的点积来得到。
余弦相似度 = A' · B' = ∑(A'i * B'i)，其中∑表示求和运算，A'i表示向量A'的第i个元素，B'i表示向量B'的第i个元素。
3. 将余弦相似度转换为余弦距离。余弦距离可以通过以下公式计算：
余弦距离 = 1 - 余弦相似度。
通过这个计算过程，我们可以看到当向量进行L2归一化后，平方欧氏距离可以等效为余弦距离。
举个例子，假设有两个向量A=[2, 3, 4]和B=[1, 2, 3]：
1. 归一化向量A和B：
A' = [2/∥A∥₂, 3/∥A∥₂, 4/∥A∥₂]，B' = [1/∥B∥₂, 2/∥B∥₂, 3/∥B∥₂]。
其中∥A∥₂ = √(2² + 3² + 4²) ≈ 5.385，∥B∥₂ = √(1² + 2² + 3²) ≈ 3.742。
A' ≈ [0.371, 0.557, 0.742]，B' ≈ [0.267, 0.534, 0.801]。
2. 计算余弦相似度：
余弦相似度 = A' · B' = (0.371 * 0.267) + (0.557 * 0.534) + (0.742 * 0.801) ≈ 0.979。
3. 计算余弦距离：
余弦距离 = 1 - 余弦相似度 = 1 - 0.979 = 0.021。
因此，通过L2归一化后，向量A和B之间的平方欧氏距离等于余弦距离，即0.021。
4. 一些概念
1）欧式距离（Euclidean distance）
欧式距离（Euclidean distance）是用于衡量两个点之间的直线距离（直线段长度）的一种度量方式。它基于欧几里德空间中的几何概念，适用于多维空间中的点或向量之间的距离计算。
假设有两个点 A 和 B，它们的坐标分别为 (x1, y1, z1, …) 和 (x2, y2, z2, …)。欧式距离可以通过以下方式计算：
对应坐标相减得到差值：(x1 - x2, y1 - y2, z1 - z2, …)
每个差值进行平方：(x1 - x2)^2, (y1 - y2)^2, (z1 - z2)^2, …
将所有平方项相加得到总和：sum((x1 - x2)^2, (y1 - y2)^2, (z1 - z2)^2, …)
对总和取平方根得到欧式距离。
欧式距离 = sqrt(sum((x1 - x2)^2, (y1 - y2)^2, (z1 - z2)^2, …))
其中，sqrt 表示平方根运算，^2 表示平方运算。
欧式距离的计算结果是一个非负实数，代表了点 A 和 B 之间的直线距离。
2）低维最近邻结构的保留问题
欧式距离的计算通常是在高维空间中进行的，而不是在转换到低维表示之后计算。
当涉及到降维技术（例如主成分分析）时，首先将数据从高维空间降到低维空间。在降维过程中，利用某种技术将原始数据投影到一个较低维度的空间，通常选择保留最大方差的维度。
转换后的低维表示（例如主成分）可以用于可视化、数据压缩或其他分析目的。但在进行欧式距离计算时，通常是在原始高维空间中计算两个数据点之间的直线距离。
这意味着，尽管数据降维到低维空间进行了可视化或其他用途，但在衡量两个数据点之间的相似性或距离时，仍然使用高维空间中的欧式距离进行计算。这是因为在低维空间中进行距离计算可能无法准确地捕捉到原始数据在高维空间中的关系。
当使用欧式距离作为相似度度量时，存在一个问题，即在将高维数据转换为低维表示（例如主成分分析）时，原始数据的最近邻关系可能不再被保持。也就是，欧式距离作为常见的相似度度量时所引发的低维最近邻结构的保留问题。
具体来说，欧式距离在衡量两个点之间的相似性时会受到各个特征之间的尺度影响。如果某些特征具有较大的尺度差异，那么在计算欧式距离时，这些具有较大尺度差异的特征会主导距离的计算。这可能导致在低维表示中，原始数据的最近邻关系发生变化。
换言之，欧式距离容易受到特征尺度的支配，而忽略了数据之间的方向、线性关系以及数据分布的非线性特性。当在保留最近邻结构时，将高维数据映射到低维空间时，欧式距离可能不能准确捕捉数据之间的相似性，从而可能导致最近邻关系的改变。
为了应对这个问题，人们会使用其他的相似度度量方法，例如余弦相似度或相关性，它们在一定程度上可以捕捉到数据在低维表示下的最近邻关系，并更好地处理特征尺度的差异。
3）余弦相似度（Cosine Similarity）
余弦相似度（Cosine Similarity）是一种用于衡量两个向量之间相似性的度量方法，常用于文本挖掘、信息检索和推荐系统中。
在余弦相似度中，向量之间的相似性是通过计算它们之间的夹角来测量的，而不仅仅依赖于向量的长度或尺度。具体而言，余弦相似度衡量的是两个向量在多维空间中的方向相似程度。
给定两个向量A和B，它们的余弦相似度可以通过以下公式计算：
cosine_sim(A, B) = (A·B) / (||A|| * ||B||)
其中，A·B表示向量A和向量B的内积（点积），||A||和||B||分别表示向量A和向量B的范数（即向量的长度或模）。
余弦相似度的取值范围在[-1, 1]之间。当余弦相似度接近1时，表示两个向量的方向非常相似；而当余弦相似度接近-1时，表示两个向量的方向非常不相似；当余弦相似度接近0时，表示两个向量之间没有明显的相关性。
4）软K均值聚类（Soft K-means clustering）
软K均值聚类（Soft K-means clustering）是一种基于距离和相似性的聚类算法，它与传统的K均值算法类似，但允许数据点关联到多个聚类中心。
传统的K均值聚类将每个数据点分配给最近的聚类中心，并根据平均值更新聚类中心的位置。这种硬分配的方法在一些场景下可能不适用，因为它无法处理模糊或不确定的数据点分类。
与此不同，软K均值聚类引入了“隶属度”（membership degree）的概念，它表示每个数据点属于每个聚类的程度。隶属度是一个介于0和1之间的值，表示数据点与聚类中心的相似性度量，值越大表示相似性越高。
软K均值聚类的关键步骤如下：
初始化聚类中心：选择初始的聚类中心位置。
计算隶属度：对于每个数据点，计算它属于每个聚类的隶属度。隶属度可以使用高斯核函数、指数核函数等进行计算。
更新聚类中心：根据每个数据点的隶属度，更新聚类中心的位置。隶属度越高的数据点对聚类中心的贡献越大。
重复迭代：重复执行步骤2和步骤3，直到达到停止条件（例如，最大迭代次数或者聚类中心位置变化很小）。
软K均值聚类的结果是每个数据点到每个聚类的隶属度，而不是硬分配的分类结果。这样的结果可以用于实现模糊聚类，以及处理数据点的模糊或不确定归属问题。
5）L2 normalized
L2归一化是指将向量除以其L2范数，使其长度变为1。L2范数（也称为欧氏距离或向量的2-范数）是一种衡量向量长度的方法，其计算方式是将向量中各个元素的平方和求平方根。
通过L2归一化，可以将向量转换为单位向量，也就是其长度变为1。这种归一化操作使得向量在数值上更稳定，可以更好地比较它们之间的相似性或距离。
例如，假设有一个向量v=[2, 3, 4]，它的L2范数为∥v∥₂ = √(2² + 3² + 4²) = √(29) ≈ 5.385。通过L2归一化，将向量除以其L2范数得到v' = [2/5.385, 3/5.385, 4/5.385] ≈ [0.371, 0.557, 0.742]，使得v'的长度为1。
L2归一化可以用于对向量进行标准化或正则化的处理，以便更好地处理不同尺度、不同长度的向量。在机器学习、数据挖掘和计算机视觉等领域，L2归一化常用于特征向量的预处理，以提高模型的鲁棒性和性能。
参考：
1）https://github.com/immunogenomics/harmony
2）Published in final edited form as: Nat Methods. 2019 December ; 16(12): 1289–1296. doi:10.1038/s41592-019-0619-0. Title: Fast, sensitive, and accurate integration of single cell data with Harmony
