基于特征转移概率的网络日志聚类分析算法

齐 文，朱曦源，宋 杰

1(辽东学院 工程技术学院，辽宁 丹东 118001) 2(东北大学 软件学院，沈阳 110819)

1 引 言

随着信息化建设，互联网行业的发展，各种信息设备在运行和通信中，会产生大量的网络日志数据.日志数据的来源很多，如网络、文件和计算服务器，网络日志数据对于商业规则、统计分析、网络广告、推荐系统等都很有用[1].因此，能够合理处理并分析体量庞大的网络日志数据是有实际意义的.

当前的研究提出了许多使用Hadoop[2]和MapReduce的网络日志分析聚类优化算法[3].然而这种使用MapReduce的网络日志处理方法都存在计算速度慢，磁盘I/O开销大，尤其在实时处理在线式的网络日志数据方面性能较低.也有研究提出了使用Spark的聚类处理方法[4]，但是这些方法，而既不提供数据分析，也不提供对RDD内容的查询机制.这种缺乏对捕获、存储和查询出处的支持，是在数据处理过程中和之后充分利用详细分析的瓶颈.以及存在诸如没有去除冗余数据，以及没有考虑以最小的空间要求实现高精度的预处理的问题，以及输出不适合对数据的进一步处理，比如聚类或是分类等.针对上述问题，网络日志的聚类算法可以进一步改进.

本文提出了一种网络日志处理方法，实现了高精度的预处理以及实现了数据的高效进一步聚类处理.该方法以提高聚类性能为目标，以最少的时间处理和分析网络日志，并能获得较高的准确率和灵敏度.本文提出的特征转移概率是指特征向量向一特定聚类中心转移的概率，基于此，分布式并行处理方法能够分析完整的网络日志数据集并提取有用的信息，在集群上进行并行处理完成聚类算法.

本文提出的基于特征转移概率的聚类方法首先要对网络日志数据集进行数据预处理，生成特征向量再用分布式优化的K-means聚类方法基于特征转移概率进行聚类，为了获得更好的并行效率和速度，本文采用了Apache Spark[5]以及弹性分布式数据集.实验与其他优化的聚类算法进行比较，本文分布式改进的网络日志处理技术实际实验中选择的特征能够在高准度下提高聚类速度，保持了与现有的聚类方法接近的收敛灵敏度和准确度，并将执行时间降低到了75.97%.

本文第2节介绍了一些关于聚类算法的预备知识.第3节介绍了预处理的方法，并进行了举例演示.第4节介绍了特征转移概率与相关的公式以及本文提出的基于特征转移概率的算法实现.第5节介绍了实验，实验测试在不同约束条件如聚类精度和数据量规模下进行.

2 预备知识

数据聚类的目的是确定数据值的分组或发现数据中的模式.聚类算法根据一些相似性度量将n个对象分成k个组.相似性度量可以从维度或模式集合生成.一个理想的集群将n个数据的一部分放入一个与其他组隔离的紧凑组中.聚类通常被认为是一项无监督的任务，因为没有提供具有特定标签的训练.聚类过程包括4个步骤:特征提取、模式接近度确定(即建立对之间的距离值)、聚类(即分组)和抽象(例如，从聚类中选择一个小的子样本统计表示完整的数据集).

K-means聚类算法[6]是最经典的聚类算法之一，该算法以距离作为评价的相似度指数，即两个对象之间的距离越近，相似度越大.对于给定的样本集，计算任意两个样本之间的距离，根据样本之间的距离将样本集划分为k个聚类，它实现起来比较简单，可以扩展到大型数据集，并且保证收敛性.实现的算法如算法1所示.

算法1.K-means聚类算法

步骤1.随机选择k个集群中心点.

步骤2.聚类分配.在这一步，将数据集中的每个数据点分配给一个中心点，选择与数据点最接近的中心点.

