sort() 方法
 
要在 MongoDB 中的文档进行排序，需要使用sort()方法。 sort() 方法接受一个文档，其中包含的字段列表连同他们的排序顺序。
 
要指定排序顺序1和-1。 1用于升序排列，而-1用于降序。
 
语法:
 
sort() 方法的基本语法如下
 
> db.COLLECTION_NAME.find().sort({KEY:1})
 
例子
 
以下数据为 person 集合。
 
{ "_id" : ObjectId("578c3d306775f085b5fea8d9"), "name" : "zhangsan", "age" : 22 }
{ "_id" : ObjectId("578c3d306775f085b5fea8da"), "name" : "lisi", "age" : 18 }
{ "_id" : ObjectId("578c3d306775f085b5fea8db"), "name" : "wangwu", "age" : 25 }
 
下面的例子将显示按年龄降序排序的记录。
 
> db.person.find().sort({"age":-1})
{ "_id" : ObjectId("578c3d306775f085b5fea8db"), "name" : "wangwu", "age" : 25 }
{ "_id" : ObjectId("578c3d306775f085b5fea8d9"), "name" : "zhangsan", "age" : 22 }
{ "_id" : ObjectId("578c3d306775f085b5fea8da"), "name" : "lisi", "age" : 18 }
>
 
请注意，如果不指定排序优先，然后sort() 方法将文档显示在升序排列。
 
作者：itmyhome

1.Sort
 
org.apache.lucene.search.Sort
 封装排序标准的类。
 
SortField[] org.apache.lucene.search.Sort.fields
 字段。
 
 
org.apache.lucene.search.Sort.Sort(SortField field)
 
 
构造函数。按照指定的SortField进行排序。
 
org.apache.lucene.search.Sort.Sort(SortField... fields)
 
上面函数的重载，指定多个field进行排序，它们的优先级由高到低。当且仅当前面的field比不出大小时，才会用到后面的field。
 
void org.apache.lucene.search.Sort.setSort(SortField... fields)
 
 
它被上面的构造函数调用。
 
2.SortField
 
org.apache.lucene.search.SortField
 类，代表用于排序的Field。此field必须被索引。
 org.apache.lucene.search.SortField.Type
 内部静态枚举，表示排序的类型，如相关性分数排序、文档号排序、字符串顺序排序等。
 org.apache.lucene.search.SortField.SortField(String field, FieldComparatorSource comparator)
 构造函数。用自定义的comparator来排序。
 

 
 
3.FieldComparator
 
3.1 FieldComparatorSource
 
org.apache.lucene.search.FieldComparatorSource
 抽象类，用于得到FieldComparator，定义见下。
 
 
 
public abstract class FieldComparatorSource {
  public abstract FieldComparator<?> newComparator(String fieldname, int numHits, int sortPos, boolean reversed) throws IOException;
}
 
 
3.2 FieldComparator
 
 
org.apache.lucene.search.FieldComparator<T>
 抽象泛型类。T代表待比较得分的类型，通常是int或float。
 
 int org.apache.lucene.search.FieldComparator.compare(int slot1, int slot2)
 比较 slot1与slot2，当slot1>slot2时返回正数（确定是正数？）。
 
 
3.3 LeafFieldComparator
 
 
void org.apache.lucene.search.LeafFieldComparator
 
 
接口,定义见下。
 
 
public interface LeafFieldComparator {

  //设置slot为队列的尾部。对应评分最低的文档结果。
  void setBottom(final int slot);

  //将当前doc与队列的尾部进行比较。如果doc>bottom，返回正数。
  int compareBottom(int doc) throws IOException;

  int compareTop(int doc) throws IOException;

  //将新的命中结果，也就是这个doc copy至指定slot上，用于以后的比较。
  void copy(int slot, int doc) throws IOException;

  void setScorer(Scorer scorer);
}
 

 
 
