URL 归一化

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