步骤3.中心点移动.对于每个中心点，计算分配给每个中心点的所有数据点的平均值.这个计算出来的平均值就是这个特定中心点的新值.

步骤4.计算每个中心点从之前的值中移动的距离平方的总和，重复步骤2和3，直到这个值不小于或等于阈值(通常是0.01)或迭代次数达到指定的最大迭代次数.

然而，传统的串行K-means聚类算法还是难以高效、准确地对海量运行状态监测进行聚类分析.接下来本文将讨论这个算法在不同平台上的实现细节，以深入了解这种迭代算法如何被修改以适应不同的数据集.

2.1 在MapReduce上的K-means分析

MapReduce的工作原理是将处理过程分成两个阶段:map阶段和reduce阶段.每个阶段都有键值对作为输入和输出.输入的网络日志文件通常驻留在Hadoop分布式文件系统(HDFS)中，Hadoop会提供一个包含要读取的文件的路径，读取这个目录中的所有网络日志.然后，它将这些网络日志分成一个或多个块.一个MapReduce作业无非是一个应用于数据集的程序，由若干个任务组成的.在完成第一个map任务后，各节点仍然各自再执行几个map任务.但是他们也开始将一个map任务的中间输出交换到另一个reducers需要的地方，shuffling是将数据从mappers转移到reducers的过程，从而使得reducers获得输入，不同子集分区的键空间被分配给每个reduce节点;这些子集分区是reduce任务的输入.它决定了映射阶段输出的一个键值对，将被送到哪个reducer中去.partitioner类可以找到一个给定的键值对将被送到哪个分区.默认的partitioner会对键的哈希值进行操作，并根据这个结果分配分区.单个节点上的中间键集合在交付给Reducer之前，会被Hadoop自动排序.当排序后的输入数据中的下一个键与前一个键不同时，它就会启动新的reduce任务.Hadoop框架对排序顺序中的每一个唯一的键都会调用一次Reduce().Reduce可以遍历与该键相关的值，并产生零个或多个输出值.输出值需要与输入值的类型相同，输入键也不需要改变.通过调用到方法OutputCollector.collect(Object，Object)来收集输出对.Reducer还接收OutputCollector和Reporter对象作为参数，其使用方式与map()方法相同.RecordWriter将mapreduce作业的输出键值对写入一个输出文件.RecordWriter实现将作业输出写到HDFS中.然后，Reducers写入的输出文件存在HDFS中.MapReduce的网络日志处理方法结束.这里Hadoop的特点是把计算移到数据上，而不是把数据移到计算上，数据以块的方式存储在集群中的多个节点上，从而相对于传统的串行处理方法，这种基于Hadoop和MapReduce的分布式并行处理方法，取得了不错的效果，并且成功地处理了大规模网络日志数据集.

对于K-means聚类等迭代算法，MapReduce并不是一个理想的选择.基本上，映射器从磁盘上读取数据和中心点.磁盘上的数据和中心点.然后这些映射器将数据实例分配给集群.一旦每个映射器完成了他们的操作，还原器通过计算每个簇中存在的数据点的平均数来计算新的中心点.每个集群中存在的数据点的平均值.现在，这些新的中心点被写入到磁盘上.然后，这些中心点由映射器在下一次迭代中读取，整个过程不断重复，直到算法结束.整个过程不断重复，直到算法收敛.算法2给出了在MapReduce上的K-means的伪代码.算法3和算法4给出了K-means聚类的映射器和化简器函数的伪代码.

算法2.在MapReduce上的K-means

输入:数据点D，聚类数k.

步骤1.随机初始化k个聚类中心.

步骤2.将D中的每个数据点与最近的聚类中心联系起来，把数据点分成k个集群.

步骤3.重新计算聚类中心的位置.重复第2步和第3步，直到数据点的成员资格不再有变化.

输出:是集群成员的数据点.

算法3.Map映射器.

输入:数据点D，聚类数k和聚类中心.

步骤1.对于每个数据点d∈D.