4.DocComparator
 
 
org.apache.lucene.search.FieldComparator.DocComparator
 FieldComparator的内部静态类，按照docid进行排序。定义见下。
 
 
 
public static final class DocComparator extends FieldComparator<Integer> implements LeafFieldComparator {...}
 

 

说明：文章内容来源于课程视频和课程ppt。我只学习了课程没有做习题。文章不是翻译，是我对课程的理解。
 
 
上文提到文档排序函数是TR的核心。文档排序函数的实现有几种思路，其中一种是基于相似度的模型。这种模型具体是用空间向量模型(Vector Space Model)实现。这篇文章就介绍VSM。
 
VSM概念
 
什么是VSM
 

 　VSM定义了两点。
 　第一，用词向量(term vector)来表示查询语句、表示文档。英文中的term vector，我们翻译为词向量。但是这里的“词”并不是指汉语中的一个词，具体含义是：基本概念，可以是一个字、一个词、一个短语。每个词表示一个维度，N个词就可以定义N维空间。如上图所示，programming,libarary,presidential，分别定义了三个维度。查询语句的向量表示：$q=(x_1,x_2,...x_N)$，文档的向量表示：$d=(y_1,y_2,...y_N)$。
 　第二，查询语句和文档的相关度正比于查询语句和文档的相似度：$relevance(q,d)\propto similarity(q,d)=f(q,d)$
 
VSM没有定义的
 
1 怎么定义或者说怎么选择term。只说term是文档集中的基本概念，并未指明什么可以作为term。
 　2 向量的表示。用什么值来计算查询向量和文档向量。
 　3 相似度怎么计算。
 　基于以上几点说VSM其实是一个框架frame。在实践中有好多版本的实现。继续往下看。
 
VSM实现
 
来源于ppt的例子。
 　query=“news about presidential campaign”
 　d1:"… news about …"
 　d2:"… news about organic food campaign…"
 　d3:"… news of presidential campaign …"
 　d4:"… news of presidential campaign … … presidential candidate …"
 　d5:"… news of organic food campaign… campaign…campaign…campaign…"
 
在这个例子中很理想的排序大概应该是：d4,d3。d1,d2,d5其实是不相关文档。
 
简单实现
 
BOW+bit-vector+dotproduct 这是一个最简单的实现。
 　1 用文档中的每一个词定义一个维度。称为词袋模型(Bag of Word=BOW)。
 　2 用Bit-Vector 表示向量。如果词出现则记为1，否则为0。
    
     
      
       
        
         x
        
        
         i
        
       
       
        ,
       
       
        
         y
        
        
         i
        
       
       
        ∈
       
       
        {
       
       
        0
       
       
        ,
       
       
        1
       
       
        }
       
      
      
       x_i,y_i \in \{0,1\}
      
     
    xi​,yi​∈{0,1}。
 　3 相似度通过点积(dot product)计算。
 　最终表示
 　
    
     
      
       
        q
       
       
        =
       
       
        (
       
       
        
         x
        
        
         1
        
       
       
        ,
       
       
        
         x
        
        
         2
        
       
       
        .
       
       
        .
       
       
        .
       
       
        .
       
       
        
         y
        
        
         n
        
       
       
        )
       
       
        ,
       
       
        
         x
        
        
         i
        
       
       
        ∈
       
       
        {
       
       
        0
       
       
        ,
       
       
        1
       
       
        }
       
      
      
       q=(x_1,x_2....y_n),x_i \in \{0,1\}
      
     
    q=(x1​,x2​....yn​),xi​∈{0,1}
 　
    
     
      
       
        d
       
       
        =
       
       
        (
       
       
        
         y
        
        
         1
        
       
       
        ,
       
       
        
         y
        
        
         2
        
       
       
        .
       
       
        .
       
       
        .
       
       
        
         y
        
        
         n
        
       
       
        )
       
       
        ,
       
       
        
         y
        
        
         i
        
       
       
        ∈
       
       
        {
       
       
        0
       
       
        ,
       
       
        1
       
       
        }
       
      
      
       d=(y_1,y_2...y_n),y_i \in \{0,1\}
      
     
    d=(y1​,y2​...yn​),yi​∈{0,1}
 　$sim(q,d)=x_1{y}_1+x_2{y}_2+....+x_N{y}_N={\sum }_{i=1}^N{x}_i{y}_i$
 　
 　计算一下例子。
 　V= {news, about, presidential, campaign, food …. }
 　q= (1, 1, 1, 1, 0, …)
 　d1= (1, 1, 0, 0, 0, …)
 　d2= (1, 1, 0, 1, 0, …)
 　d3= (1, 0, 1, 1, 0, …)
 　…
 　f(q,d1)=11+11+0…=2
 　f(q,d2)=11+11+0+1*1+…=3
 　…
 　本算法中sim(q,d)函数的实质就是表示有多少个不同的查询词出现在文档中。
 　在d2,d3,d4文档中各出现了3次，值为3,；在d1,d5文档中各出现了2次，值为2。
 
