算法性能实验分析

2025-09-29 理论教育版权反馈

【摘要】：如图3.5所示显示出了两个算法程序的运行时间。此图验证了前一自然段中的时间效率分析，表明CpecuFind时间效率的优势显著。表3.54个ROC曲线下方面积对比结果图3.6两算法在30+330数据集上计算的ROC曲线PecuFind；CpecuFind图3.7两算法在550数据集上计算的ROC曲线Pecu Find；Cpecu Find由此，4个ROC曲线的对比说明，CpecuFind算法性能优于Pecufind算法性能。

1.算法时间效率分析

以属性层次为讨论依据，Zhong Ning的算法时间复杂度明显是O（N2），其中N是属性集合中的数据数目。对于本书提出的算法，设经聚类后，聚类的个数为k；经计算聚类的CPF后，需以数据单独参加PF值计算的数据个数与以类整体参加PF值计算的类的个数之和为n。在聚类阶段，采用的聚类算法时间复杂度是线性的，为O（N）；聚类后计算每个聚类的CPF值阶段时间复杂度是O（k）；最后计算PF阶段的时间复杂度是O（n2）。其中，最后阶段的时间复杂度是平方级的，希望n与N的比值很小，最好与N的增长保持线性以下的增长速度。在第3.3.2小节的数据集30+300、50+500、100+1000、200+2000、300+3000上运行Cpecu Find算法程序，λ取10%，采集在运行过程中n与N的关系，得到图3.4。其中，A17、A18、A19 3条曲线显示的是在数据集中第17、第18、第19个属性集在实验中n随N变化的情况，作为对比，直线10%显示的是n与N比值为10%的直线。

由图3.4可知，n与N的比值会在给定λ周围变化。因不同属性的数据集特征不同，聚类结果不同，n的变化没有统一的规律。由于特异挖掘中λ值很小，提出的算法具有较好的可扩展性。

仍采用在第3.3.2小节的渐增数据集30+300、50+500、100+1000、200+2000、300+3000，在其上分别运行PecuFind算法和CpecuFind算法。在Cpecu Find算法程序中，λ取10%。如图3.5所示显示出了两个算法程序的运行时间。其中Pecu Find在运行“100+1000”子集时，运行时间已超过1800s（0.5h），运行被中止，图3.5中用“”表示。此图验证了前一自然段中的时间效率分析，表明CpecuFind时间效率的优势显著。

pagenumber_ebook=47,pagenumber_book=42

图3.4　不同数据集规模下n与N的关系图

pagenumber_ebook=47,pagenumber_book=42

图3.5　PecuFind程序和CpecuFind程序运行时间比较

2.两算法ROC曲线对比

KDDCUP99数据集是网络访问数据记录集，其中的记录有两大类：正常访问记录和网络攻击记录，而网络攻击记录在数据集中占的比例很小，如果将攻击记录设为正类，正常访问记录设为负类，本章讨论的特异数据挖掘问题在此数据集上就是不平衡数据集的二分类问题。这类问题的结果评估，除前述的挖掘特异数据能力，还可以以ROC曲线特征来评估。对于第3.3.2节的30+300和50+500数据集，分别利用Cpecu Find和Pecu Find算法计算出的记录特异因子RPF值绘制ROC曲线，得到4个ROC曲线图，如图3.6和图3.7所示，曲线x轴表示假正率（Sensitivity），y轴表示真正率（1-Specificity）。4个ROC曲线下方面积的对比结果如表3.5所示。(https://www.chuimin.cn)

表3.5　4个ROC曲线下方面积对比结果

pagenumber_ebook=47,pagenumber_book=42