知识点整理

k-means 怎么优化选取k

1、减少聚类的数目K。因为,每个样本都要跟类中心计算距离。
2、减少样本的特征维度。比如说,通过PCA等进行降维。
3、考察其他的聚类算法,通过选取to据,去测试聚类算法的性能。

4、hadoop集群,K-means算法是很容易进行并行计算的。

kmeans一般在数据分析前期使用,选取适当的k,将数据聚类后,然后研究不同聚类下数据的特点。

算法原理:

(1) 随机选取k个中心点;

(2) 在第j次迭代中,对于每个样本点,选取最近的中心点,归为该类;

(3) 更新中心点为每类的均值;

(4) j<-j+1 ,重复(2)(3)迭代更新,直至误差小到某个值或者到达一定的迭代步数,误差不变.

空间复杂度o(N)

时间复杂度o(I*K*N)

其中N为样本点个数,K为中心点个数,I为迭代次数

为什么迭代后误差逐渐减小:

SSE=

对于 而言,求导后,当 时,SSE最小,对应第(3)步;

对于 而言,求导后,当 时,SSE最小,对应第(2)步。

因此kmeans迭代能使误差逐渐减少直到不变

轮廓系数:

轮廓系数(Silhouette Coefficient)结合了聚类的凝聚度(Cohesion)和分离度(Separation),用于评估聚类的效果。该值处于-1~1之间,值越大,表示聚类效果越好。具体计算方法如下:

对于每个样本点i,计算点i与其同一个簇内的所有其他元素距离的平均值,记作a(i),用于量化簇内的凝聚度。
选取i外的一个簇b,计算i与b中所有点的平均距离,遍历所有其他簇,找到最近的这个平均距离,记作b(i),即为i的邻居类,用于量化簇之间分离度。
对于样本点i,轮廓系数s(i) = (b(i) – a(i))/max{a(i),b(i)}
计算所有i的轮廓系数,求出平均值即为当前聚类的整体轮廓系数,度量数据聚类的紧密程度
从上面的公式,不难发现若s(i)小于0,说明i与其簇内元素的平均距离小于最近的其他簇,表示聚类效果不好。如果a(i)趋于0,或者b(i)足够大,即a(i)<<b(i),那么s(i)趋近与1,说明聚类效果比较好。

K值确定

法1:(轮廓系数)在实际应用中,由于Kmean一般作为数据预处理,或者用于辅助分聚类贴标签。所以k一般不会设置很大。可以通过枚举,令k从2到一个固定值如10,在每个k值上重复运行数次kmeans(避免局部最优解),并计算当前k的平均轮廓系数,最后选取轮廓系数最大的值对应的k作为最终的集群数目。

法2:(Calinski-Harabasz准则)

其中SSB是类间方差, ,m为所有点的中心点,mi为某类的中心点;

SSW是类内方差,;

(N-k)/(k-1)是复杂度;

比率越大,数据分离度越大.

前提:

Duda-Hart test 看数据集是否适合分为超过1类

初始点选择方法:

思想,初始的聚类中心之间相互距离尽可能远.

法1(kmeans++):

1、从输入的数据点集合中随机选择一个点作为第一个聚类中心

2、对于数据集中的每一个点x,计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)

3、选择一个新的数据点作为新的聚类中心,选择的原则是:D(x)较大的点,被选取作为聚类中心的概率较大

4、重复2和3直到k个聚类中心被选出来

5、利用这k个初始的聚类中心来运行标准的k-means算法

从上面的算法描述上可以看到,算法的关键是第3步,如何将D(x)反映到点被选择的概率上,一种算法如下:

1、先从我们的数据库随机挑个随机点当“种子点”

2、对于每个点,我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里,然后把这些距离加起来得到Sum(D(x))。

3、然后,再取一个随机值,用权重的方式来取计算下一个“种子点”。这个算法的实现是,先取一个能落在Sum(D(x))中的随机值Random,然后用Random -= D(x),直到其<=0,此时的点就是下一个“种子点”。

4、重复2和3直到k个聚类中心被选出来

5、利用这k个初始的聚类中心来运行标准的k-means算法

法2:选用层次聚类或Canopy算法进行初始聚类,然后从k个类别中分别随机选取k个点

,来作为kmeans的初始聚类中心点

优点:

1、 算法快速、简单;

2、 容易解释

3、 聚类效果中上

4、 适用于高维

缺陷:

1、 对离群点敏感,对噪声点和孤立点很敏感(通过k-centers算法可以解决)

2、 K-means算法中聚类个数k的初始化

3、初始聚类中心的选择,不同的初始点选择可能导致完全不同的聚类结果。

实践操作:

R语言

1、####################判断是否应该分为超过1类##########################

dudahart2(x,clustering,alpha=0.001)

2、###################判断使用轮廓系数或Calinski-Harabasz准则选用k值,以及是否使用大规模样本点处理方式##########################################