进阶实现
 
BOW+term frequency+dotproduct
 　问题：d4中 “presidential ”的次数要比d2多，应该排在前面才对。
 　解决策略就是使用词频这个信息。
 　最终表示
 　$q=(x_1,x_2…y_n),x_i $是词$w_i$在查询语句中出现次数$d=(y_1,y_2…y_n),y_i $是词$w_i$在文档中出现次数$sim(q,d)=x_1y_1+x_2y_2+…+x_Ny_N=\sum_{i=1}^{N}x_iy_i$
 　
 　计算一下例子。
 　f(q,d4)=11+10+12+11+0+…=4
 　f(q,d2)=…
 　…
 
TF-IDF
 
BOW+TF-IDF+dotproduct
 　
 　
 　问题：d2与d3，虽然都命中3个词，但是显然命中presidential比命中about得分要高。presidential含有更重要的信息嘛。
 　解决策略：使用逆文档频率IDF，在越多文档中出现，权重越低。
 　$IDF=log\frac{M+1}{k}$，M是文档集中文档数量，k是词在多少个文档中出现。
 　
 　可以看到当k=1的时候，IDF=log(M+1)；当k=M的时候IDF接近0。
 　
 　最终表示
 　$q=(x_1,x_2…y_n),x_i $是词$w_i$在查询语句中出现次数$d=(y_1,y_2…y_n),y_i =c(w_i,d)*IDF(w_i)，c(w_i,d)$是$w_i$在文档中的出现次数，$IDF(w_i)$是$w_i$在整个文档集中的逆文档频率。$sim(q,d)=x_1y_1+x_2y_2+…+x_Ny_N=\sum_{i=1}^{N}x_iy_i$
 　
 　计算例子
 　V= {news, about, presidential, campaign, food …. }
 　IDF(W)= 1.5 1.0 2.5 3.1 1.8
 　f(q,d2)=5.6 ， f(q,d3)=7.1问题解决。但是f(q,d5)=13.9。我们在最开始就分析了排在前面的文档应该是d4，d3。
 
TF变形
 
$sim(q,d)=f(q,d)={\sum }_{i=1}^N{x}_i{y}_i={\sum }_{w\in q\cap d}c(w,q)c(w,d)log\frac{M+1}{df(w)}$,df(w)是指词w的文档量。
 　问题：d5的打分太高了：13.9，分值高是因为“campaign”的频率太高。当一个词从无到有，有重要价值。但一个文档中包含某个词3-5次，与10次基本上不会有太大差异。所以要适当降低词频的影响。
 　解决方法1：被称为“亚线性变换(Sublinear TF Transformation)”。使用log函数。函数1：$y=x$，函数2：$y=log(1+x)$，函数1的增长率要比函数2大多了。
 　
 
