精华内容
下载资源
问答
  • 第一代技术,将互联网网页看作文本,主要采用传统信息检索的方法。 第二代技术,利用互联网的超文本结构,有效地计算网页的相关度与重要度,代表的算法有 PageRank 等。 第三代技术,有效利用日志数据与统计学习...

    从使用的数据类型,以及相关的机器学习技术的观点来看,互联网搜索经历了三代的发展历程。

           第一代技术,将互联网网页看作文本,主要采用传统信息检索的方法。

           第二代技术,利用互联网的超文本结构,有效地计算网页的相关度与重要度,代表的算法有 PageRank 等。

           第三代技术,有效利用日志数据与统计学习方法,使网页相关度与重要度计算的精度有了进一步的提升,代表的方法包括排序学习、网页重要度学习、匹配学习、话题模型学习、查询语句转化学习。

    基于词频统计——词位置加权的搜索引擎

             利用关键词在文档中出现的频率和位置排序是搜索引擎最早期排序的主要思想,其技术发展也最为成熟,是第一阶段搜索引擎的主要排序技术,应用非常广泛,至今仍是许多搜索引擎的核心排序技术。其基本原理是:关键词在文档中词频越高,出现的位置越重要,则被认为和检索词的相关性越好

    1)词频统计

            文档的词频是指查询关键词在文档中出现的频率。查询关键词词频在文档中出现的频率越高,其相关度越大。但当关键词为常用词时,使其对相关性判断的意义非常小。TF/IDF很好的解决了这个问题。TF/IDF算法被认为是信息检索中最重要的发明。

    • TF(Term Frequency):单文本词汇频率,用关键词的次数除以网页的总字数,其商称为“关键词的频率”。
    • IDF(Inverse Document Frequency):逆文本频率指数,其原理是,一个关键词在N个网页中出现过,那么N越大,此关键词的权重越小,反之亦然。当关键词为常用词时,其权重极小,从而解决词频统计的缺陷。

    2)词位置加权

            在搜索引擎中,主要针对网页进行词位置加权。所以,页面版式信息的分析至关重要。通过对检索关键词在Web页面中不同位置和版式,给予不同的权值,从而根据权值来确定所搜索结果与检索关键词相关程度。可以考虑的版式信息有:是否是标题,是否为关键词,是否是正文,字体大小,是否加粗等等。同时,锚文本的信息也是非常重要的,它一般能精确的描述所指向的页面的内容。

    基于链接分析排序的第二代搜索引擎

            链接分析排序的思想起源于文献引文索引机制,即论文被引用的次数越多或被越权威的论文引用,其论文就越有价值。链接分析排序的思路与其相似,网页被别的网页引用的次数越多或被越权威的网页引用,其价值就越大。被别的网页引用的次数越多,说明该网页越受欢迎,被越权威的网页引用,说明该网页质量越高。

             链接分析排序算法大体可以分为以下几类:基于随机漫游模型的,比如PageRank和Repution算法;基于概率模型的,如SALSA、PHITS;基于Hub和Authority相互加强模型的,如HITS及其变种;基于贝叶斯模型的,如贝叶斯算法及其简化版本。所有的算法在实际应用中都结合传统的内容分析技术进行了优化。本文主要介绍以下几种经典排序算法:

    1)PageRank算法

          PageRank是Google用于用来标识网页的等级/重要性的一种方法,是Google用来衡量一个站点的好坏的唯一标准。在揉合了诸如Title标识和Keywords标识等全部其他因素之后,Google通过PageRank来调整结果,使那些更具“等级/重要性”的网页在搜索结果中另站点排名获得提升,从而提高搜索结果的相关性和质量。其级别从0到10级,10级为满分。PR值越高说明该网页越受欢迎(越重要)。

              在PageRank提出之前,已经有研究者提出利用网页的入链数量来进行链接分析计算,这样的入链方法如果一个网页的入链越多,则该网页越重要。早期的非常多搜索引擎也採纳了入链数量作为链接分析方法,对于搜索引擎效果提升也有较明显的效果。 PageRank除了考虑到入链数量的影响,还參考了网页质量因素,两者相结合获得了更好的网页重要性评价标准。页面的重要程度用PageRank值来衡量,PageRank值主要体现在两个方面:

    • 如果一个网页被很多其他网页链接到的话说明这个网页比较重要,也就是PageRank值会相对较高
    • 如果一个PageRank值很高的网页链接到一个其他的网页,那么被链接到的网页的PageRank值会相应地因此而提高

      PageRanks实现

         PageRank的计算充分利用了两个如果:数量如果和质量如果。过程例如以下:
          1)在初始阶段:网页通过链接关系构建起Web图,每一个页面设置同样的PageRank值,通过若干轮的计算,会得到每一个页面所获得的最终PageRank值。随着每一轮的计算进行,网页当前的PageRank值会不断得到更新。

          2)在一轮中更新页面PageRank得分的计算方法:在一轮更新页面PageRank得分的计算中,每一个页面将其当前的PageRank值平均分配到本页面包括的出链上,这样每一个链接即获得了对应的权值。而每一个页面将全部指向本页面的入链所传入的权值求和,就可以得到新的PageRank得分。当每一个页面都获得了更新后的PageRank值,就完毕了一轮PageRank计算。 

    步骤一:  我们将Web做如下抽象:1、将每个网页抽象成一个节点;2、如果一个页面A有链接直接链向B,则存在一条有向边从A到B(多个相同链接不重复计算边)。因此,整个Web被抽象为一张有向图。现在假设世界上只有四张网页:A、B、C、D,其抽象结构如下图: 

                                                       这里写图片描述
            当一个用户停留在某页面时,跳转到页面上每个被链页面的概率是相同的。例如,上图中A页面链向B、C、D,所以一个用户从A跳转到B、C、D的概率各为1/3。设一共有N个网页,则可以组织这样一个N维矩阵:其中i行j列的值表示用户从页面j转到页面i的概率。这样一个矩阵叫做转移矩阵(Transition Matrix)。
                                     

    设初始时每个页面的rank值为1/N,这里就是1/4。按A-D顺序将页面rank为向量v: 
                                                                     

    注意,M第一行分别是A、B、C和D转移到页面A的概率,而v的第一列分别是A、B、C和D当前的rank,因此用M的第一行乘以v的第一列,所得结果就是页面A最新rank的合理估计,即同理,Mv的结果就分别代表A、B、C、D新rank:
                                 

        最终收敛为:

                            

    算法小问题:

    要满足收敛性,需要具备一个条件:图是强连通的,即从任意网页可以到达其他任意网页 ,否则使用矩阵连续相乘就会出现两种问题:1.终止点问题;2.陷阱问题 
    这里写图片描述

     

                   1.如果有些网页不指向其他网页(可能是垃圾网页),如果按照上面的计算,上网者到达这样的网页后便走投无路、四顾茫然,导致前面累计得到的转移概率被清零,这样计算下去得到的概率分布向量所有元素几乎为0。 
                  2.上网者跑到C网页后,就像跳进了陷阱,陷入了漩涡,再也不能从C中出来,将最终导致概率分布值全部转移到C上来,这使得其他网页的概率分布值为0,从而整个网页排名就失去了意义。

    改进:解决终止点问题和陷阱问题 ,地址栏输入而跳转到各个网页的概率是1/n; 

        我们假定他有一个确定的概率会输入网址直接跳转到一个随机的网页,并且跳转到每个网页的概率是一样的。即上网者每一步查看当前网页的概率为a,那么从浏览器地址栏跳转的概率为(1-a) ,a一般取0.85。

                               

    这里写图片描述

         一般迭代到30次以上就收敛了,取e为所有分量都为1/n的列向量。真的web结构的转移矩阵非常大,目前的网页数量已经超过100亿, 转移矩阵是100亿*100亿的矩阵,直接按矩阵乘法的计算方法不可行,需要借助Map-Reduce的计算方式来解决。https://www.cnblogs.com/rubinorth/p/5799848.html

             PageRank是一个与查询无关的静态算法,因此所有网页的PageRank值均可以通过离线计算获得。这样,减少了用户检索时需要的排序时间,极大地降低了查询响应时间。但是PageRank存在两个缺陷:首先PageRank算法严重歧视新加入的网页,因为新的网页的出链接和入链接通常都很少,PageRank值非常低。另外PageRank算法仅仅依靠外部链接数量和重要度来进行排名,而忽略了页面的主题相关性,以至于一些主题不相关的网页(如广告页面)获得较大的PageRank值,从而影响了搜索结果的准确性。为此,各种主题相关算法纷纷涌现,其中以以下几种算法最为典型。

    from:https://blog.csdn.net/u010700066/article/details/81868780

    2)Topic-Sensitive PageRank算法

             由于最初PageRank算法中是没有考虑主题相关因素的,斯坦福大学计算机科学系Taher Haveli-wala提出了一种主题敏感(Topic-Sensitive)的PageRank算法解决了“主题漂流”问题。该算法考虑到有些页面在某些领域被认为是重要的,但并不表示它在其它领域也是重要的。

             网页A链接网页B,可以看作网页A对网页B的评分,如果网页A与网页B属于相同主题,则可认为A对B的评分更可靠。因为A与B可形象的看作是同行,同行对同行的了解往往比不是同行的要多,所以同行的评分往往比不是同行的评分可靠。遗憾的是TSPR并没有利用主题的相关性来提高链接得分的准确性。

    3)HillTop算法

             HillTop是Google的一个工程师Bharat在2001年获得的专利。HillTop是一种查询相关性链接分析算法,克服了的PageRank的查询无关性的缺点。HillTop算法认为具有相同主题的相关文档链接对于搜索者会有更大的价值。在Hilltop中仅考虑那些用于引导人们浏览资源的专家页面(Export Sources)。Hilltop在收到一个查询请求时,首先根据查询的主题计算出一列相关性最强的专家页面,然后根据指向目标页面的非从属专家页面的数量和相关性来对目标页面进行排序。

             HillTop算法确定网页与搜索关键词的匹配程度的基本排序过程取代了过分依靠PageRank的值去寻找那些权威页面的方法,避免了许多想通过增加许多无效链接来提高网页PageRank值的作弊方法。HillTop算法通过不同等级的评分确保了评价结果对关键词的相关性,通过不同位置的评分确保了主题(行业)的相关性,通过可区分短语数防止了关键词的堆砌。

            但是,专家页面的搜索和确定对算法起关键作用,专家页面的质量对算法的准确性起着决定性作用,也就忽略了大多数非专家页面的影响。专家页面在互联网中占的比例非常低(1.79%),无法代表互联网全部网页,所以HillTop存在一定的局限性。同时,不同于PageRank算法,HillTop算法的运算是在线运行的,对系统的响应时间产生极大的压力。

    4)HITS

             HITS(Hyperlink Induced Topic Search)算法是Kleinberg在1998年提出的,是基于超链接分析排序算法中另一个最著名的算法之一。该算法按照超链接的方向,将网页分成两种类型的页面:Authority页面和Hub页面。Authority页面又称权威页面,是指与某个查询关键词和组合最相近的页面,Hub页面又称目录页,该页面的内容主要是大量指向Authority页面的链接,它的主要功能就是把这些Authority页面联合在一起。对于Authority页面P,当指向P的Hub页面越多,质量越高,P的Authority值就越大;而对于Hub页面H,当H指向的Authority的页面越多,Authority页面质量越高,H的Hub值就越大。对整个Web集合而言,Authority和Hub是相互依赖、相互促进,相互加强的关系。Authority和Hub之间相互优化的关系,即为HITS算法的基础。

             HITS基本思想是:算法根据一个网页的入度(指向此网页的超链接)和出度(从此网页指向别的网页)来衡量网页的重要性。在限定范围之后根据网页的出度和入度建立一个矩阵,通过矩阵的迭代运算和定义收敛的阈值不断对两个向量Authority和Hub值进行更新直至收敛。

            实验数据表明,HITS的排名准确性要比PageRank高,HITS算法的设计符合网络用户评价网络资源质量的普遍标准,因此能够为用户更好的利用网络信息检索工具访问互联网资源带来便利。

             但却存在以下缺陷:首先,HITS算法只计算主特征向量,处理不好主题漂移问题;其次,进行窄主题查询时,可能产生主题泛化问题;第三,HITS算法可以说一种实验性质的尝试。它必须在网络信息检索系统进行面向内容的检索操作之后,基于内容检索的结果页面及其直接相连的页面之间的链接关系进行计算。尽管有人尝试通过算法改进和专门设立链接结构计算服务器(Connectivity Server)等操作,可以实现一定程度的在线实时计算,但其计算代价仍然是不可接受的。

    基于智能化排序的第三代搜索引擎

            排序算法在搜索引擎中具有特别重要的地位,目前许多搜索引擎都在进一步研究新的排序方法,来提升用户的满意度。但目前第二代搜索引擎有着两个不足之处,在此背景下,基于智能化排序的第三代搜索引擎也就应运而生。

    1)相关性问题

             相关性是指检索词和页面的相关程度。由于语言复杂,仅仅通过链接分析及网页的表面特征来判断检索词与页面的相关性是片面的。例如:检索“稻瘟病”,有网页是介绍水稻病虫害信息的,但文中没有“稻瘟病”这个词,搜索引擎根本无法检索到。正是以上原因,造成大量的搜索引擎作弊现象无法解决。解决相关性的的方法应该是增加语意理解,分析检索关键词与网页的相关程度,相关性分析越精准,用户的搜索效果就会越好。同时,相关性低的网页可以剔除,有效地防止搜索引擎作弊现象。检索关键词和网页的相关性是在线运行的,会给系统相应时间很大的压力,可以采用分布式体系结构可以提高系统规模和性能。

    from:https://blog.csdn.net/xiaoyu714543065/article/details/7932134

    2) 机器学习排序(Learning to Rank)

            利用机器学习技术来对搜索结果进行排序,这是最近几年非常热门的研究领域。信息检索领域已经发展了几十年,为何将机器学习技术和信息检索技术相互结合出现较晚?主要有两方面的原因。

            一方面是因为:在前面几节所述的基本检索模型可以看出,用来对査询和文档的相关性进行排序,所考虑的因素并不多,主要是利用词频、逆文档频率和文档长度这几个因子来人工拟合排序公式。因为考虑因素不多,由人工进行公式拟合是完全可行的,此时机器学习并不能派上很大用场,因为机器学习更适合采用很多特征来进行公式拟合,此时若指望人工将几十种考虑因素拟合出排序公式是不太现实的,而机器学习做这种类型的工作则非常合适。

             随着搜索引擎的发展,对于某个网页进行排序需要考虑的因素越来越多,比如网页的pageRank值、查询和文档匹配的单词个数、网页URL链接地址长度等都对网页排名产生影响,Google目前的网页排序公式考虑200多种因子,此时机器学习的作用即可发挥出来,这是原因之一。
           另外一个原因是:对于有监督机器学习来说,首先需要大量的训练数据,在此基础上才可能自动学习排序模型,单靠人工标注大量的训练数据不太现实。对于搜索引擎来说, 尽管无法靠人工来标注大量训练数据,但是用户点击记录是可以当做机器学习方法训练数据的一个替代品,比如用户发出一个查询,搜索引擎返回搜索结果,用户会点击其中某些网页,可以假设用户点击的网页是和用户查询更加相关的页面。尽管这种假设很多时候并不成立,但是实际经验表明使用这种点击数据来训练机器学习系统确实是可行的。

             传统的检索模型靠人工拟合排序公式,并通过不断的实验确定最佳的参数组合,以此来形成相关性打分函数。机器学习排序与此思路不同,最合理的排序公式由机器自动学习获得,而人则需要给机器学习提供训练数据。图1是利用机器学习进行排序的基本原理图。 机器学习排序系统由4个步骤组成:人工标注训练数据、文档特征抽取、学习分类函数、在实际搜索系统中采用机器学习模型.

           首先,由人工标注训练数据。对于某个查询Q,人工标出哪些文档是和这个査询相关的,同时标出相关程度,相关程度有时候可以用数值序列来表示,比如从1分 到5分为3个档次,1代表微弱相关,5代表最相关,其他数值代表相关性在两者之间。对于某个查询,可能相关文档众多,同时用户査询也五花八门,所以全部靠人工标注有时候 不太可能。此时,可以利用用户点击记录来模拟这种人工打分机制。
          对于机器学习来说,输入是用户查询和一系列标注好的文档,机器学习系统需要学习打分函数,然后按照打分函数输出搜索结果,但是在其内部,每个文档由若干特征构成的,即每个文档进入机器学习系统之前,首先需要将其转换成特征向量,比较常用的特征包括:

    • • 查询词在文档中的词频信息
    • • 查询词的IDF信息
    • • 文档长度: 
    • • 网页的入链数量: 
    • • 网页的出链数量:
    • • 网页的pageRank值; 
    • • 网页的URL松度: 
    • • 査询词的Proximity值:即在文档中多大的窗口内可以出现所有査询词。

            以上所列只是影响排序的一部分特征,实际上还有很多类似的特征可以作为特征向量中的一维加入。在确定了特征数量后,即可将文档转換为特征向量X,前面说过每个文档会人工标出其相关性得分y.这样每个文档会转換为<X,Y>的形式,即特征向量及其对应的相关性得分,这样就形成了一个具体的训练实例。

           通过多个调练实例,就可以采用机器学习技术来对系统进行训练,训练的结果是―个分类函数或者回归函数,在之后的用户搜索中,就可以用这个分类函数对文档进行打分,形成搜索结果 

        从目前的研究方法来说,可以将机器学习揉序方法分为以下3种:单文档方法、文档对方法和文档列表方法。

     单文档方法      

         单文档方法的处理对象是单独的一篇文档,将文档转换为特征向量后,机器学习系统根据从训练数据中学习到的分类或者回归函数对文档打分,打分结果即是搜索结果。下面我们用一个简单的例子说明这种方法。 
          在这个例子中,我们对于每个文档采用了3个特征: 査询与文档的Cosme相似性分值、査询词的Proximity值及页面的PageRank数值,而相关性判断是二元的,即要么相关要么不相关,当然,这里的相关性判断完全可以按照相关程度扩展为多元的,本例为了方便说明做了简化。

               

          例子中提供了5个训练实例,每个训练实例分别标出来其对应的查询,3个特征的得分情况及相关性判断。对于机器学习系统来说,根据训练数据,需要如下的线性打分函数:
           Score(Q, D)=a * CS+ b *PM+c*PR+ d 

            如果得分大于一设定阀值,则叫以认为是相关的, 如果小于设定闽值则可以认为不相关。通过训练实例,可以获得最优的a、 b,、c、d参数组合,当这些参数确定后,机器学习系统就算学习完毕,之后即可利用这个打分函数进行相关性判断。对于某个新的查询Q和文档D,系统首先获得其文档D对应的3个特 I特征值,之后利用学习到的参数组合计算两者得分,当得分大于设定的闽值,即可判断文档是相关文档,否则判断为不相关文档。

    文档对方法(PairWise Approach)

            对于搜索系统来说,系统接收到用户査询后,返回相关文档列表,所以问题的关键是确定文档之间的先后顺序关系。单文档方法完全从单个文档的分类得分角度计算,没有考虑文档之间的顺序关系。文档对方法则将重点转向量对文档顺序关系是否合理进行判断。

            之所以被称为文档对方法,是因为这种机器学习方法的训练过程和训练目标,是判断任意两个文档组成的文档对<D0C1,D0C2>是否满足顺序关系,即判断是否D0C1应该排在DOC2的前面。下图展示了一个训练实例:査询Q1对应的搜索结果列表如何转换为文档对的形式,因为从人工标注的相关性得分可以看出,D0C2得分最高,D0C3次之,D0C1得分最低,于是我们可以按照得分大小顺序关系得到3个如图3所示的文档对,将每个文档对的文档转换为特征向量后,就形成了一个具体的训练实例。

                              

         根据转换后的训练实例,就可以利用机器学习方法进行分类函数的学习,具体的学习方法有很多,比如SVM. Boosts、神经网络等都可以作为具体的学习方法,其学习目标是一致的,即输入一个査询和文档对<Doc1,DOC2>, 机器学习排序能够判断这种顺序关系是否成立,如果成立,那么在搜索结果中D0C1应该排在D0C2 前面,否则Doe2应该摔在Doc1前面,通过这种方式,就完成搜索结果的排序任务。
            尽管文档对方法相对单文档方法做出了改进,但是这种方法也存在两个明显的问题:

           一个问题是:文档对方法只考虑了两个文档对的相对先后顺序,却没有考虑文档出现在搜索列表中的位置,排在搜索站果前列的文档更为重要,如果前列文档出现判断错误,代价明显高于排在后面的文档。针对这个问题的改进思路是引入代价敏感因素,即每个文档对根据其在列表中的顺序具有不同的权重,越是排在前列的权重越大,即在搜索列表前列如果排错顺序的话其付出的代价更高•
            另外一个问题是:不同的査询,其相关文档数量差异很大,所以转换为文档对之后, 有的查询对能有几百个对应的文档对,而有的查询只有十几个对应的文档对,这对机器学习系统的效果评价造成困难 •我们设想有两个查询,査询Q1对应500个文文档对,查询Q2 对应10个文档对,假设学习系统对于査询Ql的文档对能够判断正确480个,对于査询 Q2的义格对能够判新正确2个,如果从总的文档对数量来看,这个学习系统的准确率是 (480+2)/(500+10)=0.95.即95%的准确率,但是从査询的角度,两个査询对应的准确率 分别为:96%和20%,两者平均为58%,与纯粹从文档对判断的准确率相差甚远,这对如何继续调优机器学习系统会带来困扰。

    文档列表方法(ListWise Approach)

            单文档方法将训练集里每一个文档当做一个训练实例,文档对方法将同一个査询的搜索结果里任意两个文档对作为一个训练实例,文档列表方法与上述两种表示方式不同,是将每一个查询对应的所有搜索结果列表整体作为一个训练实例,这也是为何称之为文档列表方法的原因。
            文档列表方法根据K个训练实例(一个査询及其对应的所有搜索结果评分作为一个实例)训练得到最优评分函数F, 对于一个新的用户査询,函数F对每一个文档打分,之后按照得分顺序由高到低排序,就是对应的搜索结果。所以关键问题是:拿到训练数据,如何才能训练得到最优的打分函数?

            这里介绍一种训练方法,它是基于搜索结果排列组合的概率分布情况来训练的,图4是这种方式训练过程的图解示意。

                   

                                           图4 不同评分函数的KL距离

           首先解释下什么是搜索结果排列组合的概率分布,我们知道,对于搜索引擎来说,用户输入査询Q, 搜索引擎返回搜索结果,我们假设搜索结果集合包含A. B 和C共3个文档,搜索引擎要对搜索结果排序,而这3个文档的顺序共有6种排列组合方式: ABC, ACB, BAG, BCA, CAB和CBA,而每种排列组合都是一种可能的搜索结果排序方法。

            对于某个评分函数F来说,对3个搜索结果文档的相关性打分,得到3个不同的相关度得分F(A)、 F(B)和F(C), 根据这3个得分就可以计算6种排列组合情况各自的概率值。 不同的评分函数,其6种搜索结果排列组合的概率分布是不一样的。

          了解了什么是搜索结果排列组合的概率分布,我们介绍如何根据训练实例找到最优的评分函数。图4展示了一个具体的训练实例,即査询Q1及其对应的3个文档的得分情况,这个得分是由人工打上去的,看做是标准答案。可以设想存在一个最优的评分函数g,对查询Q1来说,其打分结果是:A文档得6分,B文档得4分,C文档得3分。

           我们的任务就是找到一个函数,使得函数对Ql的搜索结果打分顺序和人工打分顺序尽可能相同。既然人工打分已知,那么我们可以计算函数g对应的搜索结果排列组合概率分布,其具体分布情况如图4中间的概率分布所示。假设存在两个其他函数h和f,它们的计算方法已知,对应的对3个搜索结果的打分在图上可以看到,由打分结果也可以推出每个函数对应的搜索结果排列组合概率分布,那么h与f哪个与虚拟的最优评分函数g更接近呢?一般可以用两个分布概率之间的距离远近来度量相似性,KL距离就是一种衡量概率分布差异大小的计算工具,通过分别计算h与g的差异大小及f与g的差异大小,可以看出f比h更接近的最优函数g,那么在这个函数中,我们应该优先选f作为将来搜索可用的评分函数,训练过程就是在可能的函数中寻找最接近虚拟最优函数g的那个函数作为训练结果,将来作为在搜索时的评分函数。

           上述例子只是描述了对于单个训练实例如何通过训练找到最优函数,事实上我们有K 个训练实例,虽然如此,其训练过程与上述说明是类似的,可以认为存在一个虚拟的最优评分函数g (人工打分),训练过程就是在所有训练实例基础上,探寻所有可能的候选函数,从中选择那个KL距离最接近于函数g的,以此作为实际使用的评分函数。 经验结果表明,基于文档列表方法的机器学习排序效果要好于前述两种方法。

         补充:KL距离,是Kullback-Leibler差异(Kullback-Leibler Divergence)的简称,也叫做相对熵(Relative Entropy)。它衡量的是相同事件空间里的两个概率分布的差异情况。其物理意义是:在相同事件空间里,概率分布P(x)对应的每个事件,若用概率分布 Q(x)编码时,平均每个基本事件(符号)编码长度增加了多少比特。我们用D(P||Q)表示KL距离,计算公式如下:

      当两个概率分布完全相同时,即P(X)=Q(X),其相对熵为0 。

    from:https://blog.csdn.net/jirongzi_cs2011/article/details/9621945#t1

     

    展开全文
  • 网页中的信息排序信息显示

    千次阅读 2014-06-25 20:39:14
    那么今天我们就来学习下网页中的信息排序显示   列表标记 1. 标记的用途 列表标记可以创建一般的无序列表、编号列表,以及定义列表三种方式。还可以在一种列表中嵌套另一种列表,便于概括显示一系列相关的内容。 ...

     平常我们在浏览网页的时候,经常会见到下图所示的列表信息。

    那么今天我们就来学习下网页中的信息排序显示

     

    列表标记

    1.    标记的用途

    列表标记可以创建一般的无序列表、编号列表,以及定义列表三种方式。还可以在一种列表中嵌套另一种列表,便于概括显示一系列相关的内容。

     

    2.    无序列表

    语法:

    <ul type=”项目符号类型”>
    
          <li type=”项目符号类型”>内容1</li>
    
    …
    
    </ul>
    
    


     

    牛刀小试

    <span style="color:#cc0000;">  </span><html>
        <head>
    	<title>
            排序列表练习一
    	</title>
        </head>
    <body>
    <Ul>
    <li type="circle">基本表格:</li>
    <li>无边框表格:</li>
    <li>双线表格:</li>
    <li>合并多行表格:</li>
    <li>复杂表格1:</li>
    <li>基本表格:</li>
    <li type="square">基本表格:</li>
    <ul>
    </body>
      </html>

     

     

    结果如下图


     

    3.    有序列表

    语法:

    <ol start=”列表起点” type=”项目符号类型”>
    
          <li>内容1</li>
    
    …
    
    </ol>
    
    


     

    属性名称

    属性值

    说明

    Type

    1

    表示1234

    a

    标识abcd

    A

    表示ABC

    i

    表示i ii iii

    L

    表示l ll lll

     

    牛刀小试

     

      <html>
        <head>
    	<title>
            排序列表练习一
    	</title>
        </head>
    <body>
    <ol type="A">
    <li >基本表格:</li>
    <li>无边框表格:</li>
    <li>双线表格:</li>
    <li>合并多行表格:</li>
    <li>复杂表格1:</li>
    <li>基本表格:</li>
    
    <ol>
    </body>
      </html>

     

    结果如下图


     

    4.    自定义列表

    语法:

    <dl>
    
    <dt>标题1</dt>
    
    <dd>内容1</dd>
    
    <dt>标题2</dt>
    
    <dd>内容2</dd>
    
    </dl>
    
    


     

    <dl></dl>:定义列表

    <dt></dt>:表示一个项目

    <dd></dd>:表示一个项目下更详细的内容解释

     

    牛刀小试

      <html>
        <head>
    	<title>
            排序列表练习一
    	</title>
        </head>
    <body>
    <dl >
    <dt>水果:</dt>
    <dd>苹果</dd>
    <dd>香蕉</dd>
    <dt>饮料:</dt>
    <dd>可乐</dd>
    <dd>雪碧</dd>
    
    </dl>
    </body>
      </html>


    结果如下图

     

     

     

                 未完待续

    展开全文
  • 【蓝桥杯】_06三部排序

    千次阅读 多人点赞 2020-07-12 21:00:20
    一般的排序有许多经典算法,如快速排序、希尔排序等。 但实际应用时,经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法,可以根据实际情况建立更好的解法。 比如,对一个整型数组中的数字进行分类排序...

    img

    package java2013B;
    
    /**
     * @Author bennyrhys
     * @Date 2020-03-11 23:06
    标题:三部排序
    
    一般的排序有许多经典算法,如快速排序、希尔排序等。
    
    但实际应用时,经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法,可以根据实际情况建立更好的解法。
    
    比如,对一个整型数组中的数字进行分类排序:
    
    使得负数都靠左端,正数都靠右端,0在中部。注意问题的特点是:负数区域和正数区域内并不要求有序。可以利用这个特点通过1次线性扫描就结束战斗!!
    
    以下的程序实现了该目标。
    
    static void sort(int[] x)
    {
    int p = 0;
    int left = 0;
    int right = x.length-1;
    
    while(p<=right){
    if(x[p]<0){
    int t = x[left];
    x[left] = x[p];
    x[p] = t;
    left++;
    p++;
    }
    else if(x[p]>0){
    int t = x[right];
    x[right] = x[p];
    x[p] = t;
    right--;
    }
    else{
    _________________________;  //代码填空位置
    }
    }
    }
    
    如果给定数组:
    25,18,-2,0,16,-5,33,21,0,19,-16,25,-3,0
    则排序后为:
    -3,-2,-16,-5,0,0,0,21,19,33,25,16,18,25
    
    请分析代码逻辑,并推测划线处的代码,通过网页提交
    注意:仅把缺少的代码作为答案,千万不要填写多余的代码、符号或说明文字!!
    
     */
    public class _06三部排序 {
        public static void main(String[] args) {
            int arr[] = {25,18,-2,0,16,-5,33,21,0,19,-16,25,-3,0};
            sort(arr);
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i]+" ");
            }
        }
        static void sort(int[] x)
        {
            int p = 0;
            int left = 0;
            int right = x.length-1;
    
            while(p<=right){
                if(x[p]<0){
                    int t = x[left];
                    x[left] = x[p];
                    x[p] = t;
                    left++;
                    p++;
                }
                else if(x[p]>0){
                    int t = x[right];
                    x[right] = x[p];
                    x[p] = t;
                    right--;
                }
                else{
                    p++;  //代码填空位置
                }
            }
        }
    }
    

    文末福利

    对了对了,文末发波福利

    1. 通过公众号提示的关键字可以领取竞赛资料。但是,有时候会失效,小伙伴可以在后台留言提醒我修复。

    2. 最后一波分享一些很有意义的开源干货

    蓝桥杯必刷真题:https://github.com/bennyrhys/LanQiao
    求职必备刷题官网:https://github.com/bennyrhys/interview
    SpringBoot两小时快速入门,极客表白浪漫红包程序
    https://github.com/bennyrhys/LuckyMoney-SpringBootProject
    SpringBoot两小时快速入门,基因芯片个人信息程序
    https://github.com/bennyrhys/Girl-SpringBootProject
    SpringBoot之web进阶,人类基因芯片程序-提升篇
    https://github.com/bennyrhys/GirlPlus-SpringBootProject

    小伙伴的支持是我坚持的动力,动动小手,点点(关注、👍、在看)。

    点击图片扫一扫,获取竞赛、项目、求职干货

    展开全文
  • java实现第四届蓝桥杯快速排序

    万次阅读 多人点赞 2019-07-29 18:24:42
    快速排序 题目描述 快速排序算法是典型的分治思想的运用。它使用某个key把全部元素分成两组,其中一组的元素不大于另一组。然后对这两组再次进行递归排序。 以下代码实现了快速排序。请仔细阅读代码,填写缺少...
     快速排序  
    
    题目描述
    
    快速排序算法是典型的分治思想的运用。它使用某个key把全部元素分成两组,其中一组的元素不大于另一组。然后对这两组再次进行递归排序。
    
        以下代码实现了快速排序。请仔细阅读代码,填写缺少代码的部分。
    
    static void f(int[] x, int left, int right)
    {
        if(left >= right) return;
        
        int key = x[(left+right)/2];
        
        int li = left;
        int ri = right;
        while(li<=ri){
            while(x[ri]>key) ri--;
            while(x[li]<key) li++;
            
            if(________________){    //填空位置
                int t = x[li];
                x[li] = x[ri];
                x[ri] = t;
                li++;
                ri--;
            }    
        }
        
        if(li < right) f(x, li, right);
        if(ri > left) f(x, left, ri);
    }
    
    请分析代码逻辑,并推测划线处的代码,通过网页提交。
    注意:仅把缺少的代码作为答案,千万不要填写多余的代码、符号或说明文字!!
    
    li <= ri
    
    
    展开全文
  • java实现第四届蓝桥杯三部排序

    万次阅读 多人点赞 2019-07-29 16:50:29
    三部排序 题目描述 一般的排序有许多经典算法,如快速排序、希尔排序等。 但实际应用时,经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法,可以根据实际情况建立更好的解法。 比如,对一个整型...
  • 模糊查询符号

    千次阅读 2018-03-26 15:08:04
    在查询前将待查字符串先经该函数处理即可,并且在网页上连接数据库用到这类的查询语句时侯要注意: 如Select * FROM user Where name LIKE '老[^1-4]';上面 《'》老[^1-4]《'》是要有单引号的,别忘了,我经常忘! ...
  • 空间复杂度 用什么符号表示Do you really understand Big O? If so, then this will refresh your understanding before an interview. If not, don’t worry — come and join us for some endeavors in computer ...
  • Lucene 的索引排序是使用了倒排序原理 其实LUCENE写的真的挺烂的,不论算法还是代码都很一般,不知道国内为什么这么多人都用它,哎,中国程序员的技术水平真的差太远了,不过为了一些初级的程序员做研究之用,还是...
  • 一般的排序有许多经典算法,如快速排序、希尔排序等。 但实际应用时,经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法,可以根据实际情况建立更好的解法。 比如,对一个整型数组中的数字进行分类排序:...
  • 推荐系统中的排序学习

    千次阅读 2020-09-26 22:17:57
    “本文首先介绍排序学习的三种主要类别,然后详细介绍推荐领域最常用的两种高层排序学习算法框架:BPR和LambdaMART。因为排序学习的算法和实践大都来源于信息检索,一些理论也必须从信...
  • 2013蓝桥杯【初赛试题】三部排序

    千次阅读 2014-03-11 20:00:37
    三部排序 一般的排序有许多经典算法,如快速排序、希尔排序等。 但实际应用时,经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法,可以根据实际情况建立更好的解法。 比如,对一个整型数组中的数字进行...
  • 三部排序 - 蓝桥杯

    千次阅读 2013-06-12 18:51:54
    标题:三部排序 - 蓝桥杯 内容:2013年第四届蓝桥杯全国软件大赛预赛第6题,代码填空题。三部排序,提供了一种小算法,小思维。 作者:MilkCu 题目描述 标题:三部排序 一般的排序有许多经典算法,如快速排序、希尔...
  • 一般的排序有许多经典算法,如快速排序、希尔排序等。 但实际应用时,经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法,可以根据实际情况建立更好的解法。 比如,对一个整型数组中的数字进行分类排序...
  • 标题:三部排序 一般的排序有许多经典算法,如快速排序、希尔排序等。 但实际应用时,经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法,可以根据实际情况建立更好的解法。 比如,对一个整型数组...
  • 对于一些没有编程经验的小白来说,看到这类动态排序条形图视频比较震撼,自己也想做,但是又有看到大段的代码就头疼的症状,鉴于有学员需要,这次就选择一个最简单的方式创建这类动态的排序图。 中国安全生产事故...
  • “本文首先介绍排序学习的三种主要类别,然后详细介绍推荐领域最常用的两种高层排序学习算法框架:BPR和LambdaMART。因为排序学习的算法和实践大都来源于信息检索,一些理论也必须从信...
  • 标题:三部排序 一般的排序有许多经典算法,如快速排序、希尔排序等。 但实际应用时,经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法,可以根据实际情况建立更好的解法。 比如,对一个整型数组中的...
  • 排座椅(排序

    千次阅读 2018-04-12 21:46:23
    上图中用符号*、※、+标出了3对会交头接耳的学生的位置,图中3条粗线的位置表示通道,图示的通道划分方案是唯一的最佳方案。 题解 甚至刷到一个08年普及组的题 第一次写甚至还要写错 因为数据保证不是...
  • 标题:三部排序  一般的排序有许多经典算法,如快速排序、希尔排序等。  但实际应用时,经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法,可以根据实际情况建立更好的解法。  比如,对一个...
  • HTML网页编程

    千次阅读 2016-05-21 17:41:57
    HTML网页编程 前 言 ☆静态页面和动态页面 网站页面分为静态页面和动态页面两种 • 静态页面:有一个html页面文件保存在服务器上,浏览器要这个页面的时候服务器就把这个页面文件发给浏览器; • 动态页面:...
  • 搜索引擎的性质与软件体系结构2:大规模搜索引擎—Google3:早期体系结构--中小型搜索引擎(1)采集数据(2)建立索引(3)提供检索服务(4)数据结构(5)Google检索算法(1)单个检索词的查询排序(2)多个检索词...
  • 网页列表

    千次阅读 2018-07-03 23:34:23
    ,常用于导航有序列表,结构化列表,考虑排序,&lt;ol&gt;+&lt;li&gt;定义列表,当作字典或术语,包含定义和描述,&lt;dl&gt;+&lt;dt&gt;+&lt;dd&gt;(其中,dl表示定义...
  • 各种算法 排序 查找 等等

    千次阅读 2011-07-27 09:42:48
    //归并排序(归并排序也是外排序的主要思想) //基数排序 #include #include //宏定义,求数组元素个数 #define N(x) sizeof((x))/sizeof((x)[0]) //因为在工程中其他文件定义了Print,所以这里声明为static static ...
  • 一般的排序有许多经典算法,如快速排序、希尔排序等 但实际应用时,经常会或多或少有一些特殊的要求,我们没必要套用那些经典算法,可以根据实际情况建立更好的解法, 比如:对一个整型数组中的数字进行分类排序:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,801
精华内容 11,120
关键字:

网页排序符号