步骤2.将d分配给最接近的聚类中心.

输出:带有相关数据点的聚类中心.

算法4.Reduce化简器.

输入:带有相关数据点的聚类中心.

步骤1.计算集群中数据点的平均值计算新的聚类中心.

步骤2.将全局中心写到磁盘上.

输出:新的聚类中心.

2.2 在Spark上的K-means分析

与基于Map-Reduce的Hadoop模型相比，Apache Spark具有很多优势.Spark提供的内存计算在大规模分析中非常有用.内存计算主要有两个优势.第一，由于数据存储在内存中，所以迭代作业不需要重复的磁盘访问.第二，交互式作业不需要每次查询都访问磁盘，相反，Spark可以用来将数据库存储在内存中并频繁查询.

由于日志数据是非结构化的，本文从每一行中解析并创建一个结构，在分析时，这个结构又会成为每一行.之后创建Spark Context、SQL Context、DataFrame.然后，Spark可以从文本文件中加载数据作为RDD，然后它可以处理这些数据.给定一个日志行的RDD，使用map函数将每一行转化为Apache Access Log对象.Apache Access Log RDD会被缓存在内存中，因为会对其进行多次转换和操作.通过映射变换提取出内容大小，然后调用不同的操作(reduce、count、min和max)来输出各种统计数据.

Spark上的K-means实现与在MapReduce上的K-means实现类似.节中描述的基于MapReduce的K-means.全局中心点不是写在磁盘上，而是写在内存中.这样可以加快处理速度并减少 磁盘I/O的开销.此外，数据将被加载到系统内存中，以提供更快的访问.以便提供更快的访问.CPU上的K-均值聚类涉及多线程每个线程将一个数据向量与一个中心点联系起来，最后中心点被重新计算，用于下一次迭代.最后为下一次迭代重新计算.

Spark允许本文对大量的输入数据进行流处理.由于Spark基于内存计算的良好性能，降低了时间要求，并保证了一定的准确度.

由于Spark对于迭代计算的性能良好，故本文选择Spark的K-means为基础进行优化，提出了基于特征转移概率的K-means聚类算法.具体实现在下节开始讨论.

3 预处理与聚类特征

一些公开的网络服务器日志数据集，如Calgary-HTTP，ClarkNet-HTTP，NASA-HTTP和 Saskatchewan-HTTP的数据集都是优质的数据集.本文通过这些数据集来熟悉处理Web服务器日志.由于这些网络日志数据具有非结构化数据的特点，含有大量的噪声数据，必须消除这些不相关的数据，所以需要对网络日志进行预处理.表1描述了一个样本的entry headers.

表1 对网络日志条目头的简要描述Table 1 Brief description of the weblog entry headers

预处理使用了整个网络日志数据集的解析技术[7].在本次实验，首先将网络日志数据按照以下方式进行拆分到其属性.特征选择作为一个预处理步骤，需要通过消除冗余和不相关的特征，只选取信息丰富和简洁的特征来增强分类过程.在应用这一原则后，分类过程中由于过度拟合而导致的问题就被消除了.为了加强这一任务，通常采用特征选择算法来选择信息量最大的属性，从而减少特征空间.

对于较大的数据集，有多种技术可以确保计算、存储和数据工作流程得到优化，并且可以实现潜在的更大规模建模的可扩展性.这些计算扩展技术如MapReduce，它将数据分割为单元进行并行处理.然后，被处理的单元被重新映射回更大的数据集，以便进一步分析或处理.Apache Hadoop计算平台旨在通过提供包括大量存储、分布式文件系统和先进的处理能力在内的高性能计算环境来利用MapReduce的概念.Spark是一个开源的HPC框架的实现，在需要进行大数据分析时，对R、Python和Java的使用进行了优化.Spark使用更复杂的分布式聚类模型，数据被一次性加载到内存中，可以对其进行大量操作.当Spark应用程序提交时，在主节点上创建SparkContext对象，从HDFS读取数据以创建RDD对象.它从HDFS读取数据以创建RDD对象，并向集群资源管理器请求资源 向集群资源管理器请求资源.集群资源管理器将资源分配给每个工作节点的一个或多个执行器进程.每个工作节点有一个或多个执行器进程，每个工作节点向集群资源管理器报告资源使用和任务运行状态.每个工作节点使用心跳机制来向集群资源管理器报告资源使用情况和任务运行状态.SparkContext对象根据多个RDD之间的依赖关系构建一个有向无环图(DAG)，并将该DAG提交给DAG调度器以确定多个RDD之间的依赖关系.