pamk(data,krange=2:10,criterion="asw", usepam=TRUE,

scaling=FALSE, alpha=0.001, diss=inherits(data, "dist"),    critout=FALSE, ns=10, seed=NULL, ...)

3、############利用pamk求出来的k,用kmeans聚类####################

pamk.result <- pamk(data)

pamk.result$nc

kc <- kmeans(data, pamk.result$nc)

4、############画出k与轮廓系数关系,求出拐点值########################

# 0-1 正规化数据

min.max.norm <- function(x){

    (x-min(x))/(max(x)-min(x))

}

raw.data <- iris[,1:4]

norm.data <- data.frame(sl = min.max.norm(raw.data[,1]),

                                        sw = min.max.norm(raw.data[,2]),

                                        pl = min.max.norm(raw.data[,3]),

                                        pw = min.max.norm(raw.data[,4]))

## k取2到8,评估K

K <- 2:8

round <- 30 # 每次迭代30次,避免局部最优

rst <- sapply(K, function(i){

    print(paste("K=",i))

    mean(sapply(1:round,function(r){

        print(paste("Round",r))

        result <- kmeans(norm.data, i)

        stats <- cluster.stats(dist(norm.data), result$cluster)

        stats$avg.silwidth

    }))

})

plot(K,rst,type='l',main='轮廓系数与K的关系', ylab='轮廓系数')

5、层次聚类得出k-means初始点

iris.hc <- hclust( dist(iris[,1:4]))

# plot( iris.hc, hang = -1)

plclust( iris.hc, labels = FALSE, hang = -1)

re <- rect.hclust(iris.hc, k = 3)

iris.id <- cutree(iris.hc, 3)######得出类别##########

 

6、################采用kmeans++选用k个初始点##################################

n<-length(x)

seed<-round(runif(1,1,n))

for ( i in 1:k){

       if(i==1){ seed[i]<- round(runif(1,1,N)) }

       dd<-0

       tmp<-0

       for(s in 1:n)

       {

              m<-length(seed)

                     for (j in 1:m) {

                            if(j==1){ tmp<-dist(x[s],seed[j]) }

                            else

                                   {

                                          tmptwo<-tmp

                                          tmp<-dist(x[s],seed[j])

                                          if(tmp>tmptwo)tmp<-tmptwo

                                   }

                            }

              dd[s]<-tmp

       }

       sumd<-sum(dd)

       random<--round(runif(1,0, sumd))

       for(ii in 1:n)

       {

              if(random<=0){break};

              else{

              random<-random-dd[ii]

         }

}

seed[i+1]<-ii

}

 

 

KNN邻近分类算法

K邻近(k-Nearest Neighbor,KNN)分类算法是最简单的机器学习算法了。它采用测量不同特征值之间的距离方法进行分类。它的思想很简单:计算一个点A与其他所有点之间的距离,取出与该点最近的k个点,然后统计这k个点里面所属分类比例最大的,则点A属于该分类。

下面用一个例子来说明一下:

 

电影名称

打斗次数

接吻次数

电影类型

California Man

3

104

Romance

He’s Not Really into Dudes

2

100

Romance

Beautiful Woman

1

81

Romance

Kevin Longblade

101

10

Action

Robo Slayer 3000

99

5

Action

Amped II

98

2

Action

简单说一下这个数据的意思:这里用打斗次数和接吻次数来界定电影类型,如上,接吻多的是Romance类型的,而打斗多的是动作电影。还有一部名字未知(这里名字未知是为了防止能从名字中猜出电影类型),打斗次数为18次,接吻次数为90次的电影,它到底属于哪种类型的电影呢?

KNN算法要做的,就是先用打斗次数和接吻次数作为电影的坐标,然后计算其他六部电影与未知电影之间的距离,取得前K个距离最近的电影,然后统计这k个距离最近的电影里,属于哪种类型的电影最多,比如Action最多,则说明未知的这部电影属于动作片类型。

在实际使用中,有几个问题是值得注意的:K值的选取,选多大合适呢?计算两者间距离,用哪种距离会更好呢?计算量太大怎么办?假设样本中,类型分布非常不均,比如Action的电影有200部,但是Romance的电影只有20部,这样计算起来,即使不是Action的电影,也会因为Action的样本太多,导致k个最近邻居里有不少Action的电影,这样该怎么办呢?

没有万能的算法,只有在一定使用环境中最优的算法。

1.1 算法指导思想

kNN算法的指导思想是“近朱者赤,近墨者黑”,由你的邻居来推断出你的类别。

先计算待分类样本与已知类别的训练样本之间的距离,找到距离与待分类样本数据最近的k个邻居;再根据这些邻居所属的类别来判断待分类样本数据的类别。

 

1.2相似性度量

