《web挖掘毕业论文第九章基于singlepass聚类的微博话题检测方法mb-singlepass.doc》由会员分享，可在线阅读，更多相关《web挖掘毕业论文第九章基于singlepass聚类的微博话题检测方法mb-singlepass.doc（110页珍藏版）》请在金锄头文库上搜索。
1、第一章 绪论1.1 选题背景及研究意义随着Internet的普遍应用及各种信息化的到来，各类数据急剧膨胀，人们日益被湮没在海量的存储数据当中而不知所措，因此如何从海量而繁杂的数据当中发现有价值的信息或知识一直以来受到国内外学者的密切关注和倾力研究。人类工作、生活中产生的数据是海量的，更是多样的，有存储和处理人类行为的结构化数据、有存储卫星图像的卫星数据、有存储Internet网站的网页数据、更有近些年流行起来的微博数据等。归纳起来这些数据包括存储于关系数据库中的结构化数据、和存储在网络当中的非结构化数据。如何从海量而且结构多样的数据中提取有利于人类发展的有用信息一直困扰着人类，数据挖掘正是为解
2、决此类问题而迅速发展起来的。数据挖掘（Data Mining，DM）是将潜在的、事先未知的、并且有用的知识和模式从含有相对复杂结构的数据库中提取出来的过程，因此也被人们习惯地称作数据库中的知识发现KDD（Knowledge Discovery in Database）。数据挖掘被应用于人类面临的数据问题越来越流行，但是怎样根据数据的特殊性进行数据挖掘进而更好地指导人类研究与决策值得深思。H省计生委为适应国家信息化的要求(出于保密需求隐掉了省的真实名字，而称为“H省”)，已于2008开始并基本完成了该省全员及流动人口信息的录入与采集工作，这些数据涵盖了该省7000多万人员的基本信息及扩展信息，其
3、中育龄妇女信息达209项，而这些信息基本都包含了每个人员的地理位置信息及各类行为的时间信息，即HH省人口信息具有多尺度特性，如人员居住及管理信息归属于空间尺度，而人员的迁入迁出信息归属于时间尺度。政府政策的实施也要参考相应的多尺度特性，如针对于县市级的决策不一定适用于地市级，针对于村级的决策不一定适用于乡县级，针对于A村的决策不一定适用于B村，针对于学生团体的决策不一定适用于其它社会团体。因此如何针对此类数据的多尺度特性进行挖掘，进而更好的指导政府的决策对社会的良性快速发展有着至关重要的作用。聚类是数据挖掘任务中重要的一环，因此聚类结果的优良也决定着后续挖掘结果的好坏。完成数据的多尺度聚类挖掘
4、对其后续的多尺度数据挖掘也起着至关重要的作用，从而为更有效地支撑政府的多尺度决策提供科学指导和依据。在理论上对数据挖掘的研究有了丰富，对多尺度数据挖掘的研究进度有了促进，更为后续的研究工作提供了指导。1.2 国内外研究现状1.2.1 聚类数据挖掘聚类作为数据挖掘过程中的重要一环，时至今日也没有一个统一的定义，Everitt在1974年对聚类作出了以下的定义：将数据集中的实体分成若干的类簇，以达到一个类簇内的实体是相似的，而不同类簇内的实体是不相似的；类簇为作测试空间中点的会聚，同一个类簇内的任意两个点之间的距离不大于不同类簇的任意两个点之间的距离；类簇也可以表示成一个包含密度相对较高的点集的多
5、维空间中的连通区域，而通过包含密度相对较低的点集的区域与其他类簇所分开。基于划分的聚类、基于层次的聚类、基于密度的聚类和基于模型的聚类挖掘算法组成了聚类挖掘庞大的算法家族。5。基于划分思想的聚类算法预先设定聚类数目或聚类中心，并通过反复迭代的运算方法慢慢减小目标函数的误差，以使得目标函数可以收敛，聚类结果也最终生成。其中MacQueen于1967年基于该思想提出了K-Means聚类算法，由于K-Means聚类算法通常会在获取一个局部最优解时终止，且只适合于数据型的数据和聚类结果为凸形的数据集聚类，Huang于1998年针对K-Means聚类算法对数值型数据集的局限性提出了一个适用于分类属性数据
6、聚类的K-Modes算法，该算法对K-Means算法进行了以下改进：引入新的相异性度量标准，使用Modes而非Means，在聚类的过程当中使用基于频度的方法来修正Modes以使得聚类代价函数值最小。Sun等人于2002年将Bradley的迭代初始点集求精算法应用于K-Modes算法而提出了迭代初始点集求精K-Modes算法，因为尽管Huang的K-Modes算法可以聚类分类数据，但其需要预先决定或随即选择类簇的初始Modes，而Modes的初始化差异经常会导致截然不同的聚类结果，而迭代初始化点集求精的应用刚好解决了这个问题。Ding等人于2004年提出了一致性保留K-Means聚类算法K-Me
7、ans-CP，他们认为最近邻一致性可以用于改善聚类的正确率，并提出了kNN和kMN一致性强制和改进算法，将类k最近邻或类k互最近邻一致性作为数据聚类的一种重要质量度量方法并验证了局部一致性信息可以用来优化全局聚类目标函数，进而得到更好的聚类结果。基于层次的聚类算法根据不同的聚类走向分成两小类，从底向上的层次聚合算法和从顶向下的层次分解算法。前者的思想是把每个数据点对象看成一个类，再对这些类进行聚合，将相似度高的两类聚成一类，以达到满足了事先设定的停止条件，或这些数据点对象成了一类的目的；后者却反其道而行之，把所有的数据点对象当成一类，再进行一步步地分解，以达到事先设定的停止条件，或每个数据点对
8、象成为一类的目的。其中Guha等人于1998年提出的CURE算法和Karypis等人于1999年提出的CHAMELEON聚类算法是聚合聚类算法中最具有代表性的两个算法。其中CURE把数据点集中既定数目的点对象当成某类的代表，而非单个中心或数据对象，以排除了孤立点的影响而达到很好地识别具有复杂形状和不同大小的聚类的目的。Guha于1999年对具有类别属性的数据进行聚类时在保留CURE算法的优良特性之外对CURE算法进行了改进，并提出了ROCK聚类算法。而CHAMELEON聚类算法在聚合聚类过程中利用了动态建模的技术。基于密度的聚类算法亦是一种非常重要的聚类方法，其在以空间信息为代表的多个领域均有
9、着广泛的应用，特别是随着大数据集、伸缩聚类算法的研究与发展，其在空间数据挖掘研究领域中日益活跃。该类聚类算法发现任何形状类的手段是定义数据密度，另外异常数据也能被很好得处理，在空间数据的聚类很常用。其中Ester M等人于1996年提出了DBSCAN方法，它以密度为基础，在该方法中，类就是一些密度相连的数据对象，而足够高密度的数据区域被生成以达到聚类的目的。为了克服聚类DBSCAN聚类算法受目标数据的维度影响较大的问题，Hinneburg A等人于1998年提出了DENCLUE算法，在该算法中，网格的预处理和以密度为基础的聚类方法被结合了起来，从而很好地实现了这一目的。此外，针对于数据在空间中
10、所呈现的不同密度分布，Ankest等提出了OPTICS方法，Xu等提出了DBCLASD方法，在这两个方法中对DBSCAN进行了改进，也是以密度为基础的方法。基于模型的聚类算法中，每一个类就是一个模型，只要找出数据的最佳模型来反映数据的分布函数就可以很好地完成聚类工作。其中Fisher于1987年提出的COBWEB是基于模型聚类算法当中的典型代表，该算法以分类树的形式构建一个层次聚类，并用“分类属性值”对作为输入对象的描述，在一个“分类属性-值”对输入后，该算法就按既定的规则改变计数，来找到分类的最好点，而产生最高分类效果的位置便为对象节点的最好选择。针对COBWEB算法中存在的不足之处，Gen
11、nari，Langley等人于1989年提出CLASSIT算法，Cheeseman和Stutz于1996年提出的AutoClass算法分别对COBWEB算法进行了改进。除以上四种分类以外，聚类算法家族还有基于ANN的、基于FS的、基于Grids的聚类方法，如Rumelhart和Zipser于1985年提出的竞争学习聚类方法，Kohonen于1982年提出的SOM聚类方法；Pileva等人于2005年提出的用于大型高维空间数据库的网格聚类算法GCHL等。1.2.2 多尺度数据挖掘尺度作为地学领域的重要概念，随着信息科学及智能处理在地学领域的广泛应用而发展到了其它学科，并最终形成了独立的一门学科多
12、尺度科学，即研究具有广泛时空尺度耦合现象的科学6。尺度是指所研究的事物在其“容器”中规模相对大小的一种描述，尺度特性不仅存在于地学领域，也同样是存在于社会、经济领域的过程和现象，在对地理现象的研究通常是通过对其描述的概念、量纲和内容的层次性完成的，将不同的尺度过程用特定的概念、量纲来抽象描述，进而发展了概念多尺度、量纲多尺度及内容或属性多尺度。概念多尺度是指描述地理现象的概念具有多尺度的含义；量纲多尺度是指描述地理现象或空间实体的单位及两侧的数据量级别，其尺度单位主要分为空间距离单位和时间长度单位；而内容或属性多尺度主要表现了属性变化的强弱幅度及内容的层次性，其中强弱幅度可以用单位时间内属性特
13、征变化的值来表示，而内容的层次性是指数据描述过程中的级别组合性7。尺度作为空间数据的重要属性，是指数据所表达的空间范围的大小和时间的长短，不同的尺度所表示的信息强度有很大的差异。一般来说，尺度越大，其所表达的信息强度就越小，尺度越小，所表达的信息强度就越大。而空间数据的多尺度特性主要从两方面进行理解：空间多尺度和时间多尺度，其中空间多尺度是数据所表达的空间范围的相对大小，分为不同的层次，即不同的尺度，较大的尺度所代表的空间范围就相对的大，而较小的尺度所代表的空间范围就相对小。时间多尺度是数据所表达的时间周期的相对长短，粗尺度所代表的时间周期相对长，而细尺度所代表的时间周期相对短。GPS、传感网
14、络和移动终端设备的应用越来越多，产生的数据飞速增长，怎样抽取这些数据中的有用知识和规则一直是时空数据挖掘研究的重要课题。多尺度数据挖掘是在数据的不同尺度进行挖掘的过程。Tsoukatos等人于2001年首次提出了DFS_MINE方法，这个方法可以挖掘数据库中多尺度的频繁模型，它利用了DFS搜索思想，对数据进行扫描，以达到在不同的尺度上挖掘的目的8，Cao等在2005年通过对串树结构和Apriori方法进行改进把序列变成子序列的方法来挖掘多尺度频繁模式9。Gianoti等在2007年考虑了空间尺度信息，使用一种新颖的轨迹模式来描述同样时间和位置的频繁行为，提出了能够发现兴趣空间域的轨迹挖掘方法1
15、0。Le等在2009年扫描多尺度数据，并生成映像图和轨道信息表，并在此图上进行DFS搜索来完成频繁模式挖掘。除了对轨迹进行频繁模式挖掘外，对多尺度事件进行挖掘也是多尺度频繁挖掘的内容11。Tao等人在2004年把空间索引和图论技术结合了起来，缩小了搜索域，查询时间大大降低了，精度也提高了12。只是，这个他们并没有把时空信息纳入研究范围内。Verhein等人于2006年把区域时空信息纳入到研究范围之内，对时空关联规则进行了更进一步完善，基于一个快速解决多尺度的空间支持度和时间模式，进而提出了一种高效挖掘这类模式的算法STAR-Miner13。除了这些多尺度数据挖掘以外，还有其它很多挖掘模式。多尺
16、度数据挖掘除了挖掘时空数据的关联模式以外，还更多地包括时空数据的聚类模式，即多尺度聚类挖掘，这种挖掘模式是将时空对象分面几类，而其依据则是时间相似度的应用，使得不同类簇间的差别尽可能的大，而同一类簇内的差别尽可能的小，以实现不同时空数据在不同尺度上的聚类。这种挖掘模式有着很广泛的应用，比如预测气象、城市交通分析、生态物种迁徙、银行电子诈骗、孤立点检测等。Gafney等在1999年将EM算法和以回归混合模型为基础的概率方法结合起来以决定类的隶属关系14。Chudov等人在2003年，Nani等人在2006年把参数设定为时间信息的轨迹漂移来进行多个尺度的聚类15，16。Nani等人。施培蓓等人于2011年通过在聚类算法是引入控制尺度的参数提出了多尺度的谱聚类算法17。多尺度数据挖掘除完成时空数据的关联模式挖掘、聚类挖掘以外，还有异常检测挖掘、预测挖掘及分类等。但无论对时空数据进行怎样的多尺度数据挖掘，其挖掘模式基本可以归纳为三种途径：1、在挖掘前将单一尺度