$f(q,d)={\sum }_{w\in q\cap d}c(w,q)ln[1+c(w,d)]log\frac{M+1}{df(w)}$
 
解决方法2：被称为“BM25变换”。这种变换需要为词频设置一个最大值。假设最大值为6，超过6的词频都没有区别。函数$y=\frac{(k+1)x}{x+k}$，函数值会无线接近于k+1。实践证明BM25变换是非常健壮和有效的(robust and effective)。
 　
 　
 
$f(q,d)={\sum }_{w\in q\cap d}c(w,q)\frac{(k+1)c(w,d)}{c(w,d)+k}log\frac{M+1}{df(w)}$
 
文档长度变形
 
问题：当一个文档很长的时候，会更容易出现一个词，一个词的频率也更可能高。所以我们需要惩罚一下长文档。一个文档很长可能因为两个原因：一种是文档内容很详细，做了很多必要的描述；还有一种情况是一个大的文档中讲述了很多内容，每个内容一个小的段落，这样的文档其实是一个一个的小文档。在第二种情况中，词的相关度计算出来是不同的：从长文档中计算与从短文档中计算。
 　
 　解决：算法称为Pivoted Length Normalization。这里同样也有一个参数需要选择：平均文档长度avdl。函数：$normalizer=1-b+b\frac{d}{avdl}$，参数b是惩罚因子，$b\in [0,1]$。
 　
 　normalizer会放在相似度函数$f(q,d)$的分母上。
 　当b=0，所有值都为1，没有惩罚。
 　当b>0，当文档长度$<$avdl，normalizer<1，f(q,d)会增加；当文档产度>avdl，normalizer>1，f(q,d)会减小。
 　
 　最后的公式
 　TF亚线性变换：$f(q,d)={\sum }_{w\in q\cap d}c(w,q)\frac{ln[1+c(w,d)]}{1-b+b\frac{d}{avdl}}log\frac{M+1}{df(w)}$
 　BM25变换：$f(q,d)={\sum }_{w\in q\cap d}c(w,q)\frac{(k+1)c(w,d)}{c(w,d)+k(1-b+b\frac{d}{avdl})}log\frac{M+1}{df(w)}$
 　
 　考虑文档长度其实是把词频转为词频率，便于比较。
 
如何进一步提高VSM的效果
 
从词的维度改进。例如可以去掉停止词、做词的变换(stemmed words)、使用短语、语义索引、n元模型等待。
 　改进相似度函数。例如可以用欧式距离、用余弦距离表示相似度。实践中证明点积还是最适合的。

　在概率模型中，我们定义排序函数是基于文档与查询之间的相关度、可能性来做的。f(d,q) = p(R=1|d,q), R $\in$ {0,1}。概率模型有几个小分类： 
 　　经典概率模型——>BM25 
 　　语言模型Language Model —–>Query Likelihood 
 　　Divergence from randomness—–>PL2 
 　　
 
1 查询似然算法
 
　语言模型的假设是：$p(R=1|q,d)\approx p(q|d,R=1)$，文档与查询相关的概率约等于 在文档相关的前提下，用户输入q的概率。
 
1.1 概率模型的基本概念
 
　给定下面这个表格，收集了不同用户基于不同query，认为文档是否相似。 
 　$f(q,d) = p(R=1|q,d)=\dfrac{count(q,d,R=1)}{count(q,d)}$ 
 　例如p(R=1|q1,d1) = 1/2;p(R=1|q1,d2)=2/2….
 
　 
 　这里的问题是对于不在表格中的查询，不在表格中的文档怎么处理？
 
1.2 查询似然算法
 
　解决上述问题，我们换个角度计算一下上面那个表格中，在文档d1相关的前提下，用户输入q1的概率是多少。如果概率越高则q1与d1的相关度就越高。 
 　需要提出一个假设：用户输入的查询词是基于想象的相关文档。
 
2 统计语言模型LM
 
2.1 LM的概念
 
