PSO-FSPMiner：一种用于挖掘频繁相似模式代表性子集的元启发式方法

《Algorithms》：PSO-FSPMiner: A Metaheuristic Approach for Mining a Representative Subset of Frequent Similar Patterns Ansel Y. Rodríguez-González, Rosa María Valdovinos-Rosas, Gretel Bernal Baró, Ramón Aranda, Angel Díaz-Pacheco and Miguel á. álvarez-Carmona

　　

近年来，采用超越严格相等关系的相似性函数以揭示隐藏知识的算法日益受到关注。然而，这类算法面临的一个显著挑战是会产生大量频繁相似模式，从而增加计算开销，并使人工分析变得更加复杂。本文提出了一种基于粒子群优化（Particle Swarm Optimization，PSO）的元启发式方法PSO-FSPMiner，用于提取模式的代表性子集以应对该问题。基于真实世界数据集的实验表明，由PSO-FSPMiner挖掘得到的频繁相似模式子集能够捕获数据集约86.4%的知识，同时将频繁相似模式数量大幅减少约85.9%。

本文发表于《Algorithms》，研究聚焦于频繁相似模式（Frequent Similar Pattern，FSP）挖掘中普遍存在的“模式爆炸”问题。传统频繁模式挖掘通常以严格相等作为匹配基础，但在许多真实场景中，对象在属性值层面往往并非完全一致，而是以近似相似的形式出现。围绕这一局限，频繁相似模式挖掘通过在频率计算中引入相似性函数，使得相似对象描述也能对模式频率产生贡献，从而能够发现传统频繁模式挖掘难以揭示的潜在规律。尽管ObjectMiner、STreeDC-Miner、RP-Miner和X-FSPMiner等方法已能有效挖掘FSP，但其共同问题在于会产生数量极其庞大的模式集合，既提高了计算成本，也加重了后续知识分析与解释负担。因此，如何从完整FSP集合中提取一个紧凑且具有代表性的模式子集，成为值得开展的关键研究问题。

针对上述问题，研究人员提出了PSO-FSPMiner，这是一种基于粒子群优化（Particle Swarm Optimization，PSO，群体智能优化方法）的元启发式框架，目标不是穷举全部候选模式，而是在大规模组合搜索空间中寻找能够代表整体数据知识的FSP子集。该方法以模式频率作为质量指标，同时引入“代表性”（representativeness）与“覆盖度”（coverage）两个新评价函数，用于识别冗余模式并保留更具信息量的模式。研究表明，该方法在多个真实数据集上可显著压缩模式规模，在平均减少约85.9%频繁相似模式的同时，仍保持约86.4%的总体描述能力。论文的重要意义在于：其一，为频繁相似模式挖掘提供了由“全量发现”转向“代表性筛选”的新思路；其二，通过将PSO与FSP挖掘结合，构建了受控的随机搜索过程，降低了组合枚举压力；其三，提出的代表性与覆盖度机制为模式冗余判别提供了形式化标准。

方法上，研究人员首先采用X-FSPMiner获得完整频繁相似模式集，并将其作为评价PSO-FSPMiner所挖掘代表性子集质量的基线。PSO-FSPMiner以粒子表示候选模式，每个粒子由属性向量构成，通过惯性因子w、加速度常数c₁与c₂更新速度与位置；对数值属性采用连续更新与边界修复，对非数值属性采用sigmoid函数与轮盘赌选择机制进行更新。算法维护外部列表（ExternalList），结合频率、代表性与覆盖度对新解进行筛选；若两个模式的代表性为1且覆盖度高于最小覆盖阈值，则视为冗余，并依据模式长度及覆盖实例数执行支配判定。实验使用UCI Machine Learning Repository中的双分类数据集，频率阈值在0.02至0.10之间变化，并采用K近邻（K-Nearest-Neighbor，KNN）分类器评估代表性子集对完整FSP集合的描述质量。

研究结果如下。

1. Introduction
引言部分系统阐述了研究动机。研究人员指出，传统频繁模式挖掘依赖严格相等判定，不适用于大量真实世界近似匹配场景。FSP挖掘通过显式引入相似性函数扩展了传统框架，能够将相似对象描述累积到模式频率中，但随之产生大量模式，导致计算与分析复杂度上升。基于此，论文提出采用PSO设计一种用于提取代表性FSP子集的元启发式方法，并说明该方法以代表性与覆盖度衡量候选子集质量。引言同时给出了核心实验结论，即所获子集平均保留约86.4%的数据知识，而模式数量平均减少约85.9%。

