计算两段文字的KL距离 -

finallyliuyu

浏览: 8302 次
性别:
来自: 北京

最近访客更多访客>>

gyb997

小座长

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

2010-03 ( 2)
更多存档...

计算两段文字的KL距离

博客分类：

自然语言理解与处理

Matlab D语言 J#

相对熵（relative entropy或 Kullback-Leibler divergence,KL距离）的java实现（一）
利用信息论的方法可以进行一些简单的自然语言处理
        比如利用相对熵进行分类或者是利用相对熵来衡量两个随机分布的差距，当两个随机分布相同时，其相对熵为0.当两个随机分布的差别增加时，器相对熵也增加。我们下面的实验是为了横量概率分布的差异。

试验方法、要求和材料
要求：
    1.任意摘录一段文字，统计这段文字中所有字符的相对频率。假设这些相对频率就是这些字符的概率（即用相对频率代替概率）；

    2.另取一段文字，按同样方法计算字符分布概率；

    3.计算两段文字中字符分布的KL距离；

    4.举例说明（任意找两个分布p和q）,KL距离是不对称的，即D(p//q)!=D(q//p);

方法：
D（p//q）=sum(p(x)*log(p(x)/q(x)))。其中p(x)和q(x)为两个概率分布

约定 0*log(0/q(x))=0;p(x)*log(p(x)/0)=infinity;

实验材料：
   从凤凰新闻网，提取的两篇新闻名字为:

   《《小团圆》究竟泄了张爱玲什么“秘密”？》

    《《小团圆》：张爱玲的一个梦》

《1945年毛zedong和蒋介石在重庆谈判前的秘密情报战》

三篇新闻的编码均为utf-8,大小都是11k左右，都为多页新闻。

三篇新闻的内容如下

[img]相对熵（relative entropy或 Kullback-Leibler divergence,KL距离）的java实现（一）
利用信息论的方法可以进行一些简单的自然语言处理
        比如利用相对熵进行分类或者是利用相对熵来衡量两个随机分布的差距，当两个随机分布相同时，其相对熵为0.当两个随机分布的差别增加时，器相对熵也增加。我们下面的实验是为了横量概率分布的差异。

试验方法、要求和材料
要求：
    1.任意摘录一段文字，统计这段文字中所有字符的相对频率。假设这些相对频率就是这些字符的概率（即用相对频率代替概率）；

    2.另取一段文字，按同样方法计算字符分布概率；

    3.计算两段文字中字符分布的KL距离；

    4.举例说明（任意找两个分布p和q）,KL距离是不对称的，即D(p//q)!=D(q//p);

方法：
D（p//q）=sum(p(x)*log(p(x)/q(x)))。其中p(x)和q(x)为两个概率分布

约定 0*log(0/q(x))=0;p(x)*log(p(x)/0)=infinity;

实验材料：
   从凤凰新闻网，提取的两篇新闻名字为:

   《《小团圆》究竟泄了张爱玲什么“秘密”？》

    《《小团圆》：张爱玲的一个梦》

《1945年毛zedong和蒋介石在重庆谈判前的秘密情报战》

三篇新闻的编码均为utf-8,大小都是11k左右，都为多页新闻。

实验中，我们采用两种方法计算概率。一：以字符为单位计算概率；二：以汉语词为单位计算概率在第二种情况下，我们采用Jeasy分词组件进行分词处理，该分词组件为基于前向最大匹配的分词方法，分词结果在绝大多数情况下是正确的。

**

 * @author liuyu
 * 此实体作为每个字符的一个单位
 *
 */
public class Entity
{
    String word;//存储字符
    float pValue;//存储该字符对应的概率值
    public Entity()//类的构造函数
    {  
        pValue=0;
        word="";
        
    }

}

读取文件 
public static String GetFileText(String path) throws  FileNotFoundException,IOException
    {   
        InputStreamReader inStreamReader=new InputStreamReader(new FileInputStream(path),"UTF-8");
        //String strFile1=
        BufferedReader bufReader=new BufferedReader(inStreamReader);
        String line;
        StringBuilder sb=new StringBuilder();
        while((line=bufReader.readLine())!=null)
        {
            sb.append(line+"　");
        }
        inStreamReader.close();
        bufReader.close();
        String strFile=sb.toString();
      
        
        
        return strFile;
        
    }

3.分割字符

（1）分词

public static String CutText(String path)throws FileNotFoundException,IOException
    {
        
      String fileText=GetFileText(path);
     
        
        MMAnalyzer analyzer=new MMAnalyzer();
        String result =null;
        String spliter="|";
        try      
        {
            result = analyzer.segment(fileText, spliter);    
        }      
        catch (IOException e)      
        {     
            e.printStackTrace();     
        }     
        //System.out.print(result);
        return result;
        
    }

(2)分单字

public static String CutTextSingleCharacter(String path)throws FileNotFoundException,IOException
    {   String text=GetFileText(path);
        String proText=null;
        Pattern pattern=Pattern.compile("[\\u4E00-\\u9FA5\\uF900-\\uFA2D]");
        Matcher m=pattern.matcher(text);
        StringBuffer sb=new StringBuffer();
        Boolean flag=m.find();
        while(flag)
        {
            int start=m.start();
            int end=m.end();
            sb.append(text.substring(start, end)+"|");
            //System.out.println(text.substring(start,end));
            flag=m.find();
        }
       proText=sb.toString();
        return proText;
}

4.计算字符的概率

public static ArrayList<Entity> CalcuP(String path) throws IOException
    {    //以词为单位计算相对熵
        //String result=CutText(path);
        //以字为单位计算相对熵
        String result=CutTextSingleCharacter(path);
        String []words=result.split("\\|");
        
      
        ArrayList<Entity> enList=new ArrayList();
        for(String w: words)
        {  w=w.trim();
            Entity en=new Entity();
            en.word=w;
            en.pValue=1;
            enList.add(en);
            //System.out.println(w);
        }
    
        float total=enList.size();
        for(int i=0;i<enList.size()-1;i++)
        { 
            
            if(!enList.get(i).word.isEmpty())
            {
                for(int j=i+1;j<enList.size();j++)
                {
                    if(enList.get(i).word.equals(enList.get(j).word))
                    {
                        enList.get(i).pValue++;
                        enList.get(j).pValue=0;
                        enList.get(j).word="";
                    }
                }
            }
        }
        for(int i=enList.size()-1;i>=0;i--)
        {
            if(enList.get(i).pValue<1.0)
                enList.remove(i);
        }
        for(int i=0;i<enList.size();i++)
        {
            enList.get(i).pValue=enList.get(i).pValue/total;
        }
        
    return enList;
    }

5.计算相对熵

/*用于计算两段文本的相对熵*/
public static float CalKL(ArrayList<Entity>p,ArrayList<Entity>q)
{  
    float kl=0;
    
    float infinity=10000000;//无穷大
    double accretion=infinity;//设置熵增加量的初始值为无穷大。
    //从q中找出与p中相对应词的概率，如果找到了，就将accretion的值更新，并累加到相对熵上面；如果没找到，则增加了为无穷大
    for(int i=0;i<p.size();i++)
    {   
        if(q.size()!=0)
        {   for(int j=q.size()-1;j>=0;j--)
            {    
                if(p.get(i).word.equals(q.get(j).word))
                {  accretion=p.get(i).pValue*Math.log(p.get(i).pValue/q.get(j).pValue);
                    //q.remove(j);
                    break;
                    
                }
        }
        
        kl+=accretion;
        accretion=infinity;
        }
        
        
    }

    
    return kl;
    
}

}

结果分析
主函数代码

public static void main(String[] args) throws  FileNotFoundException,IOException
    {
        
        
        // TODO Auto-generated method stub;
        ArrayList<Entity> enList1=new ArrayList<Entity>();
        enList1=CalcuP("C:/Users/liuyu/workspace/KL/KL/zhangailing.txt");
        ArrayList<Entity> enList2=new ArrayList<Entity>();
        enList2=CalcuP("C:/Users/liuyu/workspace/KL/KL/zhangailing2.txt");
        ArrayList<Entity>enList3=new ArrayList<Entity>();
        enList3=CalcuP("C:/Users/liuyu/workspace/KL/KL/maozedong.txt");
　　　　 double f1=CalKL(enList1,enList2);
        double f2=CalKL(enList2,enList1);
        double f3=CalKL(enList1,enList3);
        double f4=CalKL(enList3,enList1);
        double f5=CalKL(enList2,enList3);
        double f6=CalKL(enList3,enList2);
        System.out.println("《《小团圆》究竟泄了张爱玲什么“秘密”？》与《《小团圆》：张爱玲的一个梦》的KL距离： "+f1);
        System.out.println("《《小团圆》：张爱玲的一个梦》与《《小团圆》究竟泄了张爱玲什么“秘密”？》的KL距离"+f2);
        System.out.println("《《小团圆》究竟泄了张爱玲什么“秘密”？》与《1945年毛和蒋介石在重庆谈判前的秘密情报战》的KL距离 "+f3);
        System.out.println("《1945年毛和蒋介石在重庆谈判前的秘密情报战》与《《小团圆》究竟泄了张爱玲什么“秘密”？》的KL距离 "+f4);
        System.out.println("《“小团圆”张爱玲的一个梦》与《1945年毛和蒋介石在重庆谈判前的秘密情报战》的KL距离"+f5);
        System.out.println("《1945年毛和蒋介石在重庆谈判前的秘密情报战》与《“小团圆”张爱玲的一个梦》的KL距离"+f6);
]

a.以字符为单位的计算结果如下：

《《小团圆》究竟泄了张爱玲什么“秘密”？》与《《小团圆》：张爱玲的一个梦》的KL距离： 2.269998592E9
《《小团圆》：张爱玲的一个梦》与《《小团圆》究竟泄了张爱玲什么“秘密”？》的KL距离4.099975168E9
《《小团圆》究竟泄了张爱玲什么“秘密”？》与《1945年毛和蒋介石在重庆谈判前的秘密情报战》的KL距离 3.029988864E9
《1945年毛和蒋介石在重庆谈判前的秘密情报战》与《《小团圆》究竟泄了张爱玲什么“秘密”？》的KL距离 4.289972736E9
《“小团圆”张爱玲的一个梦》与《1945年毛和蒋介石在重庆谈判前的秘密情报战》的KL距离4.10997504E9
《1945年东和蒋介石在重庆谈判前的秘密情报战》与《“小团圆”张爱玲的一个梦》的KL距离3.539982336E9

b.以词为单位计算结果如下

《《小团圆》究竟泄了张爱玲什么“秘密”？》与《《小团圆》：张爱玲的一个梦》的KL距离： 5.629955584E9
《《小团圆》：张爱玲的一个梦》与《《小团圆》究竟泄了张爱玲什么“秘密”？》的KL距离8.62991872E9
《《小团圆》究竟泄了张爱玲什么“秘密”？》与《1945年毛和蒋介石在重庆谈判前的秘密情报战》的KL距离 6.50994432E9
《1945年毛和蒋介石在重庆谈判前的秘密情报战》与《《小团圆》究竟泄了张爱玲什么“秘密”？》的KL距离 8.029924864E9
《“小团圆”张爱玲的一个梦》与《1945年毛和蒋介石在重庆谈判前的秘密情报战》的KL距离9.219941376E9
《1945年毛和蒋介石在重庆谈判前的秘密情报战》与《“小团圆”张爱玲的一个梦》的KL距离7.739928576E9

从上面结果可以看出：《张秘密》与《张梦》之间距离最近，《毛》与《张梦》直接的概率分布距离近于《毛》与《张秘密》之间的概率分布。

另外补充一点java传参的方式：对于简单类型采用值传递的方法；对于复杂类型采用的是引用传递的机制。这有点类似于matlab.所以，

double f1=CalKL(enList1,enList2);
double f2=CalKL(enList2,enList1);
double f3=CalKL(enList1,enList3);

CalKL函数中如果改变了enlist1，enlist2的值就会使结果不正确。

分享到：