3.1.4　基于聚类的填补方法

基于聚类的填补方法是指采用聚类算法处理数据缺失问题的填补方法。聚类算法基于样本间的相似度将数据集划分为若干子集，其中，每个子集通常称为一个簇，簇中样本分布的中心称为聚类中心，也称原型。

基于聚类的填补方法采用聚类算法将不完整数据集划分为不同的簇，并参照聚类中心及簇内完整样本对不完整样本的缺失值进行填补。下面主要从三个方面对该方法进行介绍，即缺失值填补中常见的聚类算法，聚类过程中不完整数据的处理，基于不完整数据聚类的缺失值填补方法。

1.缺失值填补中常见的聚类算法

K均值聚类和FCM是常用于缺失值填补的聚类算法，下面分别介绍两种聚类算法。

（1）K均值聚类算法

K均值聚类算法是一种迭代式聚类算法，该算法将每个样本划到距该样本最近的聚类中心所在的簇中，接着通过簇内样本的均值更新聚类中心，并由此反复迭代直至聚类结束。假设X={x_i|x_i∈^s,i=1,2,…,n}表示样本数量为n，属性数量为s的数据集，其第i个样本为x_i=[x_i1,x_i2,…,x_is]^T(i=1,2,…,n)，基于此数据集的聚类流程如图3-3所示。

图3-3　K均值聚类算法流程图

如图3-3所示，K均值聚类算法首先在数据集X中随机选择K个样本分别作为各簇的聚类中心。随后，采用迭代的方式进行样本聚类，每轮迭代分两步进行。第一步，对于数据集中的n个样本，分别计算其与K个聚类中心的欧式距离，将各样本划入其最近聚类中心所在的簇中；第二步，根据划分结果更新聚类中心，计算划分结束后簇内样本各属性值的均值并以此更新聚类中心。若更新前后聚类中心的变化小于设定的阈值，则结束迭代，并将最后一轮迭代中划分的样本簇作为聚类结果，各簇记为X⁽¹⁾,X⁽²⁾,…,X^(k)。在K均值聚类算法中，样本x_i(i=1,2,…,n)相对于簇X^(k)(k=1,2,…,K)的隶属关系可由式（3-17）所示的隶属函数表示：

式（3-17）中，隶属函数u_ik需满足式（3-18）、式（3-19）中的两个条件：

式（3-18）表明每个样本只能属于一个簇，式（3-19）限定了每个簇均为非空。若样本划分的结果符合上述隶属函数，则称这样的划分为硬划分。

（2）FCM算法

FCM算法可视为K均值聚类算法基于模糊划分的改进算法。模糊划分的概念由Ruspini于1969年首先提出，该划分是相对于硬划分而言的，即所有样本并非完全属于某一个簇，而是以不同程度隶属于各个簇。模糊划分中隶属度u_ik的取值范围由{0，1}扩展到[0,1]区间，从而刻画出样本分属于各簇的程度。对于数据集X中的样本，采用FCM算法对其进行聚类，相应的聚类模型如式（3-20）所示：

式（3-20）中，u_ik为隶属度，表示样本x_i隶属于第k个簇的程度，记U=[u_ik]∈^n×K，称为划分矩阵。v_k为第k个簇的聚类中心，即该簇的原型，v_k∈^s，记V=[v_kj]=[v₁,v₂,…,v_K]^T∈^K×s，称为原型矩阵。z∈(1,∞)是一个模糊化参数，其控制着样本在各簇间的分享程度。当z=1时，FCM算法退化为K均值算法；当z趋近于无穷时，FCM算法将失去划分能力。在实际应用中，可结合数据集自身特征确定z的取值，一个常用的取值是z=2^[7]。为了简便描述，将u_ik∈[0,1]和作为隶属度必须满足的默认条件，后续不再列写。

考虑式（3-20）中关于隶属度u_ik的等式约束条件，采用拉格朗日乘子法，设增广拉格朗日函数如式（3-21）所示：

式（3-21）中，λ=[λ₁,λ₂,…,λ_n]^T为拉格朗日乘子，使FCM聚类过程中的目标函数J达到极小的必要条件如式（3-22）、式（3-23）所示：

对式（3-22）和式（3-23）进行交替迭代式求解，当先后两次迭代中原型矩阵或划分矩阵的改变量小于某一预先设定的阈值时，则迭代停止。以下为算法的具体步骤。

步骤1：设定模糊化参数z，聚类数K和阈值ε，(ε>0)，随机初始化划分矩阵U⁽⁰⁾；

步骤2：当迭代次数为l,l=1,2,…时，基于U^(l-1)使用式（3-22）更新原型矩阵V^(l)；

步骤3：基于V^(l)，使用式（3-23）更新划分矩阵U^(l)；

步骤4：若满足条件∀k,，算法停止，输出划分矩阵U和原型矩阵V；否则l←l+1，返回步骤2。

