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在聚类中心点表内出现多个中心点，最后会对距离非常近的中心点进行合并。