Simhash 小记

2016年04月18日 yonghuawho留下评论

Simhash 最早是Google 用来对海量的数据文本进行去重的算法，算法的原理很简单，但很实用。

1、simhash的第一步是对每个要去重的文本集合进行Finger Print 计算，计算方法如下图：

simhash

算法过程大概如下：

将Doc进行关键词抽取(其中包括分词和计算权重)，抽取出n个(关键词，权重)对，即图中的(feature, weight)们。记为 feature_weight_pairs = [fw1, fw2 … fwn]，其中 fwn = (feature_n,weight_n`)。
hash_weight_pairs = [ (hash(feature), weight) for feature, weight infeature_weight_pairs ] 生成图中的(hash,weight)们, 此时假设hash生成的位数bits_count = 6（如图）;
然后对 hash_weight_pairs 进行位的纵向累加，如果该位是1，则+weight,如果是0，则-weight，最后生成bits_count个数字，如图所示是[13, 108, -22, -5, -32, 55], 这里产生的值和hash函数所用的算法相关。
[13,108,-22,-5,-32,55] -> 110001这个就很简单啦，正1负0。

simhash和普通hash最大的不同在于传统的hash函数虽然也可以用于映射来比较文本的重复，但是对于可能差距只有一个字节的文档也会映射成两个完全不同的哈希结果，而simhash对相似的文本的哈希映射结果也相似。Google的论文中取了f=64，即将整个网页的加权特征集合映射到一个64-bit的fingerprint上。

2、

『simhash值的海明距离计算』

二进制串A 和二进制串B 的海明距离就是 A xor B 后二进制中1的个数。

举例如下：

A = 100111;
B = 101010;
hamming_distance(A, B) = count_1(A xor B) = count_1(001101) = 3;

当我们算出所有doc的simhash值之后，需要计算doc A和doc B之间是否相似的条件是：

A和B的海明距离是否小于等于n，这个n值根据经验一般取值为3,

simhash本质上是局部敏感性的hash，和md5之类的不一样。正因为它的局部敏感性，所以我们可以使用海明距离来衡量simhash值的相似度。

『高效计算二进制序列中1的个数』

/* src/Simhasher.hpp */
bool isEqual(uint64_t lhs, uint64_t rhs, unsigned short n = 3)
{
    unsigned short cnt = 0;
    lhs ^= rhs;
    while(lhs && cnt <= n)
    {
        lhs &= lhs - 1;
        cnt++;
    }
    if(cnt <= n)
    {
        return true;
    }
    return false;
}

由上式这个函数来计算的话，时间复杂度是 O(n); 这里的n默认取值为3。由此可见还是蛮高效的。

simhash 实现的工程项目

C++ 版本 simhash
Golang 版本 gosimhash

主要是针对中文文档，也就是此项目进行simhash之前同时还进行了分词和关键词的抽取。

应用

每篇文档得到SimHash签名值后，接着计算两个签名的海明距离即可。根据经验值，对64位的 SimHash值，海明距离在3以内的可认为相似度比较高。
- 海明距离的求法：异或时，只有在两个比较的位不同时其结果是1 ，否则结果为0，两个二进制“异或”后得到1的个数即为海明距离的大小。

举个例子，上面我们计算到的“CSDN博客”的simhash签名值为“1 0 1 0 1 1”，假定我们计算出另外一个短语的签名值为“1 0 1 0 0 0”，那么根据异或规则，我们可以计算出这两个签名的海明距离为2，从而判定这两个短语的相似度是比较高的。

换言之，现在问题转换为：对于64位的SimHash值，我们只要找到海明距离在3以内的所有签名，即可找出所有相似的短语。

但关键是，如何将其扩展到海量数据呢？譬如如何在海量的样本库中查询与其海明距离在3以内的记录呢？

一种方案是查找待查询文本的64位simhash code的所有3位以内变化的组合
- 大约需要四万多次的查询。
另一种方案是预生成库中所有样本simhash code的3位变化以内的组合
- 大约需要占据4万多倍的原始空间。

这两种方案，要么时间复杂度高，要么空间复杂度复杂，能否有一种方案可以达到时空复杂度的绝佳平衡呢？答案是肯定的：

我们可以把 64 位的二进制simhash签名均分成4块，每块16位。根据鸽巢原理（也称抽屉原理），如果两个签名的海明距离在 3 以内，它们必有一块完全相同。如下图所示：
然后把分成的4 块中的每一个块分别作为前16位来进行查找，建倒排索引。

具体如下图所示：

如此，如果样本库中存有2^34（差不多10亿）的simhash签名，则每个table返回2^(34-16)=262144个候选结果，大大减少了海明距离的计算成本。

假设数据是均匀分布，16位的数据，产生的像限为2^16个，则平均每个像限分布的文档数则为2^34/2^16 = 2^(34-16)) ，四个块返回的总结果数为 4* 262144 （大概 100 万）。
- 这样，原本需要比较10亿次，经过索引后，大概只需要处理100万次。

【References】

http://leoncom.org/?p=650607

http://taop.marchtea.com/06.03.html

Understanding EM Algorithms

2016年02月2日2016年02月2日 yonghuawho留下评论

[开篇说明]：这篇文章转自zouxy09的CSDN博客，之所以转发过来是因为觉得文中对于EM的讲解逻辑和对于EM的引子引入的恰到好处，相信很多人都会很容易就理解。

用“鸡生蛋，蛋生鸡”的问题来引入EM简直再好不过；由此引出的“索性先初始化一坨参数值”，再“不断迭代收敛”从而得到最终param 的阐述也很到位。

总之，简单明了，很适合初学者一看。

<正文>

机器学习十大算法之一：EM算法。能评得上十大之一，让人听起来觉得挺NB的。什么是NB啊，我们一般说某个人很NB，是因为他能解决一些别人解决不了的问题。神为什么是神，因为神能做很多人做不了的事。那么EM算法能解决什么问题呢？或者说EM算法是因为什么而来到这个世界上，还吸引了那么多世人的目光。

我希望自己能通俗地把它理解或者说明白，但是，EM这个问题感觉真的不太好用通俗的语言去说明白，因为它很简单，又很复杂。简单在于它的思想，简单在于其仅包含了两个步骤就能完成强大的功能，复杂在于它的数学推理涉及到比较繁杂的概率公式等。如果只讲简单的，就丢失了EM算法的精髓，如果只讲数学推理，又过于枯燥和生涩，但另一方面，想把两者结合起来也不是件容易的事。所以，我也没法期待我能把它讲得怎样。希望各位不吝指导。

一、最大似然

扯了太多，得入正题了。假设我们遇到的是下面这样的问题：

假设我们需要调查我们学校的男生和女生的身高分布。你怎么做啊？你说那么多人不可能一个一个去问吧，肯定是抽样了。假设你在校园里随便地活捉了100个男生和100个女生。他们共200个人（也就是200个身高的样本数据，为了方便表示，下面，我说“人”的意思就是对应的身高）都在教室里面了。那下一步怎么办啊？你开始喊：“男的左边，女的右边，其他的站中间！”。然后你就先统计抽样得到的100个男生的身高。假设他们的身高是服从高斯分布的。但是这个分布的均值u和方差∂²我们不知道，这两个参数就是我们要估计的。记作θ=[u, ∂]^T。

用数学的语言来说就是：在学校那么多男生（身高）中，我们独立地按照概率密度p(x|θ)抽取100了个（身高），组成样本集X，我们想通过样本集X来估计出未知参数θ。这里概率密度p(x|θ)我们知道了是高斯分布N(u,∂)的形式，其中的未知参数是θ=[u, ∂]^T。抽到的样本集是X={x₁,x₂,…,x_N}，其中x_i表示抽到的第i个人的身高，这里N就是100，表示抽到的样本个数。

这个概率反映了，在概率密度函数的参数是θ时，得到X这组样本的概率。因为这里X是已知的，也就是说我抽取到的这100个人的身高可以测出来，也就是已知的了。而θ是未知了，则上面这个公式只有θ是未知数，所以它是θ的函数。这个函数放映的是在不同的参数θ取值下，取得当前这个样本集的可能性，因此称为参数θ相对于样本集X的似然函数（likehood function）。记为L(θ)。

这里出现了一个概念，似然函数。还记得我们的目标吗？我们需要在已经抽到这一组样本X的条件下，估计参数θ的值。怎么估计呢？似然函数有啥用呢？那咱们先来了解下似然的概念。

直接举个例子：

某位同学与一位猎人一起外出打猎，一只野兔从前方窜过。只听一声枪响，野兔应声到下，如果要你推测，这一发命中的子弹是谁打的？你就会想，只发一枪便打中，由于猎人命中的概率一般大于这位同学命中的概率，看来这一枪是猎人射中的。

这个例子所作的推断就体现了极大似然法的基本思想。

再例如：下课了，一群男女同学分别去厕所了。然后，你闲着无聊，想知道课间是男生上厕所的人多还是女生上厕所的人比较多，然后你就跑去蹲在男厕和女厕的门口。蹲了五分钟，突然一个美女走出来，你狂喜，跑过来告诉我，课间女生上厕所的人比较多，你要不相信你可以进去数数。呵呵，我才没那么蠢跑进去数呢，到时还不得上头条。我问你是怎么知道的。你说：“5分钟了，出来的是女生，女生啊，那么女生出来的概率肯定是最大的了，或者说比男生要大，那么女厕所的人肯定比男厕所的人多”。看到了没，你已经运用最大似然估计了。你通过观察到女生先出来，那么什么情况下，女生会先出来呢？肯定是女生出来的概率最大的时候了，那什么时候女生出来的概率最大啊，那肯定是女厕所比男厕所多人的时候了，这个就是你估计到的参数了。

从上面这两个例子，你得到了什么结论？

回到男生身高那个例子。在学校那么男生中，我一抽就抽到这100个男生（表示身高），而不是其他人，那是不是表示在整个学校中，这100个人（的身高）出现的概率最大啊。那么这个概率怎么表示？哦，就是上面那个似然函数L(θ)。所以，我们就只需要找到一个参数θ，其对应的似然函数L(θ)最大，也就是说抽到这100个男生（的身高）概率最大。这个叫做θ的最大似然估计量，记为：

有时，可以看到L(θ)是连乘的，所以为了便于分析，还可以定义对数似然函数，将其变成连加的：

好了，现在我们知道了，要求θ，只需要使θ的似然函数L(θ)极大化，然后极大值对应的θ就是我们的估计。这里就回到了求最值的问题了。怎么求一个函数的最值？当然是求导，然后让导数为0，那么解这个方程得到的θ就是了（当然，前提是函数L(θ)连续可微）。那如果θ是包含多个参数的向量那怎么处理啊？当然是求L(θ)对所有参数的偏导数，也就是梯度了，那么n个未知的参数，就有n个方程，方程组的解就是似然函数的极值点了，当然就得到这n个参数了。

最大似然估计你可以把它看作是一个反推。多数情况下我们是根据已知条件来推算结果，而最大似然估计是已经知道了结果，然后寻求使该结果出现的可能性最大的条件，以此作为估计值。比如，如果其他条件一定的话，抽烟者发生肺癌的危险时不抽烟者的5倍，那么如果现在我已经知道有个人是肺癌，我想问你这个人抽烟还是不抽烟。你怎么判断？你可能对这个人一无所知，你所知道的只有一件事，那就是抽烟更容易发生肺癌，那么你会猜测这个人不抽烟吗？我相信你更有可能会说，这个人抽烟。为什么？这就是“最大可能”，我只能说他“最有可能”是抽烟的，“他是抽烟的”这一估计值才是“最有可能”得到“肺癌”这样的结果。这就是最大似然估计。

好了，极大似然估计就讲到这，总结一下：

极大似然估计，只是一种概率论在统计学的应用，它是参数估计的方法之一。说的是已知某个随机样本满足某种概率分布，但是其中具体的参数不清楚，参数估计就是通过若干次试验，观察其结果，利用结果推出参数的大概值。最大似然估计是建立在这样的思想上：已知某个参数能使这个样本出现的概率最大，我们当然不会再去选择其他小概率的样本，所以干脆就把这个参数作为估计的真实值。

求最大似然函数估计值的一般步骤：

（1）写出似然函数；

（2）对似然函数取对数，并整理；

（3）求导数，令导数为0，得到似然方程；

（4）解似然方程，得到的参数即为所求；

二、EM算法

好了，重新回到上面那个身高分布估计的问题。现在，通过抽取得到的那100个男生的身高和已知的其身高服从高斯分布，我们通过最大化其似然函数，就可以得到了对应高斯分布的参数θ=[u, ∂]^T了。那么，对于我们学校的女生的身高分布也可以用同样的方法得到了。

再回到例子本身，如果没有“男的左边，女的右边，其他的站中间！”这个步骤，或者说我抽到这200个人中，某些男生和某些女生一见钟情，已经好上了，纠缠起来了。咱们也不想那么残忍，硬把他们拉扯开。那现在这200个人已经混到一起了，这时候，你从这200个人（的身高）里面随便给我指一个人（的身高），我都无法确定这个人（的身高）是男生（的身高）还是女生（的身高）。也就是说你不知道抽取的那200个人里面的每一个人到底是从男生的那个身高分布里面抽取的，还是女生的那个身高分布抽取的。用数学的语言就是，抽取得到的每个样本都不知道是从哪个分布抽取的。

这个时候，对于每一个样本或者你抽取到的人，就有两个东西需要猜测或者估计的了，一是这个人是男的还是女的？二是男生和女生对应的身高的高斯分布的参数是多少？

只有当我们知道了哪些人属于同一个高斯分布的时候，我们才能够对这个分布的参数作出靠谱的预测，例如刚开始的最大似然所说的，但现在两种高斯分布的人混在一块了，我们又不知道哪些人属于第一个高斯分布，哪些属于第二个，所以就没法估计这两个分布的参数。反过来，只有当我们对这两个分布的参数作出了准确的估计的时候，才能知道到底哪些人属于第一个分布，那些人属于第二个分布。

这就成了一个先有鸡还是先有蛋的问题了。鸡说，没有我，谁把你生出来的啊。蛋不服，说，没有我，你从哪蹦出来啊。（呵呵，这是一个哲学问题。当然了，后来科学家说先有蛋，因为鸡蛋是鸟蛋进化的）。为了解决这个你依赖我，我依赖你的循环依赖问题，总得有一方要先打破僵局，说，不管了，我先随便整一个值出来，看你怎么变，然后我再根据你的变化调整我的变化，然后如此迭代着不断互相推导，最终就会收敛到一个解。这就是EM算法的基本思想了。

不知道大家能否理解其中的思想，我再来啰嗦一下。其实这个思想无处在不啊。

例如，小时候，老妈给一大袋糖果给你，叫你和你姐姐等分，然后你懒得去点糖果的个数，所以你也就不知道每个人到底该分多少个。咱们一般怎么做呢？先把一袋糖果目测的分为两袋，然后把两袋糖果拿在左右手，看哪个重，如果右手重，那很明显右手这代糖果多了，然后你再在右手这袋糖果中抓一把放到左手这袋，然后再感受下哪个重，然后再从重的那袋抓一小把放进轻的那一袋，继续下去，直到你感觉两袋糖果差不多相等了为止。呵呵，然后为了体现公平，你还让你姐姐先选了。

EM算法就是这样，假设我们想估计知道A和B两个参数，在开始状态下二者都是未知的，但如果知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。

EM的意思是“Expectation Maximization”，在我们上面这个问题里面，（例子）我们是先随便猜一下男生（身高）的正态分布的参数：如均值和方差是多少。例如男生的均值是1米7，方差是0.1米（当然了，刚开始肯定没那么准），然后计算出每个人更可能属于第一个还是第二个正态分布中的（例如，这个人的身高是1米8，那很明显，他最大可能属于男生的那个分布），这个是属于Expectation一步。有了每个人的归属，或者说我们已经大概地按上面的方法将这200个人分为男生和女生两部分，我们就可以根据之前说的最大似然那样，通过这些被大概分为男生的n个人来重新估计第一个分布的参数，女生的那个分布同样方法重新估计。这个是Maximization。然后，当我们更新了这两个分布的时候，每一个属于这两个分布的概率又变了，那么我们就再需要调整E步……如此往复，直到参数基本不再发生变化为止。

这里把每个人（样本）的完整描述看做是三元组y_i={x_i,z_i1,z_i2}，其中，x_i是第i个样本的观测值，也就是对应的这个人的身高，是可以观测到的值。z_i1和z_i2表示男生和女生这两个高斯分布中哪个被用来产生值x_i，就是说这两个值标记这个人到底是男生还是女生（的身高分布产生的）。这两个值我们是不知道的，是隐含变量。确切的说，z_ij在x_i由第j个高斯分布产生时值为1，否则为0。例如一个样本的观测值为1.8，然后他来自男生的那个高斯分布，那么我们可以将这个样本表示为{1.8, 1, 0}。如果z_i1和z_i2的值已知，也就是说每个人我已经标记为男生或者女生了，那么我们就可以利用上面说的最大似然算法来估计他们各自高斯分布的参数。但是它们未知，因此我们只能用EM算法。

咱们现在不是因为那个恶心的隐含变量（抽取得到的每个样本都不知道是从哪个分布抽取的）使得本来简单的可以求解的问题变复杂了，求解不了吗。那怎么办呢？人类解决问题的思路都是想能否把复杂的问题简单化。好，那么现在把这个复杂的问题逆回来，我假设已经知道这个隐含变量了，哎，那么求解那个分布的参数是不是很容易了，直接按上面说的最大似然估计就好了。那你就问我了，这个隐含变量是未知的，你怎么就来一个假设说已知呢？你这种假设是没有根据的。呵呵，我知道，所以我们可以先给这个给分布弄一个初始值，然后求这个隐含变量的期望，当成是这个隐含变量的已知值，那么现在就可以用最大似然求解那个分布的参数了吧，那假设这个参数比之前的那个随机的参数要好，它更能表达真实的分布，那么我们再通过这个参数确定的分布去求这个隐含变量的期望，然后再最大化，得到另一个更优的参数，……迭代，就能得到一个皆大欢喜的结果了。

这时候你就不服了，说你老迭代迭代的，你咋知道新的参数的估计就比原来的好啊？为什么这种方法行得通呢？有没有失效的时候呢？什么时候失效呢？用到这个方法需要注意什么问题呢？呵呵，一下子抛出那么多问题，搞得我适应不过来了，不过这证明了你有很好的搞研究的潜质啊。呵呵，其实这些问题就是数学家需要解决的问题。在数学上是可以稳当的证明的或者得出结论的。那咱们用数学来把上面的问题重新描述下。（在这里可以知道，不管多么复杂或者简单的物理世界的思想，都需要通过数学工具进行建模抽象才得以使用并发挥其强大的作用，而且，这里面蕴含的数学往往能带给你更多想象不到的东西，这就是数学的精妙所在啊）

三、EM算法推导

假设我们有一个样本集{x⁽¹⁾,…,x^(m)}，包含m个独立的样本。但每个样本i对应的类别z⁽ⁱ⁾是未知的（相当于聚类），也即隐含变量。故我们需要估计概率模型p(x,z)的参数θ，但是由于里面包含隐含变量z，所以很难用最大似然求解，但如果z知道了，那我们就很容易求解了。

对于参数估计，我们本质上还是想获得一个使似然函数最大化的那个参数θ，现在与最大似然不同的只是似然函数式中多了一个未知的变量z，见下式（1）。也就是说我们的目标是找到适合的θ和z让L(θ)最大。那我们也许会想，你就是多了一个未知的变量而已啊，我也可以分别对未知的θ和z分别求偏导，再令其等于0，求解出来不也一样吗？

本质上我们是需要最大化（1）式（对（1）式，我们回忆下联合概率密度下某个变量的边缘概率密度函数的求解，注意这里z也是随机变量。对每一个样本i的所有可能类别z求等式右边的联合概率密度函数和，也就得到等式左边为随机变量x的边缘概率密度），也就是似然函数，但是可以看到里面有“和的对数”，求导后形式会非常复杂（自己可以想象下log(f₁(x)+ f₂(x)+ f₃(x)+…)复合函数的求导），所以很难求解得到未知参数z和θ。那OK，我们可否对（1）式做一些改变呢？我们看（2）式，（2）式只是分子分母同乘以一个相等的函数，还是有“和的对数”啊，还是求解不了，那为什么要这么做呢？咱们先不管，看（3）式，发现（3）式变成了“对数的和”，那这样求导就容易了。我们注意点，还发现等号变成了不等号，为什么能这么变呢？这就是Jensen不等式的大显神威的地方。

Jensen不等式：

设f是定义域为实数的函数，如果对于所有的实数x。如果对于所有的实数x，f(x)的二次导数大于等于0，那么f是凸函数。当x是向量时，如果其hessian矩阵H是半正定的，那么f是凸函数。如果只大于0，不等于0，那么称f是严格凸函数。

Jensen不等式表述如下：

如果f是凸函数，X是随机变量，那么：E[f(X)]>=f(E[X])

特别地，如果f是严格凸函数，当且仅当X是常量时，上式取等号。

如果用图表示会很清晰：

图中，实线f是凸函数，X是随机变量，有0.5的概率是a，有0.5的概率是b。（就像掷硬币一样）。X的期望值就是a和b的中值了，图中可以看到E[f(X)]>=f(E[X])成立。

当f是（严格）凹函数当且仅当-f是（严格）凸函数。

Jensen不等式应用于凹函数时，不等号方向反向。

回到公式（2），因为f(x)=log x为凹函数（其二次导数为-1/x²<0）。

（2）式中的期望，（考虑到E(X)=∑x*p(x)，f(X)是X的函数，则E(f(X))=∑f(x)*p(x)），又，所以就可以得到公式（3）的不等式了（若不明白，请拿起笔，呵呵）：

OK，到这里，现在式（3）就容易地求导了，但是式（2）和式（3）是不等号啊，式（2）的最大值不是式（3）的最大值啊，而我们想得到式（2）的最大值，那怎么办呢？

现在我们就需要一点想象力了，上面的式（2）和式（3）不等式可以写成：似然函数L(θ)>=J(z,Q)，那么我们可以通过不断的最大化这个下界J，来使得L(θ)不断提高，最终达到它的最大值。

见上图，我们固定θ，调整Q(z)使下界J(z,Q)上升至与L(θ)在此点θ处相等（绿色曲线到蓝色曲线），然后固定Q(z)，调整θ使下界J(z,Q)达到最大值（θ^t到θ^t+1），然后再固定θ，调整Q(z)……直到收敛到似然函数L(θ)的最大值处的θ*。这里有两个问题：什么时候下界J(z,Q)与L(θ)在此点θ处相等？为什么一定会收敛？

首先第一个问题，在Jensen不等式中说到，当自变量X是常数的时候，等式成立。而在这里，即：

再推导下，由于（因为Q是随机变量z⁽ⁱ⁾的概率密度函数），则可以得到：分子的和等于c（分子分母都对所有z⁽ⁱ⁾求和：多个等式分子分母相加不变，这个认为每个样例的两个概率比值都是c），则：

至此，我们推出了在固定参数θ后，使下界拉升的Q(z)的计算公式就是后验概率，解决了Q(z)如何选择的问题。这一步就是E步，建立L(θ)的下界。接下来的M步，就是在给定Q(z)后，调整θ，去极大化L(θ)的下界J（在固定Q(z)后，下界还可以调整的更大）。那么一般的EM算法的步骤如下：

EM算法（Expectation-maximization）：

期望最大算法是一种从不完全数据或有数据丢失的数据集（存在隐含变量）中求解概率模型参数的最大似然估计方法。

EM的算法流程：

初始化分布参数θ；

重复以下步骤直到收敛：

E步骤：根据参数初始值或上一次迭代的模型参数来计算出隐性变量的后验概率，其实就是隐性变量的期望。作为隐藏变量的现估计值：

M步骤：将似然函数最大化以获得新的参数值：

这个不断的迭代，就可以得到使似然函数L(θ)最大化的参数θ了。那就得回答刚才的第二个问题了，它会收敛吗？

感性的说，因为下界不断提高，所以极大似然估计单调增加，那么最终我们会到达最大似然估计的最大值。理性分析的话，就会得到下面的东西：

具体如何证明的，看推导过程参考：Andrew Ng《The EM algorithm》

http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html

四、EM算法另一种理解

坐标上升法（Coordinate ascent）：

图中的直线式迭代优化的路径，可以看到每一步都会向最优值前进一步，而且前进路线是平行于坐标轴的，因为每一步只优化一个变量。

这犹如在x-y坐标系中找一个曲线的极值，然而曲线函数不能直接求导，因此什么梯度下降方法就不适用了。但固定一个变量后，另外一个可以通过求导得到，因此可以使用坐标上升法，一次固定一个变量，对另外的求极值，最后逐步逼近极值。对应到EM上，E步：固定θ，优化Q；M步：固定Q，优化θ；交替将极值推向最大。

五、EM的应用

EM算法有很多的应用，最广泛的就是GMM混合高斯模型、聚类、HMM等等。具体可以参考JerryLead的cnblog中的Machine Learning专栏：

（EM算法）The EM Algorithm

混合高斯模型（Mixtures of Gaussians）和EM算法

K-means聚类算法

没有鸡和蛋的先后之争，因为他们都知道“没有你就没有我”。从此他们一起过上了幸福美好的生活。

最大熵模型介绍

2014年06月11日2016年02月2日 yonghuawho留下评论

本文转自http://www.cnblogs.com/hexinuaa/p/3353479.html

sam注：本篇文章介绍的最大熵是对论文《A MAXIMUM ENTROPY APPROACH TO NATURAL LANGUAGE PROCESSING》的翻译，其中添加了对最大熵公式及求解公式的推导过程，便于理解。

统计建模方法是用来modeling随机过程行为的。在构造模型时，通常供我们使用的是随机过程的采样，也就是训练数据。这些样本所具有的知识（较少），事实上，不能完整地反映整个随机过程的状态。建模的目的，就是将这些不完整的知识转化成简洁但准确的模型。我们可以用这个模型去预测随机过程未来的行为。

在统计建模这个领域，指数模型被证明是非常好用的。因此，自世纪之交以来，它成为每个统计物理学家们手中不可或缺的工具。最大熵模型是百花齐放的指数模型的一种，它表示的这类分布有着有趣的数学和哲学性质。尽管最大熵的概念可以追溯到远古时代，但直到近年来计算机速度提升之后，才允许我们将最大熵模型应用到统计评估和模式识别的诸多现实问题中（最大熵才在现实问题上大展身手）。

下面几页讨论基于最大熵的统计建模方法，尤其是它在自然语言处理上的应用。我们提供大量的结果和benchmarks，以及一些实用的用来训练最大熵模型的算法。最后我们介绍下条件最大熵模型(Conditional maxent model)和马尔科夫随机场(Markov random fields) （在计算机视觉领域广泛使用的模型）之间的联系。

我们下面要讨论的算法能从一组数据中自动抽取出数据之间的内在关系（规则），并组合这些规则生成准确而紧凑的数据模型。For instance, starting from a corpus of English text with no linguistic knowledge whatsoever, the algorithms can automatically induce a set of rules for determining the appropriate meaning of a word in context. Since this inductive learning procedure is computationally taxing, we are also obliged to provide a set of heuristics to ease the computational burden.

尽管本篇讨论的主题是NLP，但我保证没有内容是只适应NLP的，最大熵模型已经成功应用到天体物理学和医学领域。

Motivating Example

我们通过一个简单的例子来介绍最大熵概念。假设我们模拟一个翻译专家的决策过程，关于英文单词in到法语单词的翻译。我们的翻译决策模型p给每一个单词或短语分配一个估计值p(f),即专家选择f作为翻译的概率。为了帮助我们开发模型p，我们收集大量的专家翻译的样本。我们的目标有两个，一是从样本中抽取一组决策过程的事实（规则），二是基于这些事实构建这一翻译过程的模型。

我们能从样本中得到的一个明显的线索是允许的翻译候选列表。例如，我们可能发现翻译专家总是选择下面这5个法语词汇：{dans, en, à, au cours de, pendant}。一旦有了这些信息，我们可以给模型p施加第一个约束条件：

p(dans)+p(en)+ p(à)+p(au cours de)+p(pendant) = 1

这个等式代表了这一翻译过程的第一个统计信息，我们现在可以进行寻找满足这一条件的模型了。显然，有无数满足这个条件的模型可供选择。其中一个模型是p(dans)=1，换句话说这个模型总是预测dans。另外一个满足这一约束的模型是p(pendant)=1/2 and p(à)=1/2。这两个模型都有违常理：只知道翻译专家总是选择这5个法语词汇，我们哪知道哪个概率分布是对的。两个模型每个都在没有经验支持的情况下，做了大胆的假设。最符合直觉的模型是：

p(dans) = 1/5

p(en) = 1/5

p(à) = 1/5

p(au cours de) = 1/5

p(pendant) = 1/5

这个模型将概率均匀分配给5个可能的词汇，是与我们已有知识最一致的模型。我们可能希望从样本中收集更多的关于翻译决策的线索。假设我们发现到有30％时间in被翻译成dans 或者en. 我们可以运用这些知识更新我们的模型，让其满足两个约束条件：

p(dans) + p(en) = 3/10

p(dans)+p(en)+ p(à)+p(au cours de)+p(pendant) = 1

同样，还是有很多概率分布满足这两个约束。在没有其他知识的情况下，最合理的模型p是最均匀的模型，也就是在满足约束的条件下，将概率尽可能均匀的分配。

p(dans) = 3/20

p(en) = 3/20

p(à) = 7/30

p(au cours de) = 7/30

p(pendant) = 7/30

假设我们又一次检查数据，这次发现了另外一个有趣的事实：有一般的情况，专家会选择翻译成dans 或 à.我们可以将这一信息列为第三个约束：

p(dans) + p(en) = 3/10

p(dans)+p(en)+ p(à)+p(au cours de)+p(pendant) = 1

p(dans)+ p(à)=1/2

我们可以再一次寻找满足这些约束的最均匀分配的模型p,但这一次的结果没有那么明显。由于我们增加了问题的复杂度，我们碰到了两个问题：首先，”uniform（均匀）”究竟是什么意思？我们如何度量一个模型的均匀度（uniformity）？第二，有了这些问题答案之后，我们如何找到满足一组约束且最均匀的模型？就像前面我们看到的模型。

最大熵的方法回答了这两个问题。直观上讲，很简单，即：对已知的知识建模，对未知的不过任何假设（model all that is known and assume nothing about that which is unknown）。换句话说，在给定一组事实（features+output）的条件下，选择符合所有事实，且在其他方面近可能均匀的模型，这恰恰是我们在上面例子每一步选择模型p所采取的方法。

Maxent Modeling

我们考虑一个随机过程，它产生一个输出y，y属于一个有穷集合。对于刚才讨论的翻译的例子，该过程输出单词in的翻译，输出值y可以是集合｛dans, en, à, au cours de, pendant｝中任何一个单词。在输出y时，该过程可能会被上下文信息x影响，x属于有穷的集合。在目前的例子中，这信息可能包括英文句子中in周围的单词。

我们的任务是构造一个统计模型，该模型能够准确表示随机过程的行为。该模型任务是预测在给定上下文x的情况下，输出y的概率：p(y|x).

Training Data

为了研究这一过程，我们观察一段时间随机过程的行为，收集大量的样本：

。在我们讨论的例子中，每一个样本由包含in周围单词的词汇x，和in的翻译y组成。现在，我们可以假设这些训练样本已经由一个专家搞定了，我们提供大量包含in的随机的短语要求她选择一个合适的翻译。

我们可以通过它的经验分布来总结训练样本的特性：

通常，对于一个特定的pair （x, y），它要么不出现在样本中，要么最多出现几次。

Features and constraints

我们的目标是构造一个产生训练样本这一随机过程的统计模型。组成这个模型的模块将是一组训练样本的统计值。在目前的例子中，我们已经采用了几个统计数据：（1）in被翻译成dans 或者en的频率是3/10;(2) in被翻译成dans 或 à的概率是1/2 ；…等。这些统计数据是上下文独立的，但我们也可以考虑依赖上下文信息x的统计数据。例如，我们可能注意到，在训练样本中，如果 April 是一个出现在in之后，那么in翻译成en的频率有9/10.

为了表示这个事件(event)，即当Aprial出现在in之后，in被翻译成en，我们引入了指示函数：

特征f 关于经验分布的期望值，正是我们感兴趣的统计数据。我们将这个期望值表示为：

(1)

我们可以将任何样本的统计表示成一个适当的二值指示函数的期望值，我们把这个函数叫做特征函数（feature function）或简称特征（feature）。

当我们发现一个统计量，我们觉得有用时，我们让模型去符合它（拟合），来利用这一重要性。拟合过程通过约束模型p分配给相应特征函数的期望值来实现。特征f关于模型p(y|x)的期望值是：

(2)

这里，是x在训练样本中的经验分布。我们约束这一期望值和训练样本中f的期望值相同。那就要求：

(3)

组合(1),(2) 和(3)，我们得到等式：

我们称（3）为约束等式（constraint equation）或者简称约束（constraint）。我们只关注那么满足（3）的模型，不再考虑那些和训练样本中特征f频率不一致的模型。

目前总结来看，我们现在有办法表示样本数据中内在的统计现象（叫做），也有办法使我们的模型继承这一现象（叫做）。

最后，仍我关于特征和约束再罗嗦两句：单词 “feature” and “constraint”在讨论最大熵时经常被混用，我们希望读者注意区分这两者的概念：特征（feature）是（x,y）的二值函数；约束是一个等式：即模型的特征函数期望值等于训练样本中特征函数的期望值。

The maxent prinple

假设给我们n个特征函数f_i，它们的期望值决定了在建模过程中重要的统计数据。我们想要我们的模型符合这些统计，就是说，我们想要模型p属于的子集。

图1是这一限制的几何解释。这里，P是三点上所有可能的概率分布空间。如果我们不施加任何约束（图a），所有概率模型都是允许的。施加一个线性约束C₁后，模型被限制在C₁定义的区域，如图b示。如果两个约束是可满足的, 施加第二个线性约束后可以准确确定p，如图c所示。另一种情形是，第二个线性约束与第一个不一致，例如，第一个约束可能需要第一个点的概率是1/3，第二个约束需要第三个点的概率是3/4，图d所示。在目前的设置中，线性约束是从训练数据集中抽取的，不可能手工构造，因此不可能不一致。进一步来说，在我们应用中的线性约束甚至不会接近唯一确定的p,就象图c那样。相反，集合中的模型是无穷的。

属于集合C的所有模型p中，最大熵的理念决定我们选择最均匀的分布。但现在，我们面临一个前面遗留的问题：什么是”uniform(均匀)”？

数学上，条件分布p(y|x)的均匀度就是条件熵定义：

熵的下界是0, 这时模型没有任何不确定性；熵的上界是log|Y|,即在所有可能(|Y|个)的y上均匀分布。有了这个定义，我们准备提出最大熵原则。

当从允许的概率分布集合C中选择一个模型时，选择模型，使得熵H(p)最大。

(6)

可以证明是well-defined的，就是说，在任何的约束集合C中，总是存在唯一的模型取得最大熵。

Exponential form

最大熵原理呈现给我们的是一个约束优化问题：find the which maximizes H(p)。简单的情况，我们可以分析求出问题的解。如翻译模型中我们施加前两个约束时，容易求得p的分布。不幸的是，通常最大熵模型的解无法明显得出，我们需要一个相对间接的方法。

为了解决这个问题，我们采用约束优化理论中Lagrange multipliers的方法。这里仅概述相关步骤，请参考进一步阅读以更深入了解约束优化理论如何应用到最大熵模型中的。

我们的约束优化问题是：

我们将这个称为原始问题（primal）。简单的讲，我们目标是在满足以下约束的情况下，最大化H(p)。

for all x,y.
. This and the previous condition guarantee that p is a conditional probability distribution.
In other words, , and so satisfies the active constraints C.

为了解决这个优化问题，引入Lagrangian 乘子。

实值参数和对应施加在解上的n+1个约束。

下面的策略可以求出p的最优解（），但我们不打算证明它。

首先，将和看成常量，寻找p最大化公式（8）。这会产生以和为参数的表示式p，（参数没有解决）。接着，将该表达式代回（8）中，这次求和的最优解（ and ,respectively）。

按照这一方式，我们保证和不变，计算在所有空间下，计算的无约束的最大值。

令该式等于0, 求解 p(y|x):

可以看出公式（10）的第二个因子对应第二个约束：

将上式带入公式（10）得到：

将公式（11）带入（10），我们得到：

因此，

Z(x)是正则化因子。

现在我们要求解最优值, 。显然，我们已经知道了，还不知道。

为此，我们介绍新的符号，定义对偶函数：

对偶优化问题是：

因为p^*和是固定的，公式（15）的右边只有自由变量。

参数值等于的p^*就是一开始约束优化问题的最优解。这办法不明显看出为什么，但这的确是Lagrange multipliers理论的基本原理，通常叫做Kuhn-Tucker theorem(KTT)。详细的解释已经超出本文讨论的范围。我们简单地陈述最后结论：

满足约束C最大熵模型具有（13）参数化形式，最优参数可以通过最小化对偶函数求得。

补充说明：

究竟是什么样呢？ (记住我们要求的最小值，这是Lagrange multipliers理论的基本原理)

Maximum likelihood

最大似然率：找出与样本的分布最接近的概率分布模型。

比如：10次抛硬币的结果是：

画画字画画画字字画画

假设p是每次抛硬币结果为”画”的概率。

得到这样试验结果的概率是：

P = pp(1-p)ppp(1-p)(1-p)pp=p⁷(1-p)³

最大化似然率的方法就是：

最优解是：p=0.7

似然率的一般定义为：

p(x)是模型估计的概率分布，是结果样本的概率分布。

在我们的问题里，要估计的是p(y|x)，最大似然率为：

(15)

因此，有：

这里的p具有公式（13）的形式，我们的结果进一步可以表述为：

最大熵模型是具有公式（13）形式，且最大化样本似然率的模型。最大熵模型与最大似然率模型一致。

Computing the Parameters

要算λ，解析解肯定是行不通的。对于最大熵模型对应的最优化问题，GIS，lbfgs，sgd等等最优化算法都能解。相比之下，GIS大概是最好实现的。这里只介绍GIS算法。

具体步骤如下：

（1）set 等于任意值, 比如等于0.

(2) 重复直到收敛：

这里，(t)是迭代下标，常数C定义为：

, 实践中C是训练样本里最大的特征个数。尽管C再大些也没关系，但是它决定了收敛速度，还是取最小的好。

实际上，GIS算法用第N次迭代的模型来估算每个特征在训练数据中的分布。如果超过了实际的，就把相应参数变小。否则，将它们变大。当训练样本的特征分布和模型的特征分布相同时，就求得了最优参数。

最大熵模型介绍

2014年06月11日2016年02月2日 yonghuawho留下评论

本文转自http://www.cnblogs.com/hexinuaa/p/3353479.html

尽管本篇讨论的主题是NLP，但我保证没有内容是只适应NLP的，最大熵模型已经成功应用到天体物理学和医学领域。

Motivating Example

p(dans)+p(en)+ p(à)+p(au cours de)+p(pendant) = 1

p(dans) = 1/5

p(en) = 1/5

p(à) = 1/5

p(au cours de) = 1/5

p(pendant) = 1/5

p(dans) + p(en) = 3/10

p(dans)+p(en)+ p(à)+p(au cours de)+p(pendant) = 1

p(dans) = 3/20

p(en) = 3/20

p(à) = 7/30

p(au cours de) = 7/30

p(pendant) = 7/30

假设我们又一次检查数据，这次发现了另外一个有趣的事实：有一般的情况，专家会选择翻译成dans 或 à.我们可以将这一信息列为第三个约束：

p(dans) + p(en) = 3/10

p(dans)+p(en)+ p(à)+p(au cours de)+p(pendant) = 1

p(dans)+ p(à)=1/2

Maxent Modeling

我们的任务是构造一个统计模型，该模型能够准确表示随机过程的行为。该模型任务是预测在给定上下文x的情况下，输出y的概率：p(y|x).

Training Data

为了研究这一过程，我们观察一段时间随机过程的行为，收集大量的样本：

我们可以通过它的经验分布来总结训练样本的特性：

通常，对于一个特定的pair （x, y），它要么不出现在样本中，要么最多出现几次。

Features and constraints

为了表示这个事件(event)，即当Aprial出现在in之后，in被翻译成en，我们引入了指示函数：

特征f 关于经验分布的期望值，正是我们感兴趣的统计数据。我们将这个期望值表示为：

(1)

我们可以将任何样本的统计表示成一个适当的二值指示函数的期望值，我们把这个函数叫做特征函数（feature function）或简称特征（feature）。

(2)

这里，是x在训练样本中的经验分布。我们约束这一期望值和训练样本中f的期望值相同。那就要求：

(3)

组合(1),(2) 和(3)，我们得到等式：

目前总结来看，我们现在有办法表示样本数据中内在的统计现象（叫做），也有办法使我们的模型继承这一现象（叫做）。

The maxent prinple

属于集合C的所有模型p中，最大熵的理念决定我们选择最均匀的分布。但现在，我们面临一个前面遗留的问题：什么是”uniform(均匀)”？

数学上，条件分布p(y|x)的均匀度就是条件熵定义：

熵的下界是0, 这时模型没有任何不确定性；熵的上界是log|Y|,即在所有可能(|Y|个)的y上均匀分布。有了这个定义，我们准备提出最大熵原则。

当从允许的概率分布集合C中选择一个模型时，选择模型，使得熵H(p)最大。

(6)

可以证明是well-defined的，就是说，在任何的约束集合C中，总是存在唯一的模型取得最大熵。

Exponential form

我们的约束优化问题是：

我们将这个称为原始问题（primal）。简单的讲，我们目标是在满足以下约束的情况下，最大化H(p)。

for all x,y.
. This and the previous condition guarantee that p is a conditional probability distribution.
In other words, , and so satisfies the active constraints C.

为了解决这个优化问题，引入Lagrangian 乘子。

实值参数和对应施加在解上的n+1个约束。

下面的策略可以求出p的最优解（），但我们不打算证明它。

按照这一方式，我们保证和不变，计算在所有空间下，计算的无约束的最大值。

令该式等于0, 求解 p(y|x):

可以看出公式（10）的第二个因子对应第二个约束：

将上式带入公式（10）得到：

将公式（11）带入（10），我们得到：

因此，

Z(x)是正则化因子。

现在我们要求解最优值, 。显然，我们已经知道了，还不知道。

为此，我们介绍新的符号，定义对偶函数：

对偶优化问题是：

因为p^*和是固定的，公式（15）的右边只有自由变量。

满足约束C最大熵模型具有（13）参数化形式，最优参数可以通过最小化对偶函数求得。

补充说明：

究竟是什么样呢？ (记住我们要求的最小值，这是Lagrange multipliers理论的基本原理)

Maximum likelihood

最大似然率：找出与样本的分布最接近的概率分布模型。

比如：10次抛硬币的结果是：

画画字画画画字字画画

假设p是每次抛硬币结果为”画”的概率。

得到这样试验结果的概率是：

P = pp(1-p)ppp(1-p)(1-p)pp=p⁷(1-p)³

最大化似然率的方法就是：

最优解是：p=0.7

似然率的一般定义为：

p(x)是模型估计的概率分布，是结果样本的概率分布。

在我们的问题里，要估计的是p(y|x)，最大似然率为：

(15)

因此，有：

这里的p具有公式（13）的形式，我们的结果进一步可以表述为：

最大熵模型是具有公式（13）形式，且最大化样本似然率的模型。最大熵模型与最大似然率模型一致。

Computing the Parameters

具体步骤如下：

（1）set 等于任意值, 比如等于0.

(2) 重复直到收敛：

这里，(t)是迭代下标，常数C定义为：

, 实践中C是训练样本里最大的特征个数。尽管C再大些也没关系，但是它决定了收敛速度，还是取最小的好。

Logistic Regression

2014年05月16日2016年02月2日 yonghuawho留下评论

Logistic Regression is a classical Classification method. It is the same with Maximum Entropy Model as Log linear Model.

（还是用中文说吧，用英文太扭捏了。）

首先提一下Logistic Distribution，即逻辑斯蒂分布，其在数学上的定义和公式如下：

定义（逻辑斯蒂分布）设X是连续随机变量，X服从逻辑斯蒂分布是指X具有下列分布函数和密度函数：

公式中，u为位置参数，r>0为形状参数。分布函数和密度函数的曲线图像如下：

从曲线图示可以看出，逻辑斯蒂分布函数是一个S形曲线，曲线在中心附近增长较快，在两端增长速度较慢。

【注】将Logistic Regression 应用到二分类中的话，可以将S形曲线的上半段和下半段分别看作是二分类的两类区间，如果待分类数据的Logistic Regression值落在了某一段则其就分类到某一类中，并且Logistic Regression的概率值离中心点u越远，则分到该类的可能性越大。

定义（逻辑斯蒂回归模型）：二项Logistic Regression回归模型是如下的条件概率分布：

P（Y=1|X） = exp（w·x + b）/（1+exp（w·x + b））

P（Y=0|X） = 1/（1+exp（w·x + b））

这里，X属于n维R实数域向量表示输入，Y属于{0,1}表示输出的类标签，w也属于n维R实数域表示Logistic Regression模型的参数集合，b也是参数。w称为权值向量，b称为偏置。w·x表示w和x的内积。

（二分类）：

在使用Logistic Regression 进行二分类时，根据上面的回归模型的公式，我们根据训练语料可以得到输入X，输出Y，因此要训练得到回归模型就是要学习得到参数w和b，一旦知道了符合训练语料的最优参数w和b，之后再随机给出一个输入X，在w和b已知的条件下就可以计算出X对应的最优Y分类是0还是1，并且可以给出具体的概率来衡量。

模型参数估计：采用极大似然估计来计算模型参数，学习过程通常采用 梯度下降法 或者 拟牛顿法。

因为是二分类，设：

P（Y=1|X）=pi（x）

P（Y=0|X）=1 – pi（x）

那么似然函数，即在训练语料上作分类后每一条数据的分类所得概率之乘积为：

A =

A 的值越大，表明分类越准确，也就是模型越优。

从而，要求最优参数w和b使得似然函数A 的值最大即可，即求A的极大值。

取log后得：

L（w）=

对L(w)求极大值，得到w的估计值，即模型参数。有了模型参数就有了模型。

（多分类）：

以上为logistic regression模型在二分类上的应用，可以推广到多分类的情况。在二分类的情况下，参数w为在1和0两类上分别对应一个n维参数向量（w1,w2，，，，wn），在多分类情况下则在每一类上都对应一个n维参数向量。在实际编码过程中可将w存放在一个n*m维的矩阵，其中n为类数目，m为最大特征数。

多分类情况下的logistic regression公式为：

P（Y=k|X）=

跟二项logistic regression的似然函数类似，多项的似然函数为：

L(w) =

在所有N条训练数据上进行分类，分类结果在正确类别上的概率进行乘积运算，最终得到L（w），当参数w使得L（w）的值最大时，w即为最终模型。

对L（w）求极大值，得到参数矩阵。具体可采用梯度下降法或者拟牛顿法。

kmeans 聚类

2014年04月17日2016年02月2日 yonghuawho留下评论

应该是最简单的一种聚类方法，最大的缺点是需要事先有监督地给出要聚出的簇的数目。

kmeans的实现相对简单，如果你还不知道它的原理，那么，百度一下吧。

系统输入要求以数字的方式进行，如要对多篇文档进行聚类，首先找出文档的特征向量并数字化，如：

1:10000 2:2 3:300 4:40 5:0.05 6:0.6
1:1 2:2 3:3 4:4 5:5 6:6
1:1 2:2 3:3 4:4 5:5 6:6
1:1 2:2 3:3 4:4 5:5 6:6
1:1 2:2 3:3 4:4 5:5 6:6
1:1 2:2 3:3 4:4 5:5 6:6
1:1 2:2 3:3 4:4 5:5 6:6
1:1 2:2 3:3 4:4 5:5 6:6
1:10 2:20 3:30 4:40 5:50 6:600
1:10 2:20 3:30 4:40 5:50 6:600
1:10 2:20 3:30 4:40 5:50 6:600
1:10 2:20 3:30 4:40 5:50 6:600
1:0.001 2:0.002 3:0.003 4:0.004 5:0.005 6:0.006
1:0.001 2:0.002 3:0.003 4:0.004 5:0.005 6:0.006
1:0.001 2:0.002 3:0.003 4:0.004 5:0.005 6:0.006
1:0.001 2:0.002 3:0.003 4:0.004 5:0.005 6:0.006
1:0.001 2:0.002 3:0.003 4:0.004 5:0.005 6:0.006
1:100 2:200 3:300 4:400 5:500
1:100 2:200 3:300 4:400 5:500
1:100 2:200 3:300 4:400 5:500
1:100 2:200 3:300 4:400 5:500
1:100 2:200 3:300 4:400 5:500
1:100 2:200 3:300 4:400 5:500
1:100 2:200 3:300 4:400 5:500
1:100 2:200 3:300 4:400 5:500
1:100 2:200 3:300 4:400 5:500
1:10000 2:20000 3:30000 4:40000 5:50000 6:6000
1:10000 2:20000 3:30000 4:40000 5:50000 6:6000
1:10000 2:20000 3:30000 4:40000 5:50000 6:6000
1:10000 2:20000 3:30000 4:40000 5:50000 6:6000
1:10000 2:20000 3:30000 4:40000 5:50000 6:6000
1:1000 2:2000 3:3000 4:4000 5:5000 6:6000
1:1000 2:2000 3:3000 4:4000 5:5000 6:6000
1:1000 2:2000 3:3000 4:4000 5:5000 6:6000
1:1000 2:2000 3:3000 4:4000 5:5000 6:6000

同时需要提供给系统要求最终聚出的簇数N，通过迭代取中心点（取中心点的方法：首次均匀取所有数据点每个dimensioin的N平均；之后每个簇迭代取簇内均值中心点。），按照上述进行输入有下列聚类结果：

N=4时，

0##10000 2 300 40 0.05 0.6
3##1 2 3 4 5 6
3##1 2 3 4 5 6
3##1 2 3 4 5 6
3##1 2 3 4 5 6
3##1 2 3 4 5 6
3##1 2 3 4 5 6
3##1 2 3 4 5 6
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##0.001 0.002 0.003 0.004 0.005 0.006
3##0.001 0.002 0.003 0.004 0.005 0.006
3##0.001 0.002 0.003 0.004 0.005 0.006
3##0.001 0.002 0.003 0.004 0.005 0.006
3##0.001 0.002 0.003 0.004 0.005 0.006
3##100 200 300 400 500 0
3##100 200 300 400 500 0
3##100 200 300 400 500 0
3##100 200 300 400 500 0
3##100 200 300 400 500 0
3##100 200 300 400 500 0
3##100 200 300 400 500 0
3##100 200 300 400 500 0
3##100 200 300 400 500 0
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000

N=7时，

0##10000 2 300 40 0.05 0.6
6##1 2 3 4 5 6
6##1 2 3 4 5 6
6##1 2 3 4 5 6
6##1 2 3 4 5 6
6##1 2 3 4 5 6
6##1 2 3 4 5 6
6##1 2 3 4 5 6
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##10 20 30 40 50 600
5##0.001 0.002 0.003 0.004 0.005 0.006
5##0.001 0.002 0.003 0.004 0.005 0.006
5##0.001 0.002 0.003 0.004 0.005 0.006
5##0.001 0.002 0.003 0.004 0.005 0.006
5##0.001 0.002 0.003 0.004 0.005 0.006
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000

N=10时，

0##10000 2 300 40 0.05 0.6
5##1 2 3 4 5 6
5##1 2 3 4 5 6
5##1 2 3 4 5 6
5##1 2 3 4 5 6
5##1 2 3 4 5 6
5##1 2 3 4 5 6
5##1 2 3 4 5 6
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##10 20 30 40 50 600
4##0.001 0.002 0.003 0.004 0.005 0.006
4##0.001 0.002 0.003 0.004 0.005 0.006
4##0.001 0.002 0.003 0.004 0.005 0.006
4##0.001 0.002 0.003 0.004 0.005 0.006
4##0.001 0.002 0.003 0.004 0.005 0.006
6##100 200 300 400 500 0
6##100 200 300 400 500 0
6##100 200 300 400 500 0
6##100 200 300 400 500 0
6##100 200 300 400 500 0
6##100 200 300 400 500 0
6##100 200 300 400 500 0
6##100 200 300 400 500 0
6##100 200 300 400 500 0
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000

由以上聚类结果可以看出，最终聚类的结果跟选择的初始点的数量N有很大的关联：若给出的N小于语料中实际存在的簇数，那聚出的结果会比较粗糙，存在没有聚出的簇，这些簇被分配到了与其特征向量最接近的簇中，如N=5的结果；反之，若给出的N>=实际存在的簇数，则可以较准确地给出聚类结果，如N=7和N=10的结果是最理想的，但是N=10时的cost却比N=7时要高得多。因此N的选择对整个聚类系统的好坏起着决定性作用。

对于未知的语料该信息可通过不断尝试来决定；也可通过分析每次聚类结果中每个簇的最大间隔和平均间隔的差值来决定是否需要调整N的值。

数据打乱顺序后，聚类结果不变。

0##10000 2 300 40 0.05 0.6
5##1 2 3 4 5 6
5##1 2 3 4 5 6
6##0.001 0.002 0.003 0.004 0.005 0.006
6##0.001 0.002 0.003 0.004 0.005 0.006
6##0.001 0.002 0.003 0.004 0.005 0.006
5##1 2 3 4 5 6
5##1 2 3 4 5 6
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##10 20 30 40 50 600
6##0.001 0.002 0.003 0.004 0.005 0.006
6##0.001 0.002 0.003 0.004 0.005 0.006
5##1 2 3 4 5 6
5##1 2 3 4 5 6
5##1 2 3 4 5 6
4##100 200 300 400 500 0
4##100 200 300 400 500 0
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000