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