提交给DAG调度器 DAG调度器将DAG解析为多个任务集，提交给任务调度器.任务调度器将任务分配给执行进程，当一个执行进程收到一个任务时，会从执行进程的线程池中抽取一个线程来执行该任务.

3.1 预处理方法

在这个实验中，本文使用了弹性分布式数据集和Spark，用于运行和操作在多个节点在一个集群上做并行处理并有效地获得所需信息.Spark不仅支持映射和还原操作，还提供了过滤、按键还原、按键分组等操作.Spark提供了弹性分布式数据集(RDD)的抽象，它提供了一个只读的对象集合，在一组机器上进行分区.RDD通过线程实现容错.每当RDD的任何一个分区丢失时，RDD都有足够的信息来重建丢失的分区.

首先加载数据集，将文件的每一行转换成 RDD 中的元素.接下来，本文使用map将解析函数应用于RDD中的日志文件中每个元素.然后要进行数据清理，验证一下原始数据集中是否有空行.分割样本，生成m条数据，再创建一个RDD，包含n个分区，每个RDD分区包含m/n个数据.对于第s个RDD分区，每l个数据被划分到一个样本，完成样本划分后，将得到m/l个新样本RDD.对于样本RDD的第s个RDD分区，其中每条数据都将按max-min算法[8]进行归一化.样本中包含的一条数据，从某条属性来考虑.max代表数据的最大值，min代表最小值.

在所有样本被归一化后，得到一个新的RDD，并在此基础上操作进行样本分解形成特征向量.每个特征向量可以由不同的属性构建.最后，在对所有样本进行分解后，得到m/l个特征向量.

3.2 预处理举例

本文使用了NASA-HTTP数据集来进行一个演示，预处理算法提取了不同的结果，如主机、请求路径、请求内容的字节数等.在本文第4节的实验中以NASA-HTTP为例，表2显示了一个包含部分属性的预处理网络日志样本.对于解析日志文件中host这一元素.如果想要提取排行前10的host.首先，本文使用lambda函数中的和map函数如txt_.map(lambdax:(x，x.split(′1′))).filter(lambday:y[0].startswith(′host′))从RDD中提取主机字段，创建一个新的RDD，使用由主机和1组成的元组，让本文计算特定主机的请求创建了多少记录.使用新的RDD，本文用Lambda函数执行一个reduce函数，将两个值相加.然后，本文根据每个主机的访问次数(每对主机的第2个元素)大于10来过滤结果.

表2 数据集预处理之后的部分结果Table 2 Partial results of the dataset after pre-processing

在Spark环境下，预处理的步骤可简述为:输入网络日志数据集，对数据集中所需的属性应用上文的解析技术，设置数据集的正则表达式，应用并检查日志解析的输出，如果解析成功，则将内容存储起来，否则，应用新的解析规则，添加新旧两个规则，用于解析日志.将不同的正则表达式进行分组，解析日志，输出主机、HTTP请求和响应的数量以及数据的特征.

为了举例，这里做了一个可视化展示，本文从产生的RDD中提取10个元素，输出结果(来自170455条网络日志记录的主机数量)如图1所示.

图1 预处理输出的前10主机展示Fig.1 Preprocessed output of the top 10 hosts

4 基于特征转移概率的聚类算法

