C++博客-尼克舅姑http://www.cppblog.com/NickGu/Nick9Guzh-cnThu, 23 Apr 2026 10:08:44 GMTThu, 23 Apr 2026 10:08:44 GMT60贝叶斯分类器实验http://www.cppblog.com/NickGu/archive/2009/10/08/98058.htmlNick9GuNick9GuWed, 07 Oct 2009 16:30:00 GMThttp://www.cppblog.com/NickGu/archive/2009/10/08/98058.htmlhttp://www.cppblog.com/NickGu/comments/98058.htmlhttp://www.cppblog.com/NickGu/archive/2009/10/08/98058.html#Feedback4http://www.cppblog.com/NickGu/comments/commentRss/98058.htmlhttp://www.cppblog.com/NickGu/services/trackbacks/98058.html数据。20个邮件组的邮件，共约20000条记录。

主要是实践了下naive bayesian classifier。做了两个集合的实验，包括全集和书中实践的小集合（3个特定的邮件组集合）。
全集上最后的准确率可以达到83.7%。而使用小集合对比书中的（89%-90.5%），可以达到91.3%的准确率。

其中有一些需要注意的：
1. 对低频概率的光滑操作很重要。主要用于计算P(w|g)时在w频次很低的情况下。
   如果没有光滑，答案整个就被误差毁了，直接准确率掉到20%以下。
   如果使用P(w|g)=(C(g,w)+1)/(C(g,all_w)+C(words_in_g))可以保证结果达到预期水平
   如果使用P(w|g)=(C(g,w)+1)/(C(g,all_w)+C(words))结果还更好些。这似乎和预期不是很符合。
2. 对stopword的选取。
   使用idf作为选择标准（不取log）。刚开始选定的覆盖文章范围在0.6才去除。后来发现一直到1/12都能保证单调递增。效果不错。
3. 既然bayesian是逆概，还尝试了正向概率计算求答案，也是使之相互独立。准确率在75%左右。怀疑是模型本身并不是reasonable的。（就是比naive bayesian还不靠谱）

从误分类的数据来看，有些确实是无法很好分类。同时后续改进还有这么一些方法：
1. 低频词的影响。
2. 调整模型，使之更好去识别。这在看论文。看看是否可行。

同时今天还看了一篇介绍bayesian的一些应用之处的文章。讲的很广泛，把很多知识都串一起了。很好！





Nick9Gu 2009-10-08 00:30 发表评论
]]>{看论文}k最短路http://www.cppblog.com/NickGu/archive/2009/06/14/87668.htmlNick9GuNick9GuSun, 14 Jun 2009 14:44:00 GMThttp://www.cppblog.com/NickGu/archive/2009/06/14/87668.htmlhttp://www.cppblog.com/NickGu/comments/87668.htmlhttp://www.cppblog.com/NickGu/archive/2009/06/14/87668.html#Feedback0http://www.cppblog.com/NickGu/comments/commentRss/87668.htmlhttp://www.cppblog.com/NickGu/services/trackbacks/87668.htmlD Eppstein

这篇论文不错。方法很好，但是我觉得读的有点拗口。
说几个重点nb的吧。
1. 能够将路径用最短路径树和“弯路”表示
2. 考虑到路径的层次结构。
如果考虑到以上两点会有很多启发的，之后还有几个nb的：
3. 把堆表示在dag上。
4. 这个最最nb,很容易考虑到每次找到一个最小后缀，然后更新堆，但这样复杂度就是nm的。而其通过将每个点的后缀重新组织成一个小堆。就控制住复杂度了！

这篇论文之前比赛的时候就很想看，后来搞输入法的时候又听说了，还是没时间看。今天花了一下午看了还是挺开心的。不过觉得他有的地方方法有些冗余或者说不是很优，什么时候再细细想想。今天好困。。。



Nick9Gu 2009-06-14 22:44 发表评论
]]>{NLP}最大概率分词问题及其解法http://www.cppblog.com/NickGu/archive/2009/06/06/86900.htmlNick9GuNick9GuSat, 06 Jun 2009 04:00:00 GMThttp://www.cppblog.com/NickGu/archive/2009/06/06/86900.htmlhttp://www.cppblog.com/NickGu/comments/86900.htmlhttp://www.cppblog.com/NickGu/archive/2009/06/06/86900.html#Feedback5http://www.cppblog.com/NickGu/comments/commentRss/86900.htmlhttp://www.cppblog.com/NickGu/services/trackbacks/86900.html最大概率分词问题及其解法，hit的刘挺等，1998 这篇文章前面给出的一些模型对我这个新手来说不错。后面对问题的解决一般。
第一个问题是找分割点，这个很简单，在找到每个点的最远距离后，O(n)扫一遍就可以了。
第二个问题是每个字段内的最优概率计算。这个如果按原有的概率算比较难，n-gram的n不确定，不过他这里用的是unigram
这样就简单多了。。取log以后最短路，dp啥的爱咋搞咋搞。




Nick9Gu 2009-06-06 12:00 发表评论
]]>{解题报告}德黑兰2005 [PKU2894-2903]http://www.cppblog.com/NickGu/archive/2008/11/07/66218.htmlNick9GuNick9GuFri, 07 Nov 2008 08:08:00 GMThttp://www.cppblog.com/NickGu/archive/2008/11/07/66218.htmlhttp://www.cppblog.com/NickGu/comments/66218.htmlhttp://www.cppblog.com/NickGu/archive/2008/11/07/66218.html#Feedback1http://www.cppblog.com/NickGu/comments/commentRss/66218.htmlhttp://www.cppblog.com/NickGu/services/trackbacks/66218.html
2894 Ancient Keyboard 858 Tehran 2005
2895 Best SMS to Type 909 Tehran 2005
2896 Changing Phone Numbers 98 Tehran 2005
2897 Dramatic Multiplications 614 Tehran 2005
2898 Entertainment 230 Tehran 2005
2899 Fortune at El Dorado 105 Tehran 2005
2900 Griddy Hobby 94 Tehran 2005
2901 Hotel 70 Tehran 2005
2902 Intercepting Missiles 31 Tehran 2005
  2903 Joy of Mobile Routing 15 Tehran 2005