用空间内两个点的距离来度量。距离越大,表示两个点越不相似。距离的选择有很多[13],通常用比较简单的欧式距离。

欧式距离

马氏距离:马氏距离能够缓解由于属性的线性组合带来的距离失真,是数据的协方差矩阵。

曼哈顿距离

 

切比雪夫距离

闵氏距离:r取值为2时:曼哈顿距离;r取值为1时:欧式距离。

 

平均距离

弦距离

 

测地距离

 

 

1.2 类别的判定

投票决定:少数服从多数,近邻中哪个类别的点最多就分为该类。

加权投票法:根据距离的远近,对近邻的投票进行加权,距离越近则权重越大(权重为距离平方的倒数)

 优缺点

1.2.1              优点

  1. 简单,易于理解,易于实现,无需估计参数,无需训练;
  2. 适合对稀有事件进行分类;
  3. 特别适合于多分类问题(multi-modal,对象具有多个类别标签), kNN比SVM的表现要好。
  4. 懒惰算法,对测试样本分类时的计算量大,内存开销大,评分慢;
  5. 当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数;
  6. 可解释性较差,无法给出决策树那样的规则。

1.2.2              缺点

1.3 常见问题

1.3.1              k值的设定

k值选择过小,得到的近邻数过少,会降低分类精度,同时也会放大噪声数据的干扰;而如果k值选择过大,并且待分类样本属于训练集中包含数据数较少的类,那么在选择k个近邻的时候,实际上并不相似的数据亦被包含进来,造成噪声增加而导致分类效果的降低。

如何选取恰当的K值也成为KNN的研究热点。k值通常是采用交叉检验来确定(以k=1为基准)。

经验规则:k一般低于训练样本数的平方根。

1.3.2              类别的判定方式

投票法没有考虑近邻的距离的远近,距离更近的近邻也许更应该决定最终的分类,所以加权投票法更恰当一些。

1.3.3              距离度量方式的选择

高维度对距离衡量的影响:众所周知当变量数越多,欧式距离的区分能力就越差。

变量值域对距离的影响:值域越大的变量常常会在距离计算中占据主导作用,因此应先对变量进行标准化。

1.3.4              训练样本的参考原则

学者们对于训练样本的选择进行研究,以达到减少计算的目的,这些算法大致可分为两类。第一类,减少训练集的大小。KNN算法存储的样本数据,这些样本数据包含了大量冗余数据,这些冗余的数据增了存储的开销和计算代价。缩小训练样本的方法有:在原有的样本中删掉一部分与分类相关不大的样本样本,将剩下的样本作为新的训练样本;或在原来的训练样本集中选取一些代表样本作为新的训练样本;或通过聚类,将聚类所产生的中心点作为新的训练样本。

在训练集中,有些样本可能是更值得依赖的。可以给不同的样本施加不同的权重,加强依赖样本的权重,降低不可信赖样本的影响。

1.3.5              性能问题

kNN是一种懒惰算法,而懒惰的后果:构造模型很简单,但在对测试样本分类地的系统开销大,因为要扫描全部训练样本并计算距离。

已经有一些方法提高计算的效率,例如压缩训练样本量等。

1.4 算法流程

  1. 准备数据,对数据进行预处理
  2. 选用合适的数据结构存储训练数据和测试元组
  3. 设定参数,如k
  4. 维护一个大小为k的的按距离由大到小的优先级队列,用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组,分别计算测试元组到这k个元组的距离,将训练元组标号和距离存入优先级队列
  5. 遍历训练元组集,计算当前训练元组与测试元组的距离,将所得距离L 与优先级队列中的最大距离Lmax
  6. 进行比较。若L>=Lmax,则舍弃该元组,遍历下一个元组。若L < Lmax,删除优先级队列中最大距离的元
  7. 组,将当前训练元组存入优先级队列。
  8. 遍历完毕,计算优先级队列中k 个元组的多数类,并将其作为测试元组的类别。

9.测试元组集测试完毕后计算误差率,继续设定不同的k 值重新进行训练,最后取误差率最小的k 值。

 

 

结巴动语规划

1 简介

jieba分词主要是基于统计词典,构造一个前缀词典;然后利用前缀词典对输入句子进行切分,得到所有的切分可能,根据切分位置,构造一个有向无环图;通过动态规划算法,计算得到最大概率路径,也就得到了最终的切分形式。

2 实例讲解

以“去北京大学玩”为例,作为待分词的输入文本。

离线统计的词典形式如下,每一行有三列,第一列是词,第二列是词频,第三列是词性。

...
北京大学 2053 nt
大学 20025 n
去 123402 v
玩 4207 v
北京 34488 ns
北 17860 ns
京 6583 ns
大 144099 a
学 17482 n
...

2.1 前缀词典构建