基于Spark的K-means算法需要一个用户定义的参数.这也是大多数聚类方法的情况.一个缺点是难以确定最佳的聚类数量.有多种技术可以做出这种决定，其中大多数是基于找到k的值，以平衡最小化集群内距离和最大化集群间距离的搜索.然而，对于 "最佳 "技术并没有达成共识.k的选择也可能经常依赖于研究人员的专家意见，以及对不同位置误差和空间分布误差的拟合度的解释.在本文中聚类的数量是通过最大化平均轮廓系数来确定的，而不是试错的学习方法.轮廓系数是一个簇中所有点之间的平均距离，与一个点与它与最近簇的距离之间的平均距离之比.K-means算法随机选择k个观测值作为群组的中心，然后计算每个观测值与所有群组中心之间在特征空间中的欧几里得距离.接下来，它根据欧氏距离最近的聚类中心给每个观测值分配一个组，即k.中心被反复更新，直到达到一定数量的群组，所有的观测值被分配到一个独特的群组.由于K-means由于计算量过大而无法处理大型数据集，本文采用了基于Spark的K-means-标准K-means算法的高级版本，以减少计算负担.基于Spark的K-means对所有数据对的距离进行并行计算，同时需要一个通过平均轮廓系数确定的参数k，将数据分成k个聚类.这种方法适合于探索无法存储在计算机存储器中的大规模数据集.与基本的K-means算法相比，基于Spark的K-means的计算速度更快.

本文提出的基于特征转移概率的Spark-K-means聚类算法，可以充分利用集群的计算资源，高效并行处理大规模网络日志数据.对于特征转移概率及其算法的实现步骤在4.1和4.2中介绍.

4.1 特征转移概率

特征转移概率的概念如定义1所示，通过计算特征转移概率，可以得到最大过渡概率，进行比较可以得到每个特征向量及其接入点的键值对，确定其每次的聚类中心.

定义1.特征转移概率(Feature Transition Probability).特征转移概率Pik表示样本i到第k个聚类中心的转移概率，由公式(1)进行计算.

(1)

(2)

(3)

(4)

(5)

以上是本文算法用到的公式.其中M={μ1，μ2，…，μk}是所有聚类中心的集合.其中εik=1/εik，其中εik代表i点和k点之间的欧几里得距离，参数σik(n)可由公式(2)来迭代计算，表示发生第i个点转移到第n次聚类中心的欧几里得距离.α和β是可变参数.

4.2 聚类算法实现步骤

聚类算法实现如图2所示，具体步骤见步骤1～步骤8.

图2 聚类算法实现流程Fig.2 Clustering algorithm implementation process

步骤1.读取预处理后的数据，提取为m个特征向量.创建RDD.创建一个包含n个分区的RDD特征向量RDD，每个RDD分区包含m/n个特征向量，每个工作节点将处理多个RDD分区.

步骤2.随机选取初始聚类中心.计算所有点之间的平均距离即轮廓系数，通过计算最大化平均轮廓系数来确定聚类数量.从特征向量RDD中随机选取k个特征向量作为初始聚类中心M={μ1，μ2，…，μk}，由主节点向各工作节点广播.

步骤5.判断初始聚类中心是否已经收敛.计算路径RDD的第s个RDD分区的所有特征向量与其对应的初始聚类中心之间的均方误差MSE，然后将每个RDD分区得到的均方误差从每个工作节点收集到主节点，则总均方误差可由公式(5)来计算，判断MSE是否小于或等于收敛阈值，如果是，则输出全局最优初始聚类中心，否则返回步骤3.

步骤6.将每个特征向量并行划分到最近的聚类中.计算出每个特征向量与每个聚类中心之间的欧氏距离，并将每个特征向量分类到最近的聚类中，将一个特征向量及其对应的最近聚类的中心点分别视为值和键，得到键值对RDD集群RDD.

