 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
［推荐］Kaldi会议记录
下载积分：1500
内容提示：［推荐］Kaldi会议记录
文档格式：PDF|
浏览次数：1|
上传日期： 05:48:06|
文档星级：
该用户还上传了这些文档
［推荐］Kaldi会议记录
官方公共微信基于聚类分析和决策树算法的服装销售预测模型_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
您可以上传图片描述问题
联系电话：
请填写真实有效的信息，以便工作人员联系您，我们为您严格保密。
基于聚类分析和决策树算法的服装销售预测模型
|0|0|暂无简介
北京龙源网通电子商务有限公司|
总评分0.0|
试读已结束，如果需要继续阅读或下载，敬请购买
定制HR最喜欢的简历
你可能喜欢1671人阅读
Automatic Speech Recognition（38）
最近一直在看KALDI官网的资料，在看的同时加一些注解，方便自己的理解。
我的学习笔记基本上都是转自KALDI官方网址http://kaldi.sourceforge.net，并加上我的注解，特此说明。
Clustering mechanisms in Kaldi
注：这一部分主要介绍了Kaldi中的聚类机制
See Classes and functions related to clustering for a list of classes and functions involved in this. This page does not cover phonetic decision-tree clustering (seeDecision
tree internals and How decision trees are used in Kaldi), although classes and functions introduced in this page are used in lower levels of the phonetic clustering code.
注：这部分不涉及音素决策树的聚类而是比较低级别的音素聚类
The Clusterable interface
The Clusterable class is a pure virtual class from which the classGaussClusterable inherits (GaussClusterable represents Gaussian statistics). In
future we will add other types of clusterable object that inherit fromClusterable. The reason for the
Clusterable class is to allow us to use generic clustering algorithms.
注：主要的类，Clusterable，GaussClusterable
The central notion of theClusterable interface is that of adding statistics together, and measuring the objective function. The notion of distance between twoClusterable
objects is derived from measuring the objective function of the two objects separately, then adding them together and measuring th the negative of the decrease in objective function gives the notion of distance.
Examples of
Clusterable classes that we intend to add at some point include mixture-of-Gaussian statistics derived from posteriors of a fixed, shared, mixture-of-Gaussians model, and also collections of counts of discrete observations (the objective function would
be equivalent to the negated entropy of the distribution, times the number of counts).
An example of getting a pointer of type Clusterable* (which is actually of theGaussClusterable type) is as follows:
Vector&BaseFloat& x_stats(10), x2_stats(10);
BaseFloat count = 100.0, var_floor = 0.01;
// initialize x_stats and x2_stats e.g. as
// x_stats = 100 * mu_i, x2_stats = 100 * (mu_i*mu_i + sigma^2_i)
Clusterable *cl = new GaussClusterable(x_stats, x2_stats, var_floor, count);Clustering algorithms
We have implemented a number of generic clustering algorithms. These are listed inAlgorithms for clustering. A data-structure that is used heavily in these algorithms is a vector
of pointers to theClusterable interface class:
std::vector&Clusterable*& to_be_The index into the vector is the index of the &point& to be clustered.
K-means and algorithms with similar interfaces
A typical example of calling clustering code is as follows:
std::vector&Clusterable*& to_be_
// initialize &to_be_clustered& somehow ...
std::vector&Clusterable*&
int32 num_clust = 10; // requesting 10 clusters
ClusterKMeansO // all default.
std::vector&int32&
ClusterKMeans(to_be_clustered, num_clust, &clusters, &assignments, opts);After the clustering code is called, &assignments& will tell you for each item in &to_be_clustered&, which cluster it is assigned to. The ClusterKMeans()algorithm is
fairly efficient even for la click the function name for more details.
There are two more algorithms that have a similar interface toClusterKMeans(): namely,
ClusterBottomUp() and ClusterTopDown(). Probably the more useful one is
ClusterTopDown(), which should be more efficient thanClusterKMeans()
if the number of clusters is large (it does a binary split, and then does a binary split on the leaves, and so on). Internally it callsTreeCluster(), see below.
Tree clustering algorithm
The function
TreeCluster() clusters points into a binary tree (the leaves won't necessarily have just one point each, you can specify a maximum number of leaves). This function is useful, for instance, when building regression trees for adaptation. See that function's
documentation for a detailed explanation of its output format. The quick overview is that it numbers leaf and non-leaf nodes in topological order with the leaves first and the root last, and outputs a vector that tells you for each node what its parent is.
如果有什么问题或者有关于Kaldi的评论亦或是添加Kaldi使用者的邮件列表可以给这个地址发邮件：
或者访问：
http://sourceforge.net/p/kaldi/discussion/
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：162415次
积分：2725
积分：2725
排名：第10983名
原创：113篇
转载：12篇
评论：37条
(7)(3)(1)(2)(1)(3)(4)(1)(8)(14)(3)(3)(3)(7)(4)(12)(3)(13)(20)(14)一小时了解数据挖掘⑤数据挖掘步骤＆常用的聚类、决策树和CRISP
我的图书馆
一小时了解数据挖掘⑤数据挖掘步骤＆常用的聚类、决策树和CRISP
数据挖掘的一般步骤
从数据本身来考虑，数据挖掘通常需要有信息收集、数据集成、数据规约、数据清理、数据变换、数据挖掘实施过程、模式评估和知识表示8个步骤。
步骤（1）信息收集：根据确定的数据分析对象，抽象出在数据分析中所需要的特征信息，然后选择合适的信息收集方法，将收集到的信息存入数据库。对于海量数据，选择一个合适的数
据存储和管理的数据仓库是至关重要的。
步骤（2）数据集成：把不同来源、格式、特点性质的数据在逻辑上或物理上有机地集中，从而为企业提供全面的数据共享。
步骤（3）数据规约：如果执行多数的数据挖掘算法，即使是在少量数据上也需要很长的时间，而做商业运营数据挖掘时数据量往往非常大。数据规约技术可以用来得到数据集的规约表示，它小得多，但仍然接近于保持原数据的完整性，并且规约后执行数据挖掘结果与规约前执行结果相同或几乎相同。
步骤（4）数据清理：在数据库中的数据有一些是不完整的（有些感兴趣的属性缺少属性值）、含噪声的（包含错误的属性值），并且是不一致的（同样的信息不同的表示方式），因此需要进行数据清理，将完整、正确、一致的数据信息存入数据仓库中。不然，挖掘的结果会差强人意。
步骤（5）数据变换：通过平滑聚集、数据概化、规范化等方式将数据转换成适用于数据挖掘的形式。对于有些实数型数据，通过概念分层和数据的离散化来转换数据也是重要的一步。
步骤（6）数据挖掘过程：根据数据仓库中的数据信息，选择合适的分析工具，应用统计方法、事例推理、决策树、规则推理、模糊集，甚至神经网络、遗传算法的方法处理信息，得出有
用的分析信息。
步骤（7）模式评估：从商业角度，由行业专家来验证数据挖掘结果的正确性。
步骤（8）知识表示：将数据挖掘所得到的分析信息以可视化的方式呈现给用户，或作为新的知识存放在知识库中，供其他应用程序使用。
数据挖掘过程是一个反复循环的过程，每一个步骤如果没有达到预期目标，都需要回到前面的步骤，重新调整并执行。不是每件数据挖掘的工作都需要这里列出的每一步，例如在某个工作
中不存在多个数据源的时候，步骤（2）便可以省略。步骤（3）数据规约、步骤（4）数据清理、步骤（5）数据变换又合称数据预处理。在数据挖掘中，至少60%的费用可能要花在步骤（1）信息收集阶段，而其中至少60%以上的精力和时间花在了数据预处理过程中。
几个数据挖掘中常用的概念
除了之前我们提到的，还有一些概念是我们在数据挖掘中常用的，比如聚类算法、时间序列算法、估计和预测以及关联算法等。我们将在本节中介绍几个常用概念以加深读者对数据挖
掘的理解。
所谓聚类，就是类或簇（Cluster）的聚合，而类是一个数据对象的集合。
和分类一样，聚类的目的也是把所有的对象分成不同的群组，但和分类算法的最大不同在于采用聚类算法划分之前并不知道要把数据分成几组，也不知道依赖哪些变量来划分。
聚类有时也称分段，是指将具有相同特征的人归结为一组，将特征平均，以形成一个“特征矢量”或“矢心”。聚类系统通常能够把相似的对象通过静态分类的方法分成不同的组别或者更多的子集（Subset），这样在同一个子集中的成员对象都有相似的一些属性。聚类被一些提供商用来直接提供不同访客群组或者客户群组特征的报告。聚类算法是数据挖掘的核心技术之一，而除了本身的算法应用之外，聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。
下图是聚类算法的一种展示。图中的Cluster1和Cluster2分别代表聚类算法计算出的两类样本。打“+”号的是Cluster1，而打“○”标记的是Cluster2。
在商业中，聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体，并且概括出每一类消费者的消费模式或者消费习惯。它作为数据挖掘中的一个模块，可以作为一个单独的工具以发现数据库中分布的一些深层次的信息，或者把注意力放在某一个特定的类上以作进一步的分析并概括出每一类数据的特点。
在商业中，聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体，并且概括出每一类消费者的消费模式或者消费习惯。它作为数据挖掘中的一个模块，可以作为一个单独的工具以发现数据库中分布的一些深层次的信息，或者把注意力放在某一个特定的类上以作进一步的分析并概括出每一类数据的特点。
聚类分析的算法可以分为划分法（Partitioning Methods）、 层次法（Hierarchical Methods）、基于密度的方法（Density-Based Methods）、基于网格的方法（Grid-Based Methods）和基于模型的方法（Model-Based Methods）等。
比如，下面几个场景比较适合应用聚类算法，同时又有相应的商业应用：
哪些特定症状的聚集可能预示什么特定的疾病？
租同一类型车的是哪一类客户？
网络游戏上增加什么功能可以吸引哪些人来？
哪些客户是我们想要长期保留的客户？
聚类算法除了本身的应用之外还可以作为其他数据挖掘方法的补充，比如聚类算法可以用在数据挖掘的第一步，因为不同聚类中的个体相似度可能差别比较大。例如，哪一种类的促销对客户响应最好？对于这一类问题，首先对整个客户做聚集，将客户分组在各自的聚集里，然后对每个不同的聚集，再通过其他数据挖掘算法来分析，效果会更好。
后面的文章中我们还会详细介绍聚类算法是如何实现的。本文中多次提到的RFM模型也是基于聚类算法的数据挖掘模型。而在营销领域的客户关系管理中，RFM聚类模型也是最经常被使用的一种模型。
估测和预测
估测（Estimation）和预测（Prediction）是数据挖掘中比较常用的应用。估测应用是用来猜测现在的未知值，而预测应用是预测未来的某一个未知值。估测和预测在很多时候可以使用同样的算法。估测通常用来为一个存在但是未知的数值填空，而预测的数值对象发生在将来，往往目前并不存在。举例来说，如果我们不知道某人的收入，可以通过与收入密切相关的量来估测，然后找到具有类似特征的其他人，利用他们的收入来估测未知者的收入和信用值。还是以某人的未来收入为例来谈预测，我们可以根据历史数据来分析收入和各种变量的关系以及时间序列的变化，从而预测他在未来某个时间点的具体收入会是多少。
估测和预测在很多时候也可以连起来应用。比如我们可以根据购买模式来估测一个家庭的孩子个数和家庭人口结构。或者根据购买模式，估测一个家庭的收入，然后预测这个家庭将来最需要的产品和数量，以及需要这些产品的时间点。
对于估测和预测所做的数据分析可以称作预测分析（Predictive Analysis），而因为应用非常普遍，现在预测分析被不少商业客户和数据挖掘行业的从业人员当作数据挖掘的同义词。
我们在数据分析中经常听到的回归分析（Regression Analysis）就是经常被用来做估测和预测的分析方法。所谓回归分析，或者简称回归，指的是预测多个变量之间相互关系的技术，而这门技术在数据挖掘中的应用是非常广泛的。
在所有的数据挖掘算法中，最早在 提到的决策树可能是最容易让人理解的数据挖掘过程。决策树本质上是导致做出某项决策的问题或数据点的流程图。比如购买汽车的决策树可以从是否需要2012年的新型汽车开始，接着询问所需车型，然后询问用户需要动力型车还是经济型车等，直到确定用户所最需要的车为止。决策树系统设法创建最优路径，将问题排序，这样，经过最少的步骤，便可以做出决定。
据统计，在2012年，被数据挖掘业者使用频率最高的三类算法是决策树、回归和聚类分析。而且因为决策树的直观性，几乎所有的数据挖掘的专业书籍都是从某一个决策树算法开始讲起的：如ID3/C4.5/C5.0，CART，QUEST，CHAID等。
有些决策树做得很精细，用到了数据大部分的属性，这时，我们可能闯入了一个误区，因为在决策树算法上我们需要避免的一个问题是把决策树构建得过大，过于复杂。过于复杂的决策树往往会过度拟合（Over-Fitting），不稳定，而且有时候无法诠释。
这时我们可以把一棵大的决策树分解成多棵较小的决策树来解决这一问题。
我们来看一个商用的决策树实例。下图中展示的是用IBM SPSS Modeler数据挖掘软件构建的一棵决策树，是美国商业银行用以判断客户的信用等级的决策树模型。
上图是根据收入、信用卡数量和年龄构建的决策树，并以80%的准确率作为划分的阈值。第一个分支查的是收入，设立了两个关键数据分隔点，按照收入把人群先划分成3组：低收入、中等收入和高收入。其中低收入的节点直接变成叶子节点，这组人中82.0976%的人的信用等级是差的（Bad），而且信用卡个数或者年龄对信用等级的分类没有帮助。决策树的第二层判断是根据已经拥有的信用卡个数。以此作为判断，高收入人群可以再做划分。其中拥有卡个数在5个或以上的82.4176%信用等级是优质的（Good），而拥有卡的数量在5张以下的，高达96.8944%的人信用等级是优质的。因为这棵树一共有6个叶子节点，所我们最终划分出6组人群，其中有一组信用等级为优质的人群占比56.3147%，是无法判断的。其中在数据上表现最好的是高收入而信用卡个数在5张以下的人，把他们判断为优质信用等级有96.8944%的准确率。
如果我们手里还有别的数据，比如是否有房有车，是否结婚等，那么通过测试，可以进一步提高这棵决策树的精度。
1999年，在欧盟（European Commission）的资助下，由SPSS、DaimlerChrysler、NCR和OHRA发起的CRISP-DM Special Interest Group 组织开发并提炼出CRISP-DM（CRoss-Industry Standard Process for Data Mining），进行了大规模数据挖掘项目的实际试用。
CRISP-DM提供了一个数据挖掘生命周期的全面评述。它包括项目的相应周期，它们的各自任务和这些任务的关系。在这个描述层，识别出所有关系是不可能的。所有数据挖掘任务之间关系的存在是依赖用户的目的、背景和兴趣，最重要的还有数据。SIG组织已经发布了CRISP-DM Process Guide and User Manual的电子版。CRISP-DM的官方网址是。在这个组织中，除了SPSS是数据挖掘软件提供商，其他的几个发起者都是数据挖掘的应用方。所以CRISP-DM和SPSS自有开发的SPSS Modeler契合度非常好。
一个数据挖掘项目的生命周期包含六个阶段。这六个阶段的顺序是不固定的，我们经常需要前后调整这些阶段。这依赖每个阶段或是阶段中特定任务的产出物是否是下一个阶段必须的输入，下图中箭头指出了最重要的和依赖度高的阶段关系。
上中最外面这一圈表示数据挖掘自身的循环本质，每一个解决方案发布之后代表另一个数据挖掘的过程也已经开始了。在这个过程中得到的知识可以触发新的，经常是更聚焦的商业问题。后续的过程可以从前一个过程中得到益处。
我们把CRISP-DM的数据挖掘生命周期中的六个阶段，也就是上图中的概念解释如下：
业务理解（Business Understanding）
最初的阶段集中在理解项目目标和从业务的角度理解需求，同时将这个知识转化为数据挖掘问题的定义和完成目标的初步计划。
数据理解（Data Understanding）
数据理解阶段从初始的数据收集开始，通过一些活动的处理，目的是熟悉数据，识别数据的质量问题，首次发现数据的内部属性，或是探测引起兴趣的子集去形成隐含信息的假设。
数据准备（Data Preparation）
数据准备阶段包括从未处理的数据中构造最终数据集的所有活动。这些数据将是模型工具的输入值。这个阶段的任务能执行多次，没有任何规定的顺序。任务包括表、记录和属性的选择，以及为模型工具转换和清洗数据。
建模（Modeling）
在这个阶段，可以选择和应用不同的模型技术，模型参数被调整到最佳的数值。一般，有些技术可以解决一类相同的数据挖掘问题。有些技术在数据形成上有特殊要求，因此需要经常跳回到数据准备阶段。
评估（Evaluation）
到这个阶段，你已经从数据分析的角度建立了一个高质量显示的模型。在开始最后部署模型之前，重要的事情是彻底地评估模型，检查构造模型的步骤，确保模型可以完成业务目标。这个阶段的关键目的是确定是否有重要业务问题没有被充分的考虑。在这个阶段结束后，一个数据挖掘结果使用的决定必须达成。
TA的最新馆藏HTK之决策树聚类
可以毫不夸张的说，没有聚类的成功应用，就不会有今天的连续语音识别率（虽说不是很高）。由于语流中语音的变体十分丰富，为了能够足够精确的描述这些变体，人们往往必须设计一个较为复杂的语音单元（比如上下文音素单元）。
可是这样，问题就出现了，实际上，我们可以用于训练的语音数据总是有限的，往往不能够满足复杂语音单元训练的要求，这就形成了模型复杂度（模型描述的准确度）和训练数据规模之间的矛盾。一味的增加训练数据是不现实的，一方面这会极大的增加存储空间，人工劳动和训练费用等等；还有一个困难是致命的，就是不管你如何增大训练数据的规模，总是存在训练数据集以外的语音变体，所以仅仅依靠增加数据集来解决这个矛盾是不可行的。而聚类就可以有效的缓解这个矛盾。
用于基于HMM的语音识别的模型训练的聚类方法大致可以分为两类：一是基于数据驱动的聚类方法，而另一个就是现今正广泛使用的基于决策树的聚类方法。决策树聚类的好处是：第一，它可以得到与基于数据驱动聚类方法相同的聚类性能，另一个好处更为重要，就是它可以为训练集未包含的但实际语流中又可能会出现的语音单元（称为不可见语音单元）提供一个较为可信的参数估计。
这里主要讨论的决策树聚类是：上下文语音单元状态的聚类。如上图所示。
2. 实现状态捆绑（tying）的决策树聚类
基于决策树的状态捆绑（Decision tree based state
tying）是一种自顶向下的聚类过程。假设三音素（triphones）模型是上下文相关的模型（context dependent
model），起初位于根节点的triphones中的状态模型从单音素模型中获得。从根节点开始像二叉树一样分裂成两个相继的节点（称为yes和no节点），然后再以相继的节点为根节点，继续向下分裂，直到满足给定的条件为止，最后，所有叶节点上的triphones集合就是tied
triphones。如下所示
音素决策树
这里介绍两种决策树聚类方法。
以下讨论的聚类方法都假设：模型的输出概率分布为单高斯分布，协方差矩阵为对角阵
1. 基于最大似然（ML）准则的决策树聚类
基于最大似然准则的决策树的构造如下
一组一维高斯分布的上下文相关的HMM已训练好
预备聚类的状态集放在决策树的根节点上并计算其对数似然值
对每个节点、每个问题：计算在这个问题下分裂成的yes和no子节点的对数似然值比父节点的对数似然值增加值。记似然值增加最多的节点为及其对应问题为，使用问题分裂节点
重复步骤3，直到对数似然值的增加值低于设定的域值
决策树的分裂条件是：
是节点在q提问下分裂前后的对数似然值（Log
likelihood）之差，即：
节点的对数似然值是通过训练数据观察向量的均值、方差以及节点的期望占有数（expected
number of occupation）近似计算所得。
先给出节点的均值和方差
其中、、分别是节点中某元素的第i个状态的均值向量、方差矩阵（对角协方差矩阵）、占有数向量。上标k表示向量的第k个分量。给定训练数据中的一观察序列，那么节点的对数似然值可以通过下式求得：
、分别指节点在t时刻的期望占有数和序列的期望占有数。聚类后决策树的叶节点就是求得的捆绑的triphones，对应的均值向量为，协方差矩阵为。这里必须指出的是，不知道为什么大多数文献直接给出，实际上节点的对数似然值为，以后笔者会证明它与式（3-5）之间并不能划上等号，事实上，应该是的辅助函数（这里的表示状态序列）与式（3-5）相等。
下面推导节点的对数似然值公式：
由Baum-Welch参数估计公式：
式（3-9）重写为：
重写式（3-4）如下：
将式（3-11）代入式（3-10），得：
下面证明为0。
所以：式（3-8）
2. 基于最小描述长度（MDL）的决策树聚类
基于最大似然（ML）准则的决策树聚类已广泛使用，但基于这种方法的聚类有一个缺点，就是需要外部提供一个域值来控制其聚类的程度。这个域值的选取是经验性的，没有可靠的理论来保证选取的最优性，且不同的训练数据需要不同的域值。较好的域值，只能通过反复凑试获得，这通常是很费时。
这里将要讨论的基于MDL的决策树聚类，可以避免外部选择域值的麻烦，算法可以根据模型复杂度和数据规模自适应的产生一个域值。有实验证明这个域值比较可靠。
假设有一组概率模型和一组数据，模型的描述长度计算公式如下
其中，是模型的维数（自由参数的个数），是模型对应最大似然估计的参数。
式（1）中的第一项称为模型关于数据的编码长度。这项与ML中的对数似然值的负数等同。
式（1）中的第二项称为模型的编码长度，该项代表了模型的复杂度。
式（1）中的第三项称为选择模型的编码长度，这个假设为常数。
先定性讨论一下式（1）的含义：当模型的复杂度增加时，第一项的值变小，第二项的值变大，第二项可以看成对选择复杂模型的一种惩罚。具有最小描述长度的模型可以认为其复杂度是适中的。从中可以看出，MDL准则不需要外部提供参数来帮助判断模型的最优性。
用于语音识别的MDL的计算
如上图，假设节点分裂成个叶节点，则模型的描述长度的计算公式如下：
式（2）中的变量的意义与ML中相同。
模型的维数是（个均值向量，个协方差矩阵对角元素向量）
假设节点在问题的提问下分裂成和分支
当节点分裂，否则节点停止分裂。
这里的相当于ML中外部提供的域值。
3. HHED模块
HTK中HHED模块的功能非常强大，它主要负责对HMM定义文件进行修改，比如将单音素模型拷贝生成上下文三音素模型（通过CL命令完成）。这里要主要讨论HHED的决策树聚类的功能（HHED也提供了基于数据驱动的聚类方法）。HHED的工作模式和Shell非常相识，用户提供命令脚本文件（文件扩展名通常为：.hed），脚本文件中一行只能写一个命令，HHED模块每次读入一行命令，解析后就执行该命令，执行完后，接着再读入下一行命令，解析后并执行，如此重复，直到执行完所有命令行。
决策树聚类主要通过QS和TB两个命令完成，每执行一条QS命令，HHED就向聚类问题集中增加一个问题，每执行一条TB命令，HHED便会构造一棵决策树并利用聚类问题集进行分裂聚类，聚类结束时，HHED便会将每个叶节点中的所有元素聚为一类（捆绑状态）。
下面先给出HHED模块程序主流程图
格式：QS 问题名称 {匹配字符串}
例子：QS "L-Vowel"
{aa^*,ae^*,ah^*,ao^*,...}
上面例子中QS命令将所有左音素为元音的音素模型归为一类（yes节点），其他的则归为另一类（no节点）。
匹配字符串中的字符*表示匹配0个或多个任意字符，字符?表示匹配任意单个字符。
正如前面所述，执行一条QS命令，HHED便会向聚类问题集中增加一个问题。比如执行前面例子中的QS命令，HHED就会向聚类问题集增加一个名称为"L-Vowel"的问题。
HHED模块中主要由QuestionCommand
()函数负责将问题加入到聚类问题集中。
关键代码：
ChkedAlpha("QS question name",
PItemList(&ilist, &type, hset,
&source, NULL, trace&T_ITM);
LoadQuestion(qName, ilist,
下面的分析以命令QS "L_p" {p-*}为例
执行ChkedAlpha()后，(char*)qName存储问题名称字符串"L_p"。
PItemList()主要负责将匹配字符串所匹配的模型形成一个模型链表，由(ILink)ilist指向链表头。(char*)pattern存储的就是匹配字符串"{p-*}"。
匹配的模型链表
装载问题函数LoadQuestion()，将问题信息记录到QLink数据结构中，并加入到聚类问题集链表中，(QLink)qHead和(QLink)qTail分别指向这个聚类问题集链表的头和尾。QLink所描述的问题有以下三个部分组成
问题名称 (LabId)QLink-&qName
匹配字符串链表 (IPat*)QLink-&patList
匹配的模型链表 (ILink)QLink-&ilist
格式：TB 域值 宏名 {项列表}
例子：TB 000 mcep_s2_
{*.state[2].stream[1]}
上面例子中TB命令将所有音素模型的状态号2的数据流号1的所有项归为一个聚类集。这个聚类集对应于决策树的根节点。字符串"mcep_s2_"作为聚类完成后取名的前缀。
注意：HHED中的TB命令只支持单高斯连续输出分布的HMM模型的聚类。
在HHED中由TreeBuildCommand()函数完成TB命令。
下面先给出TreeBuildCommand()函数的程序流程图
读入项列表 PItemList()
聚类可以是状态的聚类也可以是状态下某条数据流的聚类等等，总之模型参数的任何一项或多项都可以进行聚类。这里主要讨论状态的聚类或者状态下某条数据流的聚类。
PItemList()前面已经遇到过，这里的功能是将匹配项列表的所有HMM模型组成一个模型参数链表，(ILink)ilist指向该链表头。
以项列表"*.state[2].stream[1]"为例，执行PItemList()函数后(ILink)ilist指向HMMSet集中所有HMM模型在状态号2下的数据流号1的参数组成的模型
参数链表头。
具体到代码上，链表中每一项都记录
模型的状态2参数
&&&&&&&&&&&&&
ILink-&item = (HLink)hmm-&svec+2
模型参数&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
ILink-&owner = (HLink)hmm
由于这里是数据流聚类，所以HHED还使用一集合变量(IntSet)Streams来记录聚类的数据流号。在上面的例子中，Streams-&set[1]
= TRUE，其它元素都为FALSE，表示只对数据流号1聚类。
初始化累加器，创建决策树
BuildTree()函数的第一步就是初始化全局yes和no分支累加器(AccSum)yes、(AccSum)no，接着就是创建决策树及其根节点。
首先要说明的是关于对节点提出的问题的回答。
聚类集由一个链表组成，(CLink)clHead指向该链表头。HHED通过模型参数链表、聚类集和聚类问题集的指针交换实现对节点提问的回答(yes和no)。
下面先给出关键代码片断
&& //聚类集
i = 1; clHead = NULL;
(p=p!=NULL;p=p-&next,i++)
&& . . . . . .
&& cl = (CLink)
New(&tmpHeap,sizeof(CRec));
p-&owner-&hook = //这是关键
&& cl-&item =
p;& cl-&ans = FALSE;
&& cl-&idx =
//模型参数链表中项的索引号
cl-&next = clH
&& clHead =
& for (q=qH q!=NULL;
q=q-&next)
(p=q-& p!=NULL; p=p-&next)
&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&
//问题的模型链表项 = 聚类集中相应的项
&&&&&&&&&&&&&&&&&&&&
//也就是聚类集中该项对这个问题的回答是yes
p-&owner-&
(p=p!=NULL;p=p-&next,i++)
p-&owner-&hook = NULL;
是不是对上面的代码所起的作用还不清楚，有些迷糊，没关系，下面的函数会帮助你更好的理解如何完成对节点提出问题的回答。
回答问题函数AnswerQuestion()的代码片断
void AnswerQuestion(CLink clist, QLink
//先设置聚类集关于问题(QLink)q的回答为no
for (p=p!=NULL;p=p-&next)
&&&&&&&&&&&&&
p-&ans = FALSE;
if (q!=NULL)
(i=q-&i!=NULL;i=i-&next)
&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&
if ((p=(CLink) i-&item) != NULL)
&&&&&&&&&&&&&&&&&&&&&&&&&&&
p-&ans = TRUE; //这是关键
&&&&&&&&&&&&&
通过关于聚类集问题的回答将聚类集分为yes
(CLink-&ans = TRUE)和no(CLink-&ans =
FALSE)两个子聚类集。
决策树由(Tree*)tree表示，开始的时候只有一个根节点，它也是叶节点，根节点对应于聚类集。
(Node*)node = tree-&leaf
= tree-&root = CreateTreeNode(clHead, NULL);
分析分裂节点的最优问题 ValidProbNode()
关键代码：ValidProbNode(node,
threshold);
计算节点(Node*)node在问题聚类集中所有问题的提问下的yes和no分支的似然值之和（ClusterLogL()）的最大值（(double)node-&sProb）并记录对应的问题（(QLink)node-&quest）。
如果这个最大似然值比节点node的似然值还小，则node-&sProb＝节点似然值，node-&quest
下面给出ValidProbNode()函数的的代码片断
qbest = NULL;
best = node-&tP //节点似然值
for (q=qHq!=NULL;q=q-&next)
&&&&&&&&&&&&&
AnswerQuestion(node-&clist, q);
&&&&&&&&&&&&&
sProb = ClusterLogL(node-&clist,
&no, &yes, occs);
&&&&&&&&&&&&&
. . . . . .
&&&&&&&&&&&&&
if (sProb & best)
&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&
. . . . . .
node-&sProb=
node-&quest=
分析叶节点中最优的分裂节点 FindBestSplit()
关键代码：node =
FindBestSplit(tree-&leaf, threshold);
计算所有叶节点中分裂前后后的似然值之差（node-&sProb-node-&tProb）中的最大值并返回其节点指针。如果这个最大值小于域值(double)threshold，则返回NULL。
下面给出FindBestSplit()函数的代码片断
Node *FindBestSplit(Node *first, double
threshold)
Node *best, *
double sProb,
best = NULL;imp = 0.0;
for (node =node != NULL;node =
node-&next)
&&&&&&&&&&&&&
sProb = node-&sProb -
&&&&&&&&&&&&&
if (sProb&imp &&
sProb&threshold)
&&&&&&&&&&&&&&&&&&&&
best =imp = sP
return(best);
分裂节点 SplitTreeNode()
关键代码：SplitTreeNode(tree, node);
节点(Node*)node在问题(QLink)
node-&quest提问下分裂成(Node*)yes和(Node*)no两分支。
首先将node在问题(QLink)
node-&quest提问下回答no的子聚类集赋予子节点(Node*)no，将node在问题(QLink)
node-&quest提问下回答no的子聚类集赋予子节点(Node*)yes。
接着调整(Node*)tree-&leaf仍指向叶节点链表头，并调整yes和no节点的相关指针。
根节点示意图
第一次分裂后示意图
第二次分裂后示意图
下面给出SplitTreeNode()函数的代码片断
void SplitTreeNode(Tree *tree, Node *node)
if (node-&quest == NULL)
cprob += node-&sProb -
AnswerQuestion(node-&clist,
node-&quest);
node-&yes = CreateTreeNode(NULL,node);
node-&yes-&ans= TRUE;
node-&no = CreateTreeNode(NULL,node);
node-&no-&ans=TRUE;
//分裂聚类集
for(cl=node-&cl!=NULL;cl=nextcl)
&&&&&&&&&&&&&
nextcl=cl-&
&&&&&&&&&&&&&
switch(cl-&ans)
&&&&&&&&&&&&&
&&&&&&&&&&&&&
case FALSE:
cl-&next=node-&no-&
&&&&&&&&&&&&&&&&&&&&
node-&no-&clist=
&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&
case TRUE:&
cl-&next=node-&yes-&
&&&&&&&&&&&&&&&&&&&&
node-&yes-&clist=
&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&
HError(2694,"SplitTreeNode: Unspecified question result");
&&&&&&&&&&&&&
}// for(cl=node-&cl!=NULL;cl=nextcl)
node-&clist = NULL;
//调整yes和no分支指针，以及叶节点链表
node-&yes-&next =
node-&no-&prev =
node-&no-&next =
node-&yes-&prev =
if (node-&next!=NULL)
&&&&&&&&&&&&&
node-&next-&prev=node-&
if (node-&prev==NULL)
&&&&&&&&&&&&&
tree-&leaf = node-&
&&&&&&&&&&&&&
node-&prev-&next=node-&
&&&&&&&&&&&&&
numTreeClust++; //叶节点数++
对所有叶节点进行聚类 TieLeafNodes()
关键代码：TieLeafNodes(tree, macRoot);
决策树分裂结束后，执行TieLeafNodes()将每个叶节点中所有元素聚为一类（新构造一个宏），聚类宏名以(char*)macRoot为前缀，后接序号。聚类的输出概率的均值向量和协方差矩阵取其对应节点的均值向量和协方差矩阵（具体公式见前）。
以前的讨论都没有涉及到聚类模型，所以在这里有必要说明一下。
在HTK中主要通过使用计数（-&nUse）标志聚类（捆绑）。如果对模型的状态参数或者状态下某些数据流参数捆绑，那么这些参数都指向同一个同类型的参数，这个参数中的使用计数（&1）记录捆绑参数的个数。
明白了吗？是不是太抽象了，不用担心，下面的代码片断会帮助你进一步弄清是这么回事的。
TieLeafStream()函数实现状态下某条数据流的捆绑
void TieLeafStream(ILink ilist, LabId macId, int stream)
StreamInfo *
. . . . . .
sti = ((StateElem
*)ilist-&item)-&info-&pdf[stream].
sti-&nUse = 1; //使用计数为1
NewMacro(hset, fidx, 'p', macId, sti);//构造一个新聚类的宏
&&&&&&&&&&&&&
//捆绑集中所有数据流参数
for (i=ilist-& i!=NULL;
i=i-&next)
((StateElem
*)i-&item)-&info-&pdf[stream].info
TieState ()函数实现状态的捆绑
void TieState(ILink ilist, LabId macId)
StateInfo *si,*
StateElem *
&& & . . . . .
&&&&&&&&&&&&&
if (hset-&hsKind==TIEDHS ||
hset-&hsKind==DISCRETEHS)
ti = TypicalState(ilist, macId); //选择较好的状态参数来代表这个聚类
se = (StateElem *) ti-&
tsi = se-&
tsi-&nUse = 1; //使用计数为1
NewMacro(hset, fidx, 's', macId, tsi); /构造一个新聚类的宏
&&&&&&&&&&&&&
//捆绑集中所有状态参数
for (i= i!=NULL; i=i-&next)
se = (StateElem *)i-& si =
if (si != tsi)
&&&&&&&&&&&
se-&info =
&&&&&&&&&&&
&&&&&&&&&&&&&
聚类完成后，ST命令可以将内存中的决策树列表输出到文件中。其中包括聚类时使用的问题集，一组构建好的决策树。
文件的存储方式如下：
决策树列表
问题集中的问题的存储格式和前面的QS命令相同。
下面给出决策树的存储的典型格式
m[3].stream[1]
C-Vowel&&&&&&&&&&&&&
&&&&&&&&&&&&&
-1&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&
C-silences&&&
&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&
C-Unvoiced_Stop&&&&&&&&&&&&&
&&&&&&&&&&&&&
C-l&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
-4&&&&&&&&&
&&&&&&&&&&&
C-Low_Vowel&&&&&&&&&&&&&&&&&&
"s3_3"&&&&&&&&&&&&&&&&&&&&&&&
其中，第一行，指明树的名称（m）和聚类的类型（状态号3下的数据流号1的聚类）。
以第三行为例，"C-Vowel"是用来分裂决策树节点号为0（根节点）的问题名称，后面分别是yes子节点（序号为1）和no子节点（序号为3），如果子节点是非叶节点则用序号表示，否则用聚类宏名显示。
将由ST命令输出的决策树列表文件装入。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。