摘要：序列模式挖掘是從序列數據中發現用戶感興趣的模式。對比模式挖掘是其中的一類挖掘方法,其特點是在兩類或多類別的序列庫中找到特征信息,在實際的生活和生產中應用十分廣泛。隨著數據規模的不斷增加,算法的挖掘效率顯得尤為重要,但是當前對比模式挖掘仍存在挖掘速度太慢的問題。為了快速挖掘滿足密度約束和間隙約束的對比模式,文中提出了一種近似求解算法ADMD(Approximately Distinguishing Patterns Mining Based on Density Constraint),該算法在模式的挖掘過程中允許存在小部分的模式丟失,從而換取挖掘速度的大幅提升。該算法采用網樹的特殊結構來計算模式的支持數;采用模式拼接的方式來生成候選模式;采用預判式剪枝策略對模式進行剪枝,以避免大量冗余模式的生成。但由于在剪枝過程中可能會剪掉一部分非冗余模式,造成挖掘結果并非完備,因此該算法是一種近似求解算法。在ADMD算法的基礎上,通過在剪枝策略中設定參數k的方式來得到ADMD-k算法,該算法可以通過設定k的取值來調整剪枝程度,從而在挖掘效率和準確率方面取得平衡。最后在真實的蛋白質數據集上將所提算法與其他算法從挖掘的對比模式數量和挖掘速度方面進行對比實驗。實驗結果表明,在k=1.5的情況下,所提算法僅用不到原來13%的時間,就可以挖掘到99%以上的模式,具有近似度高、速度快的特點。