首先是基于统计词典构造前缀词典,如统计词典中的词“北京大学”的前缀分别是“北”、“北京”、“北京大”;词“大学”的前缀是“大”。统计词典中所有的词形成的前缀词典如下所示,你也许会注意到“北京大”作为“北京大学”的前缀,但是它的词频却为0,这是为了便于后面有向无环图的构建。

...
北京大学 2053
北京大 0
大学 200251234024207
北京 3448817860658314409917482
...

2.2 有向无环图构建

然后基于前缀词典,对输入文本进行切分,对于“去”,没有前缀,那么就只有一种划分方式;对于“北”,则有“北”、“北京”、“北京大学”三种划分方式;对于“京”,也只有一种划分方式;对于“大”,则有“大”、“大学”两种划分方式,依次类推,可以得到每个字开始的前缀词的划分方式。

在jieba分词中,对每个字都是通过在文本中的位置来标记的,因此可以构建一个以位置为key,相应划分的末尾位置构成的列表为value的映射,如下所示,

0: [0]
1: [1,2,4]
2: [2]
3: [3,4]
4: [4]
5: [5]

对于0: [0],表示位置0对应的词,就是0 ~ 0,就是“去”;对于1: [1,2,4],表示位置1开始,在1,2,4位置都是词,就是1 ~ 1,1 ~ 2,1 ~ 4,即“北”,“北京”,“北京大学”这三个词。

对于每一种划分,都将相应的首尾位置相连,例如,对于位置1,可以将它与位置1、位置2、位置4相连接,最终构成一个有向无环图,如下所示,

2.3 最大概率路径计算

在得到所有可能的切分方式构成的有向无环图后,我们发现从起点到终点存在多条路径,多条路径也就意味着存在多种分词结果,例如,

# 路径1
0 -> 1 -> 2 -> 3 -> 4 -> 5
# 分词结果1
去 / 北 / 京 / 大 / 学 / 玩
# 路径2
0 -> 1 , 2 -> 3 -> 4 -> 5
# 分词结果2
去 / 北京  /  大 / 学 / 玩
# 路径3
0 -> 1 , 2 -> 3 , 4 -> 5
# 分词结果3
去 / 北京  /  大学  /  玩
# 路径4
0 -> 1 , 2 , 3 , 4 -> 5
# 分词结果4
去 / 北京大学    /     玩
...

因此,我们需要计算最大概率路径,也即按照这种方式切分后的分词结果的概率最大。在计算最大概率路径时,jieba分词采用从后往前这种方式进行计算。为什么采用从后往前这种方式计算呢?因为,我们这个有向无环图的方向是从前向后指向,对于一个节点,我们只知道这个节点会指向后面哪些节点,但是我们很难直接知道有哪些前面的节点会指向这个节点。

在采用动态规划计算最大概率路径时,每到达一个节点,它前面的节点到终点的最大路径概率已经计算出来。

3 源码分析

3.1 算法流程

jieba.__init__.py中实现了jieba分词接口函数cut(self, sentence, cut_all=False, HMM=True)。

jieba分词接口主入口函数,会首先将输入文本解码为Unicode编码,然后根据入参,选择不同的切分方式,本文主要以精确模式进行讲解,因此cut_all和HMM这两个入参均为默认值;

切分方式选择,

re_han = re_han_default
re_skip = re_skip_default

块切分方式选择,

cut_block = self.__cut_DAG

函数__cut_DAG(self, sentence)首先构建前缀词典,其次构建有向无环图,然后计算最大概率路径,最后基于最大概率路径进行分词,如果遇到未登录词,则调用HMM模型进行切分。本文主要涉及前三个部分,基于HMM的分词方法则在下一文章中详细说明。

3.2 前缀词典构建

get_DAG(self, sentence)函数会首先检查系统是否初始化,如果没有初始化,则进行初始化。在初始化的过程中,会构建前缀词典。

构建前缀词典的入口函数是gen_pfdict(self, f),解析离线统计词典文本文件,每一行分别对应着词、词频、词性,将词和词频提取出来,以词为key,以词频为value,加入到前缀词典中。对于每个词,再分别获取它的前缀词,如果前缀词已经存在于前缀词典中,则不处理;如果该前缀词不在前缀词典中,则将其词频置为0,便于后续构建有向无环图。

jieba分词中gen_pfdict函数实现如下,

# f是离线统计的词典文件句柄
def gen_pfdict(self, f):
    # 初始化前缀词典
    lfreq = {}
    ltotal = 0
    f_name = resolve_filename(f)
    for lineno, line in enumerate(f, 1):
        try:
            # 解析离线词典文本文件,离线词典文件格式如第2章中所示
            line = line.strip().decode('utf-8')
            # 词和对应的词频
            word, freq = line.split(' ')[:2]
            freq = int(freq)
            lfreq[word] = freq
            ltotal += freq
            # 获取该词所有的前缀词
            for ch in xrange(len(word)):
                wfrag = word[:ch + 1]
                # 如果某前缀词不在前缀词典中,则将对应词频设置为0,
                # 如第2章中的例子“北京大”
                if wfrag not in lfreq:
                    lfreq[wfrag] = 0
        except ValueError:
            raise ValueError(
                'invalid dictionary entry in %s at Line %s: %s' % (f_name, lineno, line))
    f.close()
    return lfreq, ltotal

