CDKM：基于K-means聚类的因果分解

CDKM：Causal Decomposition Method Based on K-means Clustering

关键词:  因果发现  因果分解  K-means聚类  因果网络  条件独立性测试  

Key words:  causal discovery  causal decomposition  K-means clustering  causal network  conditional independence test  

摘要:

冗余的条件独立性测试严重影响了因果发现中基于约束方法的效率和准确性。针对这一问题,提出了一种基于K-means聚类的因果分解方法(Causal Decomposition Method Based on K-means Clustering,CDKM)。CDKM利用K-means聚类将原始因果发现问题划分为多个子因果发现问题,然后再将子因果网络合并得到完整的因果网络。CDKM首先利用K-means聚类将原始变量集分割成个簇；其次在每个簇中加入其他簇中相关距离最小的两个节点,得到更新后的个簇；然后在每个簇上进行因果发现,得到各个子因果网络；最后将每一个子因果网络合并得到一个完整的因果网络。CDKM既避免了使用高阶条件独立性测试进行分解,又减少了冗余的条件独立性测试,相比递归型基于约束的方法,CDKM可以将原始变量集任意分割。在8个数据集上的实验结果表明,CDKM可以极大地加速因果发现,降低了时间复杂度,且精准度优于基线模型。

Abstract:

Redundant conditional independence tests have seriously affected the efficiency and accuracy of constraint-based methods in causal discovery. To solve this problem, a causal decomposition method CDKM based on K-means clustering is proposed. CDKM divides the original causal discovery problem into multiple sub-causal discovery problems using K-means clustering, and then merges the sub-causal networks to obtain a complete causal network. Specifically, CDKM first uses K-means clustering to divide the original variable set into clusters, and then adds two nodes with the smallest correlation distance from other clusters to each cluster to obtain updated clusters. After that, it discovers causality in each cluster and obtain various sub-causal networks. Finally, it merges each sub-causal network to obtain a complete causal network. CDKM avoids the decomposition using high-order conditional independence tests and reduces redundant conditional independence tests. Compared with recursive constraint-based methods, CDKM can divide the original variable set into any segments. Experimental results on 8 [ ]datasets show that CDKM can greatly accelerate causal discovery, reduce time complexity, and have better accuracy than baseline models.