8. 顺序聚类分析算法（Microsoft Sequence Clustering Algorithm）
a.
目的
Microsoft 顺序聚类分析算法是由 Microsoft SQL Server Analysis Services 提供的一种顺序分析算法。 您可以使用该算法来研究包含可通过下面的路径或“顺序”链接到的事件的数据。 该算法通过对相同的顺序进行分组或分类来查找最常见的顺序。
该算法在许多方面都类似于 Microsoft 聚类分析算法。 不过，Microsoft 顺序聚类分析算法不是查找包含类似属性的事例的分类，而是查找顺序中包含类似路径的事例的分类。
b.
原理
Microsoft 顺序聚类分析算法是一种混合算法，它综合了聚类分析方法和 Markov 链分析，以识别分类及其顺序。Microsoft 顺序聚类分析算法的特点之一是使用顺序数据。 此数据通常表示数据集中状态之间的一系列事件或转换，例如，特定用户的一系列产品购买或 Web 点击操作。 该算法会检查所有转换概率，并测量数据集中所有可能顺序之间的差异或距离，以确定最好使用哪些顺序作为聚类分析的输入。 在创建候选顺序列表后，该算法将该顺序信息用作聚类分析的 EM 方法的输入。
c.
方法
Microsoft 顺序聚类分析模型使用 Markov 模型来识别序列并确定序列的概率。 Markov 模型是存储不同状态之间的转换的定向图形。 Microsoft 顺序聚类分析算法使用 N 阶 Markov 链，而不使用隐 Markov 模型。
您可由 Markov 链中的阶数知道有多少个状态用于确定当前状态的概率。 在一阶 Markov 模型中，当前状态的概率仅取决于前一个状态。 在二阶 Markov 链中，当前状态的概率取决于前两个状态。其他情况下的概率可依此类推。 对于每个 Markov 链，转换矩阵都会存储每种状态组合的转换。 当 Markov 链的长度增加时，转换矩阵的规模也会呈指数增长，但同时会变得非常稀疏。 处理时间也会按比例增加。
点击流分析法是一种分析网站网页的访问情况的方法，它可帮助进行链的可视化处理。 对于每个会话，用户都会创建一个很长的点击序列。 通过创建模型来分析用户在网站中的行为时，用于定型的数据集就是一个 URL 序列；该序列可转换为一个图形，其中包含相同点击路径的所有实例的计数。 例如，该图形可包含用户从第 1 页转到第 2 页的概率 (10%) 以及用户从第 1 页转到第 3 页的概率 (20%)，其余依此类推。 当将所有可能的路径以及路径片段整合到一起时，就可获得一张图，它比所观察到的任何单个路径都长，而且更复杂。
默认情况下，Microsoft 顺序分析和聚类分析算法使用聚类分析的 Expectation Maximization (EM) 方法。 聚类分析的目标是序列属性和非序列属性。 每个分类都是利用概率分布随机选择的。 每个分类都具有表示完整路径集的 Markov 链以及包含序列状态转换和概率的矩阵。 算法会基于初始分布，使用 Bayes 定理来计算所有属性（包括序列）属于特定分类的概率。
Microsoft 顺序分析和聚类分析算法支持在模型中使用其他非序列属性。 这意味着将会将这些非序列属性与序列属性组合起来，创建具有相似属性的事例分类，就像典型的聚类分析模型中一样。
与典型的聚类分析模型相比，顺序分析和聚类分析模型通常会创建更多的分类。 因此，Microsoft 顺序分析和聚类分析算法会执行“分类分解”，以基于序列属性和其他属性分解分类。
顺序聚类分析在生成序列时不会调用功能选择，但可以通过设置参数 MINIMUM_SUPPORT 和 MINIMUM_PROBABILIITY 的值来控制算法的行为。在聚类分析阶段则会应用功能选择。功能选择的方法是兴趣性分数。因为尽管聚类分析算法可能使用离散算法或离散化算法，但每个属性的分数仍将作为间距进行计算，并且是连续的，因此使用兴趣性分数。
d.
数据要求
The case table must have a case ID column. Optionally the case
table can contain other columns that store attributes about the case.
The Microsoft Sequence Clustering algorithm requires sequence
information, stored as a nested table. The nested table must have a single Key
Sequence column. A Key Sequence column can contain any type of data that can be sorted,
including string data types, but the column must contain unique values for each
case. Moreover, before you process the model, you must ensure that both the
case table and the nested table are sorted in ascending order on the key that
relates the tables.
意思是说，事例表必须具有事例 ID 列。 此外，事例表还可以包含其他存储事例属性的列。这个算法要求序列信息以嵌套表的形式存储。 该嵌套表必须包含一个 Key Sequence 列。 Key Sequence 列可包含可以存储的任何类型的数据（包括字符串数据类型），还必须包含每个事例的唯一值。 而且，在处理模型之前，您必须确保事例表和嵌套表要按与其相关的键的升序存储。
· 单个 key 列 - 顺序聚类分析模型需要一个用于标识记录的键。
· 顺序列 - 对于顺序数据，模型必须具有包含顺序 ID 列的嵌套表。 顺序 ID 可以为任何可排序的数据类型。 例如，可以使用数据类型为网页标识符、整数或文本字符串的列，只要该列可以标识顺序中的事件。 每个顺序只允许有一个顺序标识符，且每个模型中只允许有一种类型的顺序。
· 可选的非顺序属性 - 该算法支持添加与顺序无关的其他属性。 这些属性可以包含嵌套列。
例如，在Adventure Works Cycles 网站的示例中，顺序聚类分析模型可以包含订单信息（作为事例表）、每个订单的具体客户的人口统计数据（作为非顺序属性）以及包含客户浏览网站和将商品放入购物车的顺序的嵌套表（作为顺序信息）。
注意：如果创建使用 Microsoft 顺序分析算法、但却不使用序列的模型，则生成的模型将不包含任何序列，而仅会基于模型中包含的其他属性对事例进行分类。
e.
查看模型
该算法创建的挖掘模型在数据中包含了最常见顺序的说明。 若要浏览该模型，可以使用 Microsoft 序列分类查看器。 查看顺序聚类分析模型时，Analysis Services 显示包含多个转换的分类。
f.
预测
对模型进行定型后，结果将存储为一组模式。 您可以使用数据中最常见顺序的说明来预测新顺序的下一个可能步骤。 但是，因为该算法包括了其他列，所以您可以使用得到的模型来识别顺序数据和非顺序输入之间的关系。 例如，您可以向模型添加客户的人口统计数据，还可以进行针对特定客户群体的预测。 可以自定义预测查询，以便返回数目可变的预测或返回说明性的统计信息。
g.
自定义参数与性能优化
i. 设置算法参数
1.
CLUSTER_COUNT
指定将由算法生成的大致分类数。 如果无法基于相应的数据生成该大致数目的分类，则算法将生成尽可能多的分类。 如果将 CLUSTER_COUNT 设置为 0，则算法将会使用试探性方法确定要生成的分类的最佳数量。默认值为 10。
注意：指定一个作为对算法的提示的非零数，算法将会查找该指定数，但最终的查找结果可能会大于或小于所指定的数。
2.
MINIMUM_SUPPORT
指定支持属性创建分类所需的最小事例数。默认值为 10。
3.
MAXIMUM_SEQUENCE_STATES
指定一个顺序可以拥有的最大状态数。
将该值设置为大于 100 的数将导致算法创建一个不提供有意义的信息的模型。
默认值为 64。
4.
MAXIMUM_STATES
指定算法支持的非序列属性的最大状态数。 如果非序列属性的状态数大于最大状态数，则算法将使用该属性最常见的状态，并将视剩余状态为 Missing。默认值为 100。
ii. 建模标志
支持将以下建模标志与 Microsoft 顺序分析和聚类分析算法配合使用。
1.
NOT NULL
指示该列不能包含 Null。 如果 Analysis Services 在模型定型过程中遇到 Null 值，将会导致错误。适用于挖掘结构列。
2.
MODEL_EXISTENCE_ONLY
表示列将被视为具有两个可能状态：Missing 和 Existing。 Null 视为 Missing 值。
适用于挖掘模型列。
小结： Microsoft 顺序聚类分析算法支持多种处理优化方法：
·
通过设置 CLUSTER_COUNT 参数的值可以控制生成的分类数。
·
通过增大 MINIMUM_SUPPORT 参数的值可以减少包含为属性的序列的数量。 这会导致删除一些罕见的序列。
·
在处理模型之前，通过对相关属性进行分组可以降低复杂性。
通常，您可以使用多种方法来优化 n 阶 Markov 链模式的性能：
·
控制可能的序列的长度。
·
以编程方式减小 n 值。
·
仅存储超出指定阈值的概率。
h.
应用
Adventure Works Cycles 网站收集有关站点用户访问哪些页面以及页面访问顺序的信息。 因为该公司提供在线订购，所以用户必须登录到此站点。 这可以为该公司的各个客户配置文件提供点击信息。 通过对此数据使用 Microsoft 顺序分析和聚类分析算法，该公司可以查找具有相同的点击模式或点击顺序的客户组或分类。 然后，该公司可以使用这些分类来分析用户如何在网站中移动，来识别哪些页面与特定商品的销售关系最密切及预测接下来哪些页面最有可能被访问。
通常应用该算法的的示例有：
·
用户在导航或浏览网站时创建的单击路径。
·
列出发生事故（如硬盘故障或服务器死锁）之前的事件的日志。
·
说明客户将商品添加到在线零售商的购物车中的顺序的事务记录。
·
根据一段时间内的客户（或患者）交互来预测服务取消或其他不良结果的记录。
