遗忘算法系列(二):大规模语料词库生成
一、前言
写这篇文时,突然想到一个问题,大家的词库都是从哪来的?
之所以会这么有些意外的问,是因为从没把词库当成个事儿:平时处理微博,就用程序跑一下微博语料获得微博词库;处理新闻,程序跑一下新闻语料获得新闻词库。甚至没有把跑出来的词库存下来的习惯,谁知道过两天是不是又出什么新词,与其用可能过时的,不如随手生成个新鲜出炉的。
二、词库生成
1、算法分析,先来考虑以下几个问题
问:目标是从文本中抽取词语,是否可以考虑使用遗忘的方法呢?
答:可以,词语具备以相对稳定周期重复再现的特征,所以可以考虑使用遗忘的方法。这意味着,我们只需要找一种适当的方法,将句子划分成若干子串,这些子串即为“候选词”。在遗忘的作用下,如果“候选词”会周期性重现,那么它就会被保留在词库中,相反如果只是偶尔或随机出现,则会逐渐被遗忘掉。
问:那用什么方法来把句子划分成子串比较合适呢?
答:考察句中任意相邻的两个字,相邻两字有两种可能:要么同属于一个共同的词,要么是两个词的边界。我们都会有这样一种感觉,属于同一个词的相邻两字的“关系”肯定比属于不同词的相邻两字的“关系”要强烈一些。
数学中并不缺少刻划“关系”的模型,这里我们选择公式简单并且参数容易统计的一种:如果两个字共现的概率大于它们随机排列在一起的概率,那么我们认为这两个字有关,反之则无关。
如果相邻两字无关,就可以将两字中间断开。逐字扫描句子,如果相邻两字满足下面的公式,则将两字断开,如此可将句子切成若干子串,从而获得“候选词”集,判断公式如下图所示:
公式中所需的参数可以通过统计获得:遍历一次语料,即可获得公式中所需的“单字的频数”、“相邻两字共现的频数”,以及“所有单字的频数总和”。
问:如何计算遗忘剩余量?
答:使用牛顿冷却公式,各参数在遗忘算法中的含义,如下图所示:
牛顿冷却公式的详情说明,可以参考阮一峰老师的博文《基于用户投票的排名算法(四):牛顿冷却定律》。
问:参数中时间是用现实时间吗,遗忘系数取多少合适呢?
答:a、关于时间:
可以使用现实时间,遗忘的发生与现实同步。
也可以考虑用处理语料中对象的数量来代替,这样仅当有数据处理时,才会发生遗忘。比如按处理的字数为计时单位,人阅读的速度约每秒5至7个字,当然每个人的阅读速度并不相同,这里的参数值要求并不需要特别严格。
b、遗忘系数可以参考艾宾浩斯曲线中的实验值,如下图(来自互联网)
我们取6天记忆剩余量约为25.4%这个值,按每秒阅读7个字,将其代入牛顿冷却公式可以求得遗忘系数:
注意艾宾浩斯曲线中的每组数值代入公式,所得的系数并不相同,会对词库的最大有效容量产生影响。
2、算法的代码实现(C#版)
呼,算法分析完成,相比于上面的文档,还是写代码要容易的多。
2.1、候选词生成
————————————————————————————————
/// <summary>
/// 从文本中生成候选词
/// </summary>
/// <param name="text">文本行</param>
/// <param name="objCharBondColl">相邻字典</param>
/// <param name="objKeyWordColl">词库</param>
/// <param name="bUpdateCharBondColl">是否更新相邻字典</param>
/// <param name="bUpdateKeyWordColl">是否更新词库</param>
public static void UpdateKeyWordColl(string text, MemoryBondColl<string> objCharBondColl, MemoryItemColl<string> objKeyWordColl, bool bUpdateCharBondColl = true, bool bUpdateKeyWordColl = true)
{
if (String.IsNullOrEmpty(text)) return;
StringBuilder buffer = new StringBuilder();//用于存放连续的子串
string keyHead = text[0].ToString(); //keyHead、keyTail分别存放相邻的两个字符
buffer.Append(keyHead);
for (int k = 1; k < text.Length; k++) //遍历句子中的每一个字符
{
//从句子中取一个字作为相邻两字的尾字
string keyTail = text[k].ToString();
if (bUpdateCharBondColl)
{
//更新相邻字典
DictionaryDAL.UpdateMemoryBondColl<string>(keyHead, keyTail, objCharBondColl);
}
if (bUpdateKeyWordColl)
{
//判断相邻两字是否有关
if (!DictionaryDAL.IsBondValid<string>(keyHead, keyTail, objCharBondColl ) )
{
//两字无关,则将绥中的字串取出,此即为候选词
string keyword = buffer.ToString();
//将候选词添加到词库中
DictionaryDAL.UpdateMemoryItemColl<string>(keyword, objKeyWordColl);
//清空缓冲
buffer.Clear();
//并开始下一个子串
buffer.Append(keyTail);
}
else
{
//两个字有关,则将当前字追加至串缓冲中
buffer.Append(keyTail);
}
}
//将当前的字作为相邻的首字
keyHead = keyTail;
}
}
————————————————————————————————
2.2、相邻字统计
————————————————————————————————
/// <summary>
/// 相邻字统计
/// </summary>
/// <param name="text">文本行</param>
/// <param name="objCharBondColl">存放相邻结果的字典</param>
/// <remarks>遍历句中相邻的字,将结果存放到字典中</remarks>
public static void UpdateCharBondColl(string text, MemoryBondColl<string> objCharBondColl)
{
if (String.IsNullOrEmpty(text)) return;
string keyHead = text[0].ToString();
for (int k = 1; k < text.Length; k++)
{
string keyTail = text[k].ToString();
//存入相邻字典中
DictionaryDAL.UpdateMemoryBondColl<string>(keyHead, keyTail, objCharBondColl);
keyHead = keyTail;
}
}
————————————————————————————————
2.3、切片算法
————————————————————————————————
/// <summary>
/// 判断键是否为有效关联键
/// </summary>
/// <typeparam name="T">C#中的范型,具体类型由调用者传入</typeparam>
/// <param name="keyHead">相邻键中首项</param>
/// <param name="keyTail">相邻键中尾项</param>
/// <param name="objMemoryBondColl">相邻字典</param>
/// <returns>返回是否判断的结果:true、相邻项有关;false、相邻项无关</returns>
/// <remarks>判断标准:共享键概率 > 单字概率之积 </remarks>
public static bool IsBondValid<T>(T keyHead, T keyTail, MemoryBondColl<T> objMemoryBondColl )
{
//如果相邻项任何一个不在相邻字典中,则返回false 。
if (!objMemoryBondColl.Contains(keyHead) || !objMemoryBondColl.Contains(keyTail)) return false;
//分别获得相邻单项的频次
double dHeadValidCount = CalcRemeberValue<T>(keyHead, objMemoryBondColl);
double dTailValidCount = CalcRemeberValue<T>(keyTail, objMemoryBondColl);
//获得相邻字典全库的总词频
double dTotalValidCount = objMemoryBondColl.MinuteOffsetSize;
if (dTotalValidCount <= 0) return false;
//获得相邻项共现的频次
MemoryItemColl<T> objLinkColl = objMemoryBondColl[keyHead].LinkColl;
if (!objLinkColl.Contains(keyTail)) return false;
double dShareValidCount = CalcRemeberValue<T>(keyTail, objLinkColl);
//返回计算的结果
return dShareValidCount / dHeadValidCount > dTailValidCount / dTotalValidCount;
}
————————————————————————————————
2.4、牛顿冷却公式
————————————————————————————————
/// <summary>
/// 牛顿冷却公式
/// </summary>
/// <param name="parameter">冷却系数</param>
/// <param name="interval">时间间隔</param>
/// <returns></returns>
/// <remarks>
/// 建议遗忘系数:-Math.Log(0.254, Math.E) / (6天 * 24小时 * 60分钟 *60秒 *7每秒阅读字数);
/// </remarks>
public static double CalcNetonCooling(double parameter, double interval)
{
return Math.Exp(-1 * parameter * interval);
}
————————————————————————————————
2.5、遗忘是在词入库的时候计算的(其实算法核心仅此一行)
————————————————————————————————
/// <summary>
/// 将候选项添加到词典中
/// </summary>
/// <typeparam name="T">C#中的泛型,具体类型由调用者传入</typeparam>
/// <param name="keyItem">候选项</param>
/// <param name="objMemoryItemColl">候选项词典</param>
public static void UpdateMemoryItemColl<T>(T keyItem, MemoryItemColl<T> objMemoryItemColl)
{
if (!objMemoryItemColl.Contains(keyItem))
{
//如果词典中不存在该候选项
//声明数据对象,用于存放候选项及其相关数据
MemoryItemMDL<T> mdl = new MemoryItemMDL<T>();
mdl.Key = keyItem;//候选项
mdl.TotalCount = 1;//候选项出现的物理次数
mdl.ValidCount = 1;//边遗忘边累加共同作用下的有效次数
mdl.ValidDegree = 1;//该词的成熟度
objMemoryItemColl.Add(mdl);//添加至词典中
}
else
{
//如果词典中已包含该候选项
//从词典中取出该候选项
MemoryItemMDL<T> mdl = objMemoryItemColl[keyItem];
//计算从最后一次入库至现在这段时间剩余量系数
double dRemeberValue = MemoryDAL.CalcRemeberValue(objMemoryItemColl.OffsetTotalCount - mdl.UpdateOffsetCount, objMemoryItemColl.MinuteOffsetSize);
mdl.TotalCount += 1;//累加总计数
//计算成熟度,嗯,这个公式写的比较乱,我自己现在看都有点头晕,看不懂算了,改天琢磨换个公式
mdl.ValidDegree = mdl.ValidDegree * ((mdl.ValidCount * dRemeberValue) / (mdl.ValidCount * dRemeberValue + 1)) + (1 - mdl.ValidCount * (1 - dRemeberValue)) * (1 / (mdl.ValidCount * dRemeberValue + 1));
mdl.ValidCount =mdl.ValidCount* dRemeberValue+ 1;// 遗忘累频=记忆保留量+1
mdl.UpdateOffsetCount = objMemoryItemColl.OffsetTotalCount;//更新时的偏移量(相当于记录本次入库的时间)
}
objMemoryItemColl.OffsetTotalCount += 1;//处理过的数据总量(相当于一个全局的计时器)
}
————————————————————————————————
2.6、按词权重排序显示词库(词的权重将在后面的文章中详解)
————————————————————————————————
/// <summary>
/// 按权重排序输出词库
/// </summary>
/// <param name="objMemoryItemColl">词库</param>
/// <param name="nKeyWordTopCount">输出词的数量</param>
/// <param name="bIsOnlyWord">是否仅输出词</param>
/// <returns>输出的结果</returns>
public static string ShowKeyWordWeightColl(MemoryItemColl<string> objMemoryItemColl, int nKeyWordTopCount, bool bIsOnlyWord = true)
{
StringBuilder sb = new StringBuilder();
sb.AppendLine(String.Format(" 【{0}】 | {1} | {2} | {3}", "主词", "遗忘词频", "累计词频", "词权值"));
var tbuffer = from x in objMemoryItemColl
//如果只显示词,则要求:长度大于1,且不包含符号
where !bIsOnlyWord || x.Key.Length > 1 && !Regex.IsMatch(x.Key,@"p{P}")
//按权重排序
orderby x.ValidCount <= 0 ? 0 : (x.ValidCount )* (Math.Log(objMemoryItemColl.MinuteOffsetSize) - Math.Log(x.ValidCount)) descending
select x;
var buffer = (tbuffer).Take(nKeyWordTopCount);
sb.AppendLine(String.Format("================ 共{0} 个 ================== ", buffer.Count()));
//逐词输出,每个词一行
foreach (var x in buffer)
{
sb.AppendLine(String.Format(" 【{0}】 | {1} | {2} | {3}", x.Key, Math.Round(DictionaryDAL.CalcRemeberValue<string>(x.Key, objMemoryItemColl), 2), x.TotalCount, Math.Round((x.ValidCount <= 0 ? 0 : (x.ValidCount ) * (Math.Log(objMemoryItemColl.MinuteOffsetSize) - Math.Log(x.ValidCount))), 4)));
}
return sb.ToString();
}
————————————————————————————————
2.7、清理词频低于阀值的词
————————————————————————————————
/// <summary> /// 清理集合,移除低于阈值的项 /// </summary> /// <typeparam name="T">C#中的泛型,具体类型由调用者传入</typeparam> /// <param name="objMemoryItemColl">词库</param> /// <param name="dMinValidValue">阈值,默认值相当于至少1个记忆周期时间内,未曾再次出现</param> public static void ClearMemoryItemColl<T>(MemoryItemColl<T> objMemoryItemColl,double dMinValidValue=1.25) { for (int k = objMemoryItemColl.Count - 1; k >= 0; k--) { //此处使用最后一次的计数即可,无需计算当前剩余值 //double dValidValue = CalcRemeberValue<T>(objMemoryItemColl[k].Key, objMemoryItemColl); //if (dValidValue < dMinVaildValue) objMemoryItemColl.RemoveAt(k); if (objMemoryItemColl[k].ValidCount < dMinValidValue) objMemoryItemColl.RemoveAt(k); } }
3、该算法生成词库的特点
3.1、无监督学习
3.2、O(N)级时间复杂度
3.3、训练、执行为同一过程,可无缝处理流式数据
3.4、未登录词、新词、登录词没有区别
3.5、领域自适应:领域变化时,词条、词频自适应的随之调整
3.6、算法中仅使用到频数这一语言的共性特征,无需对任何字符做特别处理,因此原理上跨语种。
词库成熟度
由于每个词都具备一个相对稳定的重现周期,不难证明,当训练语料达到一定规模后,在遗忘的作用下,每个词的词频在衰减和累加会达到平衡,也即衰减的速度与增加的速度基本一致。成熟的词库,词频的波动就会比较小,利用这个特征,我们可以衡量词库的成熟程度。
词频的这种波动也有一些妙用,比如:微博中重复发的广告、突然暴发的热点事件等情况,都会因词频的非正常变化而导致这些词的成熟度变低。
鉴于目前所用的模型,属于顺手写的,算不上满意,也没在这块花精力,这里就不再细讲。源代码中包含具体的方法,算是抛砖引玉,哪位兄弟找到更好的模型公式,记得跟俺说一声。
修改说明,上传的代码中,成熟度公式修改为:
————————————————————————————————
/// <summary>
/// 计算当前关键词的成熟度
/// </summary>
/// <typeparam name="T">泛型,具体类别由调用者传入</typeparam>
/// <param name="mdl">待计算的对象</param>
/// <param name="dRemeberValue">记忆剩余量系数</param>
/// <returns>当前成熟度</returns>
/// <remarks>
/// 1、成熟度这里用对象遗忘与增加的量的残差累和来表征;
/// 2、已经累计的残差之和会随时间衰减;
/// 3、公式的意思是: 成熟度 = 成熟度衰减剩余量 + 本次遗忘与增加量的残差的绝对值
/// </remarks>
public static double CalcValidDegree<T>(MemoryItemMDL<T> mdl, double dRemeberValue)
{
return mdl.ValidDegree * dRemeberValue + Math.Abs(1 - mdl.ValidCount * (1 - dRemeberValue));
}
————————————————————————————————
演示程序下载
使用内附语料(在“可直接运行的演示程序”下可以找到)生成词库效果图如下:
下载地址:遗忘算法(词库生成、分词、词权重)演示程序.rar
————————————————
版权声明:本文为CSDN博主「gzdmcaoyc」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/gzdmcaoyc/article/details/50001801
一THE END一
免责声明:本文来自互联网新闻客户端自媒体,不代表本网的观点和立场。
合作及投稿邮箱:E-mail:editor@tusaishared.com
上一篇:遗忘算法系列(三):分词
下一篇:遗忘算法系列(六):语义模型
热门资源
应用笔画宽度变换...
应用背景:是盲人辅助系统,城市环境中的机器导航...
人体姿态估计的过...
人体姿态估计是计算机视觉中一个很基础的问题。从...
GAN之根据文本描述...
一些比较好玩的任务也就应运而生,比如图像修复、...
端到端语音识别时...
从上世纪 50 年代诞生到 2012 年引入 DNN 后识别效...
谷歌发布TyDi QA语...
为了鼓励对多语言问答技术的研究,谷歌发布了 TyDi...
智能在线
400-630-6780
聆听.建议反馈
E-mail: support@tusaishared.com