为什么jieba没有使用trie树作为前缀词典存储的数据结构?

参考jieba中的issue–不用Trie,减少内存加快速度;优化代码细节 #187,本处直接引用该issue的comment,如下,

对于get_DAG()函数来说,用Trie数据结构,特别是在Python环境,内存使用量过大。经实验,可构造一个前缀集合解决问题。

该集合储存词语及其前缀,如set([‘数’, ‘数据’, ‘数据结’, ‘数据结构’])。在句子中按字正向查找词语,在前缀列表中就继续查找,直到不在前缀列表中或超出句子范围。大约比原词库增加40%词条。

该版本通过各项测试,与原版本分词结果相同。

测试:一本5.7M的小说,用默认字典,64位Ubuntu,Python 2.7.6。

Trie:第一次加载2.8秒,缓存加载1.1秒;内存277.4MB,平均速率724kB/s;

前缀字典:第一次加载2.1秒,缓存加载0.4秒;内存99.0MB,平均速率781kB/s;

此方法解决纯Python中Trie空间效率低下的问题。

同时改善了一些代码的细节,遵循PEP8的格式,优化了几个逻辑判断。

3.2 有向无环图构建

有向无环图,directed acyclic graphs,简称DAG,是一种图的数据结构,顾名思义,就是没有环的有向图。

DAG在分词中的应用很广,无论是最大概率路径,还是其它做法,DAG都广泛存在于分词中。因为DAG本身也是有向图,所以用邻接矩阵来表示是可行的,但是jieba采用了Python的dict结构,可以更方便的表示DAG。最终的DAG是以{k : [k , j , ..] , m : [m , p , q] , …}的字典结构存储,其中k和m为词在文本sentence中的位置,k对应的列表存放的是文本中以k开始且词sentence[k: j + 1]在前缀词典中的 以k开始j结尾的词的列表,即列表存放的是sentence中以k开始的可能的词语的结束位置,这样通过查找前缀词典就可以得到词。

get_DAG(self, sentence)函数进行对系统初始化完毕后,会构建有向无环图。

从前往后依次遍历文本的每个位置,对于位置k,首先形成一个片段,这个片段只包含位置k的字,然后就判断该片段是否在前缀词典中,

  1. 如果这个片段在前缀词典中,1.1 如果词频大于0,就将这个位置i追加到以k为key的一个列表中;1.2 如果词频等于0,如同第2章中提到的“北京大”,则表明前缀词典存在这个前缀,但是统计词典并没有这个词,继续循环;
  2. 如果这个片段不在前缀词典中,则表明这个片段已经超出统计词典中该词的范围,则终止循环;
  3. 然后该位置加1,然后就形成一个新的片段,该片段在文本的索引为[k:i+1],继续判断这个片段是否在前缀词典中。

jieba分词中get_DAG函数实现如下,

# 有向无环图构建主函数
def get_DAG(self, sentence):
    # 检查系统是否已经初始化
    self.check_initialized()
    # DAG存储向无环图的数据,数据结构是dict
    DAG = {}
    N = len(sentence)
    # 依次遍历文本中的每个位置
    for k in xrange(N):
        tmplist = []
        i = k
        # 位置k形成的片段
        frag = sentence[k]
        # 判断片段是否在前缀词典中
        # 如果片段不在前缀词典中,则跳出本循环
        # 也即该片段已经超出统计词典中该词的长度
        while i < N and frag in self.FREQ:
            # 如果该片段的词频大于0
            # 将该片段加入到有向无环图中
            # 否则,继续循环
            if self.FREQ[frag]:
                tmplist.append(i)
            # 片段末尾位置加1
            i += 1
            # 新的片段较旧的片段右边新增一个字
            frag = sentence[k:i + 1]
        if not tmplist:
            tmplist.append(k)
        DAG[k] = tmplist
    return DAG

以“去北京大学玩”为例,最终形成的有向无环图为,

{0: [0], 1: [1,2,4], 2: [2], 3: [3,4], 4: [4], 5: [5]}

3.3 最大概率路径计算

3.2章节中构建出的有向无环图DAG的每个节点,都是带权的,对于在前缀词典里面的词语,其权重就是它的词频;我们想要求得route = (w1,w2,w3,…,wn),使得 weight(wi)∑weight(wi) 最大。

如果需要使用动态规划求解,需要满足两个条件,

  • 重复子问题
  • 最优子结构

我们来分析一下最大概率路径问题,是否满足动态规划的两个条件。

