URL 归一化

出于各种各样的原因，在 Web 应用中，路径会做随机串处理，这些形式相似的 URL 实质上是在访问同一资源，譬如下面的 URL 应该泛化为一同个模式，即 /jiage/CODE.html。URL 归一化就是将同一资源下被随机串处理的路径泛化成同一个模式。

/jiage/AA.html
/jiage/BB.html
/jiage/CC.html
/jiage/DD.html

目前业内对 URL 归一化有很多种解法，传统的做法有正则表达式法和基于统计的方法，算法的做法有基于模式树的方法。

在实际的工程实践中，单看一个 URL 的字面信息是无法准确判断其是否应该进行归一化，需要看到更多接口的流量才能做到准确的判断。一般来说框架也会由离线训练和在线使用两部分组成：

• 离线训练是指算法的训练过程,通过不断迭代和采样创建接近实际的训练池，从全局看到每个接口的全部流量以及其周围全部的接口，输出待归一化接口的聚类中心点表供线上使用，这部分需要保证准确率。
• 在线使用是指来一条 URL 过来就可以判断出其是否需要进行归一化处理，如果需要归一化则给出正确的 URL Pattern，这部分需要保证高效率。

文本聚类

使用 URL 的 simhash 值作为特征，再结合改进的层次聚类 BIRCH 算法，生成聚类特征树（Clustering Feature Tree，简称 CF Tree）森林。选择该算法主要原因是它适用于类别数比较大的情况，并且不用预先输入类别数，基于 BIRCH 算法基础上我们做了一些优化，目的是提高短文本聚类的稳定性和准确性，具体优化如下：

• BIRCH 算法是一种流式建立 CF Tree 过程，每读入一个样本点计算它与现有 CF 节点海明距离，如果在半径为 T 的超球体范围内，则更新样本到该 CF 节点中，反之，再建立一个新的 CF 节点。但是这种方法会因为样本读入顺序导致树结构不合理，因此在本算法中第一步使用 K-Means，将原本建立一棵 CF Tree 改为建立 CF Forest，对训练池所有样本进行一次 K-Means，生成若干个簇，在每个簇内再建立一颗 CF Tree；

• K-Means 后先对每个簇进行评估，簇满足以下两个条件则认为该簇的 URL 可以进行归一化，则该簇停止节点分裂并将中心点加入到聚类中心点表：一个簇的 SSE（Sum of Squares for Error，残差平方和）<n; 一个簇的内距离中心点小于 l 的样本个数大于 15；

• 每个簇在建立 CF Tree 前进行异常点筛选，这一步骤可以检测出 ground truth 中的异常样本；

• 建立 CF Tree 过程中每次节点分裂前，对 CF 节点进行评估，看其是否满足 URL 归一化要求，如满足则停止节点分裂并加入聚类中心表，反之继续分裂；

• BIRCH 调参非常重要，参数对最终形成的 CF Tree 影响很大，根据大量的实验调参，每个叶子节点的最大参数 CF 为 4，叶子节点中某个 CF 的样本数为 20；

本算法最重要的产物不是 CF Forest，而是满足归一化要求的聚类中心点表，为了避免出现同一个 URL pattern 在聚类中心点表内出现多个中心点，最后会对距离非常近的中心点进行合并。