实现聚类的邻近矩阵

Question

请我对这个领域有点陌生，所以如果这个问题听起来微不足道或基本，请原谅我。

我有一组数据集（具体来说是词袋），我需要通过使用它们彼此之间的编辑距离来查找并生成邻近矩阵来生成邻近矩阵。

然而，我很困惑如何跟踪矩阵中的数据/字符串。我需要邻近矩阵来进行聚类。

或者您通常如何在该领域解决此类问题。我正在使用 perl 和 R 来实现这个。

这是我用 perl 编写的一个典型代码，它从包含我的词袋的文本文件中读取，

use strict ;
   use warnings ; 
   use Text::Levenshtein qw(distance) ;
   main(@ARGV);
   sub main
   {    
    my @TokenDistances ;
    my $Tokenfile  = 'TokenDistinct.txt';
    my @Token ;
    my $AppendingCount  = 0 ; 
    my @Tokencompare ;  
    my %Levcount  = ();
    open (FH ,"< $Tokenfile" ) or die ("Error opening file . $!");
     while(<FH>)
     {
        chomp $_;
        $_ =~ s/^(\s+)$//g;
        push (@Token , $_ ); 
     }
    close(FH); 
     @Tokencompare = @Token ; 


     foreach my $tokenWord(@Tokencompare)
     { 
        my $lengthoffile =  scalar @Tokencompare;
        my $i = 0 ;
        chomp $tokenWord ;

        #@TokenDistances = levDistance($tokenWord , \@Tokencompare );
        for($i = 0 ; $i < $lengthoffile ;$i++)
        {
            if(scalar @TokenDistances ==  scalar @Tokencompare)
            {
                print "Yipeeeeeeeeeeeeeeeeeeeee\n";
            }
            chomp $tokenWord   ;
            chomp $Tokencompare[$i];
            #print   $tokenWord. "   {$Tokencompare[$i]}  " . "      $TokenDistances[$i] " . "\n";
            #$Levcount{$tokenWord}{$Tokencompare[$i]} = $TokenDistances[$i];
            $Levcount{$tokenWord}{$Tokencompare[$i]} = levDistance($tokenWord , $Tokencompare[$i] );

        }

        StoreSortedValues ( \%Levcount ,\$tokenWord , \$AppendingCount);
        $AppendingCount++;
        %Levcount = () ;

     } 
    # %Levcount  = (); 
}

sub levDistance
{
    my $string1 = shift ;
    #my @StringList = @{(shift)};
    my $string2 =  shift ;
    return distance($string1 , $string2);
}


sub StoreSortedValues {


    my $Levcount  = shift;
    my $tokenWordTopMost = ${(shift)} ; 
    my $j = ${(shift)};
    my @ListToken;
    my $Tokenfile = 'LevResult.txt';

    if($j == 0 )
    {
        open (FH ,"> $Tokenfile" ) or die ("Error opening file . $!");
    }
    else
    {
        open (FH ,">> $Tokenfile" ) or die ("Error opening file . $!");
    }

                print $tokenWordTopMost; 
                my %tokenWordMaster = %{$Levcount->{$tokenWordTopMost}};
                @ListToken = sort { $tokenWordMaster{$a} cmp $tokenWordMaster{$b} }   keys %tokenWordMaster;
            #@ListToken = keys %tokenWordMaster;

        print FH "-------------------------- " . $tokenWordTopMost . "-------------------------------------\n";
        #print FH  map {"$_  \t=>  $tokenWordMaster{$_} \n "}   @ListToken;
        foreach my $tokey (@ListToken)
        {
            print FH  "$tokey=>\t" . $tokenWordMaster{$tokey} . "\n" 

        }

        close(FH) or  die ("Error Closing File.  $!");

}

问题是我如何从中表示邻近矩阵，并且仍然能够跟踪哪个比较代表我的矩阵中的哪个比较。

Answer 1

在 RecordLinkage 包中，有 levenshteinDist 函数，这是计算字符串之间编辑距离的一种方法。

install.packages("RecordLinkage")
library(RecordLinkage)

设置一些数据：

fruit <- c("Apple", "Apricot", "Avocado", "Banana", "Bilberry", "Blackberry", 
    "Blackcurrant", "Blueberry", "Currant", "Cherry")

现在创建一个由零组成的矩阵，为距离表保留内存。然后使用嵌套的 for 循环来计算各个距离。我们以一个矩阵结束，每个水果有一行和一列。因此，我们可以将列和行重命名为与原始向量相同。

fdist <- matrix(rep(0, length(fruit)^2), ncol=length(fruit))
for(i in seq_along(fruit)){
  for(j in seq_along(fruit)){
    fdist[i, j] <- levenshteinDist(fruit[i], fruit[j])
  }
}
rownames(fdist) <- colnames(fdist) <- fruit

结果：

fdist

             Apple Apricot Avocado Banana Bilberry Blackberry Blackcurrant
Apple            0       5       6      6        7          9           12
Apricot          5       0       6      7        8         10           10
Avocado          6       6       0      6        8          9           10
Banana           6       7       6      0        7          8            8
Bilberry         7       8       8      7        0          4            9
Blackberry       9      10       9      8        4          0            5
Blackcurrant    12      10      10      8        9          5            0
Blueberry        8       9       9      8        3          3            8
Currant          7       5       6      5        8         10            6
Cherry           6       7       7      6        4          6           10

Answer 2

邻近度或相似度（或相异度）矩阵只是一个存储对象对相似度得分的表。因此，如果您有 N 个对象，则 R 代码可以是 simMat <- matrix(nrow = N, ncol = N)，然后是 的每个条目 (i,j) >simMat 表示项目 i 和项目 j 之间的相似度。

在 R 中，您可以使用多个包（包括 vwr）来计算 Levenshtein 编辑距离。

您可能还会对这本维基教科书感兴趣：http://en.wikibooks.org/wiki/ R_编程/文本_处理