重复子问题

对于节点wi和其可能存在的多个后继节点Wj和Wk,

任意通过Wi到达Wj的路径的权重 = 该路径通过Wi的路径权重 + Wj的权重,也即{Ri -> j} = {Ri + weight(j)}
任意通过Wi到达Wk的路径的权重 = 该路径通过Wi的路径权重 + Wk的权重,也即{Ri -> k} = {Ri + weight(k)}

即对于拥有公共前驱节点Wi的节点Wj和Wk,需要重复计算达到Wi的路径的概率。

最优子结构

对于整个句子的最优路径Rmax和一个末端节点Wx,对于其可能存在的多个前驱Wi,Wj,Wk…,设到达Wi,Wj,Wk的最大路径分别是Rmaxi,Rmaxj,Rmaxk,有,

Rmax = max(Rmaxi,Rmaxj,Rmaxk,...) + weight(Wx)

于是,问题转化为,求解Rmaxi,Rmaxj,Rmaxk,…等,

组成了最优子结构,子结构里面的最优解是全局的最优解的一部分。

状态转移方程为,

Rmax = max{(Rmaxi,Rmaxj,Rmaxk,...) + weight(Wx)}

jieba分词中计算最大概率路径的主函数是calc(self, sentence, DAG, route),函数根据已经构建好的有向无环图计算最大概率路径。

函数是一个自底向上的动态规划问题,它从sentence的最后一个字(N-1)开始倒序遍历sentence的每个字(idx)的方式,计算子句sentence[idx ~ N-1]的概率对数得分。然后将概率对数得分最高的情况以(概率对数,词语最后一个位置)这样的元组保存在route中。

函数中,logtotal为构建前缀词频时所有的词频之和的对数值,这里的计算都是使用概率对数值,可以有效防止下溢问题。

jieba分词中calc函数实现如下,

def calc(self, sentence, DAG, route):
    N = len(sentence)
    # 初始化末尾为0
    route[N] = (0, 0)
    logtotal = log(self.total)
    # 从后到前计算
    for idx in xrange(N - 1, -1, -1):
        route[idx] = max((log(self.FREQ.get(sentence[idx:x + 1]) or 1) -
                          logtotal + route[x + 1][0], x) for x in DAG[idx])

题目
输入一个整型数组,数组里有正数也有负数。数组中一个或者连续的多个整数组成一个字数组。求所有字数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18
  • 1
  • 2

思路

因为时间复杂度为O(n),则只能遍历一次数组,这里同时使用两个变量sum和max,其中sum保存的是当前的和,若sum<0,则从下一个位置从新记录,max记录的是历史的最大值,只有当sum>max时用sum替换max。
  • 1
  • 2

代码

public class Item {  
    public static void main(String args[]) {  

       int array[] = {1, -2, 3, 10, -4, 7, 2, -5};  
       System.out.println(findMax(array));

    }  

    public static int findMax(int array[]){
        //加上约束条件,防止当数组为空时造成数组越界
        if (array.length == 0) {
            return 0;
        }

        int max = array[0];
        int sum = 0;

        for(int i=0; i<array.length; i++){  
            //如果加上某个元素sum>=0的话,就加;
            //当数组全为负数的时候只要有加法就一定比原来的数小,此时就相当于找出数组内最大的数 
            if(sum >= 0) { 
                sum += array[i];  
            }
            else{  
                sum = array[i]; //否则从当前位置重新计算  
            }
            if(sum > max){  
                max = sum;  
            }
        }  
        return max;  
    }
}

 

# coding:utf-8
'''
求两个字符串的最长公共子串
思想:建立一个二维数组,保存连续位相同与否的状态
'''

def getNumofCommonSubstr(str1, str2):

    lstr1 = len(str1)
    lstr2 = len(str2)
    record = [[0 for i in range(lstr2+1)] for j in range(lstr1+1)]  # 多一位
    maxNum = 0          # 最长匹配长度
    p = 0               # 匹配的起始位

    for i in range(lstr1):
        for j in range(lstr2):
            if str1[i] == str2[j]:
                # 相同则累加
                record[i+1][j+1] = record[i][j] + 1
                if record[i+1][j+1] > maxNum:
                    # 获取最大匹配长度
                    maxNum = record[i+1][j+1]
                    # 记录最大匹配长度的终止位置
                    p = i + 1
    return str1[p-maxNum:p], maxNum


if __name__ == '__main__':
    str1 = raw_input()
    str2 = raw_input()

    res = getNumofCommonSubstr(str1, str2)
    print res

 

求公共子字符串问题(连续的)

这个题目是当时远景能源公司现场笔试的一道题目,当时根本就不知道动态规划是什么鬼,直接上来就暴力求解,面试官很谄媚的问我,你这能求出来吗?当时很年轻的说,能啊!现在想,当时哪来的自信和逗比勇气说这大话。。。在《进军硅谷》这本书上看到原题,我是懵逼,怎么想出这种解答出来的,下面直接上思路和代码。

