一种移动场景下的搜索结果过滤方法

暂无

一种移动场景下的搜索结果过滤方法\n技术领域\n[0001] 本发明属于信息检索领域，具体涉及一种移动场景下的搜索结果过滤方法，该方法适用于移动场景下的个性化搜索。\n背景技术\n[0002] 过去的十几年里，搜索引擎技术取得了飞速发展，传统的互联网搜索从技术实现到商业模式都已经发展的相当成熟，并取得了巨大成功。近年来，以移动互联网为代表的新兴技术和应用不断涌现，移动搜索便是移动互联网重要应用之一。\n[0003] 移动搜索由于移动终端移动性，便携性，以及屏幕尺寸、处理能力和可用带宽等局限性，使得其不能直接照搬现有互联网搜索的实现方案，主要原因有以下两点：(1)传统的互联网搜索引擎通常返回给用户大量的结果，实际上大多数情况下这些结果对用户而言，有一半以上是不相关的。其中一个主要的原因搜索引擎在只是对搜索关键字进行了简单了匹配，没有考虑其他信息(如用户上下文信息，个人偏好等)，加上互联网上信息的激增，导致了很多“垃圾结果”的产生，用户不得不在搜索结果中自己筛选，这大大加重了用户的负担。在移动场景下，由于移动终端屏幕键盘尺寸、处理能力和可用带宽等局限性，上述情形是用户不能容忍的，一是大量垃圾结果浪费宝贵流量，二是用户在移动终端上对搜索结果进行翻页筛选是很不方便的，这决定了移动搜索必须是精准的搜索，要返回给用户尽量少的，精准的结果；(2)对同一个搜索关键字，统的互联网搜索引擎对所有的用户返回的是千篇一律的结果，然而不同用户由于其背景知识不同，兴趣爱好不同，信息需求是不同的，同一个关键字对不同的人，在不同的领域，不同的时间和地点都可能表达不同的意思，用户需要的往往只是所有搜索结果里面一个很小的子集。移动终端的移动性，便携性和私人性，使得用户可以随时随地的获取所需信息，使得个性化搜索需求更加强烈，这决定了移动搜索是一种与用户个人特征(如兴趣等)和用户上下文(如时间，地点，天气等因素)相关的个性化的搜索。\n[0004] 因此，移动搜索需要实现的是个性化的精准搜索。目前，国内移动搜索研究尚处于起步阶段，实现技术较现有互联网搜索技术都尚不成熟，较早的技术有垂直搜索技术，如手机音乐搜索，小说搜索等，目前采用较多的实现方案是结合现有互联网搜索技术和相关辅助技术，如信息过滤技术，先对用户进行特征建模，然后以此模型对搜索结果进行个性化过滤，过滤掉不相关结果，实现个性化精准搜索。\n[0005] 用户特征建模常用技术有向量空间模型和本体模型，向量空间模型因其原理简单，实现容易，应用相对广泛。\n[0006] 信息过滤技术常用的有基于内容的过滤技术和协同过滤技术，基于内容的过滤技术是对结果进行特征提取，计算结果和过滤模板(用户模型)的相似度，按设定阈值过滤，因为是以结果内容进行分析，通常能达到较好的过滤效果，但计算量较大。协同过滤技术则根据相同类型的人通常有着相同兴趣偏好这一思想，通过与当前用户兴趣相似的用户来对用户的搜索结果进行协同过滤，这一技术已在电子商务领域取得了很好的发展和应用。\n发明内容\n[0007] 本发明的目的是提供一种移动场景下的搜索结果过滤方法，该方法通过挖掘用户数据(用户历史位置信息，历史通话记录等)建立用户特征模型和用户社交网络，并依据用户特征模型和用户社交网络对搜索结果分别进行基于内容的过滤和协同过滤，过滤掉不相关的搜索结果，实现移动场景下的个性化的精准搜索，这对提高移动搜索用户体验和用户粘性是很有价值的。\n[0008] 本发明提供的一种移动场景下的搜索结果过滤方法，该方法包括下述步骤：\n[0009] 第1步对用户Ui，i＝1，2，...，N的待过滤初始结果集R1，R2，...，RZ，利用d维向量空间对待过滤结果建立特征向量，Rr的特征向量表示为fRr＝{(q1，v1)，(q2，v2)，...，(qd，vd)}，va代表各个维上的权值；利用词频/逆文档频率TF/IDF模型计算fRr，在每一维上的权值va，对q1，q2，...qd中的每一个词qa，如果其没有出现在Rr，中，则其权值为0，否则为其TF/IDF值，TF为其在Rr中出现的次数，IDF即逆文档频率，统计那些包含该词的结果个数z；\n[0010] 其中，IDF值即log(Z/z)，Z是待过滤初始结果的个数，TF/IDF值为TF与IDF的乘积，r＝1，2，...，Z，a＝1，2，...，d；\n[0011] 第2步寻找当前用户Ui，的相似用户，从下述两个用户集合中选取，一是用户所属的群体Gg，g为用户所属的群体的序号，其取值范围为1至m，二是用户社交网络里的用户的集合，将这两个集合进行合并得到集合S，记该集合中的用户为Uis，利用式I所示的向量余弦夹角公式计算用户Ui与集合S中的每一个用户Uis之间的相似度，如式II所示，向量夹角越小，余弦值越大，相似度越大，反之亦然；i表示用户的序号，N表示用户的数量，i＝1，\n2，...，N，fUi和fUis分别代表Ui和Uis的特征向量，ψ(Ui，Uis)代表Ui与Uis之间的关系程度，若Uis在Ui的社交网络中，则ψ(Ui，Uis)取相应的值，否则取零值；按相似度从高到低选取前η个用户Ui1，Ui2，...，Uiη，若不足η个，则选取S中的所有用户；η为预先设定值；\n[0012] 式I\n[0013] 式II\n[0014] 第3步基于内容过滤：\n[0015] 对每一条待过滤初始结果Rr，采用式III依次计算其与用户Ui之间的相似度，fUi和fRr分别代表Ui和Rr的特征向量；根据相似度按预先设定的阈值ζ过滤，将相似度小于阈值ζ的初始结果过滤掉，得到中间结果集Rr，r＝1，2，...，Zζ，过滤得到的中间结果按原有的先后顺序排列；\n[0016] 式III\n[0017] 其中，\n[0018] 第2步对中间结果集Rr，r＝1，2，...，Zζ进行协同过滤，利用用户Ui的η个最相似用户Ui1，Ui2，...，Uiη，对中间结果Rr，，按式IV计算相似度sim′(Ui，Rr)进行协同过滤，式中， 和 分别代表Uis与Ui，Uis与Rr之间的相似度；\n[0019] 式IV\n[0020] Rankr＝θ·r+(1-θ)·sim′(Ui，Rr) 式V\n[0021] 根据sim′(Ui，Rr)按预先设定的阈值ε进行协同过滤，将相似度小于ε的中间结果过滤掉，得到临时结果集Rr，r＝1，2，...，Zε，r代表其在临时结果集中的先后顺序排序，依次为1，2，...，Zε，对临时Rr，，以预先设定的加权系数θ利用式V计算其顺序r和sim′(Ui，Rr)的加权和，作为最终结果排名Rankr，以此排名对临时结果集Rr，重新排序，得到最终结果，返回给用户，过滤过程结束。\n[0022] 本发明提供的移动场景下的搜索结果过滤方法，综合采用了数据挖掘方法(分类，聚类)，基于内容过滤算法和协同过滤算法。具体而言，本发明有以下效果和优点：\n[0023] (1)准确度高，本发明创新性的将用户社交网络信息加以分析，在传统的基于内容过滤的基础上同时进行协同过滤，很大程度提高了准确度。\n[0024] (2)适应性强，本发明考虑到移动用户群体和个人的多样性，能很好地适应各种用户群体和个人的个性化需求。\n[0025] (3)可扩展性高，本发明提供的过滤方法除了能用于移动搜索，也能用于其移动互联网应用，精准广告投放等，用户特征建模方法也能应用于客户关系管理(CRM)等。\n附图说明\n[0026] 图1为本发明方法的整体流程图；\n[0027] 图2为移动用户历史位置变化频率简图；\n[0028] 图3为移动用户按位置聚类的流程图；\n[0029] 图4为移动用户社交网络结构图；\n[0030] 图5为移动搜索结果的详细过滤流程图。\n具体实施方式\n[0031] 下面结合附图对本发明进行详细说明。\n[0032] 本发明提供的一种移动场景下的搜索结果过滤方法，如图1所示，先是过滤预处理阶段，主要包括用户细分，构建用户特征模型和构建用户社会网络，分别对应下述步骤(1)至步骤(3)，然后是结果过滤阶段，对应下述步骤(4)。具体的处理步骤如下：\n[0033] 1、过滤预处理阶段，包括下述步骤(1)至步骤(3)。\n[0034] (1)用户细分，采用数据挖掘的方法对用户进行细分，现有电信运营商提供的用户数据集，里面收集了大量的用户数据，如用户的历史位置信息，历史通话记录，用户的历史查询记录和浏览记录，历史业务数据等，本发明主要以用户的历史位置信息来对用户进行细分，具体步骤如下：\n[0035] (a)根据用户的历史位置变化频率对用户进行划分，用户的历史位置信息记录了用户历史位置L和相应时间信息T，位置信息L以经纬度的形式记录在数据集里，如(30.2332，114.3243)，时间信息T以时间点的形式记录，已知用户相邻两次历史位置的经纬度，采用经纬度距离公式(式(1))很容易计算出其距离，设第一个位置L1的经纬度为(lon1，lat1)，第二个位置L2的经纬度为(lon2，lat2)，按照0度经线的基准，东经取正值，西经取负值，北纬按(90°-lat)带入计算，南纬按(90°+lat)带入计算，用式子(1)则可计算两点之间的距离。\n[0036] C＝sin(lat1)·sin(lat2)·cos(lon1-lon2)+cos(lat1)·cos(lat2)\n[0037] \n[0038] 对每一个用户Ui，(i＝1，2，...，N)，计算其最近一段时间ΔT(如一个月)内的历史位置累计变化频率Fi，(i＝1，2，...，N)，其中，N表示用户的数量。\n[0039] \n[0040] 如式(2)所示，(L1，T1)，(L2，T2)，...，(LM，TM)是用户Ui，(i＝1，2，...，N)最近一段时间ΔT内的历史位置信息，(Lk-1，Tk-1)和(Lk，Tk)即用户相邻的两次历史位置和时间信息，Dis(Lk，Lk-1)与Tk-Tk-1分别为相邻两次的历史位置距离与时间之差。M表示当前用户的历史位置数量，k表示历史位置的序号。\n[0041] 统计所有用户的F，得到F的总体范围区间Ω，将Ω划分成若干子区间Ω1，Ω2，...，Ωn，n表示用户群体的数量，这些子区间以F表征不同的用户群体，用户依照其F被划分至相应的子区间内，如图2所示，用户A的F较高，可能是经常出差的商务人士。用户B的F较低，则可能经常是较长时间都在某一固定位置，如可能是某一高校学生，这样根据位置的变化频率F，对用户进行一个初步的划分，将用户分成的不同的群体Ω1，Ω2，...，Ωn。对Ω进行划分可以采用均分的方式，也可以由系统预先设定一个划分标准。\n[0042] (b)接下来对每一个Ωj，(j＝1，2，...，n，j表示群体的序号)里的用户按历史位置信息进行聚类，将位置邻近的用户聚为一类，相关调查研究表明，地理位置邻近的用户在一定程度上有着相似的用户特征，采用k均值聚类算法对每一个Ωj，(j＝1，2，...，n)里的用户进行聚类，步骤如下：\n[0043] (b1)首先计算出每一个用户Ui，(i＝1，2，...，N)在ΔT时间内的历史位置的中心位置Oi，根据Oi对用户进行聚类；i表示用户的序号；\n[0044] (b2)从Ωj，(j＝1，2，...，n)中随机选取k个用户，每个用户Uq，(q＝1，2，...，k)代表一个初始的用户簇Cq，(q＝1，2，...k)，其Oq，(q＝1，2，...，k)代表用户簇的初始中心；\n[0045] (b3)对Ωj，(j＝1，2，...，n)中剩余的每个用户，计算其与每个用户簇Cq，(q＝\n1，2，...k)中心Oq，(q＝1，2，...，k)的距离(经纬度距离公式)，将其指派给距离最近的用户簇；\n[0046] (b4)然后重新计算每个用户簇的新的中心值Oq，(q＝1，2，...，k)，替换旧的中心值。按式(3)计算准则函数Ej的值，若Ej的值收敛则聚类过程结束，否则，转步骤b3。\n[0047] (j＝1，2，....n) (3)\n[0048] 如式(3)所示，Dis(U，Cq)代表Ωj，(j＝1，2，...，n)里的用户与用户簇Cq，(q＝\n1，2，...k)中心Oq，(q＝1，2，...，k)的距离。\n[0049] 聚类得到紧凑的用户簇，这样在Ω1，Ω2，...，Ωn划分的基础上，将用户进一步划分成了更小的群体G1，G2，...，Gm，实现用户细分。\n[0050] (2)构建用户特征模型，用户的历史查询记录很好的表征了用户的兴趣特征，通过分析用户的历史查询记录，采用向量空进模型对用户进行特征建模，其步骤包括：\n[0051] (a)统计所有用户ΔT时间内的所有历史查询记录，统计得到d个互异的词q1，q2，...，qd，作为向量空间的d个维，用户的特征向量表示为fUi＝{(q1，v1)，(q2，v2)，...，(qd，vd)}，(i＝1，2，...，N)，va，(a＝1，2，...，d)代表各个维的权值。\n[0052] (b)采用TF/IDF(词频/逆文档频率)模型，对每一个用户Ui，(i＝1，2，...，N)，计算其特征向量每一维的权值。对q1，q2，...，qd中的每一个词qa，(a＝1，2，...，d)，如果其没有出现在用户的历史查询记录中，则其相应权值va，(a＝1，2，...，d)为0，否则为其TF/IDF值，TF即词频，这里为用户的历史查询记录中出现该词的次数，IDF即逆文档频率，统计那些历史查询记录中出现过该词的用户的个数D，IDF值即log(N/D)，N是所有用户数，TF/IDF值为TF与IDF的乘积。\n[0053] (3)挖掘用户社交网络信息，分析用户历史通话记录，对每一个用户Ui，(i＝1，\n2，...，N)，其社交网络呈现为一个以该用户为中心的星型拓扑图，如图3所示，中心节点B代表用户自己，星星节点A，C，D，E，F，G等代表与B有通话记录的用户，边的权重ψ代表用户之间的关系程度，该步骤主要是估算ψ的值。\n[0054] 用户的历史通话记录数据记录了所有用户之间的通话记录，包括通话双方的id号码)，通话开始时间，通话结束时间等，对每一个用户Ui，(i＝1，2，...，N)，分析其ΔT时间内的通话记录，对与其有通话记录的每一个用户ux，(x＝1，2，...，e，e表示与其有通话记录的用户个数)，分析其与Ui，(i＝1，2，...，N)在ΔT内的总通话次数α，总通话时长β，通话规律γ，综合分析这些因素，可以大致推断出Ui，(i＝1，2，...，N)与ux，(x＝1，\n2，...，e)之间的关系程度ψix。\n[0055] 总通话次数α和总通话时长β比较容易统计得到，但它们都是总体性的统计量，比较单一，只能总体上粗略体估计用户之间的关系程度，而忽略了重要的细节特征，如每次通话事件随时间的分布是否均匀，是整体均匀还是局部均匀等，所以这里还引入了通话规律γ这一特征因素来表征Ui，(i＝1，2，...，N)与ux，(x＝1，2，...，e)之间的关系程度，通过统计分析时间ΔT内的所有通话事件的时间分布特点，借用方差的思想，如式(4)(5)(6)，th，(h＝1，2，...，α)为每次通话开始时间，Δth为相邻两次通话记录之间的时间差，St为其方差，γ反比于St，如式(6)所示，方差小表示该段时间内的通话比较有规律，γ相应较大，反之亦然。\n[0056] Δth＝th-th-1，(h＝2，3，...，α) (4)[0057] \n[0058] \n[0059] \n[0060] 将计算得到的α，β，γ进行归一化处理，得到0和1范围之间的值，ψix，(i＝\n1，2，...，N，x＝1，2，...，e)的值采用式(8)计算得到，它是综合考虑α，β，γ得到的一个加权值，式(8)中，0≤λ1≤1，0≤λ2≤1，0≤λ3≤1，且λ1+λ2+λ3＝1，其默认值取均值1/3。\n[0061] ψix＝λ1·α+λ2·β+λ3·γ，(λ1+λ2+λ3＝1) (8)\n[0062] 这样通过该步骤的分析与计算，就得到了每个用户Ui，(i＝1，2，...，N)的社交网络信息，包括其与之有联系的用户ux，(x＝1，2，...，e)之间的关系程度ψix。\n[0063] (4)搜索结果过滤，前面步骤(1)至步骤(3)都是准备阶段，是为了该步骤的搜索结果过滤服务的，步骤(2)建立的用户特征模型是用来对搜索结果进行基于内容的过滤，步骤(1)所做的用户细分和步骤(3)挖掘的用户社交网络信息是用来对搜索结果进行协同过滤。\n[0064] 该步骤对搜索结果先进行基于内容的过滤，然后进行协同过滤。以达到个性化和精简搜索结果的目的。\n[0065] 用户Ui，(i＝1，2，...，N)提交一次搜索Q，搜索请求首先由现有互联网搜索引擎来处理，现有互联网搜索引擎对搜索Q返回一个初始结果集，该结果集通常较大，选取该结果集里的前φ条结果来进行过滤，若不足φ条，则选取全部初始结果集，作为待过滤结果集R1，R2，...，RZ，φ为一个经验值，由系统预先设定，如设定为300，Z为待过滤结果的个数。\n结果的过滤流程如图5所示，步骤如下：\n[0066] (a)对待过滤结果集R1，R2，...，RZ，建立特征向量，采用步骤(2)中建立的d维向量空间对这些结果建立特征向量，Rr(r＝1，2，...，Z)的特征向量表示为fRr＝{q1，v1)，(q2，v2)，...，(qd，vd)}，(r＝1，2，...，Z)，va，(a＝1，2，...，d)代表各个维上的权值。同样采用步骤(2)中用到的TF/IDF(词频/逆文档频率)模型来计算fRr，(r＝1，2，...，Z)在每一维上的权值va，(a＝1，2，...，d)，对q1，q2，...qd中的每一个词qa，(a＝1，2，...，d)，如果其没有出现在Rr，(r＝1，2，...，Z)中，则其权值为0，否则为其TF/IDF值，TF为其在Rr，(r＝1，2，...，Z)中出现的次数，IDF即逆文档频率，统计那些包含该词的结果个数z，IDF值即log(Z/z)，Z是所有结果数，TF/IDF值为TF与IDF的乘积。\n[0067] (b)接下来寻找当前用户Ui，(i＝1，2，...，N)的相似用户，从两个用户集合中选取，一是步骤(1)中用户所属的群体Gg，g为用户所属的群体的序号，其取值范围为1至m，二是步骤(3)中建立的用户社交网络里的用户的集合，将这两个集合进行合并(有可能有重复的用户)得到集合S，从集合S中选取若干个相似用户。\n[0068] \n[0069] \n[0070] 式(10)中，|| ||表示向量的模。\n[0071] (5)采用式(10)所示的向量余弦夹角公式计算Ui，(i＝1，2，...，N)与集合S中的每一个用户Uis之间的相似度，如式(9)所示，向量夹角越小，余弦值越大，相似度越大，反之亦然。fUi和fUis分别代表Ui和Uis的特征向量，ψ(Ui，Uis)代表Ui与Uis之间的关系程度，若Uis在Ui的社交网络中，则ψ(Ui，Uis)取相应的值，否则取零值。按相似度从高到低选取前η个用户Ui1，Ui2，...，Uiη，若不足η个，则选取S中的所有用户。η为一个经验值，由系统预先设定，如其默认值可以取10个。\n[0072] (c)然后开始进行结果过滤了，过滤过程分两个阶段，基于内容的过滤阶段和协同过滤阶段：\n[0073] (c1)先是基于内容过滤，对(a)中的每一条待过滤初始结果Rr，(r＝1，2，...，Z)，依次计算其与用户Ui，(i＝1，2，...，N)之间的相似度，同样，采用式(10)计算两者之间的相似度，如式(11)所示，fUi和fRr分别代表Ui和Rr的特征向量。根据相似度按阈值ζ过滤，将相似度小于ζ的结果过滤掉，得到中间结果集Rr，(r＝1，2，...，Zζ)，过滤得到的中间结果按原始的先后顺序排列。阈值ζ为一个经验值，由系统预先设定，0≤ζ≤1，其默认值可以设定为0.65。\n[0074] \n[0075] (c2)接下来对中间结果集Rr，(r＝1，2，...，Zζ)进行协同过滤，协同过滤是基于相似用户通常有着相似的兴趣这一思想，以当前用户的相似用户来对当前用户进行协同推荐，采用步骤(b)中计算得到的用户Ui，(i＝1，2，...，N)的η个最相似用户Ui1，Ui2，...，Uiη，对中间结果Rr，(r＝1，2，...，Zζ)，按式(12)计算相似度sim′(Ui，Rr)进行协同过滤，式中，采用式(10)向量余弦夹角公式， 和 分别代表Uis与Ui，Uis\n与Rr之间的相似度。\n[0076] \n[0077] Rankr＝θ·r+(1-θ)·sim′(Ui，Rr) (13)[0078] 根据sim′(Ui，Rr)按阈值ε进行协同过滤，将相似度小于ε的结果过滤掉，得到临时结果集Rr，(r＝1，2，...，Zε)，r代表其在临时结果集中的先后顺序排序，依次为1，\n2，...，Zε)，对Rr，(r＝1，2，...，Zε)，以加权系数θ计算其顺序r和sim′(Ui，Rr)的加权和，作为最终结果排名Rankr，如式(13)所示，以此排名对Rr，(r＝1，2，...，Zε)重新排序，得到最终结果，返回给用户，过滤过程结束。阈值ε与加权系数θ均为经验值，由系统预先设定，0≤ε≤1，0≤θ≤1，ε的默认值可以设定为0.85，θ的默认值可以设定为\n0.5。\n[0079] 本发明不仅局限于上述具体实施方式，本领域一般技术人员根据本发明公开的内容，可以采用其它多种具体实施方式实施本发明，因此，凡是采用本发明的设计结构和思路，做一些简单的变化或更改的设计，都落入本发明保护的范围。