最终，所得划分矩阵U即聚类结果，原型矩阵V记录了划分结束后各簇的原型。

2.聚类过程中不完整数据的处理

在聚类过程中，针对数据集中的数据缺失问题，目前有4种常用的应对策略^[8]，即完整数据策略（Whole Data Stra_tegy，WDS）、局部距离策略（Partial Distance Stra_tegy，PDS）、优化完整策略（Optimal Completion Stra_tegy，OCS）和最近原型策略（Nearest Prototype Stra_tegy，NPS），以下依次对这4种策略进行详细说明。

（1）完整数据策略

完整数据策略是指将数据集中存在缺失值的样本直接剔除，仅采用完整样本参与聚类。假设数据集X中存在不完整样本，首先将数据集X划分为完整样本集X_co和不完整样本集x_in；然后直接采用标准的聚类算法对X_co进行划分，从而获得由完整样本构成的多个聚类簇；最后对x_in中的样本，分别计算其中样本与各聚类中心的局部距离（见式（3-8）），进而将不完整样本划分到与之最近聚类中心所对应的簇中。此方法虽然易于实施，但聚类过程中忽视了不完整样本中的大量现有信息，往往很难获得理想的聚类精度。

（2）局部距离策略

局部距离策略是一种简单且有效的不完整数据聚类方法，其在聚类迭代过程中仅忽略了不完整样本的缺失属性值。PDS方法采用式（3-8）所示的局部距离代替标准聚类算法中的欧式距离，从而将不完整数据集X划分为K个簇。以FCM算法为例，其相应的聚类模型如式（3-24）所示：

采用拉格朗日乘子法，设增广函数如式（3-25）所示：

式（3-25）中，λ=[λ₁,λ₂,…,λ_n]^T为拉格朗日乘子，则在关于隶属度u_ik的等式约束条件下，基于式（3-1）所定义的数据缺失情况，聚类目标函数j₂达到极小的必要条件如式（3-26）、式（3-27）所示：

PDS方法通过执行式（3-26）和式（3-27）的交替迭代，即可获得各簇原型以及完整样本和不完整样本相对于各簇的隶属度。相比于WDS方法忽略了全部不完整样本，PDS更充分地使用了不完整数据集中所有已知信息，是一种更有效的不完整数据聚类方法。

（3）优化完整策略

优化完整策略是一种关注度较高的不完整数据聚类方法，该方法将缺失值视作变量，在聚类的同时进行缺失值填补。以FCM算法为例，设X_m为数据集X中缺失值构成的集合，其聚类模型如式（3-28）所示：

由式（3-28）可见，缺失值在目标函数J₃中作为变量出现。

采用拉格朗日乘子法，设增广拉格朗日函数如式（3-29）所示：

使聚类目标函数J3达到极小的必要条件如式（3-30）、式（3-31）和式（3-32）所示：

式（3-32）表明，优化完整策略利用样本在各簇的隶属度计算权重，并将各簇原型属性值的加权平均作为填补值，上述加权平均值称为模糊均值。OCS方法执行式（3-30）、式（3-31）和式（3-32）三者的交替迭代，收敛后可同时获得各簇原型、样本隶属度和缺失值的填补结果。

（4）最近原型策略

最近原型策略是对优化完整策略的一种简单修改，其将OCS方法中的式（3-32）修改为如式（3-33）所示的形式：

在迭代过程中，NPS策略采用最近原型的相应属性值来填补缺失值。NPS方法需要执行式（3-30）、式（3-31）和式（3-33）三者的交替迭代，从而在聚类的同时进行缺失值填补。对于K均值聚类算法而言，由于其采用硬划分的方式，每个样本仅被划入一个确定的簇，因此该算法的优化完整策略和最近原型策略实际上是等价的。然而到目前为止，尚无法从理论上对NPS算法的收敛性加以证明，该算法在聚类不完整数据时可能出现不收敛的情况^[9]。

通过上述4种策略能够实现不完整数据的聚类，其中WDS和PDS仅能获得聚类结果，需根据聚类结果进行缺失值填补；OCS和NPS在聚类的同时进行缺失值填补，能够同时得到聚类结果与填补值，但其本质仍是以聚类为目标的不完整数据处理策略，获得的填补结果可能并不精确，因此需对基于聚类结果的缺失值填补方法进一步探讨。

3.基于不完整数据聚类的缺失值填补方法

K均值聚类算法和FCM算法分别采用硬划分和模糊划分进行样本聚类。因此，二者聚类结果的形式存在差异，K均值聚类算法将每个样本划分到唯一确定的簇，而FCM算法则采用划分矩阵记录样本对各簇的隶属度，从而将每个样本以不同的程度划分到各个簇。上述两种形式的聚类结果在缺失值填补中的应用方式也不尽相同，下面对其依次展开讨论。

（1）基于K均值聚类的填补方法