思路:

定义二维数组dp[i][j]记录最大公共子串的长度,

  • 若要返回字符串可以用s1.substring(i-dp[i][j]+1, i+1)
  • 当s[i]==s[j]时,dp[i][j]=dp[i-1][j-1]+1;
  • 当s[i]!=s[j]时,dp[i][j]=0;

有点类似于数学归纳法

方案:

  • 首先考虑空或者长度为0的情况,直接返回””;
  • 然后进入双重循环:
  • 1.利用charAt(int index)方法来比较两个字符串相等的时机
  • 2.考虑边界情况,两个字符串中有一个是起始为0就相等,则dp[i][j]=1
  • 3.除了边界情况,其他最大字符串长度为dp[i][j]=dp[i-1][j-1]+1;
  • 4.不断的替换掉最大的长度并返回公共子串
  • 最后循环结束后,返回最大的公共子串
 1     public static String maxCommonString(String s1, String s2) {
 2         String res = "";
 3         if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0)
 4             return res;
 5         int max = 0, m = s1.length(), n = s2.length();
 6         int[][] dp = new int[m][n]; // 定义一个二维数组记录最大公共子串的长度
 7         // 计算到s1的第i个字符和s2的第j个字符为止的最大公共子串长度
 8         for (int i = 0; i < m; i++) {
 9             for (int j = 0; j < n; j++) {
10                 // 如果s1字符串在i处和s2字符串在j处有字符相同,进入if代码块中
11                 if (s1.charAt(i) == s2.charAt(j)) {
12                     if (i == 0 || j == 0)
13                         dp[i][j] = 1;// 边界的情况
14                     else
15                         dp[i][j] = dp[i - 1][j - 1] + 1;// 加上当前长度
16                     // 记录最大长度和子串
17                     if (dp[i][j] > max) {
18                         max = dp[i][j];
19                         res = s1.substring(i - dp[i][j] + 1, i + 1);// substring()左闭右开
20                     }
21                 }
22             }
23         }
24         return res;
25     }

 

动态规划介绍

动态规划算法一般是基于一个递推公式(如上面的当s[i]==s[j]时,dp[i][j]=dp[i-1][j-1]+1;)以及一个或多个初始状态(当s[i]!=s[j]时,dp[i][j]=0;),当前子问题其实是由上一次子问题的解推算出来的。

2. 将单链表反转

从头到尾遍历原链表,每遍历一个结点,将其摘下放在新链表的最前端。注意链表为空和只有一个结点的情况。时间复杂度为O(n)。参考代码如下:

// 反转单链表  
ListNode * ReverseList(ListNode * pHead)  
{  
        // 如果链表为空或只有一个结点,无需反转,直接返回原链表头指针  
    if(pHead == NULL || pHead->m_pNext == NULL)    
        return pHead;  
  
    ListNode * pReversedHead = NULL; // 反转后的新链表头指针,初始为NULL  
    ListNode * pCurrent = pHead;  
    while(pCurrent != NULL)  
    {  
        ListNode * pTemp = pCurrent;  
        pCurrent = pCurrent->m_pNext;  
        pTemp->m_pNext = pReversedHead; // 将当前结点摘下,插入新链表的最前端  
        pReversedHead = pTemp;  
    }  
    return pReversedHead;  
}

 

图学习

1、       连通图上各边权值均不相同,则该图的最小生成树是唯一的。

(是自由树,即根结点不确定)

 

2、       用n表示图中顶点数目,e表示边或弧的数目:

(1)        对于无向图,e的取值范围是0~N(N-1)/2;有N(N-1)/2条边的无向图叫完全图。

(2)        对于有向图,e的取值范围0~N(N-1);相应的有N(N-1)条边的有向图叫有向完全图。

(3)        无向图中,对于图中任意两点都是连通的,叫做连通图;连通分量指的是无向图中极大连通子图;

(4)        在有向图中,若对于每一对顶点都存在路径,称图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量;

 

一颗有n个顶点的生成树有且仅有n-1条边;

如果一个图有n个顶点和小于n-1条边,则是非连通图;

如果一个图多余n-1条边,则一定有环;

有n-1条边的图不一定是生成树;

 

图的存储结构:

1)邻接矩阵(构造一个具有n个顶点和e条边的无向图的时间复杂度为O(n^2+e*n)),其中对邻接矩阵初始化耗费O(n^2)、

 

2)邻接表(在建立邻接表或逆邻接表时,若输入的顶点信息即为顶点编号,则建立邻接表的时间复杂度为O(n+e);否则需要通过查找才能找到顶点在图中的位置,时间复杂度为O(n.e))、

3)邻接多重表(与邻接表的区别在于同一条边在邻接表中用两个结点表示,而在邻接多重表中只有一个结点)、