http://docs.google.com/Doc?id=dhc6v8gg_126gmw86hgd



Nick9Gu 2008-11-07 16:08 发表评论
]]>{解题报告} NEERC2005 解题报告，PKU2791-2801http://www.cppblog.com/NickGu/archive/2008/10/23/64837.htmlNick9GuNick9GuThu, 23 Oct 2008 08:40:00 GMThttp://www.cppblog.com/NickGu/archive/2008/10/23/64837.htmlhttp://www.cppblog.com/NickGu/comments/64837.htmlhttp://www.cppblog.com/NickGu/archive/2008/10/23/64837.html#Feedback0http://www.cppblog.com/NickGu/comments/commentRss/64837.htmlhttp://www.cppblog.com/NickGu/services/trackbacks/64837.html

2791 Area 51 107 Northeastern Europe 2005
2792 Brackets Removal 81 Northeastern Europe 2005
2793 Cactus 103 Northeastern Europe 2005
2794 Double Patience 150 Northeastern Europe 2005
2795 Exploring Pyramids 191 Northeastern Europe 2005
2796 Feel Good 515 Northeastern Europe 2005
2797 Guards 34 Northeastern Europe 2005
2798 Hardwood Cutting 53 Northeastern Europe 2005
2799 IP Networks 422 Northeastern Europe 2005
2800 Joseph's Problem 446 Northeastern Europe 2005
2801 Knockdown 22 Northeastern Europe 2005


http://www.cppblog.com/Files/NickGu/neerc2005.pdf



Nick9Gu 2008-10-23 16:40 发表评论
]]>哈尔滨归来http://www.cppblog.com/NickGu/archive/2008/10/14/63956.htmlNick9GuNick9GuTue, 14 Oct 2008 06:39:00 GMThttp://www.cppblog.com/NickGu/archive/2008/10/14/63956.htmlhttp://www.cppblog.com/NickGu/comments/63956.htmlhttp://www.cppblog.com/NickGu/archive/2008/10/14/63956.html#Feedback1http://www.cppblog.com/NickGu/comments/commentRss/63956.htmlhttp://www.cppblog.com/NickGu/services/trackbacks/63956.html题目难度一般，不过阅读和题量比较大，所以还是挺郁闷的。我当时基本都在敲代码没多少需要想的题。。
还是要多多练习啊。

PS.火车上听说bamboo他们硬敲了D题。。700多行代码无模板。。Orz。。



Nick9Gu 2008-10-14 14:39 发表评论
]]>{思路} 关于学习，自我调节http://www.cppblog.com/NickGu/archive/2008/10/02/63169.htmlNick9GuNick9GuThu, 02 Oct 2008 15:05:00 GMThttp://www.cppblog.com/NickGu/archive/2008/10/02/63169.htmlhttp://www.cppblog.com/NickGu/comments/63169.htmlhttp://www.cppblog.com/NickGu/archive/2008/10/02/63169.html#Feedback0http://www.cppblog.com/NickGu/comments/commentRss/63169.htmlhttp://www.cppblog.com/NickGu/services/trackbacks/63169.html
这篇日志作为一篇开放式的吧，我想到啥就过来加点，作为自己的一个小Tips。

  • 我需要静一静，写代码是一项需要安静的工作，做自己的就应该少说话。[2008年10月4日13:27:40]
  • 昨天做一个问题一直在网上搜索没有好的答案。但后来和小亮交流下回去自己静静想想就会了，其实并不复杂，但自己没有静下来好好想想才导致自己半天没弄出来。


Nick9Gu 2008-10-02 23:05 发表评论
]]>{解题报告} NWERC2003 解题报告，PKU1631-1638http://www.cppblog.com/NickGu/archive/2008/10/02/63144.htmlNick9GuNick9GuWed, 01 Oct 2008 16:15:00 GMThttp://www.cppblog.com/NickGu/archive/2008/10/02/63144.htmlhttp://www.cppblog.com/NickGu/comments/63144.htmlhttp://www.cppblog.com/NickGu/archive/2008/10/02/63144.html#Feedback1http://www.cppblog.com/NickGu/comments/commentRss/63144.htmlhttp://www.cppblog.com/NickGu/services/trackbacks/63144.html总的来说这套题还是比较简单的，数据也不强，不过也都要想想。

http://www.cppblog.com/Files/NickGu/nwerc2003.pdf

题目列表：

1631 Bridging signals 824 Northwestern Europe 2003
1632 Vase collection 234 Northwestern Europe 2003
1633 Gladiators 101 Northwestern Europe 2003
1634 Who's the boss? 222 Northwestern Europe 2003
1635 Subway tree systems 426 Northwestern Europe 2003
1636 Prison rearrangement 166 Northwestern Europe 2003
1637 Sightseeing tour 287 Northwestern Europe 2003
1638 A number game 61 Northwestern Europe 2003


欢迎下载，如果谁会做最后一道麻烦给我留言。。有什么问题可以给我留言也可以电邮我。




Nick9Gu 2008-10-02 00:15 发表评论
]]>