2. Related Work
该部分综述了相似性感知模式发现相关研究，包括近似频繁模式挖掘、相似性模式匹配和广义模式挖掘，并将重点收束至FSP挖掘。研究人员依据相似性函数返回值类型，将现有算法分为布尔型与非布尔型；又依据单调性分为非增单调与增单调两类，并指出非增单调相似性函数满足f_S-downward closure性质，可用于搜索空间剪枝。在此基础上，论文重点分析了ObjectMiner、STreeDC-Miner与X-FSPMiner。ObjectMiner基于Apriori思想，但计算代价较高；STreeDC-Miner通过树结构减少相似性计算；X-FSPMiner则以FV-Tree压缩数据并避免无效候选生成，性能显著优于前两者。由于三者在给定条件下可挖掘相同FSP集合，研究人员最终选择X-FSPMiner作为完整模式集的生成基线。

3. Basic Concepts and Notation
该部分给出了论文的形式化定义体系。研究人员定义了数据集Ω、对象O_i、属性集合R及模式I_S(O)，并说明对象模式是属性子集S上的子描述。随后引入布尔相似性函数f_S，当两个对象在S涉及的所有属性上满足比较准则C_r时取值1，否则取值0。论文进一步定义了模式频率，即模式与数据集中所有对象模式相似性的累积和，并规定当频率不小于最小频率阈值minFreq时，该模式为FSP。为支持剪枝，论文讨论了f_S-downward closure性质、频率单调性及非增单调相似性函数定义，明确本文聚焦于布尔型、非增单调相似性函数下的代表性子集挖掘问题。这一部分为后续算法设计提供了严格数学基础。

4. Mining a Representative Subset of Frequent Similar Patterns
该部分是全文方法核心，说明研究人员如何将PSO用于FSP代表性子集挖掘。

4.1. Relevance Measures
本节提出两项新评价函数。第一，代表性Rp用于衡量两个模式在公共属性上的一致程度及公共属性占较短模式长度的比例；若Rp接近0，则两个模式差异较大；若Rp等于1，则二者在共有属性层面提供相同知识。第二，覆盖度Cov用于衡量两个模式对支持其频率的实例集合的重叠比例，本质上反映二者在实例覆盖层面的重复程度。研究人员据此定义冗余：若两个模式的代表性等于1，且覆盖度大于最小覆盖阈值CovMin，则它们被视为冗余。随后引入支配关系：当两个冗余模式比较时，优先保留长度更长的模式；若长度相同，则保留覆盖实例数更多、即频率更高的模式。该机制确保保留的信息更丰富、描述能力更强的模式。

4.2. PSO-FSPMiner
本节详细描述算法流程。PSO-FSPMiner输入数据集Ω、种群大小N、迭代次数Iter、最小频率阈值minFreq、最小覆盖阈值minCov、惯性因子w、加速度常数c₁和c₂以及权重变量boostWeight。每个粒子表示一个候选相似模式，其适应度由频率决定。算法随机初始化粒子种群与速度向量，并对每个粒子记录个体最优PBest和全局最优GBest。与标准PSO不同的是，论文增加了外部列表ExternalList，用于在迭代过程中存储非冗余且相关性较高的模式。每轮更新中，粒子依据速度更新公式进行移动；对于数值属性，采用加法更新并通过最小值和最大值区间进行修复，再映射到最接近的真实属性值；对于非数值属性，则先用sigmoid函数将速度转为出现概率，再依据PBest、GBest和boostWeight为各可能属性值分配概率，通过轮盘赌选择更新结果。更新后重新计算适应度，并据此更新PBest、GBest以及ExternalList。算法迭代至预设次数后，输出ExternalList中的模式子集。研究人员同时指出，该方法不进行完整模式空间枚举，因此其计算复杂度受粒子数P与迭代数T控制，单次执行成本界为O(P·T·N·m)，其中N为对象数、m为属性数。

5. Experiments and Results
该部分通过实验验证所提方法的模式压缩能力与知识保持能力。研究人员在来自UCI Machine Learning Repository的多个双分类真实数据集上开展实验，所有数据集均使用非增单调布尔相似性函数。对于数值属性，比较准则采用ε阈值形式，其中ε = α×(maxV ? minV)，且α = 0.05；对于非数值属性，则采用严格相等准则。X-FSPMiner作为基线生成完整FSP集合，PSO-FSPMiner在不同最小频率阈值下运行，参数设置为100个粒子、100次迭代、c₁ = c₂ = 1.74、w = 0.869、boostWeight = 0.1。每种设置重复运行10次，统计子集规模、所占全部FSP比例及总体精度。