　语言模型LM是一个基于单词序列的概率分布。 
 　　p(“Today is Wednesday”) $\approx$ 0.001 
 　　p(“Today Wednesday is”) $\approx$ 0.0000000000001 
 　同样的3个词，概率相差很大。这说明语言模型是基于上下文的。这个模型也可以理解为生成一个文本的概率。所以又被称为生成模型generating model。这是一种可以生成单词的随机系统。
 
2.2 LM为什么有效
 
　1 LM量化了自然语言的不确定性。 
 　2 能够解决以下问题 
 　　speech recognition：已经看到单词“John” , “feels”,那继续看到的单词更可能是“happy”而不是”habit”。 
 　　text categorization, information retrieval：一篇新闻文章中提到三次”baseball”，一次”game”，这篇文章是新闻的概率。 
 　　information retrieval：已知一个用户喜欢体育，那他输入”baseball”的概率是多大。
 
2.3 最简单的语言模型：一元模型
 
　一元模型在生成文本的时候词与词之间是独立的：$p(w_1,w_2...,w_n)=p(w_1)p(w_2)...p(w_n)$。这里有n个参数$p(w_1)$、$p(w_2)$…。生成的文本就是简单的从词的概率分布中抽取词汇。例如$p("Today  is  Wend")=p("Today")p("is")p("Wend")$。 
 　 
 　
 
　我们可以使用Topic1的词分布产生一篇 关于Text mining的文章。我们可以使用Topic2的词分布产生一篇关于 Food nurtrition的文章。当然我们也可以用Topic1的词分布产生一篇关于 Food nurtrition的文章，但这样的事情概率很低。这是依据词分布生成文章。 
 　接着我们换个角度。如果现在有一篇文档（已知文章的词的总量，每个词的词频），现在推测哪种词模型可能产生这样一篇文档，假设文章是由分布中的词汇组装而成的。 
 　p(text)=? p(mining)=?….. 
 　一种很直接的想法是用词频/词的总数：p(text)=$\dfrac{10}{100}$，$p(mining)=\dfrac{5}{100}$….. 
 　这种方法被称为极大似然估计(Maximum Likelyhood Estimator ):$p(w|\theta)=p(w|d)=\dfrac{c(w,d)}{|d|}$ 
 　对于没有出现在文档中的词，p(w|d)=0。　 
 　 
 　
 
一元模型的用途。 
 用途１：表示不同的主题。这里涉及到通用模型，集合模型，文档模型。
 
 
用途2：做词的关联分析。从语义上来讲，哪些词和”computer”最接近？第一步，我们从包含”computer”的文档中得到每次的极大似然估计概率，将概率从大到小排序；第二步，我们找到这些词中有很多是通用词库的词，与”computer”无关，我们可以使用通用词库，得到通用词库每个词的极大似然估计概率。第三步，使用者两个模型，得到的词就是与”computer”相关的词。例如我们可以使用通用模型词的概率将第一步得到的概率normalize（规则化）：$\dfrac{p(w|"computer")}{p(w|B)}$
 
　
 
3 极大似然函数与一元模型
 
3.1 基本模型
 
　在统计语言模型中，我们提出：如果用户想要查找的是文档d，那用户有多大可能性提出这个特殊的查询 
 　例如文档d=”… news of presidential campaign … presidential candidate …” 
 　$p(q= “presidential campaign”|d)=?$ 
 　 
 　现在，我们假设用户以此文档为基准，来提出一个查询，并且查询该文档。使用一元模型的极大似然思想：$p(q= “presidential campaign”|d)=p("presidential "|d)*p("campaign"|d)=\dfrac{c("presidential",d)}{|d|}*\dfrac{c("campaign",d)}{|d|}$ (一元模型，就假设了查询中每个单词的产生是相互独立的)
 
3.2 升级版模型
 
　如果q = “presidential campaign update”，每个文档中都没有”update”这个词，概率p=0，这个时候就出现问题了。 
 　
 
