房价的未来走势分析

《房价的未来走势分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

2011年商丘师范学院数学建模模拟练习承诺书我们仔细阅读了商丘师范学院数学建模模拟练习的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们的参赛报名号为：12参赛组别（本科或专科）：本科参赛队员(签名)：队员1：丁维队员2：刘明明队员3：贾淑丹12 2011年商丘师范学院建模模拟练习编号专用页参赛队伍的参赛号码：（请各个参赛队提前填写好）：竞赛统一编号（由竞赛组委会送至评委团前编号）：竞赛评阅编号（由竞赛评委团评阅前进行编号）：12 2011年商丘师范学院数学建模模拟练习题目搜索引擎与PageRank算法的改进摘要在网络发达的今天，上网的用户和网上的信息呈指数形式飞速增长，然而当单个用户面对整个Internet的海量信息时，用户往往感到很难找到他真正需要的有用信息。搜索引擎是当前广泛被采用的一项技术，每天都要无数的Internet用户通过搜索引擎查询他们所需要的信息，它对互联网的普及尤为重要，只有一个合理的搜索引擎排序算法才可为互联网营造一个公平的竞争环境。在问题一中，考察Google的PageRank算法，应用随机冲浪模型，引入阻尼系数，给出了比较合理的PageRank算法模型，并假设在一个封闭的有限的网页链接中，运用牛顿迭代法，求出各个网页的PageRank值，并对他们进行网页排名。在问题二中，通过网上大量资料查询，作为搜索引擎的建设者，我们采用了ClusterRank算法，用K-means算法对搜索引擎搜索到的网页进行聚类，分为r个聚簇，结合PageRank算法和网页点击率对聚簇后的网页进行排序，尽量为用户提供较权威的网页，并通过浏览这些网页使用户易于明确自己的检索需求。经过问题一和问题二的分析，在问题三中我们可以从链接量、链接质量、关键字等方面提出如何提高网站排名的方法，并根据实际对所提出的方法进行完善。关键字：PageRank算法、搜索引擎、随机冲浪模型、网页排名、K-means算法12 一、问题重述随着信息技术的不断发展，特别是互联网应用的迅速普及，网络规模的爆炸性增长，网上的信息正以几何级的速度在增加。如何在茫茫互联网中找到用户所关心的网页，是各个搜索引擎的主要职能。因此搜索引擎已成为互联网应用的重要组成部分，它对互联网的普及正产生着极大的影响。而其中搜索引擎的核心技术——排序算法也变得极为重要，只有一个合理的搜索引擎排序算法才可为互联网营造一个公平的竞争环境。通常一个搜索引擎的算法，要考虑很多的方面。例如：域名、密度、内链、外链、相关度、服务器稳定、内容更新、域名时间、内容数量等。我们就搜索引擎与Google的重要排名指数Pagerank提出以下问题：问题一：针对Google的Pagerank算法，建立数学模型，给出比较合理的Pagerank的计算方法；问题二：若作为搜索引擎的建设者，我们应该侧重考虑搜索网页的哪些因素，根据用户的需求，合理而公平的对上亿的网页进行有选择性的，根据其相关性紧密程度排序。问题三：若想要建立一个新的网站，由第2题中建立的搜索引擎中排名的方法，怎样使网页在各大搜索引擎中排名比较靠前。二、问题假设与符号说明2.1问题假设在问题一的模型求解中，假设HTML文件间的链接关系只闭合于五个文件中。2.2符号说明l……………………网页b页的值；l……………………链接到b页的网页p的值；l……………………网页p的出站链接数量；l……………………阻尼系数，,；lA……………………表示所有指向网页b的网页集合；三、问题分析3.1问题一分析PageRank算法是由Google公司两个创始人Sergey及LarryPage提出的一种搜索引擎排序算法。网页的PageRank值决定了随机访问到这个页面的概率，PageRank算法采用的是随机冲浪网上冲浪模型，即假设冲浪者跟随超链接进行了若干步浏览后转向一个随机的网页，冲浪者又重新跟随超链接浏览，那么这个网页的价值程度就由该网页被随机冲浪者访问到的频率所决定。阻尼系数d的引入，是因PageRank为用户不可能无限的点击链接，常常因无聊而随机跳入另一个页面。通过PageRank模型，对各个网页的PageRank值进行排序。3.2问题二分析对网页排名的问题中，采用ClusterRank算法，对搜索引擎搜索到的网页进行聚类，通过PageRank值和点击率对网页进行排名。通过浏览这些网页使用户易于明确自己的检索需求。12 3.3问题三分析根据第二问中排序方法的模型层次分析，得出其影响因素重要性的主要次序为链接数量、链接质量、页面标题、关键词密度、点击测量原则，从而得出与之相对应的提高排名的方法。并根据有关网站排名的实际案例，得出一些实用的方法。一、名词解释阻尼系数d——定义为用户不断随机点击链接的概率，所以，它取决于点击的次数，被设定为0-1之间。d的值越高，继续点击链接的概率就越大。因此，用户停止点击并随机冲浪至另一页面的概率在式子中用常数(1-d)表示。无论入站链接如何，随机冲浪至一个页面的概率总是(1-d)。(1-d)本身也就是页面本身所具有的PageRank值。二、模型的建立与求解问题一：PageRank算法简单描述如下：式中：l：网页b页的值；l：链接到b页的网页p的值；l：网页p的出站链接数量；l:阻尼系数，,。lA表示所有指向网页b的网页集合；模型（1）求解假设有像如下图（1）所表示的链接关系，并且假设HTML文件间的链接关系只是闭合于这四个文件中。即除了这些文档以外没有其他任何链接的出入。(1)BBBBBBBCADE此图可表示为矩阵A，若有网页b指向网页p的链接，记为1,否则记为012 ，则此矩阵为5*5方阵A=式的推移概率行列式G,是将A转置后将各个数值除以各自的列向量之和得到的.根据公式（1）,假设这五个网页PageRank初始值为1通过迭代法，运用MATLAB求解直到这五个值分别逼近一个定值得通过以上计算，求出各网页的排名得表如下（2）名次12345网页ABEDC问题二：网页排名算法K-means聚类算法的介绍在聚类问题中，给我们的训练样本是，每个，没有了y。K-means算法是将样本聚类成k个簇（cluster），具体算法描述如下：1，随机选取k个聚类质点心（clustercentroids）为、…属于。2，重复下面过程知道收敛﹛对于每一个样例I,计算其应该属于的类12 ﹜对于每一个j,重新计算该类的质心K是我们事先给定的聚类数，代表样例i与k个类中距离最近的那个类，的值是1到k中的一个。质心代表我们对属于同一个类的样本中心点的猜测，拿星团模型来解释就是要将所有的星星聚成k个星团，首先随机选取k个宇宙中的点（或者k个星星）作为k个星团的质心，然后第一步对于每一个星星计算其到k个质心中每一个的距离，然后选取距离最近的那个星团作为，这样经过第一步每一个星星都有了所属的星团；第二步对于每一个星团，重新计算它的质心（对里面所有的星星坐标求平均）。重复迭代第一步和第二步直到质心不变或者变化很小。ClusterRank网页排序算法ClusterRank方法的目的是在保证信息覆盖率的前提下，尽可能为用户提供较权威的网页，从而帮助用户在浏览搜索结果的过程中进一步明确查询结果的过程中进一步明确查询需求。算法流程图如图（1）12 ClusterRank算法流程图（1）第一步：假设针对用户查询关键字的请求返回一个检索结果集。采用K-means聚类方法对文档Q进行聚类，得到r个聚簇每个聚簇内部文档在内容上具有较高的相似度，而聚簇之间的文档内容相似度较低，其中其中…分别代表相应聚簇所包含的文档数目，表示第k个聚簇中的一个文档。在这一步中，我们使用向量空间模型（VSM）来表示文档：给定文档，其中表示此文档的第j个关键字，为文档中关键字的权重，两个文档与的相关度常用它们之间的相似度——向量之间的夹角来衡量：我们选择了k-means算法对文档进行聚类，对文本进行粗略分类。首先给定一个聚类数目r,随机选择r个文本作初始的类质心，根据每个文本与质心的相似度，将它归入最相似的聚簇。然后重新计算每个类的质心，不断迭代计算直到准则函数收敛。我们采用的准则函数是:12 其中代表第k个聚簇的质心。通过重复运行算法N次选出一个使准则函数最优的结果作为最终的聚类结果。第二步：根据模型1对各文档的PageRank值进行计算，并按降序排列，各重要网页的排名大大提前。第三步：初始化文档集A=，文档文档集Q可表示如下：（1）其中，当然也可以将一个指定的数值赋值给m，从而知道最后将提交给用户的最大文档个数为rm.第四步：将（1）式第一列中的文档按照其各自的用户点击率CK值的大小进行降序排列并放入A中。之所以考虑用户点击率是因为用户的选择，即搜索引擎用户对返回结果的每一次点击，实际上就是对响应网页的一次选择。用户的这种选择时评价网页重要性的一个重要因素。针对这一问题，已有研究人员提出改进算法，依照用户的选择来调整返回结果集的排序。比如Google返回页面的代码中就包含了统计用户点击次数的代码：Onmousedown=returnclk(1,this).在本算法中将用户对网页的点击视为用户对网页质量的认可。我们认为点击率高的网页往往是因为其质量较高或者内容受欢迎从而得到用户的关注；点击率低，则认为其质量较差或内容较生僻。第五步循环第四步，直到Q=。最后得到的文档A就是一个新的网页排名，排在前排的文档内容涵盖了与查询相关的不同领域，并且是用户认可的重要网页。通过浏览这些网页，用户对自己检索对象隶属的范围有了较明确的了解，明确自己的检索需求。问题三：通过问题二的分析以及叙述，可得到如下提高排名的方法：1.建立友情链接，在链接数量上不是越多越好，且网站的外部文字链接的标题要包含关键字；2．在链接质量上，作为网站建立者应找那些PR值高且外部链接数又少的网站作为友情链接，这样才能提高自己网站的质量，一般来说母链接网页的质量越高，其子链接网页的排名越靠前；3.给网页起好标题，标题要包含网页内容的关键字，标题一般在35-40个字符即可，太长会给阅览者冗长且没有中心的感觉。而且在正文中，最好把关键字加粗；4.关键字在网页正文中最好出现的密度要在6-10%之间，因为大多人一般按照关键词在网页中出现的位置和频率来判断网页对该关键词的相关性。例如，我们可以遵循标题优先于网页、网页关键词位置的优先、网页中频度大的优先等关键词位置上的政策；12 5.把网页的更新时间周期尽量的缩短，网页的内容终究还是最重要的，网页的质量上升了，随之它的点击率便也得到大大的提高；6.最好要有个网站地图，使浏览者易于查询。一、模型结果分析在问题一中网页排名PageRank值出链页入链页A1.4472B,C,DB,EB1.0361AC,AE0.9801BAD0.9776EA,EC0.56D,AD通过上面的统计数据我们可以看出，PageRank的名次和反向链接的数目是基本一致的，例如页面A，正因为反向链接的数目最多，因此其PageRank值也最高。链接源的PageRank值也在其中发挥着重大作用，尽管页面B,E的出链页数相同，但B的PageRank值明显高于E。问题二中采用ClusterRank网页排名算法，对搜索引擎检验到的结果进行聚类得到r个聚簇，结合PageRank算法和网页点击率对文档进行排序，为用户提供了信息覆盖面较广的结果列表。二、模型的优缺点7.1模型的优点在问题一中PageRank算法是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得，它能有效减少在线查询时的计算量，极大降低了查询响应时间；在问题二中运用K-means算法具有较快的聚类速度，可以对较多的文本在短时间内进行粗略分类；在第三问中考虑到现实案例，并根据实际分析得到一些提高排名的方法，使其解答更加全面。7.2模型的局限性我们在问题一中选取有限个网页作为代表，具有一定的局限性。对网页排名的因素有很多，我们只考虑了较为重要的几个因素。三、参考文献【1】姜启源等，数学模型（第三版）[M].北京：高等教育出版社，2003【2】陈洁惠，搜索引擎排序算法的研究[D]，河海大学硕士学位论文，2007.3【3】宋聚平，对网页PageRank算法的改进[J]。上海交通大学学报，2003.3附录：第一问的MATLAB的程序如下clearclcforn=2:5012 a(1)=1;b(1)=1;c(1)=1;d(1)=1;e(1)=1;a(n)=0.15+0.85*(b(n-1)+(1/2)*e(n-1));b(n)=0.15+0.85*((1/3)*a(n-1)+c(n-1));c(n)=0.15+0.85*((1/3)*a(n-1));d(n)=0.15+0.85*((1/3)*a(n-1)+(1/2)*e(n-1));e(n)=0.15+0.85*d(n-1);endabcde运行结果为a=Columns1through121.00001.42501.66581.30761.49611.46531.41641.46911.44031.44571.45111.4446Columns13through241.44811.44741.44671.44761.44711.44721.44731.44721.44721.44721.44721.4472Columns25through311.44721.44721.44721.44721.44721.44721.4472b=Columns1through121.00001.28330.92211.09271.04921.01631.05301.03171.03491.03941.03401.0368Columns13through241.03631.03571.03641.03601.03611.03611.03601.03611.03611.03611.03611.0361Columns25through311.03611.03611.03611.03611.03611.03611.0361c=Columns1through121.00000.43330.55370.62200.52050.57390.56520.55130.56620.55810.55960.5611Columns13through240.55930.56030.56010.55990.56010.56000.56000.56010.56000.56000.56000.5600Columns25through310.56000.56000.56000.56000.56000.56000.5600d=Columns1through121.00000.85830.97870.99580.93780.99740.96770.97540.97960.97420.97720.9768Columns13through240.97610.97690.97650.97660.97660.97650.97660.97660.97660.97660.97660.9766Columns25through310.97660.97660.97660.97660.97660.97660.9766e=12 Columns1through121.00001.00000.87960.98190.99640.94710.99780.97250.97910.98260.97810.9807Columns13through240.98030.97970.98040.98000.98010.98010.98010.98010.98010.98010.98010.9801Columns25through310.98010.98010.98010.98010.98010.98010.980112