4)十字链表(与建立邻接表相同的时间复杂度)。

 

遍历图的实质是对每个顶点查找器邻接点的过程。用邻接矩阵作图的存储结构时,查找每个顶点的邻接点所需要的时间为O(n^2);用邻接表作图的存储结构时,查找邻接点所需要的时间为O(e);当用邻接表作存储结构时,深度优先搜索遍历图的时间复杂度为O(n+e)。

 

一颗生成树的代价就是树上各边的代价之和。

构造最小生成树算法多利用了MST性质。主要利用 Prim算法(时间复杂度为O(n^2),与网中边数无关,适用于求边稠密的最小生成树)和 Kruskal算法(时间复杂度为O(e log e),适合于求边稀疏的最小生成树)。

 

3、       图的拓扑排序唯一,则其弧数比为n-1(n为图的顶点数)

4、       有向图中存在拓扑排序,则该图不存在回路。

 

5、       具有7个顶点的有向图至少应该有7条边才可能成为一个强连通图。

分析:强连通图必须从任何一点出发都可以回到原处,每个结点至少要有一条出路(单节点除外)至少n条边,正好可以组成一个环。

 

N个顶点的强连通图最多有N(N-1)条边,最少有    N条边。

(强连通图是指有一个有向图中任意两点v1、v2间存在路径及v2到v1的路径的图。)

最多情况:即n个顶点中两两相连,若不计方法,n个点两两相连有N(N-1)/2条边,而由于强连通图是有向图,故每条边有2个方向,N(N-1)/2*2=N(N-1),所以N个顶点的强连通图最多有N(N-1)条边;

最少情况:即N个顶点围成一个圈,且圈上各边方向一致,即均为顺时针或者逆时针,此时有N条边。

 

6、       要保证连通具有10个顶点的无向图,至少需要37条边。

分析:要保证连通具有10个顶点的无向图,重点是需要保证连通,则需要前面9个顶点两两相连,就能保证第10个顶点加入一条边时保证连通。即从9个结点中任意选出两个结点链接,则需要C(9,2)条边,再加上最后一条边,则总边数:C(9,2)+1=(9*8)/(1*2)=36,再加上1等于37.

 

分析二:

一个连通图边数最少情况就是这个图中没有回路情况,实际上这个图是一颗树,对于树,分支和结点关系是:分支数比结点数少1.

 

补充:

1)       具有10个顶点的无向图,边的总数最多为:

10*(10-1)/2=45;

2)       G是一个非连通无向图,共有28条边,则该图至少有9个顶点。

分析:假设至少有N个顶点,由于是非连通图,且要满足28条边,所以N=边为28的完全图(顶点最少)的顶点数+1(与完全图不连通)。完全图边数为28,解n(n-1)/2=28,得n=8,因此N=8+1=9;

 

7、       位示图法用于:磁盘空闲盘块的分配和回收。

8、       任何有向图的结点都可以排成拓扑排序,而且拓扑排序序列不唯一。(错误,有环就不行,有向无环图才能拓扑排序)

拓扑排序:

1)从有向图选择一个入度为0的顶点并输出之;

2)从图中删除该顶点和所有出边,直到不存在入度为0的顶点。

循环结束后,若输出的顶点数小于网中的顶点数,则有回路,否则输出的顶点序列就是一种拓扑序列。

 

补充:如何查找一个图中是否有环?

1)有向图中用拓扑排序,循环结束后,若输出的顶点数小于网中的顶点数,则有回路,否则输出的顶点序列就是一种拓扑序列。(还有顶点未输出,但已经不存在没有前驱的顶点)。拓扑排序使用前提就是有向完全图。

2)无向图中,若深度优先遍历过程中遇到回边(即指向已访问过的顶点的边),则必定存在环;有向图中用dfs比较复杂。

 

9、       图G的最小生成树G1中,可能会有某条边的权值超过未选边的权值。(正确,最小生成树是最小权重生成树的简称,只保证了所有权值之和最小,不好找每条路径都有最小权重)

 

10、  对于一个具有n个顶点的无向图,若采用邻接表表示,则存放表头结点的数组的大小为:n。

 

分析:邻接表的性质,存在多少个结点就有多少个头结点的数组,每个头结点的数组都指向该结点在图中直接相连的结点。

图的邻接表表示不是唯一的,它与表结点的链入次序有关;

 

11、  若无向图G=(V,E)中含有7个顶点,则保证图G在任何情况下都是连通的,则需要的边数最少是:16.

分析:与第6题分析一样。任何情况都连通的最少边数边数边分不最浪费的最少边情况,取点数减一的完全图即:

6*(6-1)/2=15,再加上一条边得结果16.

 

12、N个顶点的强连通图的边数至少有N个。

Leave a Reply

Your email address will not be published. Required fields are marked *