步骤7.并行更新聚类中心.对于第s个RDD分区{<μ∀j∈[1，k]，E(s-1)m/n+1>，<μ∀j∈[1，k]，E(s-1)m/n+2>，…，<μ∀j∈[1，k]，Es*m/n>}的簇RDD，重新计算第s个RDD分区的k个簇的中心点，{μs1，μs2，…，μsk}，从工作节点到主节点收集簇RDD分区的k个簇的中心点，以公式(4)确定的μj作为第j个新的聚类中心，从主节点向每个工作节点广播k个更新的聚类中心.

步骤8.判断聚类中心是否已经收敛或达到最大迭代次数.计算集群RDD的第s个RDD分区的所有特征向量与其对应的聚类中心之间的均方误差MSE.其次，将每个RDD分区得到的均方误差从每个工作节点收集到主节点，通过公式(5)计算总均方误差.判断MSE是否小于或等于收敛阈值或已达到最大迭代次数，如果是则输出网络日志的分析模型.如果不是则返回步骤6.

得到训练良好的网络日志分析模型后，就可以对数据进行分析.如图2所示，首先，将待诊断的数据进行基于Spark的分解预处理，得到特征向量，存储在HDFS[9]中.然后从HDFS中读取所有特征向量，创建RDD.通过并行计算RDD的每个特征向量与日志分析模型提供的每个聚类中心之间的加权欧氏距离.最后，将每个特征向量分类到最近的聚类中心，并输出分析结果.

5 实验分析

5.1 实验准备

本次实验使用的是NASA-HTTP网络服务器日志.包含IP地址、用户名.时间戳、访问请求、状态码、字节数等.在应用所提出的算法之前必须对网络日志数据进行预处理.表2显示了一个包含部分属性的预处理网络日志样本.

所有的实验都是在PC上使用Apache Spark 3.1.2进行的，该集群由1个主节点和8个工作节点组成，其集群资源管理器为Spark自带的独立集群管理器.节点配置信息在表3列出.大小为512 GB的硬盘和Linux Ubuntu16.04操作系统.所提出的算法采用Python和Spark应用编程接口(API).

表3 节点信息及配置Table 3 Node information and configuration

5.2 实验结果

图3分别绘制了不同工作节点数和不同规模数据集(数据集A数据集B数据集C的规模大小是递增的)下得到的并行计算速度、并行效率和部分属性的聚类时间，从图3可以看出，对于3种不同大小的数据集，随着Spark集群中工作节点数量的增加，并行速度逐渐增加.随着工作节点数的增加，得到的速度逐渐增加，接近线性增长，但并没有达到理论值，因为工作节点数量的增加所带来的通信成本和任务调度成本在一定程度上降低了并行的性能[10].当工作节点数为8时，用数据集A、数据集B、数据C，分别获得了4.86×、5.25×、6.18×的提速，当工作节点数一定时，用更大的数据集进行网络日志处理可以获得更高的提速.当工作节点数固定时，随着数据集的大小变大，所获得的并行效率逐渐提高.因此，较大的数据集更有助于发挥并行计算的优势，并充分利用Spark集群的计算资源.结果表明，随着数据集大小的增加，并行速度和效率都在逐步提高.因此，本文所提出的方法适合处理网络日志这种大规模数据集.在不同规模数据集下，通过使用Apache Spark在这些数据集上执行K-means算法，并对其执行时间与现有的结果对比其他现有使用Spark的K-means算法，有明显的改进.在执行时间上，相对现有的使用Spark的K-means算法[11]，执行时间大约是75.97%.如图4所示.

图3 不同节点数的并行速度(a)和并行效率(b)比较Fig.3 Parallel speed and parallel efficiency with different number of nodes

图4 K-means聚类处理的执行时间Fig.4 Execution time of K-means clustering

对每个数据集，选择最重要的特征来代表候选解决方案集.为测试目的，用约10和100的特征数进行测试.分类器如Naive Bayes(NB)[12]、支持向量机(SVM)[13]和K-NN[14]用于评估数据集.分类器的准确度是通过十倍交叉验证获得的.