　问题出在，如果假设用户查询的词都出在某一个文档(a document)，但实际上用户是看过很多文档，他查询的词更可能出在于一个文档模型(a document model)。 
 　 
 　
 
　从图中可以看出从文档模型产生文档，从文档模型产生查询。 
 　这样的模型该怎么计算呢？分两个步骤：1、计算文档模型(Document Language Model)；2、计算每个词在文档模型中概率的乘积。 
 　$q=w_1w_2...w_n$ 
 　$p(q|d)=p(w_1|d)*p(w_2|d)....*p(w_n|d)$ 
 　f(q,d)=logp(q|d)=$\sum_{i=1}^{n}logp(w_i|d)=\sum_{W\in V}logp(w|d)$ 
 　我的问题：增强版与简单版本的思想从字面上的区别看从“文档” 变成了“文档语言模型”。我最开始的想法是“文档语言模型”是由很多文档组成的一个文档集，但是看老师的ppt又认为不是这么回事。我需要再找资料查明什么是文档语言模型。
 
3.3 p(w|d)=?
 
　对于p(w|d)不同的估计方法会形成不同的不同的排序函数。 
 　第一种估计方法是极大似然估计。$p_{ML}(w|d)=\dfrac{c(w,d)}{|d|}$ 
 　对于没有出现在文旦中的词，我们需要平滑技术，为那些没有出现在文档中的词给一个概率。 
 　一种解决方法是从一个引用语言模型查询出一个概率。这个引用语言模型可以是Collection Language Model. 
 　
 
最后得到的排序函数是： 
 $f(q,d)=log(p|d)=\sum_{w_i \in q ,w_i \in d}[c(w_i,q)*log\dfrac{p_{seen}(w_i|d)}{\alpha_dp(w_i,C)}]+nlog\alpha_d+\sum_{i=1}^{n}logp(w_i|C)$ 
 这是公式是经过变形的，为了方便计算得到的。同时，这个公式也更像TF-IDF得到的计算公式。 
 
 
　$p_{seen}(w_i|d)$扮演了类似TF的角色。 
 　$p(w_i,C)$，在分母上，更像是IDF。 
 　$\alpha_d$类似于文档长度因子。它表示究竟想给未见过的单词多大的概率。如果文档本身很长，可能给的概率就会小一些；如果文档本身很短，给的概率就会大一些。 
 　
 
3.4 平滑方法
 
　$p_{seen}(w_i|d)=?$ 
 　$\alpha_d=?$ 
 　上面的公式留下了两个问题。
 
3.4.1 线性插入法
 
　Linear Interpolation (Jelinek-Mercer) Smoothing：固定系数 
 　结合极大似然算法： 
 　$p(w|d)=(1-\lambda)\dfrac{c(w,d)}{|d|}+\lambdap(w|C)，\lambda \in [0,1]$ 
 　$\alpha_d=\lambda$ 
 　$f_{JM}(q,d)=\sum_{W \in q,W \in d}c(w,q)log[1+\dfrac{1-\lambda}{\lambda}\dfrac{c(w,d)}{|d| p(w|C)}]$
 
3.4.2 狄利克雷
 
　Dirichlet Prior (Bayesian) Smoothing 动态系数修改，添加伪计数 
 　 
 　$\alpha_d=\dfrac{\mu}{|d|+\mu}$ 
 　$f_{DIR}(q,d)=[\sum_{W \in q,W \in d}c(w,q)log[1+\dfrac{c(w,d)}{\mu p(w|C)}]]+nlog\dfrac{\mu}{\mu +|d|}$
 
　按照查询似然的方式得到了和VSM类似的结果。不同的解决思路，过程中需要增加填补的方式也不同。 
 　查询似然->一元语言模型->文档语言模型->平滑 
 　位向量->词频->TF-IDF->TF变形->惩罚长文档