1.文本分析
在搜索过程中需要对文本进行处理，比如对查询的分析以及建立索引时对文档内容的分析，我们将这部分内容称作“Query理解”。其主要包括Query预处理、Query纠错、Query扩展、Query归一、联想词、Query分词、意图识别、term重要性分析、敏感Query识别、时效性识别等。如下图所示，用户输入一个Query，为了缓解后端压力，搜索系统会先去Cache中查询Query是否被命中，如果被命中，则直接返回该Query的结构化数据。如果没被命中，就需要后续对Query进行一系列处理。首先是简单的预处理，大小写、全半角、繁简体转化以及对过长的Query进行截断处理，接着可能需要先对Query进行分词，使用分词的Term结果进行错误检测，然后再对Query分词做重要性分析和紧密度分析，对无关紧要的词汇做丢词等处理。有了分词Term及其对应的权重、紧密度信息后，搜索系统可以进行意图识别。意图识别包括模糊意图识别和精准意图识别。除此之外，部分搜索场景还需要对Query进行敏感识别及时效分析等其他处理，以及对前面各部分处理后的结果进行人工干预，解决相应的负例。
1.1查询处理
1.1.1搜索查询中的“术”
对文档处理主要是一个词法分析的过程。词法分析的过程是将字符串（文档中的文本内容）转换成词条的过程，这些词条可以作为索引词条。因此，词法分析的主要目的是识别文本中的词条。
在对英文进行分词的过程中，除了空格分隔符，还有几种特殊的情况：数字、连字符、标点符号和字母的大小写。数字一般不适合用作索引词条，因为对于数字来说，如果不参考上下文，它没有明确的含义。对于连字符来讲，目前常用的处理方法是首先采用一定的规则选出那些对词义有影响的连字符，然后将其他连字符过滤掉。对于文本来讲，标点符号将被全部去除，但对于那些成为单词一部分的标点符号来讲，一般不可以去除。对于字母大小写，其处理方法一般是将文本中的所有词条转换成大写或者小写，但在某些特殊情况下，需要对大小写进行区分。
对于中文的词法分析，最关键的就是中文分词。在中文分词的过程中，有两大难题：一是歧义识别，所谓歧义是指同样的一句话可能有两种或者多种切分方法；二是新词识别，“新词”的专业术语为“未登录词”，也就是那些在字典中没有收录过的词。
中文分词的方法
单字切分就是按照中文一个字、一个字地进行分词。二分法是指每两个字进行一次切分。词库分词是用一个已经建立好的词的集合去匹配目标，当匹配到集合中已经存在的词时，就将其切分出来。中文分词算法
现有的分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。
- 基于字符串匹配的分词方法。它又叫作机械分词方法，是按照一定的策略将待分的字符串与一个充分大的机器词典中的词条进行匹配，若在词典中找到对应字符串，则匹配成功（识别出一个词）。按照扫描方向的不同，基于字符串匹配的分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法、分词与标注相结合的一体化方法。
下面介绍两种机械分词方法，即正向最大匹配法和逆向最大匹配法。正向最大匹配法（Forward Maximum Matching Method，FMM）的算法思想是，选取包含6~8个汉字的符号串作为最大符号串，将最大符号串与词典中的单词条目相匹配，如果不能匹配，就削掉一个汉字继续匹配，直到在词典中找到相应的单词为止。其匹配的方向是从左向右。逆向最大匹配法（Backward Maximum Matching Method，BMM）和正向最大匹配算法相似，只是匹配的方向是从右向左，比正向最大匹配的精确度高一些。下图为正向最大匹配和逆向最大匹配的算法示例。
- 基于理解的分词方法。通过计算机模拟人对句子的理解，达到识别词的效果。其基本思想是在分词的同时进行句法、语义分析，利用句法和语义信息来处理歧义现象。通常，基于理解的分词包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息，以便对分词歧义进行判断，即模拟人理解句子的过程。
- 基于统计的分词方法。从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。换句话说，字与字相邻共现的频率或概率能够较好地反映词的可信度。我们可以对语料中相邻共现的各个字组合出现的频率进行统计，计算它们的共现信息。共现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成一个词。这种方法只需对语料中的字组出现频率进行统计，不需要词典，因而又叫作无词典分词法或统计取词方法。
1.1.2搜索系统中的“道”
上述内容只是搜索查询中的“术”，要想真正理解搜索引擎，还需要深刻理解搜索系统的内核，即搜索系统的“道”。查询理解便是我们需要理解的“道”，它在搜索系统中是一个比较重要的模块。这个模块的主要目的是推断查询，通过提供建议来引导搜索引擎判断出用户的真实意图，并改进查询以获得更好的结果，下图所示。
(1)查询建议
查询建议，也被称为查询下拉建议、查询下拉推荐或者查询自动补全。它是指搜索引擎系统根据用户当前的输入，自动提供一个查询候选列表供用户选择。查询建议在搜索引擎和广告竞价平台中已经是标配的组件。它可以帮助用户明确搜索意图，减少用户的输入并节约搜索时间，提高用户体验。各个搜索系统的查询建议的处理流程基本相同，不同点主要体现在后台的查询候选产生机制上。
查询建议也有一些常用的算法，能够在查询第一步帮助用户获得满意的结果。常见的下拉推荐算法有：1）基于日志的下拉推荐；2）对页面浏览（Page View，PV）数据进行扩展，基于综合指标的下拉推荐；3）基于用户行为的下拉推荐；4）基于Query Session的下拉推荐。下拉推荐的目的和常用算法如下图所示。
全量日志的自动补全法Most Popular Completion，MPC是最常用的基于日志统计信息的方法。如图4-13所示，基于日志的下拉推荐流程主要分为三步：1）在海量的Query日志中，统计一段时间内每个Query的PV和点击数；2）经过相似度计算，得到与用户输入Query相似的候选Query集合；3）在相似Query候选集中，按照Query的PV和点击数进行排序。为提升匹配效率，我们可以通过对历史搜索Query按PV统计量筛选并预处理，然后分别构建前后缀Trie树，以便对输入Query进行前缀及后缀匹配召回。最后对召回的结果进行排序，如果是仅简单按PV量降序排列，可以在Trie树节点中存放PV信息，并用最小堆等结构进行Top N召回。
全量日志的自动补全法方法也存在一些问题：1）对于Top N Query，该推荐方法效果较好，但是对于长尾Query，可能无法挖掘到相似Query，而现实中长尾Query占了很大比例；2）候选Query语义相同，仅仅是词语顺序不同，可能导致推荐位置的浪费；3）推荐Query可能存在质量问题，如一些质量低的Query由于点击或者PV过高而被推荐，导致质量较高的Query不能被展示。
为了改善上述基于日志的下拉推荐存在的问题、增加高质量Query被推荐的机会、减少作弊行为、给出更加合理的Query排序结果，基于综合统计指标的下拉推荐方法被提出，以代替原始的基于日志的下拉推荐方法。基于综合统计指标的下拉推荐方法包括更多维度，如PV、UV、CTR、转化率等，通过多维度对Query排序能够有效防止作弊行为的发生，挖掘到高质量Query。该方法通过逻辑回归将上述指标拟合成一个实数，与基于日志的下拉推荐方法的不同之处在于：1）第一步计算每个Query的综合统计指标，不仅仅是PV值；2）Query综合统计指标不仅考虑了Query的历史PV/点击信息，而且考虑了用户行为信息，使得质量高的Query获得更多的展现机会。
基于综合统计指标的下拉推荐方法解决了高质量Query展现和排序的问题，但该方法还是和基于日志的方法一样，主要依赖Query自身的特征，比如搜索Query和候选Query之间的联系仅仅是两者的前缀相同。这种简单的动态特征没有将搜索Query和候选Query紧密地结合在一起，同时静态特征和动态特征的组合都是基于线性加权的。为了使两者之间建立动态关联，基于CTR的方法被提出。如果搜索Query和候选Query之间的关联越强，它的CTR就会越高，反之则会比较低。CTR预估是通过逻辑回归模型预估Query的CTR来实现的，使用的特征主要有：1）搜索Query和推荐Query的相关特征；2）搜索Query和推荐Query类目的相关特征；3）候选Query综合统计指标的相关特征；4）搜索Query和推荐Query的词性特征；5）搜索Query和推荐Query对应的结果页面特征等。
只依靠短短的Query信息去准确识别用户的意图是不够的，还需要结合用户的一些信息对用户意图进行推测。根据用户的信息建模，比如用户性别、年龄、学历以及兴趣偏好等，结合初排结果再次进行排序。基于用户行为的下拉推荐方法的主要步骤有：1）计算用户和Query的相关个性化特征；2）建立合适的评价体系对这类特征进行权重学习，这里可以使用逻辑回归模型，比如AUC模型。但是一般情况下，用户的某一个场景下的行为信息较少，需要挖掘其他场景下的行为信息作为补充，同时还存在冷启动问题。
另外，点击的URL也可以作为信息源，即使用用户点击的URL对简短的Query信息进行补充和表示。定义一次完整的Query Session包含搜索Query和点击的URL。基于Query Session的下拉推荐方式的主要步骤是：1）将搜索Query以及对应的点击的URL从日志库中提取出来，预处理后聚类；2）给定一个搜索Query，确定所属聚类类别，计算其在这个类别中的排序；3）返回排序靠前的相关联的Query。候选Query的排序由与搜索Query之间的相似度以及所属类别中的支持度决定，该指标通过点击日志计算得到。Query的热度和用户需要的支持度不一定成正比，因此需要将相似度和支持度归一化，线性组合计算Query的排序结果；或者考虑向用户输出两种方法的推荐列表，并让他们调整每种方法的权重。为了计算两个Query之间的相似度，我们会对每个Query中的每个词语向量化。词典是由点击的URL分词后的结果去掉停用词后组成的集合，词语的权重由词语出现的次数和URL点击的次数决定。给定一个Query(q)和一个URL(u)，令Pop(q，u)表示u在q下的热度；Tf(t，u)是词语t在u内出现的次数；q的表示向量为q，q[i]表示Query中的词语在词袋中所处的位置i，其计算公式是：
总和涵盖所有点击的URL。该表示形式通过经典Tf-idf加权中的点击流行度来更改逆文档频率。使用余弦函数计算相似度，如果两个文档的单词出现比例相似（但长度或单词出现顺序可能不同），则认为它们相似。
即使使用同样点击的URL的日志，Query聚类的方法也不尽相同。图4-14表示搜索Query和点击的URL之间的关联，左侧代表查询qi；右侧表示搜索Query对应的点击的URL；Query和URL之间的连接关系eij表示在qi下点击uj；边的权重wij表示整个日志中，在qi下点击uj的总次数。该方法便于寻找相似的Query，两个Query之间共同点击的URL越多，说明两个Query越相似。
单个Query对用户意图识别的信息量是不够的。例如有用户搜索了“小米”，我们并不能判断用户搜索的是小米这个品牌还是食物，但当我们发现用户在搜索“小米”之前还搜索了“智能手机”，就能大致理解用户的意图。所以，除了需要分析用户当前的Query外，对用户Query上下文的分析也会帮助我们理解用户查询意图。我们根据会话数据挖掘用户Query上下文序列，并结合Query的聚类结果构建概念序列后缀树（Concept Sequence Suffix Tree）。当用户提交Query后，推荐系统就可以根据该后缀树快速给出合适的下拉推荐。具体的下拉推荐方案如下图所示。
(2)查询更正
查询更正主要是指Query纠错，也就是对用户在搜索输入时的错误Query进行检测和更正。用户在使用搜索引擎时，可能由于输入法、手误或者理解偏差等造成输入错误，使返回结果不能满足用户需求或者无返回结果。因此，搜索引擎需要对此进行处理，提高搜索的准确率和召回率，为用户提供更好的使用体验。
根据Query中是否包含不在词典中的词语，可以将Query的错误类型分为两种：Non-word和Real-word。Non-word错误一般出现在带英文单词或数字的Query中，不会存在中文错误的情况。所以，中文Query一般只存在Real-word错误，而带英文、数字的Query则可能存在上述两类错误。下图对常见错误类型进行了归类并给出了相应的例子。
Query纠错可以通过噪声信道模型来理解，假设用户原本想输入Qreal，但是经过噪声信道之后，可能输入到搜索引擎中的是Qnoise，对Qnoise进行去噪处理，最大限度地还原为Qdenoise，使得Qdenoise≈Qreal。
已知Qnoise，求解最大可能的Qreal，公式如下：
Query纠错一般包括两个子任务：错误检测和错误纠正。其中，错误检测就是识别出错误的位置。对于Non-word类型的错误，我们可以根据词汇是否在维护的词典中进行判断。不过，该方法的效果取决于维护词典的规模和质量。对于Real-word类型的错误，每个词汇都可作为错误候选词。至于错误纠正，即在检测出Query存在错误的基础上对错误部分进行纠正，主要包括纠错候选召回、候选排序选择两个步骤。在进行候选召回时，没有一种策略能覆盖所有错误类型，一般采用多种策略进行多路候选召回，然后在多路候选召回的基础上通过排序模型进行最终的候选排序。在纠正Non-word类型的错误时，搜索系统可以查找词典中与错误词汇最相近的词语。常见的方法有计算最小编辑距离和最大噪声信道概率。在纠正real-word类型的错误时，搜索系统可以从发音和拼写多个角度，查找与错误词汇最相近的词语集合作为拼写建议。常见的方法有计算最大噪声信道概率和分类。
对于英文错误、多/漏字、颠倒错误，搜索系统可以通过编辑距离度量召回。编辑距离表示一个字符串通过插入、删除、替换操作转化为另一个字符串所需的操作次数，例如hapy转化成happy的编辑距离是1。由于搜索Query数量庞大，如果计算Query两两之间的编辑距离，计算量会非常大，因此一般采用启发式策略，比如首字符相同的情况下将长度小于某一值的Query分到一个桶中，计算桶中的Query两两之间的编辑距离。对于上述方式不能够处理的情况，比如顺序颠倒、漏字多字的情况，还可以利用编辑距离满足两边之和大于第三边的特性对多叉树进行剪枝。首先随机选取一个Query作为根节点，然后自顶向下对所有Query构建多叉树，树的边为两个节点Query的编辑距离。给定一个Query，需要找到与其编辑距离小于等于n的所有Query，并自顶向下计算与相应节点Query的编辑距离d，接着只需递归考虑边值在d–n到d+n范围的子树即可。如下图所示，需要查找所有与“十面埋弧”编辑距离小于等于1的Query，由于“十面埋弧”与“十面埋伏”的编辑距离为1，此时只需考虑边值在1–1到1+1范围的子树，因此不用考虑将“十面埋伏怎么样”作为根节点子树。
据统计，英文中80%的拼写错误的编辑距离是1，大多拼写错误的编辑距离小于等于2，基于此可以减少大量不必要的计算。通过最小编辑距离获取拼写建议候选集（Candidate w），再从候选集中选出概率最大的w作为最终的拼写建议，然后基于噪声信道模型，进一步计算候选词w的概率p(w)和在候选词w出现的情况下x的条件概率p(x|w)，通过对语料库统计，即可得到p(w)、p(x|w)。了采用一元词法模型Unigram，还可以推广到二元词法模型Bigram，甚至三元词法模型Trigram及更高阶，以更好地融入上下文信息。
对于等长的拼音字形错误，我们还可以使用HMM模型召回。例如：连一裙→连衣裙，可以将错误Query“连一裙”作为观测序列，正确Query“连衣裙”作为隐藏状态，映射关系可以通过人工整理的同谐音和形近字混淆词表、编辑距离度量召回的相近英文单词以及挖掘好的纠错片段对得到。通过对搜索行为日志统计得到模型参数，然后采用维特比算法对隐藏状态序列矩阵求解最大纠错概率，得到候选纠错序列。下图就是一个HMM模型处理等长拼音字形错误类型的示例。进一步地，我们还可以尝试利用深度学习模型充分挖掘搜索点击行为及搜索上下文来纠错候选召回，如采用Seq2Seq、Transformer、Pointer-Generator Networks等模型进行端到端的生成改写，通过引入注意力、记忆存储等机制以及结合混淆词表进行优化。
1.2 意图理解
用户搜索意图的识别是搜索文本分析的重要部分，也是最具挑战的部分。其存在的难点主要有如下几点。1）用户输入Query不规范。由于不同用户对同一事物认知不同，用户在通过自然语言描述时会存在差异，甚至可能会出现Query表达错误和遗漏的情况。2）歧义性和多样性。搜索Query不能明确表达用户真实意图，可能带来歧义；或者用户搜索的内容本身可能有多种含义，比如：“小米”可能是食物，也可能是品牌。
根据用户信息及搜索上下文可实现个性化意图识别，比如针对不同的用户（年龄、性别等），搜索同一个Query的意图可能不一样，用户当前Query的意图可能和上下文Query相关。按照用户意图明确程度，搜索意图识别可以分为精准意图识别和模糊意图识别。
- 精准意图识别
精准意图识别是指用户所表达的意图已经相当明确，可以根据Query锁定一个资源目标。精准意图识别在垂直搜索领域较为常见，以应用商店搜索为例，用户搜索“下载微信”的意图很明确，就是想下载微信App，那么将微信App展示在第一位即可。一般在排序模型拟合较好的情况下对应的精准资源能够排在首位，但是以下情况可能会引起排序不稳定，进而导致对应的精准资源不能排在首位，具体包括：1）长尾Query数据稀疏，模型学习不充分；2）引入用户个性化特征，排序结果因人而异；3）以商业化为导向的排序影响相关性体验。因此，我们需要通过一定策略识别出精准意图并置顶。
对于垂直搜索领域，精准意图一般是在给定Query的情况下，找到与其精准对应的item。我们可以通过文本匹配的方式，对<Query，item>对进行精准二分类。常用的分类模型有TextCNN、LSTM以及DSSM等。对于长尾Query且文本完全包含item的情况，由于用户行为量不够丰富，利用分类模型可能无法召回，直接进行文本匹配提取可能存在歧义，因此可以转化成NER任务，通过BiLSTM-CRF等序列标注模型进行item实体识别。另外，针对问答型任务，比如“姚明的身高是多少？”，可以通过召回“姚明”“身高”字样的页面为用户提供答案，但如果能够直接给出这个Query的答案，用户体验会更好。这类问答型任务一般需要结合知识图谱来实现，传统做法是先对Query进行词法、句法以及语义解析，识别出主要实体，再基于这些主题构造相应的查询逻辑表达式，进而去知识库中查询答案。近年来，业内陆续提出将问题和知识库中的候选答案映射成分布式向量进行匹配，以及利用CNN、LSTM、记忆网络等对问题及候选答案建模来解决。 - 意图分类
在进行Query意图分类前，需要先制定一套意图标签用于全面覆盖用户意图需求。这里需要对Query侧和item侧的标签体系进行统一，以便在预测出某个Query的意图标签分布后直接用标签去倒排索引中召回属于这些标签的item。在电商场景下，根据Query识别该商品的类别，按照类别召回该类别下的商品，可以解决Query无结果情况，扩大召回量。由于搜索Query长度较短且意图存在多种可能，因此意图分类可以归为多文本多标签分类任务。在样本选取上，可以通过关联用户搜索行为分布及理解item获得的标签或站点所属行业分类信息等自动构造样本。对于可能存在的样本类别不平衡的问题，我们需要对样本进行上下采样等处理，或采用主动学习等方法进行高效的样本标注。至于模型方面，传统的文本分类主要采用向量空间模型或特征工程表征文本，然后用贝叶斯、SVM、最大熵等机器学习模型进行训练预测。随着Word2vec、GloVe、Fasttext等分布式词向量技术的兴起，传统自然语言处理任务需要做大量特征工程的局面被打破。通过分布式向量对文本进行表示，然后接入其他网络进行端到端分类训练的做法成为主流，如简单又实用的浅层网络模型Fasttext。Fasttext是从Word2vec衍生出来的，其架构和Word2vec架构类似，核心思想是将整篇文档的词及n-gram向量叠加平均后得到文档向量，然后使用文档向量做softmax多分类。相对于Word2vec，Fasttext是在输入层考虑字符级n-gram特征，这在一定程度上解决了未登录词识别问题，并且在输出层支持有监督的任务学习。Fasttext训练简单，且线上接口性能很高，但因为采用相对简单的浅层网络结构，准确率相对较低。为此，我们进一步尝试了一些深度神经网络模型，如：TextRNN、TextCNN、Char-CNN、BiLSTM+Self-Attention、RCNN、C-LSTM、HAN、EntNet、DMN等。这些模型通过CNN/RNN网络结构提炼更高阶的上下文语义特征以及引入注意力机制、记忆存储机制等，有效提高了模型的分类准确率。其实，对于Query短文本分类来说，采用相对简单的TextRNN/TextCNN网络结构就已经能达到较高的准确率。其中，TextRNN通过使用GRU/LSTM编码单元能更好地捕获词序和较长长度的上下文依赖信息，但训练耗时相对较长。TextCNN主要通过不同尺寸的卷积核捕获不同局部窗口内的n-gram组合特征，然后通过max-pooling或kmax-pooling保留变长文本中一个或多个位置的最强特征，并转换为固定长度的向量再做sigmoid/softmax分类。为进一步提高网络性能、加速模型收敛，我们还可以考虑在网络中加入dropout及batch normalize等防过拟合机制，以及在输入层融入Word2vec、GloVe、Fasttext等模型预训练得到的向量。TextCNN在捕获长程依赖信息方面不如TextRNN，但对于长度相对较短的Query的推荐效果相对较好，而且其训练速度及在线接口性能也都比较符合要求。
1.3 其他文本分析方法
1.层次聚类
目前，在文本挖掘领域使用最广泛的聚类算法是层次聚类。层次聚类包括凝聚式层次聚类和分裂式层次聚类。
凝聚式层次聚类又称为自底向上的层次聚类，是将集合中的每个对象作为一个单独的类别，然后逐渐合并这些类别形成更大的类别，直到满足聚类终止条件为止。分裂式层次聚类又称为自顶向下的层次聚类，它的聚类过程与凝聚式层次聚类相反：首先将集合中的所有对象置于同一个类别，然后对这个类别不断细分，直至达到聚类终止条件。相比凝聚式层次聚类，分裂式层次聚类在分裂过程中所要依据的规则更难确定，并且细节方面的处理过程也更加复杂，因此其适应用范围比较窄。本节采用的是凝聚式层次聚类。
凝聚式层次聚类的基本流程如下。
1）将数据集中的每个点都作为一个独立的类别，类间的距离近似等于相应数据点的距离。
2）找到聚类最近的两个类别，然后合并这两个类别。
3）计算新合并的类别和原来每个类别之间的距离。
4）重复第2步和第3步，直到所有的数据都聚到一个类别中，或者满足聚类终止条件（预先设定的类别个数或者距离的阈值）为止。
类别合并的方法有三种，分别是单连接法、全连接法和平均连接法。
单连接法：也叫最短距离法，类间距离用两个类中最近的两个数据点的距离表示。距离作为度量条件，一旦最近的两个类别之间的距离小于预先设定的距离阈值，算法流程结束。
全连接法：也叫最长距离法。与单连接法选两个类中最近的两个数据点的距离作为类间距离相反，它选择将两个类中距离最远的两个数据点的距离作为类间距离。
平均连接法：无论是单连接法还是全连接法都容易受到极端值的影响，造成聚类的不稳定。与上述两种方法不同，平均连接法选取两个类别中所有对象的平均距离作为类间距离。该方法更加合理，但计算较复杂。
2.K均值聚类
K均值聚类是基于样本集合划分的聚类方法，其事先确定样本集合划分的类别数k，将所有样本分到这k个类中，目标是每个样本到所属类别的中心的距离最小。由于每个样本只能属于一个类别，所以K均值聚类是硬聚类。
K均值聚类的基本流程如下。
1）从样本集中随机选取k个样本点作为初始聚类中心。
2）计算聚类对象到聚类中心的距离，将每个样本指派到与其最近的聚类中心的类中。
3）计算当前各个类中的样本的均值，作为新的聚类中心。
4）重复第2步和第3步，直到迭代收敛或者满足聚类终止的条件为止。
K均值聚类属于启发式方法，不能保证收敛到全局最优，且初始聚类中心的选择会直接影响聚类的结果，因此在选择初始聚类中心时可以考虑用层次聚类对样本进行聚类，得到k个类时停止，然后从每个类中选取一个与中心聚类最近的样本点。这里类别数k需要事先指定，但实际中往往最合适的k值是未知的，所以需要不断尝试k值聚类，检验聚类的结果，推断出最优的k值。聚类结果的质量可以使用类的平均直径来衡量。一般情况下，类别数变小时，平均直径会增加；类别数超过某个值，且平均直径不变时，这时的k值就是最优值。
3.LDA主题模型
主题模型广泛应用于自然语言处理领域，用于挖掘文本中潜在的主题信息。它是描述主题信息的一系列数学模型，本质是形式化地刻画出主题信息。下面介绍概率主题模型的发展历程——从潜在语义分析模型LSA到概率潜在语义分析模型PLSA，最后讲述目前应用最广泛的LDA主题模型。
（1）LSA模型
在向量空间模型（Vector Space Model，VSM）中，各个单词之间是完全相互独立的，所以很难解决一义多词和一词多义问题。因此，Deerwester等人提出了潜在语义分析（Latent Semantic Analysis，LSA）模型。LSA和VSM模型的相同之处是，使用向量表示词语和文本之间的关系；不同之处是，LSA将词语和文档映射到潜在语义空间，提出单词和文本之间存在主题层这一语义关系，这比以往将单词视为文本的唯一表示元素有了巨大的进步。LSA模型结构如下图所示。
上图中，A矩阵是一个稀疏矩阵，行表示词汇，列表示文档，矩阵中的元素是词汇在文档中出现的次数；等式右边的三个矩阵也有清晰的物理含义。X矩阵是对词进行分类的结果，行表示词汇，列表示语义类别，矩阵中的元素表示词汇在对应类别下的相关性；Y矩阵是对文档的分类结果，行表示主题，列表示文档，矩阵中的元素表示每篇文档在不同主题中的相关性；B矩阵则表示词的类和文档的类之间的相关性。
LSA模型利用奇异值分解的方式，截取了最大的前K个特征值，从而完成了文本从高维单词空间到低维主题空间的降维映射，这种方式对语料集中噪声过滤起到了重要作用。此外，在低维的主题空间中，语义关系相似的单词的主题相同或者相似，所以该模型改善了原模型中一义多词的缺陷。然而，改善后的LSA模型还是无法完全解决原模型中一词多义的问题，还具有计算量过大的缺点，所以后来有研究者提出了用概率潜在语义分析模型来弥补LSA模型的不足。
（2）PLSA模型
Hofmann基于LSA模型构建了概率潜在语义分析（Probability Latent Semantic Cnalysis，PLSA）模型。该模型利用文档、主题和单词三层联合发生的概率获得与文本最贴切的语义关系，并采用迭代算法（一般是EM算法）推断文本与主题之间的语义关系，然后采用主题的语义信息表示文本信息。PLSA模型结构如下图所示。
其中，方框代表重复次数，d表示文档，z代表主题，w代表单词，M代表该语料库中文档的总数，N是当前操作的文档所包含的单词数目。
PLSA模型不仅达到了降维的目的，而且刻画出了主题层和单词层的关系。但该模型仍不是一个完备的概率生成模型，因为它没有使用概率来描述文本。并且PLSA模型中的模型参数和语料集中的文本数量呈正相关，这就造成了模型的过拟合。
（3）LDA模型
在2003年，Blei等人基于PLSA模型构建了一种三层贝叶斯结构的模型——隐狄利克雷分布（Latent Dirichlet Allocation，LDA）模型。LDA模型是一个真正意义上完备的概率生成模型，是在PLSA模型的基础上扩展了狄利克雷先验超参数α和β，构建出文档层、主题层、单词层的三层贝叶斯结构模型，解决了PLSA模型中过拟合的问题。LDA模型在文本——主题维度中利用狄利克雷分布来完成抽样，并且一致的先验超参数使模型参数不会因语料集中文本数量的改变而受到影响，具有良好的泛化能力。此外，LDA模型建立在严格的贝叶斯理论基础之上，因此具有良好的扩展性。目前LDA模型已广泛地运用于科学研究和实际生产中。
LDA模型假设总体语料库中的所有文本都服从主题空间的多项分布，同时每个主题都服从词项空间的多项分布。LDA模型结构如下图所示。
上图中，θ和φ分别表示文本——主题分布与主题——单词分布，其先验分布都是狄利克雷分布，而α和β则分别为其狄利克雷分布的参数，也称为超参数。一个语料库D中共有M篇文档，每篇文档d由N个数量不定的单词w组成。此外，每篇文档由K个主题的多项分布表示，而每个主题z又由V个单词的多项分布表示。
