GAUFS：用于聚类(Clustering)的无监督特征选择(Unsupervised Feature Selection, UFS)的遗传算法(Genetic Algorithm, GA)

《Knowledge-Based Systems》：GAUFS: Genetic Algorithm for Unsupervised Feature Selection for clustering

　　

研究人员提出一种名为GAUFS（Genetic Algorithm for Unsupervised Feature Selection for clustering）的Wrapper方法，可联合选择特征子集并估计簇数(number of clusters, k)。该方法面向真正的无监督场景：无类别标签且无需预设k值。GAUFS将k值与特征选择二进制向量共同编码于染色体(chromosome)中，采用确定性层次聚类(Hierarchical Clustering, 如Ward linkage)与Silhouette分数作为适应度函数(fitness function)评估候选解，并通过Hall of Fame(HoF)积累进化历史以计算特征权重(feature weighting)，进而依据特征权重序列与Silhouette随特征数变化的联合准则自动确定最优特征子集大小及对应k。研究在30个合成数据集与30个真实数据集上对比8种主流算法（包括Laplacian Score(LS)、SPEC、Infinite Feature Selection(INFFS/INFFS20)、FMIUFS、RNE、FSSEM-k及进化多目标算法ELSA），以Adjusted Mutual Information(AMI)为外部评价指标。结果表明GAUFS在合成数据上近完美复现真实簇结构，在真实数据上整体优于对比方法，并能输出紧凑特征子集与合理的k估计值，公开代码及两种合成数据生成器可供复现。

GAUFS：面向聚类无监督特征选择的遗传算法——论文解读

《Knowledge-Based Systems》刊载的GAUFS（Genetic Algorithm for Unsupervised Feature Selection for clustering）一文针对真正无监督聚类场景下面临的两大难题展开研究：现有无监督特征选择(Unsupervised Feature Selection, UFS)方法大多假设簇数k已知或依赖带标签真值(Ground Truth)计算外部聚类有效性指标，违背严格无监督设定；且特征选择与簇数估计相互耦合，固定k会误导特征子集评价。为此，研究人员提出GAUFS——一种基于遗传算法(Genetic Algorithm, GA)的Wrapper式无监督特征选择方法，联合优化特征子集与簇数k，完全依靠内部聚类有效性指标(Internal Cluster Validity Index, CVI，如Silhouette Index)驱动评价，无需任何标签信息。实验证明GAUFS在60个基准数据集上优于8种代表性对比算法，并能同时给出精简特征子集与自适应的k估计。

关键技术方法：

