林泽东 等：基于序列移动距离的用户行为挖掘与相似度计算０　引言近年来，随着感知技术、可穿戴设备和移动互联网技术的成熟应用，越来越多的用户行为信息能够被精确地获取和记录。这些信息真实地展示了用户在生活中的日常行为，能够准确和完整地反映用户的兴趣爱好、行为特点、生活轨迹等信息［１－２］。研究者们利用这些用户行为日志开展了许多有意义的工作，例如，利用用户行为日志分析用户的行为特征、比较和识别相似用户等［３－５］。通过分析用户行为日志，可以更加深入和准确地理解用户的行为规律和特点，为用户需求精准定位和个性化信息服务提供支持。用户行为由其背后的行为流程决定，原则上，用户行为相似度可基于流程相似度的度量方法进行计算。但是，用户行为隐含的行为流程不像普通业务流程那样具有确定的流程模型，因此无法用传统的流程相似性度量方法进行用户行为的相似性度量。为解决这一问题，本文从用户行为流程产生的行为序列出发，对用户行为进行挖掘和相似度计算。具体而言，首先，从用户的原始行为序列中挖掘出用户的行为序列多重集，并以此建模用户行为；其次，为了计算用户行为多重集的距离和相似度，定义了基于最长公共子序列的用户行为序列距离度量方法；然后，定义了基于 （ｅａｒｔｈ　ｍｏｖｅｒｓ　ｄｉｓｔａｎｃｅ）［６］的 用户行为序列多重集之间距离的计算方法，在此基础上计算用户行为相似度；最后，提出行为序列多重集之间距离度量应遵循的基本准则。通过这些基本准则评估了现有方法中存在的不足，并以真实数据验证本文所提方法的有效性。１　相关研究工作与本文相关的工作主要是用户行为相似度计算方面。下面分别对相关工作、本文研究内容与已有工作的不同进行概述。Ｙｉｎｇ等［４］提出基于最大轨迹模式（Ｍａｘｉｍａｌ　Ｔｒａｊｅｃｔｏｒｙ　Ｐａｔｔｅｒｎ，ＭＴＰ）的用户相似度计算方法。该方法通过最长公共子序列计算两个序列的相似度，将用户相似度定义为两个用户所有序列对相似度的加权平均值。Ｃｈｅｎ等［５］发现ＭＴＰ方法在有些情况下不能保证两个相同用户的相似度为１，提出了改进的 ＭＴＰ方法，解决了上述问题，却忽略了序列的频次信息。随后，Ｃｈｅｎ等［７］又提出 一 种 基 于 公 共 模 式 集 合 （Ｃｏｍｍｏｎ　ＰａｔｔｅｒｎＳｅｔ，ＣＰＳ）的用户相似度计算方法。该方法利用两个用户的公共序列模式集合计算用户相似度，考虑了公共序列的长度、支持度以及支持度的分布情况，解决了上述方法中存在的问题，但是该方法作为一种距离或相似度的度量方法，并不满足三角不等式公理；另外，该方法是基于频繁序列模式实现的，在频繁序列模式挖掘过程中存在着子序列被重复计算问题，将导致最终的相似度结果存在偏差。ＥＭＤ［６］最初在运输问题中被提出，用来测量两个分布之间的距离，相比于其他距离计算方法，能提供更接近人们感知距离的结果，因此 ＥＭＤ 在图像检索领域得到广泛的应用［６，８］。为此，本文将 ＥＭＤ 作为度量两个用户行为相似度的基础。本文的主要贡献如下：（１）直接从原始序列出发计算用户行为序列多重集的距离，避免了现有方法在计算频繁序列模式过程中子序列被重复计算而导致最终结果存在偏差的问题。（２）重新定义了基于最长公共序列的行为序列距离计算方法，并证明了该距离是一个度量。（３）定义了用户行为序列多重集之间距离的度量指标，提出了用户行为相似度计算方法。（４）从距离角度出发，重新定义了行为序列多重集之间距离应遵循的基本准则。２　相关概念行为序列通常是用户的一个活动序列，例如，先到餐厅就餐、然后前往教室上课、再到图书馆学习，构成了用户的一个行为序列?餐厅就餐，教室上课，图书馆学习?。用户在某段时间内的行为对应一个行为序列的多重集。下面在该行为序列多重集的基础上，挖掘用户的行为模式，计算用户行为相似度。相关概念如下：定义１　 频 繁 项 行 为 序 列 集 和 频 繁 项 行 为 序列。假设用户的原始行为序列多重集为 Ｄ，最小频次阈值为α。频繁项行为序列集是由 Ｄ 中每个行为序列去除掉其中出现次数小于α 的元素的所有行为序列构成的集合。频繁项行为序列集中的每一个序列就是一个频繁项行为序列。与频繁序列模式挖掘产生的频繁序列有所不同，频繁项行为序列是从用户原始行为序列中删除出现次数小于最小频次阈值α的元素而得到的活动序列。定义２　行为模式。行为模式是一个由二元组６０１１ 林泽东 等：基于序列移动距离的用户行为挖掘与相似度计算数；第１３～１６行生成用户的行为模式。算法１的时间复杂度主要表现在频繁项行为序列挖掘部分，算法要遍历所有行为序列中的每个用户活动，因此算法１的时间复杂度为 Ｏ（ｑＮ），其中：Ｎ 为行为序列的个数，ｑ为所有序列的最大长度。为了能够更好地理解用户模式的挖掘过程，举一简单例子进行说明。假设用户ｕ的原始行为序列多重集为 Ｄ＝｛ＡＢＣＺ，ＡＢＣ，ＢＣ｝，最小频次阈值为２。整个挖掘过程包括频繁项行为序列挖掘和行为模式挖掘两个主要步骤。通过频繁项行为序列挖掘过程扫描 Ｄ 中所有的行为序列，统计行为序列中各元素的出现频次，删除出现频次小于２的元素 Ｚ，得到频繁项行为序列多重集｛ＡＢＣ，ＡＢＣ，ＢＣ｝；通过行为模式挖掘过程统计多重集中各频繁项行为序列的重数，最 终 生 成 行 为 模 式 Ｐｕ＝ ｛（ＡＢＣ，２），（ＢＣ，１）｝。５　用户行为相似度计算方法用户行为相似度通过用户行为模式相似度实现。为了计算行为模式的相似度，首先计算行为模式距离。下面介绍行为模式距离的计算方法。５．１　行为模式距离计算用户的行为模式由行为序列构成。行为模式距离计算过程中需要计算行为序列之间的距离，因此首先定义行为序列之间的距离。为了使两个行为序列的公共子序列更长、相似度更大、两个行为序列之间的距离更小，将行为序列间的距离定义如下：定义４　行为序列距离。两个行为序列 Ｓ１和Ｓ２ 的距离定义为Ｄｓｅｑ（Ｓ１，Ｓ２）＝１－｜ｌｃｓ（Ｓ１，Ｓ２）｜｜Ｓ１｜＋｜Ｓ２｜－｜ｌｃｓ（Ｓ１，Ｓ２）｜。（１）式中：｜Ｓ｜为行为序列Ｓ 的长度，ｌｃｓ（Ｓ１，Ｓ２）为两个行为序列Ｓ１和Ｓ２的最长公共子序列。实际上，式（１）中的｜ｌｃｓ（Ｓ１，Ｓ２）｜｜Ｓ１｜＋｜Ｓ２｜－｜ｌｃｓ（Ｓ１，Ｓ２）｜可以用来衡量两个行为序列Ｓ１和Ｓ２的相似程度。当Ｓ１ 和Ｓ２相同即ｌｃｓ（Ｓ１，Ｓ２）＝１时，Ｄｓｅｑ（Ｓ１，Ｓ２）＝０；当Ｓ１和Ｓ２没有任何公共序列即ｌｃｓ（Ｓ１，Ｓ２）＝０时，Ｄｓｅｑ（Ｓ１，Ｓ２）＝１。定理１　行为序列距离是一个度量。证明　设ｅｄｉｔ（ｘ，ｙ）是两个行为序列ｘ 和ｙ 之间的编辑距离。根据式（１）有Ｄｓｅｑ（Ｓ１，Ｓ２）＝１－｜ｌｃｓ（Ｓ１，Ｓ２）｜｜Ｓ１｜＋｜Ｓ２｜－｜ｌｃｓ（Ｓ１，Ｓ２）｜＝｜Ｓ１｜＋｜Ｓ２｜－２｜ｌｃｓ（Ｓ１，Ｓ２）｜｜Ｓ１｜＋｜Ｓ２｜－｜ｌｃｓ（Ｓ１，Ｓ２）｜＝２｜Ｓ１｜＋２｜Ｓ２｜－４｜ｌｃｓ（Ｓ１，Ｓ２）｜２｜Ｓ１｜＋２｜Ｓ２｜－２｜ｌｃｓ（Ｓ１，Ｓ２）｜。 （２）将文献［１０］的结论ｅｄｉｔ（Ｓ１，Ｓ２）＝｜Ｓ１｜＋｜Ｓ２｜－２｜ｌｃｓ（Ｓ１，Ｓ２）｜代入式（２），得到Ｄｓｅｑ（Ｓ１，Ｓ２）＝２ｅｄｉｔ（Ｓ１，Ｓ２）｜Ｓ１｜＋｜Ｓ２｜＋ｅｄｉｔ（Ｓ１，Ｓ２）。（３）式（３）已经被文献［１１］证明是一个度量且是一个归一化编辑距离，因此 Ｄｓｅｑ（Ｓ１，Ｓ２）是一个度量。定义５　 行为模式 距离。设 Ｐｕ＝ ｛（ｐ１，ｗｐ１），…，（ｐｍ，ｗｐｍ）｝，Ｐｖ＝｛（ｑ１，ｗｑ１），…，（ｑｎ，ｗｑｎ）｝是两个用户的行为模式，ｆｉｊ为行为序列ｐｉ到ｑｊ的转换量，Ｄｓｅｑ（ｐｉ，ｑｊ）为ｐｉ和ｑｊ之间的行为序列距离，则Ｐｕ和Ｐｖ之间的行为模式距离为Ｄｐａｔ（Ｐｕ，Ｐｖ）＝ ｍｉｎ∑ｍｉ＝１∑ｎｊ＝１ｆｉｊＤｓｅｑ（ｐｉ，ｑｊ）。ｓ．ｔ．∑ｎｊ＝１ｆｉｊ ＝ｗｐｉ∑ｍｉ＝１ｗｐｉ，１≤ｉ≤ ｍ；∑ｍｉ＝１ｆｉｊ ＝ｗｑｊ∑ｎｊ＝１ｗｑｊ，１≤ｊ≤ｎ，ｆｉｊ ≥０。若将两个行为模式分别看作是一些土坑和一些土堆，则行为模式距离实际上是分别对土堆和土坑容量进行归一化后，用土堆填满土坑所需的最小运输费用。其中，土堆与土坑之间的距离就是其对应的行为序列之间的行为序列距离。下面结合图２中的例子对行为模式距离的概念进行说明。图２中的两个用户行为模式分别为 Ｐｕ＝｛（Ａ，１），（Ｂ，１）｝，Ｐｖ＝｛（Ａ，１），（Ｂ，３）｝。行为模式距离计算过程中，首先将 Ｐｕ和Ｐｖ的频次进行归一化，然后计算 Ｐｕ转换成Ｐｖ的 ＥＭＤ。因为行为序列距离是对称的，即 Ｄｓｅｑ（ｐｉ，ｑｊ）＝Ｄｓｅｑ（ｑｊ，ｐｉ），所以行为模式距离也是对称的。因此，源和目的行为模式的选择不影响行为模式距离的计算。允许 Ｐｕ中的行为序列ｐｉ以归一化的频次为数量，部分或全部转换到 Ｐｖ中的任意一个行为序列ｑｊ，单位转换代价为行为序列距离 Ｄｓｅｑ（ｐｉ，ｑｊ）。整个计算过程的目标是将寻求一个最优的转换方案ｆｉｊ，使得将 Ｐｕ完全转换成Ｐｖ的总费用最小。６０１３计算机集成制造系统 第２３卷（Ｘ，β）构成的集合，其中：Ｘ 为频繁项行为序列，β为该频繁项行为序列的频次。定义３　度量［９］。假设Ｓ 是一个集合，函数ｄ：Ｓ×Ｓ→Ｒ＋∪｛０｝。对于任意的 ｘ，ｙ，ｚ∈Ｓ，函数 ｄ满足：①自相似公理，ｘ＝ｙ，ｄ（ｘ，ｙ）＝０；② 正性公理，ｘ≠ｙ，ｄ（ｘ，ｙ）＞０；③ 对称性公理，ｄ（ｘ，ｙ）＝ｄ（ｙ，ｘ）；④三角不等公理，ｄ（ｘ，ｚ）≤ｄ（ｘ，ｙ）＋ｄ（ｙ，ｚ）。则称函数ｄ 为Ｓ 上的一个度量。３　基于序列移动距离的用户行为挖掘与相似度计算框架基于 序 列 移 动 距 离 （Ｓｅｑｕｅｎｃｅ　Ｍｏｖｅｒｓ　Ｄｉｓ－ｔａｎｃｅ，ＳＭＤ）的用户行为挖掘与相似度计算方法的整体框架如图１所示，主要包括用户行为挖掘和用户行为相似度计算两部分。用户行为通过用户的行为模式来建模和表示，用户行为挖掘本质上是从用户原始的行为序列多重集中挖掘用户的行为模式，包括频繁项行为序列挖掘和行为模式挖掘两个步骤。频繁项行为序列挖掘是根据用户设定的最小频次阈值α，删除用户原始行为序列多重集中频次小于α的元素，得到用户频繁项行为序列集；行为模式挖掘则是计算用户所有的不同频繁项行为序列和频次，生成用户的行为模式。用户行为相似度计算主要包括行为模式距离计算和行为相似度计算两个步骤。行为模式距离计算过程中涉及到用户行为序列之间的距离，因此应首先定义和计算行为序列之间的距离，然后根据行为序列间的距离和频次计算两个用户行为模式之间的距离；用户行为相似度即为行为模式相似度，在用户行为相似度计算过程中，采用行为模式距离与行为模式相似度之和为 １ 来计算用户行为模式的相似度，最终得到用户行为相似度。４　用户行为挖掘通过挖掘用户行为序列的频繁序列模式，可以对用户的行为进行建模。然而，由于向下闭包属性，频繁序列模式挖掘过程产生了许多频繁子序列，这些频繁子序列导致最终的相似度结果存在偏差［４］。为了避免上述问题，本文利用用户模式建模用户行为。用户行为挖掘的主要任务是从用户原始的行为序列中挖掘出用户的行为模式，具体算法如下：算法１　行为模式挖掘算法。输入：用户原始行为序列多重集 Ｄ，最小频次阈值α。输出：行为模式。１．令数组 ｂ：＝［０，…，０］　／／其中｜ｂ｜＝Ｎ，Ｎ 表示所有用户活动（序列中的元素）数２．ＦＯＲＥＡＣＨ（序列ｓ∈Ｄ）３．　 ｃ：＝［０，…，０］　／／｜ｂ｜＝｜ｃ｜４．　 统计ｓ中各个用户活动的频次，将频次赋值给数组ｃ５．　 ｂ：＝ｂ＋ｃ６．令序列多重集 Ψ：＝７．ＦＯＲＥＡＣＨ（序列ｓ∈Ｄ）８．　 根据ｃ的统计结果，删除ｓ中频次小于α的用户活动得到序列ｓ′９．　 Ψ：＝Ψ∪｛ｓ′｝１０．建立哈希表ｈａｓｈｍａｐ来存储行为模式和频次１１．ＦＯＲＥＡＣＨ（频繁项序列ｓ∈Ψ）１２．　 ｓ的频次加一：ｈａｓｈｍａｐ．ｐｕｔ（ｓ，ｈａｓｈｍａｐ．ｇｅｔ（ｓ）＋１）１３．初始化行为模式 Ｐ：＝１４．ＦＯＲＥＡＣＨ（频繁项序列ｓ　ｉｎ　ｈａｓｈｍａｐ．ｋｅｙｓ）１５．　 Ｐ：＝Ｐ∪｛（ｓ，ｈａｓｈｍａｐ．ｇｅｔ（ｓ））｝１６．返回行为模式 Ｐ算法１由频繁项行为序列挖掘和行为模式挖掘两部分组成。第１～９行是频繁项行为序列挖掘过程：第１～５行计算用户的所有行为序列中各用户活动的频次；第６～９行删除行为序列中频次小于最小频次阈值的用户活动，得到频繁项行为序列多重集。第１０～１６行利用哈希技术挖掘用户的行为模式：第１０～１２行统计多重集中各个频繁项行为序列的重６０１２期：２０１６－０６－２８；修订日期：２０１６－０８－２８。Ｒｅｃｅｉｖｅｄ　２８Ｊｕｎｅ　２０１６；ａｃｃｅｐｔｅｄ　２８Ａｕｇ．２０１６．基金 项 目：国 家 自 然 科 学 基 金 资 助 项 目 （６１６０２２７９，６１１７００７９，６１２０２１５２，６１４７２２２９）；山 东 省 科 技 发 展 计 划 资 助 项 目 （２０１４ＧＧＸ１０１０３５，２０１６ＺＤＪＳ０２Ａ１１）；山东省自然科学基金资助项目（ＢＳ２０１４ＤＸ０１３，ＺＲ２０１５ＦＭ０１３）；同济大学嵌入式系统与服务计算教育部重点实验室开放课题资助项目（ＥＳＳＣＫＦ２０１４０３）；山东省博士后创新专项资金资助项目（２０１６０３０５６）；山东科技大学领军人才与优秀科研团队计划资助项目（２０１５ＴＤＪＨ１０２）。Ｆｏｕｎｄａｔｉｏｎ　ｉｔｅｍｓ：Ｐｒｏｊｅｃｔ　ｓｕｐｐｏｒｔｅｄ　ｂｙ　ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ，Ｃｈｉｎａ（Ｎｏ．６１６０２２７９，６１１７００７９，６１２０２１５２，６１４７２２２９），ｔｈｅ　Ｓｃｉｅｎｃｅ　＆ Ｔｅｃｈｎｏｌｏｇｙ　Ｄｅｖｅｌｏｐｍｅｎｔ　Ｆｕｎｄ　ｏｆ　Ｓｈａｎｄｏｎｇ　Ｐｒｏｖｉｎｃｅ，Ｃｈｉｎａ（Ｎｏ．２０１４ＧＧＸ１０１０３５，２０１６ＺＤＪＳ０２Ａ１１），ｔｈｅ　Ｓｈａｎｄｏｎｇ　Ｐｒｏｖｉｎｃｉａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ，Ｃｈｉｎａ（Ｎｏ．ＢＳ２０１４ＤＸ０１３，ＺＲ２０１５ＦＭ０１３），ｔｈｅＯｐｅｎ　Ｐｒｏｊｅｃｔ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｅｍｂｅｄｄｅｄ　Ｓｙｓｔｅｍ　ａｎｄ　Ｓｅｒｖｉｃｅ　Ｃｏｍｐｕｔｉｎｇ　ｏｆ　Ｍｉｎｉｓｔｒｙ　ｏｆ　Ｅｄｕｃａｔｉｏｎ　ｉｎ　Ｔｏｎｇｊｉ　Ｕｎｉｖｅｒ－ｓｉｔｙ，Ｃｈｉｎａ（Ｎｏ．ＥＳＳＣＫＦ２０１４０３），ｔｈｅ　Ｓｈａｎｄｏｎｇ　Ｐｒｏｖｉｎｃｉａｌ　Ｐｏｓｔｄｏｃｔｏｒａｌ　Ｉｎｎｏｖａｔｉｏｎ　Ｐｒｏｊｅｃｔ，Ｃｈｉｎａ（Ｎｏ．２０１６０３０５６），ａｎｄ　ｔｈｅＳＤＵＳＴ　Ｒｅｓｅａｒｃｈ　Ｆｕｎｄ，Ｃｈｉｎａ（Ｎｏ．２０１５ＴＤＪＨ１０２）．基于序列移动距离的用户行为挖掘与相似度计算林泽东１，鲁法明１，段　华２＋（１．山东科技大学 信息科学与工程学院，山东　青岛　２６６５９０；２．山东科技大学 数学与系统科学学院，山东　青岛　２６６５９０）摘　要：为了对用户的行为进行相似性度量，从用户行为流程产生的行为序列出发计算用户行为的相似度。将推土机距离算法应用到用户行为相似度的计算领域，提出用户行为相似度计算的序列移动距离方法。首先定义了基于最长公共子序列的用户行为序列距离度量方法；其次定义了用户行为序列多重集之间距离的度量指标，在此基础上提出用户行为相似度计算的 ＳＭＤ 方法；最后提出行为序列多重集之间距离度量应遵循的基本准则。在人工和真实数据集上进行了实验，实验结果表明了所提方法的有效性。关键词：用户行为挖掘；用户行为相似度；相似性度量；ＥＭＤ 距离；序列移动距离中图分类号：ＴＰ３０１　　　文献标识码：ＡＵｓｅｒ　ｂｅｈａｖｉｏｒ　ｍｍｉｎｉｎｇ　ａｎｄ　ｓｉｍｉｌａｒｉｔｙ　ｃｏｍｐｕｔａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｓｅｑｕｅｎｃｅ　ｍｏｖｅｒｓ　ｄｉｓｔａｎｃｅＬＩＮ　Ｚｅｄｏｎｇ１，ＬＵ　Ｆａｍｉｎｇ１，ＤＵＡＮ　Ｈｕａ２＋（１．Ｃｏｌｌｅｇｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｈａｎｄｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｑｉｎｇｄａｏ　２６６５９０，Ｃｈｉｎａ；２．Ｃｏｌｌｅｇｅ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｓｙｓｔｅｍｓ　Ｓｃｉｅｎｃｅ，Ｓｈａｎｄｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｑｉｎｇｄａｏ　２６６５９０，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔｏ　ｍｅａｓｕｒｅ　ｔｈｅ　ｓｉｍｉｌａｒｉｔｙ　ｏｆ　ｕｓｅｒ　ｂｅｈａｖｉｏｒ，ｔｈｅ　ｕｓｅｒ　ｂｅｈａｖｉｏｒ　ｓｉｍｉｌａｒｉｔｙ　ｗａｓ　ｃａｌｃｕｌａｔｅｄ　ｆｒｏｍ　ｔｈｅ　ｐｅｒｓｐｅｃｔｉｖｅｏｆ　ｂｅｈａｖｉｏｒ　ｓｅｑｕｅｎｃｅ　ｇｅｎｅｒａｔｅｄ　ｂｙ　ｕｓｅｒｓ　ｂｅｈａｖｉｏｒ　ｐｒｏｃｅｓｓ．Ｓｐｅｃｉｆｉｃａｌｌｙ，Ｓｅｑｕｅｎｃｅ　Ｍｏｖｅｒｓ　Ｄｉｓｔａｎｃｅ（ＳＭＤ）ｍｅｔｈｏｄｗａｓ　ｐｒｏｐｏｓｅｄ　ｂｙ　ａｐｐｌｙｉｎｇ　Ｅａｒｔｈ　Ｍｏｖｅｒｓ　Ｄｉｓｔａｎｃｅ（ＥＭＤ）ａｌｇｏｒｉｔｈｍ　ｔｏ　ｔｈｅ　ｆｉｅｌｄ　ｏｆ　ｍｅａｓｕｒｉｎｇ　ｕｓｅｒ　ｂｅｈａｖｉｏｒ　ｓｉｍｉｌａｒｉ－ｔｙ．Ｔｈｅ　ｍｅｔｈｏｄ　ｔｏ　ｍｅａｓｕｒｅ　ｕｓｅｒ　ｂｅｈａｖｉｏｒ　ｓｅｑｕｅｎｃｅ　ｄｉｓｔａｎｃｅ　ｂａｓｅｄ　ｏｎ　ｌｏｎｇｅｓｔ　ｃｏｍｍｏｎ　ｓｕｂｓｅｑｕｅｎｃｅ　ｗａｓ　ｄｅｆｉｎｅｄ；ｔｈｅｎｔｈｅ　ｍｅｔｒｉｃｓ　ｄｉｓｔａｎｃｅ　ｂｅｔｗｅｅｎ　ｍｕｌｔｉｐｌｅ　ｓｅｔｓ　ｆｏｒ　ｕｓｅｒ　ｂｅｈａｖｉｏｒ　ｓｅｑｕｅｎｃｅ　ｗａｓ　ｄｅｆｉｎｅｄ，ａｎｄ　ＳＭＤ　ｍｅｔｈｏｄ　ｔｏ　ｍｅａｓｕｒｅ　ｕｓｅｒｂｅｈａｖｉｏｒ　ｓｉｍｉｌａｒｉｔｙ　ｗａｓ　ｐｒｏｐｏｓｅｄ；ｓｏｍｅ　ｂａｓｉｃ　ｐｒｉｎｃｉｐｌｅｓ　ｔｏ　ｍｅａｓｕｒｅ　ｔｈｅ　ｄｉｓｔａｎｃｅ　ｂｅｔｗｅｅｎ　ｍｕｌｔｉｐｌｅ　ｓｅｔｓ　ｆｏｒ　ｕｓｅｒ　ｂｅ－ｈａｖｉｏｒ　ｓｅｑｕｅｎｃｅ　ｗｅｒｅ　ｐｒｏｐｏｓｅｄ．Ｅｘｐｅｒｉｍｅｎｔｓ　ｏｎ　ｂｏｔｈ　ａｒｔｉｆｉｃｉａｌ　ａｎｄ　ｒｅａｌ　ｄａｔａ　ｓｅｔｓ　ｄｅｍｏｎｓｔｒａｔｅｄ　ｔｈｅ　ｅｆｆｅｃｔｉｖｅｎｅｓｓ　ｏｆｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｅｔｈｏｄ．Ｋｅｙｗｏｒｄｓ：ｕｓｅｒ　ｂｅｈａｖｉｏｒ　ｍｉｎｉｎｇ；ｕｓｅｒ　ｂｅｈａｖｉｏｒ　ｓｉｍｉｌａｒｉｔｙ；ｓｉｍｉｌａｒｉｔｙ　ｍｅａｓｕｒｅ；ｅａｒｔｈ　ｍｏｖｅｒｓ　ｄｉｓｔａｎｃｅ；ｓｅｑｕｅｎｃｅｍｏｖｅｒｓ　ｄｉｓｔａｎｃｅ计算机集成制造系统 第２３卷定理２　行为模式距离是一个度量。证明　行为模式距离本质上是一个运输总量为１的 ＥＭＤ 的一个特例。根据文献［６］的结论，若基距离是一个度量并且两个分布的总量相等，则 ＥＭＤ就是一个度量。在行为模式距离中，基距离是行为序列距离。定理１已经证明行为序列距离是一个度量，因此行为模式距离是一个度量。５．２　行为模式距离求解算法行为模式距离是 ＥＭＤ 的一个特例，也是一个产销平衡的运输问题，因此一定存在最优解。运输问题是最小费用流问题的一个特例，可以利用最小费用流问 题 的 求 解 方 法 进 行 求 解，具 体 求 解 过 程如下：算法２　Ｄｐａｔ（Ｐｕ，Ｐｖ）。输入：两个行为模式 Ｐｕ，Ｐｖ。输出：两个行为模式之间的距离。１．Ａ：＝｛ｐｉ｜（ｐｉ，ｗｐｉ）∈Ｐｕ｝，Ｂ：＝｛ｑｊ｜（ｑｊ，ｗｑｊ）∈Ｐｖ｝２．分别将 Ａ，Ｂ中的频次归一化，乘公共系数α使频次整数化３．ＦＯＲＥＡＣＨ（ｐｉ∈Ａ）　／／遍历 Ａ 中的序列，以序 列 为 节 点 构建运输费用网络４．　 建立顶点ｐｉ５．　 ＦＯＲＥＡＣＨ（ｑｊ∈Ｂ）６．　 　 建立顶点ｑｊ和 有 向 边（ｐｉ，ｑｊ），更 新 边（ｐｉ，ｑｊ）的 费 用ｃｉｊ：＝Ｄｓｅｑ（ｐｉ，ｑｊ）７．令数组ｂ：＝［ｗｐ１，…ｗｐｍ，－ｗｑ１，…－ｗｑｎ］８．ｂｍａｘ：＝ｍａｘ｛ｗｐｉ，ｗｑｊ｝，γ：＝２ｌｏｇ（ｂｍａｘ），ｆｉｊ：＝０９．若ｂ＝０，则转１７行，否则１０．　 选择一个ｐｉ∈Ａ，使ｂ［ｉ］≥γ１１．　 选择一个ｑｊ∈Ｂ，使ｂ［ｉ＋ｊ－１］≤－γ１２．　 若不存在这样的ｐｉ或ｑｊ，则转１５行１３．在残留网络［１２］Ｇｆ 中寻找一条费用最小边１４．ｂ［ｉ］：＝ｂ［ｉ］－γ，ｂ［ｉ＋ｊ－１］：＝ｂ［ｉ＋ｊ－１］＋γ，ｆｉｊ：＝ｆｉｊ＋γ，转９行１５．若γ＝１，则转１７行１６．　 否则，γ：＝γ／２，转９行１７．返回∑ｍｉ＝１∑ｎｊ＝１ｆｉｊｃｉｊα算法２主要包括构造运输费用网络［１２］（第３～６行）和求解运输费用网络最小费用流（第７～１７行）两个步骤。运输费用网络构造过程就是根据两个行为模式构造一个运输费用网络。其中，节点表示行为模式中的频繁项行为序列，两个行为模式中的任意行为序列之间都会建立有向边，边的运输代价为两个行为序列之间的距离。运输费用网络构造过程中的计算代价主要表现在计算边的费用，而计算边的费用主要是求解两个序列的最长公共子序列。根据文献［１３］，求解两个序列的最长公共子序列的时间复杂度为 Ｏ（ｒｌ），其中：ｒ为两个序列最长公共子序列的长度，ｌ为两个序列的最大长度。因此，构造运输费用网络的最坏情况时间复杂度为Ｏ（ｐｑｍｎ），其中：ｎ和 ｍ 分别为两个行为模式中行为序列的个数，ｐ为所有最长公共子序列的最大长度，ｑ为所有序列的最大长度。最小费用流求解主要利用容量缩放增广路算法（ＣａｐａｃｉｔｙＳｃａｌｉｎｇ　Ａｌｇｏｒｉｔｈｍ，ＣＳＡ）［１２］求最小费用流问题，该网络的最小运输费用即为两个行为模式的距离。根据文献［１２］，求解最小费用流的时间复杂度为 Ｏ（ｓ（ｍｎ＋ｓｌｏｇ　ｓ）ｌｏｇ（２＋ｂｍａｘ）），其中：ｓ＝ｍ＋ｎ，ｎ和 ｍ 分别为两个行为模式中行为序列的个数，ｂｍａｘ为两个用户行为序列的最大频次。因此，行为模式距离计算过程的最坏情况时间复杂度为 ｍａｘ｛Ｏ（ｐｑＮ２），Ｏ（Ｎ２（Ｎ＋２ｌｏｇ　２　Ｎ）ｌｏｇ（２＋ｂｍａｘ））｝，其中 Ｎ 为两个用户的用户行为的最大数目，其他参数同上。６　实验评测基于频繁序列模式的 ＣＰＳ方法在用户相似度计算方面取得了丰富的成果，文献［７］已经对 ＣＰＳ方法与之前的相关工作进行了对比，并展示了 ＣＰＳ方法的优越性。下面将本文方法与 ＣＰＳ进行对比分析，以显示本文工作的有效性。首先分析两者在距离度量准则满足性和算法复杂度方面的表现；然后以２０１４年成都电子科技大学主办的大数据挖掘大赛“学生成绩排名预测”中的公开数据为应用实例（ｈｔｔｐ：／／ｗｗｗ．ｐｋｂｉｇｄａｔａ．ｃｏｍ／ｃｏｍｍｏｎ／ｃｏｍｐｅｔｉ－ｔｉｏｎ／１２７．ｈｔｍｌ），对比两者在学 生 日常行为 相似度检索准确率方面的表现。６．１　ＳＭＤ与 ＣＰＳ对基本准则满足情况的对比距离与相似度是衡量两个对象差异程度的两个指标，两者可以相互转换。关于距离存在一些公认的基本准则，下面分别分析 ＳＭＤ 和 ＣＰＳ对这些基本准则的满足情况。定义６　基本准则。设 Ｐｕ和Ｐｖ为两个行为模式，则 Ｐｕ和Ｐｖ的行为模式距离Ｄｐａｔ（Ｐｕ，Ｐｖ）应满６０１４第５期 林泽东 等：基于序列移动距离的用户行为挖掘与相似度计算足以下 基 本 准 则：①Ｄｐａｔ（Ｐｕ，Ｐｖ）∈ ［０，１］；②Ｄｐａｔ（Ｐｕ，Ｐｖ）＝１ＳＳ（Ｐｕ）∩ＳＳ（Ｐｖ）＝ ；③Ｄｐａｔ（Ｐｕ，Ｐｖ）＝０；④Ｄｐａｔ（Ｐｕ，Ｐｖ）是一个度量。其中：Ｐｕ表示Ｐｕ中所有行为序列构成的集合，即Ｐｕ＝｛Ｘ｜（Ｘ，β）∈Ｐｕ｝；ＳＳ（Ｓ）表示由行为序列集合Ｓ 中行为序列的所有子序列构成的集合。准则１规定了该距离标准值的范围。准则２说明了当两个用户没有任何公共行为子序列时，两个用户之间的距离为１。准则３说明了两个行为模式完全相同时两者之间的距离为０。准则４要求该距离标准是一个度量，即满足非负性、对称性和三角不等式３个度量公理。距离标准是否为一个度量对于该距离标准应用非常重要，因为度量对很多算法是必须的。基本准则中没有定义类似文献［７］中规则７的准则，其原因是规则７的定义不够全面，只考虑了序列，而未考虑序列频次信息。由于 ＣＰＳ方法计算的结果是相似度，为了对比分析两种方法对距离基本准则的满足情况，下面采用最常用的相似度与距离之和为１的方法将相似度转化为距离。实验所构造的人工数据集包括７个行为模式，其中前５个来自文献［７］。Ｐｕ１＝｛（Ａ，３），（Ｂ，３），（Ｃ，４），（ＡＢ，１）｝；Ｐｕ２＝｛（Ａ，２），（Ｂ，２），（Ｃ，４），（ＡＢ，２）｝；Ｐｕ３＝｛（Ａ，１），（Ｂ，１），（Ｃ，４），（ＡＢ，３）｝；Ｐｕ４＝｛（Ａ，１），（Ｂ，１），（Ｃ，４），（ＢＡ，３）｝；Ｐｕ５＝｛（Ａ，１），（Ｄ，１），（Ｃ，４），（ＡＤ，３）｝；Ｐｕ６＝｛（ＡＢＣＤＥＦＧＨＩＪ，１）｝；Ｐｕ７＝｛（Ａ，１）｝。实验中最小频次阈值设置为 １，两种方法计算的行为模式距离矩阵如表１所示。表１　ＳＭＤ和 ＣＰＳ得到的行为模式距离矩阵ＳＭＤ　 ＣＰＳＰｕ１　Ｐｕ２　Ｐｕ３　Ｐｕ４　Ｐｕ５　Ｐｕ６　Ｐｕ７　Ｐｕ１　Ｐｕ２　Ｐｕ３　Ｐｕ４　Ｐｕ５　Ｐｕ６　Ｐｕ７Ｐｕ１　０　 ０．０９　 ０．２０　 ０．２５　 ０．４１　 ０．８９　 ０．６８　 ０　 ０．０４　 ０．０７　 ０．２４　 ０．５　 ０．９９　 ０．７９Ｐｕ２　０．０９　 ０　 ０．１１　 ０．２４　 ０．３８　 ０．８８　 ０．７０　 ０．０４　 ０　 ０．０３　 ０．２９　 ０．５３　 ０．９９　 ０．８０Ｐｕ３　０．２０　 ０．１１　 ０　 ０．２２　 ０．３３　 ０．８７　 ０．７２　 ０．０７　 ０．０３　 ０　 ０．３３　 ０．５６　 ０．９９　 ０．８１Ｐｕ４　０．２５　 ０．２４　 ０．２２　 ０　 ０．３３　 ０．９０　 ０．７２　 ０．２４　 ０．２９　 ０．３３　 ０　 ０．５６　 ０．９９　 ０．８１Ｐｕ５　０．４１　 ０．３８　 ０．３３　 ０．３３　 ０　 ０．８７　 ０．７２　 ０．５　 ０．５３　 ０．５６　 ０．５６　 ０　 ０．９９　 ０．８１Ｐｕ６　０．８９　 ０．８８　 ０．８７　 ０．９０　 ０．８７　 ０　 ０．９０　 ０．９９　 ０．９９　 ０．９９　 ０．９９　 ０．９９　 ０　 ０．９９Ｐｕ７　０．６８　 ０．７０　 ０．７２　 ０．７２　 ０．７２　 ０．９０　 ０　 ０．７９　 ０．８０　 ０．８１　 ０．８１　 ０．８１　 ０．９９　 ０从表１所示的实验结果可以发现两种方法的相同之处：①对于相同的行为模式，两种方法得到的行为模式之间的距离均为０。②两种方法计算出的结果绝对数值没有特别离谱的情况，数值大小差异不大。因此，从文献［７］的人工数据集的实验结果来看，ＳＭＤ 方法表现得也不错。然而，两种方法有两个明显的不同之处：①从表１的 ＣＰＳ方法得到的行为模 式 距 离 的 结 果 看，Ｄｐａｔ（Ｐｕ２，Ｐｕ３）＋Ｄｐａｔ（Ｐｕ２，Ｐｕ４）＜Ｄｐａｔ（Ｐｕ３，Ｐｕ４），说明 ＣＰＳ方法不满足三角不等式，因此 ＣＰＳ方法不满足准则４。②从 Ｐｕ６和 Ｐｕ７的相似度结果看，ＳＭＤ 得到的相似度结果是 ０．１，而 ＣＰＳ的相似度结果是０．０１，两种方法得到的结果大小有１０ 倍的差距。ＣＰＳ 结果的输出明显偏小，原因是 ＣＰＳ 在 计算频繁序 列模式产生的过 程 中，Ｐｕ６中的行为序列产生了许多子序列，子序列参与相似度计算，使最终结果存在偏差。下面验证ＳＭＤ 方法符合提出的基本准则。很容易验证ＳＭＤ 方法满足基本原则１～原则３，定理２验证了ＳＭＤ 方法满足准则４。为了验证准则５，假设 ＰｖＰｕＰｗ，Ｐｗ相比Ｐｕ增加了非公共行为序列或公共行为序列的频次，并且增加部分的单位转换费用为 Ｐｖ和 Ｐｗ中 行 为 序 列 距 离 的 最 大 值。相对于 Ｐｖ转换为Ｐｕ，Ｐｖ转换为Ｐｗ的单位转换费用有所增加。因此，ＳＭＤ 满足准则５。通过对实验结果的比较分析，将两种方法对基本准则的满足情况进行总结，如表２所示。表２　ＳＭＤ与 ＣＰＳ对准则满足情况对比准则１ 准则２ 准则３ 准则４ 准则５ＳＭＤ √ √ √ √ √ＣＰＳ √ √ √ × √６０１５