5.1. FSP数量压缩结果
通过比较X-FSPMiner与PSO-FSPMiner生成的模式数，研究人员发现后者具备显著的模式约简能力。在Liver Disorders数据集且频率阈值为0.02时，PSO-FSPMiner仅保留16,434个FSP中的140个；在Indian Liver Patient数据集且频率阈值为0.06时，仅保留165,608个FSP中的1298个，约减幅可达99%。整体来看，在50个测试场景中的41个场景里，PSO-FSPMiner生成的模式数不足完整FSP集合的20%，即在超过80%的场景中实现了80%以上的压缩。最差情况下，模式数也减少了40%以上，平均压缩率为85.9%。这一结果表明，所提方法能够有效剔除冗余模式，构建紧凑表示。

5.2. 子集质量评估结果
论文采用监督式K近邻分类器KNN对子集质量进行评估。具体而言，利用PSO-FSPMiner获得的FSP子集去分类由X-FSPMiner得到的完整FSP集合，并以总体精度（Overall Accuracy）衡量子集对全量模式知识的保留程度。所用距离度量定义为两个模式相似属性数占属性并集大小的比例。实验结果显示，在全部测试场景中，总体精度均不低于75%，最低值出现在Liver Disorders数据集的频率阈值0.1条件下；Glass数据集上表现最佳。进一步分析表明，在50个测试场景中的44个场景中，KNN能够正确分类超过80%的完整FSP，说明PSO-FSPMiner得到的子集在大多数条件下保留了较强的整体描述能力，平均知识保持率约为86.4%。

5.3. 统计显著性分析
为检验不同频率阈值下性能差异是否显著，研究人员采用非参数统计方法进行分析。首先计算不同频率阈值在全部实验场景中的平均秩次，再应用Nemenyi事后检验比较各阈值之间的秩差。结果显示，在显著性水平α = 0.05下，所有成对比较的平均秩差均未超过临界差（critical difference，CD），说明不同频率阈值之间不存在统计学显著差异。该结果表明，PSO-FSPMiner在所测试阈值范围内具有较好的稳定性，其性能不会因最小频率阈值变化而明显波动。

5.4. Computational Performance and Resource Considerations
本节从计算资源角度进一步说明算法特征。研究人员强调，穷举式FSP挖掘方法由于需要枚举完整候选空间，即便利用f_S-downward closure性质进行剪枝，在最坏情况下仍可能表现出指数级复杂度。相比之下，PSO-FSPMiner通过种群随机搜索避免了完整枚举，其计算代价由P、T、N和m线性控制。实验在配置为Intel? Core? i7 CPU（1.80–2.00 GHz）和8 GB RAM的工作站上完成，所有数据集与参数设定下均成功运行，未出现内存饱和或不稳定现象。即使在完整FSP数量超过200,000的场景中，PSO-FSPMiner仍能顺利执行。论文同时指出，由于其目标并非加速完整枚举，而是直接发现代表性子集，因此与穷举算法做严格运行时间对比并不构成完全等价的评估框架。

讨论部分表明，PSO-FSPMiner的核心优势不在于替代全量挖掘算法输出全部FSP，而在于通过代表性与覆盖度约束，在保持较高知识表达能力的同时大幅缩减模式规模。研究结果支持这样一个结论：频繁相似模式挖掘中的冗余问题可以通过元启发式搜索与形式化冗余判定相结合的方式得到有效缓解。论文还显示，该方法对不同频率阈值表现稳定，说明所提出的评价函数和外部列表维护机制具有较好的鲁棒性。不过，文章并未将研究重心放在与穷举算法的标准化时间、内存基准比较上，而是强调方法目标上的差异性，即“代表性子集发现”而非“全量模式枚举”。

结论部分可译为：频繁相似模式挖掘正作为传统频繁模式挖掘算法在数据挖掘中的一种替代性解决方案而兴起，并能够揭示隐藏知识。然而，现有FSP挖掘算法会产生大量模式。由于许多模式提供的是数据集中的相同知识，因此其分析代价较高。基于此，本文开发了一种元启发式方法PSO-FSPMiner，用于挖掘能够描述整个数据集的FSP子集。PSO-FSPMiner的特点在于，仅将那些被认为相关且非冗余的模式保存在解子集中。同时，本文提出了两个新函数，用于评估被分析模式的公共属性数量及其所覆盖实例的比例，分别称为代表性与覆盖度。本文的主要贡献在于提出了这一融合代表性与覆盖度两个函数的新型元启发式方法，用于挖掘能够描述整个数据集的模式子集。实验表明，该方法能够在保留约86.4%总体描述能力的同时，将FSP数量显著降低约85.9%。另一方面，结果还证明了该方法的稳定性：无论频率阈值还是数据集规模如何变化，其性能均未发生显著改变，能够获得更小的模式子集，避免冗余FSP，并保留包含有价值知识的模式。未来工作将探索布尔函数之外的不同相似性函数，以扩展算法适用性；同时还计划基于当前方案开发用于挖掘关联规则子集的元启发式方法。