如图5～图7所示，本文的聚类方法，在SVM的分类器测试下，灵敏度、特异性、准确率性能很好，其他分类器如NB、K-NN环境下，相比与其他优化的聚类方法也并没有降低.得到很好的聚类效果的同时，提升聚类的速度.

图5 文献[11]与本文聚类的特异性对比Fig.5 Sensitivity comparison between proposed algorithm and [11]

图6 文献[11]与本文聚类的特异性对比Fig.6 Specificity comparison between proposed algorithm and [11]

6 相关工作

目前，已经提出了许多聚类算法来处理各种数据集.这些聚类算法大致可分为4类:分区聚类算法、分层聚类算法、基于网格的聚类和基于密度的聚类.对于处理Web日志这种数据集，较常见的是分层聚类的方法.

文献[15]提出了一种分层聚类的方法，分层地分解给定的数据对象集合.根据层次分解的形成，层次方法可分为自底向上法和自顶向下法.自底向上方法先将每个对象分离为一个组，然后依次合并相似的对象或组，直到所有组合并为一个组，或者直到达到作为终止条件.自顶向下法将所有对象放入一个簇中.在这种类型的聚类中，所有观察值都分配给一个集群，然后将单个集群分为两个集群，并依次为每个集群进行处理，直到每个观察都有一个集群.常用的自底向上法内聚聚类方法有AGNES、BIRCH、ROCK和CURE[16-18]，常用的自顶向下划分方法有DIANA等.层次方法的缺点是缺乏全局最优函数.该技术的另一个主要问题是它不能纠正错误的决定.此外，该算法在时间和空间上具有较高的复杂度，严重限制了要处理的数据集.

文献[11]通过将K-means算法和层次算法相结合，提出了层次K-means 网络日志挖掘聚类算法.K-means 算法的主要缺点是需要预先确定聚类的数量.如果系统在聚类用户时没有意识到这一点，K-means 算法将是不自适应的.K-means算法对噪声数据和边界数据非常敏感，即使少量的噪声或边界数据也会使聚类中心发生较大程度的偏移.并且由于K-means算法对初始聚类中心敏感，必须提前给出聚类次数，这会导致聚类的主观性和随意性，影响正确的聚类结果.而内聚层次聚类算法的优点是通过内聚的方法确定聚类的个数，克服了上述缺点，并降低了一定时间复杂度.

上述工作确实提高了传统 K-means 算法的性能.然而，在面对大规模数据集时，这些算法仍然存在效率低和对噪声点敏感的问题.但仍然存在算法的时间空间复杂度较高的情况，运行速度较慢.本文提出的基于特征转移概率的聚类算法对K-means算法进行了改进.通过最大化平均轮廓系数确定了聚类的个数，避免了试错.在数据处理方面具有快速、稳定和准确的特点.

综上所述，本文提出的基于特征转移概率的方法保持了内聚层次聚类算法的优点，同时对运行速度方面有了一定的改善，同时对并行效率也有一定提升，尤其对于数据规模较大的情况，本文方法的效果更加理想，最佳情况下，执行时间大约是文献[11]中K-means聚类方法的75.97%.

7 结束语

本文提出了一种基于特征转移概率的K-means聚类算法.并对传统的聚类算法进行了分析，本文提出的算法对传统的聚类算法的不足之处各方面进行了弥补，主要在运行速度方面进行了较大改进.通过本文的方法，可以快速地对web服务器的各方面日志进行分析，了解所需要的信息.并行的分布式处理网络日志方法节省了大量的处理时间，提高了性能，在短时间内进行处理海量数据，给出了更高效的结果并在灵敏度、特异性、准确率等方面保持较高水平.对于Web日志挖掘等大量数据处理，本文提出的基于特征转移概率的K-means算法具有较好的优势.