A数据挖掘20

WEB数据挖掘一般现在分为两大类，一类关系知识挖掘，就是发现网络连接的内在模式，一类是内容知识挖掘，内容知识挖掘可以划分为结构型、半结构型以及非结构型挖掘，文本挖掘属于非结构型挖掘。pagerank算法与his算法的区别:算法和算法都是基于链接分析的搜索引擎排序算法，并且在算法中两者都利用了特征向量作为理论基础和收敛性依据。虽然两种算法均为链接分析算法，但两者之间还是有明显的区别的。HIS算法计算的值只是相对于某个检索主题的权重，因此算法也常被称为XX算法；而pagerank算法是独立于检索主题，因此也常被称为XX算法。内容挖掘与使用挖掘的区别:前者是指对Web页面的内容进行挖掘，后者指对用户访问Web时留下的访问记录进行挖掘（如：访问日志）。话题探测与话题追踪的区别:话题检测与跟踪（TopicDetectionandTracking）是近年提出的一项信息处理技术，其中检测与追踪是这项技术对信息处理的不同过程，具体来说是两者是继起关系，即：先探测出敏感话题继而对话题进行追踪。1.中文网页分类的工作原理。在分类的时候首先会遇到文档形式化表示的问题，文档模型有3种：向量空间模型，布尔模型和概率模型，其中我们常用的是向量空间模型。向量空间模型的核心描述如下：文档（Document）：文本或文本中的片断（句子或段落）。特征项（Term）：文档内容用它所包含的基本语言单位来表示，基本语言单位包括字、词、词组、短语、句子、段落等，统称为特征项。特征项权重（TermWeight）：不同的特征项对于文档D的重要程度不同，用特征项Tk附加权重Wk来进行量化，文档D可表示为（T1，W1；T2，W2；…；Tn，Wn）向量空间模型（VectorSpaceModel）：对文档进行简化表示，在忽略特征项之间的相关信息后，一个文本就可以用一个特征向量来表示，也就是特征项空间中的一个点；而一个文本集可以表示成一个矩阵，也就是特征项空间中的一些点的集合。相似度（Similarity）：相似度Sim（D1，D2）用于度量两个文档D1和D2之间的内容相关程度。当文档被表示为文档空间的向量，就可以利用欧氏距离、内积距离或余弦距离等向量之间的距离计算公式来表示文档间的相似度。其中特征选取是文本表示的关键，方法包括：文档频率法（DF）、信息增益法和互信息法等等。在做特征选取之前，一般还要进行预处理的工作，要对先对网页降噪。另外在实际的分类中，除了利用文档的内容特征之外，可能还会用到实际应用中所特有的特征，比如在网页分类中，可能用到url的特征、html的结构特征和标签特征等信息。分类的基本步骤是这样的：定义分类体系，将预先分类过的文档作为训练集，从训练集中得出分类模型，然后用训练获得出的分类模型对其它文档加以分类。2.互联网搜索引擎的的工作原理。搜索引擎的基本工作原理包括如下三个过程：首先在互联网中发现、搜集网页信息；同时对信息进行提取和组织建立索引库；再由检索器根据用户输入的查询关键字，在索引库中快速检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并将查询结果返回给用户。1、抓取网页。每个独立的搜索引擎都有自己的网页抓取程序（spider）。Spider顺着网页中的超链接，连续地抓取网页。被抓取的网页被称之为网页快照。由于互联网中超链接的应用很普遍，理论上，从一定范围的网页出发，就能搜集到绝大多数的网页。2、处理网页。搜索引擎抓到网页后，还要做大量的预处理工作，才能提供检索服务。其中，最重要的就是提取关键词，建立索引库和索引。其他还包括去除重复网页、分词（中文）、判断网页类型、分析超链接、计算网页的重要度/丰富度等。3、提供检索服务。用户输入关键词进行检索，搜索引擎从索引数据库中找到匹配该关键词的网页；为了用户便于判断，除了网页标题和URL外，还会提供一段来自网页的摘要以及其他信息。聚类算法用于根据数据的特征发现数据项的相似性，并将相似的数据项放在同一个组中，相似性采用距离进行描述。K-means聚类简单的说，一般流程如下：先随机选取k个点，将每个点分配给它们，得到最初的k个分类；在每个分类中计算均值，将点重新分配，划归到最近的中心点；重复上述步骤直到点的划归不再改变。下图是K-means方法的示意。K-Means算法的SAS实现K-means算法可以用SAS的procfastclus实现。主要涉及两个问题。首先是初始点的选择。如果指定replace=random，则系统随机选取maxcluster选项指定个数的完整观测作为凝聚点。如果分析员对研究情景比较了解，可以利用专业知识指定初始分类，那么可以在procfastclus中设定seed=dataset选项，SAS会从dataset中读取前k个观测作为初始凝聚点。此外，SAS还提供了系统自动选择初始凝聚点的方法，该方法需要指定maxclusters和radius选项，其中radius为凝聚点之间允许的最小距离。默认值是maxclusters=100，radius=0，效果是选取数据集中的前100个观测作为凝聚点。fastclus过程总是选择第一个完整观测作为第一个凝聚点，然后依次考察剩余观测，与第一个凝聚点的距离大于radius指定值的观测作为第二个凝聚点。当凝聚点的个数未达到maxcluster，且所考察观测与已有凝聚点间距离均大于radius指定值时，则所考察的观测成为下一个凝聚点。如果一个观测完整且与所有凝聚点距离均大于radius，但凝聚点个数已经达到最大值，此时fastclus过程进行两种替换检验，检验能否用当前观测替换已有凝聚点。第一个检验是替换距离最近两凝聚点检验，如果凝聚点与当前观测的最小距离大于已有凝聚点的最小距离，则一个已有凝聚点将被替换，当前观测将替换距离最近的两个凝聚点中的一个，使得替换后当前观测与最近距离两凝聚点中未被替换的那个距离最远。第二个检验是替换当前观测最近凝聚点检验，如果当前观测到除最近凝聚点外的所有凝聚点的最小距离大于当前观测最近凝聚点到所有其他凝聚点的最小距离，进行替换。如果两种检验都说明该观测不能替换已有凝聚点，则转向下一个观测，直到考察完数据集中的所有观测。当然，这种检测可以用replace=none|part|full来控制，none表示不进行替换检验，part表示只进行第一种替换检验；full为默认值，两种替换检验都进行。另一个问题是分类的修改方法。默认的方法是按批修改法，即选定一批凝聚点后；将所有观测按与其距离最近的凝聚点归类；计算每一类重心，将重心作为新的凝聚点，若新凝聚点与旧凝聚点完全重合，则终止算法，否则重新归类。批量修改法是全部观测调整完毕后，才改变类的凝聚点，而逐个修改法是每个观测一旦调整后立即改变类凝聚点，而立即改变需要算法即时验证改变后的凝聚点集合是否仍然满足radius的约束。如果不满足radius的约束，SAS会将小于radius的两类合并，计算重心，作为合并后类的凝聚点，如此往复，直到凝聚点满足radius条件。要让SAS执行逐个修改法，需要声明drift选项。补充:K-means聚类算法的问题是，均值的计算受异常点的干扰比较严重。为了克服这个问题，可以采用K中值法。K-medoid聚类:PAM（PartitionAroundMedoids）是K-medoid的基础算法，基本流程如下：首先随机选择k个对象作为中心，把每个对象分配给离它最近的中心。然后随机地选择一个非中心对象替换中心对象，计算分配后的距离改进量。聚类的过程就是不断迭代，进行中心对象和非中心对象的反复替换过程，直到目标函数不再有改进为止。非中心点和中心点替换的具体类别如下图分析（用h替换i相对j的开销）。PAM算法的问题在于伸缩性不好，需要测试所有的替换，只适用于小数据量的聚类。为了提高该算法的可伸缩性，有人提出了CLARAN算法，本质如下：从总体数据中生成多个样本数据，在每个样本数据上应用PAM算法得到一组K中值点；取出所有样本中结果最好的那一组作为最后的解。CLARAN算法存在的问题是，算法的聚类质量依赖于样本的质量。为了提高PAM和CLARAN算法的聚类质量，有人在CLARAN算法的基础上提出了CLARANS算法。与CLARAN相比，最大的区别在于没有一个时刻算法局限于固定的一个样本中，自始自终，算法的样本数据都是随机抽样的。其算法过程如下。将每套k个中值点作为一个节点，若两个节点之间有k-1个点相同，则成为邻居。用户事先指定两个数，一是最大的邻居数，二是最大的局部最优点数。算法随机选取一个当前点，随机地取出其中的一个邻居，看目标值是否有改进，如果有改进，则用邻居替代当前点，重新开始搜索邻居的过程；若抽取了最大邻居数的邻居，发现当前点最优，那么就找到了一个局部最优点。找到一个局部最优点后，再随机抽取一个当前点，进行上面的过程，直到找到了用户指定最大数量的局部最优点。比较每个局部最优点的目标值，取最优的那个点作为结果，即可得到k个中值点，于是k个类就可以轻松得到。CLARANS算法的效果不错，但算法复杂度更高。数据挖掘十大经典算法：朴素贝叶斯贝叶斯分类的基础是贝叶斯公式，如下图。P（H|X）是根据X参数值判断其属于类别H的概率，称为后验概率。P（H)是直接判断某个样本属于H的概率，称为先验概率。P（X|H)是在类别H中观测到X的概率，P(X)是在数据库中观测到X的概率。朴素贝叶斯分类器由于P（X)对于任何一个类别H而言，其值都是固定的，因此在计算P（H|X)时不需要考虑。朴素贝叶斯分类的最核心的假设是X向量中的每一个参数xi与xj之间都是相互独立的，因此有下面计算P(X|H)的公式：在这个假设下，朴素贝叶斯分类器变成了简单的概率计算。基于训练集的数据，事先计算出每个类别的概率P（Ci），再计算出每个类别下每个参数的概率P（xi|Ci）。当面临一个新样本时，利用上面简化的贝叶斯公式计算出P(Ci|X),值最大的Ci记为分类结果。为了防止出现零概率现象，可以在保存的每个概率的分子分母都+1.朴素贝叶斯分类器的算例如下图所示。贝叶斯网络贝叶斯网络能够克服朴素贝叶斯分类器参数相互独立的假设，如果参数A依赖于参数B，则建立B-A的一条有向边。贝叶斯网络与朴素贝叶斯分类器的异同如下图所示。可以看到在计算类别概率P（c）时，二者一致；只是在计算P(click|c）时，朴素贝叶斯分类器只与类别c有关，而贝叶斯网络还依赖于html的值。由于参数之间存在依赖关系，因此在计算训练集的概率之前，需要先建立贝叶斯网络。一种生成贝叶斯网络的方法如下图所示，其中MI（X,Y）表示的是参数X和参数Y之间的相关关系，当独立时，MI为0；MI大于0，表示正相关；MI小于0，表示负相关。数据挖掘十大经典算法：C4.5算法C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法.C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：1)用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；2)在树构造过程中进行剪枝；3)能够完成对连续属性的离散化处理；4)能够对不完整数据进行处理。C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。分类算法的目的是根据其他参数的取值预测类别参数的取值，希望这种预测尽可能准确。分类算法的总体框架可以分为两步：第一步是基于训练集构建分类模型，第二步是用测试集检测分类模型的准确度，若可接受，即可用于预测新数据的类别。决策树分类算法的一般流程如下：一开始，所有的实例均位于根节点，所有参数的取值均离散化；根据启发规则选择一个参数，根据参数取值的不同对实例集进行分割；对分割后得到的节点进行同样的启发式参数选择分割过程，如此往复，直到(a)分割得到的实例集合属于同一类；(b)参数用完，以子集中绝大多数的实例类别作为该叶节点的类别。核心问题：参数选择规则在每一个节点进行参数选择时，由于有众多的选项，需要一个选择规则。