论文部分内容阅读
双聚类算法是近年来提出的一种新的聚类方法,与传统聚类单向聚类不同的是,它在行和列两个方向上同时进行聚类,且能找到很有价值的局部模式。因此,在分类及预测等方面,双聚类算法比传统聚类算法更精细和准确。目前,双聚类已广泛应用于基因微阵列数据分析、电子商务、文本挖掘等领域。 Order-preserving submatrix(OPSM)作为一种有效的双聚类模型,已经被广泛地应用到生物学基因表达数据的挖掘中。它能刻画基因表达值在部分实验条件下一致的变化趋势,与寻找一致局部表达值模式的双聚类算法不同,OPSM双聚类算法寻找那些具有相同次序关系的模式。OPSM的应用包括基因表达值数据分析、自动推荐系统、电子商务目标市场营销等。 OPSM模型只关心元素值间相对大小次序,而不关心元素的实际数值大小。但是,传统OPSM模型认为任意两列间元素值的大小次序模式只有严格单增和严格单减两种,把相等这种模式与以上两种并不加以区分,而这对于现实应用中是不完整的。因此,针对以上问题,本文通过扩展OPSM模型,定义了一种新型模型Semi-Order-Preserving SubMatrix,简称SOPSM模型,该模型严格区别了相等与其他两种相对次序关系。不仅如此,本文还提出了一种挖掘所有SOPSM双聚类的精确性算法,该算法基于Apriori算法在挖掘过程中使用了剪枝策略,从而大大缩小了模式搜索空间。并且,为了进一步加快挖掘过程,本文还设计了一种改进前缀树的数据结构用于检索模式、扩展模式以及保存SOPSM结果。 另外,近来生物学家们希望在基因数据中找到那些列数很多而行数很少的Deep OPSM。这是因为它们不仅对解释基因调控网络有非常重要的作用,而且具有关键的生物意义。但是,已有的基于Apriori算法等方法的精确性序列模式挖掘算法由于以下原因不能很好解决Deep OPSM问题:(1)当算法的参数最小支持度阈值设置较小,算法时间和空间复杂度会呈指数级增长;(2)当最小支持度阈值设置较大时,虽然能快速挖掘模式,但往往会过早修剪掉大量可以生成长模式的短模式,从而导致难以找到那些支持行序列少的长模式,即Deep OPSM。为此,本文提出一种新的Deep OPSM挖掘算法,该算法先寻找数据中所有两行序列对的所有满足给定列阈值的公共子序列,再合并那些具有相同公共子序列的行对,从而最终得到所有满足给定行列闽值的Deep OPSM。 最后,为了挖掘SOPSM和Deep OPSM双聚类,本文在真实和合成数据集上做了大量实验并作了相应的结果分析。结果显示了SOPSM模型的有效性以及所提出算法的高效性。针对SOPSM双聚类的实验结果表明,SOPSM挖掘算法不仅能精确性挖掘所有满足最小支持度阈值的所有SOPSM,而且,它与现有主流OPSM算法相比有较好的挖掘效果。而针对Deep OPSM双聚类的实验结果表明,本文的DeepOPSM挖掘算法非常适合充分挖掘具有较小行支持度的Deep OPSM,甚至能找到最小支持度阈值(即行阈值)为2的全部Deep OPSM。并且,相对于依靠设置较大支持度阈值挖掘OPSM的那些传统序列模式挖掘算法,本文算法能更高效地解决Deep OPSM问题。