在利用K均值聚类结果进行缺失值填补时，一种简捷且常见的方法是采用不完整样本所在簇的聚类中心对应属性值填补缺失值。若不完整样本中的缺失值较多，则基于该样本现有值所计算的局部距离可靠性较低，可能使得该样本的聚类划分不准确，从而对填补结果的精度产生影响。为此，可采用离群样本检测算法对填补结果进行检验。离群样本是指集群中与其他大部分样本不同的样本，离群点检测算法又称局部异常因子（Local Outlier Factor，LOF）算法，用于检测样本集中的离群样本。假设K均值聚类算法将数据集X中的样本划分为K个簇，记其中的第k个簇为X^(k)，可通过如式（3-34）所示的残差平方和检验该簇中的离群样本：

式中，v_k表示簇X^(k)的聚类中心。当加入某个样本后S^(k)_res显著增大，则说明该样本为离群样本。通常而言，离群样本的属性值明显偏离期望的或常见的属性值^[10]。因此，如果填补后的样本检测为离群样本，则很可能该样本的填补值与真实值偏差较大。

加入离群样本检测的缺失值填补方法是基于K均值聚类算法填补缺失值，并采用式（3-34）检测填补后的样本是否为离群样本，去除离群样本的填补值并对其重新填补。该方法不断迭代直到填补后的样本不再被检测出离群样本。以下为加入离群样本检测的缺失值填补方法流程。

步骤1：设定聚类数K和残差平方和阈值ε(ε>0)，设数据集X中的不完整样本组成的集合为x_in。

步骤2：随机选择K个样本作为初始聚类中心，采用K均值聚类算法将数据集X中的样本划分为K个簇，对于x_i∈x_in，基于所在簇的聚类中心填补缺失值，随后清空x_in。

步骤3：对于簇X^(k)(k=1,2,…,K)，计算其残差平方和S_res^(k)，随后依次删除其中的不完整样本，计算删除后簇内样本的残差平方和S_res^(k)'，若S_res^(k)-S_res^(k)'≥ε，将该样本加入数据集x_in。

步骤4：若x_in不为空，返回步骤2，重新进行聚类填补；否则，填补结束。

此方法在缺失值填补的同时检测填补精度，及时处理精度不高的填补值，从而获得更有效、精度更高的填补结果。

（2）基于模糊C均值聚类的填补方法

在使用FCM算法对不完整数据集X聚类的过程中，采用划分矩阵U记录样本对各簇的隶属度，并采用原型矩阵V记录划分结束后各簇的原型。目前，基于上述两种矩阵填补缺失值的方法主要有3种，包括模糊均值填补法、最近原型填补法和属性投票填补法。其中，模糊均值填补法在簇原型的基础上，根据样本对各簇的隶属度计算原型中现有值的加权平均并将其作为填补结果。优化完整策略采用此方法填补缺失值，计算方式见式（3-32）。最近原型填补法是指使用不完整样本最近原型的相应属性值进行缺失值填补。最近原型策略采用此方法填补缺失值，计算方式见式（3-33）。属性投票填补法是指采用各属性投票的方式确定样本所属的聚类簇，从而根据簇原型的属性值进行缺失值填补^[11]。以下为对不完整数据集X采用属性投票填补法进行缺失值填补的流程。

步骤1：设定模糊化参数z、聚类数K和阈值ε，ε>0。

步骤2：采用FCM算法对数据集X中的样本进行模糊划分，得到划分矩阵U=[u_ik]∈^n×K和原型矩阵V=[v_kj]∈^K×s，n为数据集X中的样本数量，s为数据集X中的属性数量。

步骤3：对于数据集X中的各样本，分别计算其中完整属性值与各簇原型属性值的距离，该距离实际上是基于单个属性所得的局部距离，如式（3-35）所示：

步骤4：对于样本x_i(i=1,2,…,n)的第j(j=1,2,…,s)个属性，基于式（3-35）分别计算该属性值与各簇原型相应属性值的距离，选择距离最近的簇作为该属性的投票意向。

步骤5：统计样本中各属性的投票意向，其中得票最高的簇即该样本基于属性投票的划分结果。

步骤6：根据上述划分结果，采用原型中的现有属性值填补簇内样本的缺失值。

大部分情况下，上述3种基于FCM聚类结果进行缺失值填补的方法所得结果相差并不明显，可结合具体数据集进行选择。

相比于均值填补法、热平台填补法和K最近邻填补法，基于聚类的填补方法更加擅长处理大规模数据集，已广泛应用于工业、生物、医疗等众多领域。其中，基于K均值聚类的填补方法易于实现，时间复杂较低。但实际应用中，很多样本或属性不存在明确的边界，不适合采用硬划分的方式进行聚类，故此类填补方法的应用范围受到一定制约。基于FCM聚类的填补方法虽然计算量较大，但FCM算法提供了样本对于各聚类簇的隶属度，使得此类方法能够应用于更多实践和研究领域。