研究人员选用确定性Ward联结层次聚类(Agglomerative Hierarchical Clustering with Ward's linkage)替代随机初始化K-means以保证评估稳定性；设计混合编码染色体——首基因为整数k∈[k_min, k_max]，其余N位为二进制特征选择向量；以Silhouette分数为适应度函数；引入Hall of Fame(HoF)记录历代高适应度个体及其出现频次，据此计算各特征权重(score = max fitness × frequency，取前min(2N, M)个并按出现加权聚合多轮GA运行结果)；按特征权重降序逐步扩充子集，对每个子集在给定范围内扫描k取最大化Silhouette值得k_t，构造归一化后的Silhouette曲线Ψ_silhouette(θ_t)与权重阈值曲线Ψ_weight(θ_t)，二者平均得Φ_average(i)，计算修正差分δ?_i= δ_i/ (1 + N/eⁱ)抑制低维跳变，取argmax δ?_i确定最终特征数i?及对应子集S_t?与k_t?；并提供δ?曲线辅助人工折衷选择。基准数据含30个合成集(Spheres/Corners/AC生成器加哑变量dummy variables)及30个UCI/KEEL/Skfeature真实集，对比LS、SPEC、INFFS、INFFS20、FMIUFS、RNE、FSSEM-k及ELSA，以AMI(Adjusted Mutual Information)外部评价，辅以贝叶斯符号秩检验(Bayesian Signed-Rank Test, ROPE=0.01/0.001)与贝叶斯Bradley–Terry(Bradley–Terry, BBT)排序。

研究结果：

3.1 Data description

研究人员使用30个可控合成数据集（Spheres、Corners及AC生成器，含不同半径判定法RP1/RP2及非信息哑变量）与30个多领域真实数据集描述数据特性，Corners生成器保证任意真特征子投影不能分离簇以排除低维偶然可分性干扰评价。

3.2 Comparison methods

选定8种基准方法涵盖Filter（LS、SPEC、INFFS、INFFS20、FMIUFS、RNE）与Wrapper（FSSEM-k基于EM混合模型顺序向前搜索并内估k，ELSA为多目标进化UFS返回Pareto前沿），RNE子集大小对齐GAUFS所选特征数，FSSEM-k择优ML/TR变体（依赖外部AMI，非严格无监督）。

3.3 Experimental setup

GAUFS依特征维数设代数为150(≤100维)或300(>100维)，种群1500或7000；过滤法取GAUFS选出特征数m之Top-m，RNE直接取大小为m子集，过滤法k由对应子集上最大化Silhouette得；ELSA从Pareto前沿按最接近理想点(最大AMI,最小特征数)选单解（依赖外部AMI做后选择）；三次独立运行取均值时间。

3.4 Statistical test

为克服成对比较局限，研究人员采用贝叶斯符号秩检验估GAUFS优于各基线之后验概率P(>)，及BBT模型获全局排序——GAUFS后验均秩1.007(95%CI[1,1])，为首位概率0.987。

3.5 Results

GAUFS在合成数据集上AMI接近1.000且k估计吻合，显著优于各基线（P(>)≈1.000除FSSEM-k为0.997、LS为0.989）；真实数据集上GAUFS综合AMI仍居首，贝叶斯检验对ELSA胜率P(>)=0.74，对其余方法P(>)≥0.897；ELSA经有利后选择方可比，且常选更大特征子集。GAUFS给出更紧凑解。合成数据优因几何凸簇匹配Ward+Silhouette假设，真实数据受非凸/重叠/属性类型影响性能略降但仍领先。BBT确认GAUFS排名第一，中间组含ELSA、FMIUFS、SPEC、FSSEM-k，底部为RNE、LS、INFFS20、INFFS。

3.6 Impact of prior knowledge in the determination of the number of clusters

默认搜索带[k_min, k_max]=[2,25]；缩窄范围可提升AMI（避免Silhouette倾向过简划分），如Mfeat-pix限[7,17]优于[2,25]；即便K已知也推荐带而非单值固定，因最优k依赖于所选特征空间（例Ionosphere数据k=5比K=2获更高AMI），估计k≠K不代表方法失效而是反映数据几何诱导合并/分裂。

3.7 Ablation study

对比GAUFS-VanillaGA（直接取HoF最高适应度染色体特征与k，无特征加权与子集分析）与GAUFS-KBeforehand（先用全特征定k再锁死k搜索）——前者因Silhouette偏好极少特征致重要特征漏选，后者因k与特征解耦在合成数据明显降AMI，证实HoF加权分析及联合优化k与特征子集均为GAUFS必要组件。

讨论与结论翻译：

研究人员指出严格无监督聚类特征选择须联合估计特征子集与簇数，预设k会引入偏差。GAUFS作为Wrapper方法通过GA探索解空间并以内部CVI评估，在60数据集上较8种SOTA方法具优势，且输出显式特征子集与k估计。附带Spheres与Corners合成生成器供可重复研究。未来工作将探索多内部指标融合或模型选择罚项定k、替换密度或谱聚类以适应非凸结构、处理离散/类别变量及引入冗余惩罚(redundancy penalty)机制；当前框架未显式抑制高相关特征，后续可基于互信息或子集内相关加惩罚。论文强调需建立公开Wrapper式UFS基准仓库与标准评估协议以提升领域可复现性。