数学建模聚类算法范文1
关键词:序列决策;数据挖掘;模糊聚类;决策树
中图分类号:TP301文献标识码:A文章编号:1009-2374(2009)10-0001-04
数据挖掘的理论应用越来越广泛,商业、制造业、金融业、医药业、电信业等等许多领域都有了成功的应用实例。目前,各高校普遍采用了计算机进行教学管理,储备了各种类型的电子数据,具有了进行数据挖掘的前提条件。故而将数据挖掘理论引入到学生成绩分析中,以此来帮助教师和教学部门制定相应的措施,有利于提高教学质量。
一、序列决策的提出
序列决策是源于《运筹学》中的一个概念,它在统计学中主要是指当进行决策后又产生一些新情况,需要进行新的决策……这样,决策、情况、决策……构成一个序列。描述序列决策的有力工具是决策树,决策树是由决策点、事件点及结果构成的树形图。序列决策的概念主要是运用多种数据挖掘法,多侧面、多角度、多层次地对学生考试成绩的当前和历史数据进行综合评价,分析结果能够传递考试成绩中隐含的信息,使得教学双方能够从中受益。
二、数据采集与预处理
(一)挖掘主题
本研究的挖掘任务为某高校一次C语言程序设计课程的成绩分别为及格和不及格的学生的特征,找出能预测学生取得及格成绩的相关因素,所以挖掘主题可以明确地描述为:分析影响某高校C语言成绩的相关因素及相互关系。
(二)挖掘库的建立
根据挖掘主题的要求,分析学生取得优秀和及格的相关因素,根据该校教务管理系统得供的学生基本情况库、课程库、学生成绩库等,我们选取其中与挖掘主题有关的属性组成成绩挖掘库,见表1。
(三)数据预处理
数据预处理的主要工作是:数据清理、数据转换和归约。因为现实世界中的数据多半是不完整的、有噪声的和不一致的,为了提高分类和预测的准确性、有效性和可伸缩性、必须对数据进行预处理。具体操作为填充某些空缺的字段值,消除多个数据表中的不一致,构造一些字段以便概化,对某些数据型字段进行离散化的归约工作等。
三、聚类模型的建立
聚类就是将一组数据对象划分成多个类或簇,在同一个簇中的对象之间具有较高的相似度,而在不同簇中的对象差别较大。聚类要划分的类是未知的。
(一)模糊集
一般的基于规则的分类系统有一个缺点:对于连续属性,它们有陡峭的截断。例如,考虑关于顾客信用卡的审批规则。该规则本质上可以描述成:
IF(year_employed>=2)AND (income>=50000)THEN credit=approved
如果,一个至少工作两年的顾客的收入超过50000美元,他将得到信用卡,如果他的收入是49000则他就得不到。这种苛刻的阈值看来不公平。换一种方式,我们可以将income离散化成分类的,如{low_income,medium_income,high_income},然后使用模糊逻辑,允许对每个类定义“模糊”阈值或边界。模糊逻辑使用0.0～1.0之间的真值表示一个特定的值是一个类成员的隶属程度,而不是用类之间的精确截断。每个类表示一个模糊集。因而,使用模糊逻辑,可以表达这样的概念:在某种程度上,49000美元的收入是高的,尽管没有50000美元的收入高。模糊集理论允许我们处理模糊或不精确的事实。例如,高收入集的成员是不精确的,不像传统的“明确的”集合,元素或者属于集合S或者属于它的补,在模糊集合论中,元素可以属于多个模糊集。例如,收入值49000美元属于模糊集medium和high,但具有不同的隶属度。
(二)模糊聚类
对带有模糊特征的事物进行聚类分析,显然应该采用模糊数学的方法,因此称其为模糊聚类分析法。在很多模糊聚类算法中,受到普遍欢迎的是基于目标函数的模糊聚类方法,也就是说,把聚类归结成一个带约束的非线性规划问题,通过优化求解获得数据集的模糊划分和聚类。该方法设计简单,解决问题的范围广,还可以转化为优化问题而借助经典数学的非线性规划理论求解,并易于在计算机上实现。在基于目标函数的聚类算法中,模糊―C均值(FCM)算法的理论最为完善、应用最为广泛。模糊聚类的目标函数为:
(1)
式中为模糊分类矩阵, ,V= ,表示第i类的聚类中心(i=1,2,……,c)是用来决定聚类结果模糊度的权重指数。当m=1,该聚类变成了硬划分;在实际应用中,从物理解释上得出m=2最有意义;Pal等人则从聚类有效性的实验研究中得到m的最佳选取区间应为 [1.25,2.5], 在不作特殊要求下可取区间中值m=2。J(U,V)表示各类中样本到聚类中心的加权距离平方和,权重是样本xk到对第i类隶属度的m次方。式中
(2)
矩阵A为对称阵,一般取A=I,则dik为欧式距离。
根据聚类准则求J(U,V)的最小值:min{J(U,V)},因此
(3)
利用拉格朗日乘数法求解后进行优化可得:
(4)
(5)
(6)
其中
模糊C均值聚类算法的步骤:
1.确定类数k。
2.给出初始聚类中心。
3.利用公式4计算新的隶属矩阵,注意公式4的分母为0,则规定若。
4.利用公式6求各类的聚类中心。
5.如果两次迭代之间的聚类中心距离小设定值,则停止,否则转3。
对入学成绩和录取分数线两个属性进行模糊聚类得到基础程度属性的值,根据挖掘目标,要将基础程度分为高、中、低三类,用1、2、3来表示类别,即k=3;为简便起见,取m=2,现以某次考试C语言的成绩为数据集合进行模糊聚类,参加该课程考试的总人数为137人,用模糊C均值算法对入学成绩和录取分数线两个属性进行分组的结果见表1:
表1 对基础程度模糊聚类的训练结果
上表统计结果见表2:
表2 基础程度、实验学时及成绩属性离散化的结果
在对入学成绩进行聚类过程中,可以看出每两个相邻类中都有部分数据交叠现象,也就是一个数据可能不只属于一个固定的类,根据其属于不同类别的隶属度大小,选取隶属度最大的类作为其分类结果。通过建立聚类模型,对影响等级考试成绩的因素进行概化和归约,将成绩挖掘库中的数值型数据进行离散化,为我们进一步作分类预测奠定了基础。
四、分类模型
分类要解决的问题是为一个事件或对象归类。分类与聚类不同,分类是在已知类标记的情况下对数据集合进行分类描述,理想情况是找到准确的分类规则。而聚类是在没有先验知识的情况下对数据集合进行划分,我们在上面已经用聚类划分了数值区间,下面用决策树技术根据这些离散化的字段建立分类模型。
用于挖掘的学生成绩表中的属性很多,选择其中与成绩属性相关性较大的是否重修、实验学时、基础程度、性别四个属性作为建立成绩分类决策树模型的依据。建立成绩是否不及格决策树模型时,以是否不及格属性作为分类属性。下面以训练集为例来说明成绩是否及格决策树模型的生成。
采用C4.5算法建立决策树模型的步骤如下:
1.对表中的每个测试属性分别计算该属性的信息增益率。
2.选取信息增益比率最大的属性作为根结点,并按其值划分数据集合,如果该属性只有一个值则停止划分。
3.对划分的每个子数据集递归执行(1)～(2)。
具体的实现过程如下介绍:
1.计算分类属性的信息量。在所取的训练集中,共有137个样本。为计算每个属性的信息增益率,首先计算出对给定样本分类所需的信息熵:
2.计算“是否重修”属性的信息量。“是否重修”属性中有两个属性值,需要对每个属性值所划分的子集计算信息量,将样本集中的数据根据该属性进行归纳可得表3:
表3 是否重修属性所划分的子集
3.计算“是否重修”属性的信息熵。
4.计算“是否重修”属性的信息增益量。
5.计算“是否重修”属性的信息增益率。
同理计算基础程度、实验学时、性别属性的信息量、信息熵、信息增益量和信息增益率。
表4 各测试属性所划分的子集及信息增益
从上述计算结果可知,“实验学时”属性具有最高的信息增益率,它被选择为测试属性。创建一个节点,用“实验学时”标记,并根据它的四个属性值,引出四个分枝,样本以此划分,如图1第一层所示。
然后再计算各个分枝节点的划分。以划分“实验学时”是“少”的所有可能性为例,接着进行决策树的建立。根据上面的介绍可知,对于“实验学时”=“少”,类Yes有25个样本,类No有7个样本,分别计算“是否重修”、“基础程度”、“性别”三个测试属性的信息增益率。
表5 各测试属性所划分的子集及信息增益
当实验学时=“少”时,信息增益率最大的属性是“性别”属性,它被选择为测试属性,在“实验学时”为“少”时的分枝下创建一个节点,用“性别”标记,引出两个分枝,其划分结果如图1第二层左侧所示。再在每个分枝下对“是否重修”和“基础程度”属性进行划分,例如,当实验学时=“少”并且性别=“女”时,对“是否重修”和“基础程度”属性进行划分,信息增益率最大的属性是“基础程度”属性,它被选择为测试属性,所以在“性别”为“女”时的分枝下创建一个节点,用“基础程度”标记,引出两个分枝,其划分结果如图1第三层左侧所示。再在每个分枝下对“是否重修”属性进行划分,如图1第四层所示。
由于所选取的属性较少,决策树划分至,已经没有其的属性可划分,则根据决策树的后剪枝算法对图1所示的决策树进行剪枝整理,得出图1左侧所示。
同理对“实验学时”为“中”和“很多”时的情况进行划分,得到如图1所示的决策树:
图1 决策树模型
五、采用决策树的最大优点是能直接提取分类规则,并以 IF…THEN 形式的分类规则表示
IF…THEN 规则易于理解,特别是当给定的决策树很大时很实用。提取 IF…THEN 规则的主要做法是:对从根到叶节点的每条路径创建一个规则,沿着给定路径上的每个属性-值对形成规则前件(IF 部分)的一个合取项。叶节点包含类预测,形成规则的后件(THEN 部分)。
IF实验学时= “少”AND性别=“女” AND 基础程度=“高”THEN及格=“yes”
IF实验学时= “少”AND性别=“女” AND 基础程度=“中”THEN及格=“yes”
IF实验学时= “少” AND性别=“女” AND 基础程度=“低”AND 是否重修=Y THEN 及格=“yes”
IF实验学时= “少”AND性别=“女” AND 基础程度=“低” AND 是否重修=N THEN 及格=“no”
IF实验学时= “少”AND性别=“男” AND 基础程度=“高”THEN及格=“yes”
……
六、结论
通过观察决策树模型,可以看出所选的四个属性可以影响成绩及格,但影响强度有所不同。对及格率影响最大的因素是“实验学时”,当实验学时在17～24学时之间时,及格率最高。说明实验学时安排适当,可以适当提高教学效果。而实验学时太多时并不一定代表教学效果会更好。
另外,“性别”属性可以看出大部分不及格的学生都是男生,从教学实践中可以得出,这部分男生大多学习态度较差,而女生的学习态度绝大多数都很认真,相对及格率就高,进一步说明,学习态度对学生及格率的影响也是很大的,一个班级如果学风较好,实验学时又能安排合理,及格率就会显著提升。
数学建模聚类算法范文2
1.统计分析方法
统计分析方法是利用统计学原理对数据库中的数据进行分析，从而找出它们之间的关系和规律的方法。统计分析一直是分析空间数据的常用方法，侧重空间物体和现象的非空间特性分析。统计分析方法包括线性与非线性分析、相关分析、回归分析、差异分析、判别分析、Bayes网络等。统计分析方法的缺点是难以处理字符型数据，需要具有领域知识和统计知识，一般由具有统计经验的领域专家来完成。
2.基于集合论的数据挖掘方法
集合论（简称集论）是一门研究集合（由一些抽象数学对象构成的整体）的数学理论。集论（加上逻辑和谓词演算）是数学的公理化基础之一，通过集合、元素及成员关系来形式化地表示其他数学对象。基于集合论的数据挖掘方法包括覆盖正例排斥反例方法、概念层次网络方法和基于粗糙集理论方法，其中应用最广泛的是粗糙集（RS）理论方法。这三种方法中都使用了集合理论中的一些概念和原理，并涉及到大量的集合运算。
粗糙集理论（Rough Set Theory）是波兰学者Z.Pawlak在1982年提出的，它被广泛研究并应用于不精确、不确定、不完全的信息分类分析和知识获取。粗糙集（RS）作为集合论的扩展，是一种用于研究不完全和不完整信息描述的数据挖掘技术，它能够在缺少数据先验知识的情况下，以考察数据的分类能力为基础，解决模糊或不确定数据的分析和处理。
覆盖正例排斥反例方法是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在正例集合中任选一个种子，到反例集合中逐个比较。与字段取值构成的选择子相容则舍去，相反则保留。按此思想循环所有正例种子，将得到正例的规则（选择子的合取式），比较典型的算法有Michalski的AQ11方法、洪家荣改进的AQ15方法和AE5方法。
概念层次网络（HNC）理论是关于自然语言理解处理的一个理论体系，它建立了网络式概念符号基元体系，即概念表述的数学表示式，这个表示式能够与自然语言的词语建立起语义映射关系，同时它是高度数字化的，每一个符号基元（字母或数字）都具有确定的意义，可充当概念联想的激活因子。语义网络是树状的分层结构，每一层的若干节点分别用数字来表示，网络中的任何一个节点都可以通过从最高层开始到该节点结束的一串数字唯一确定。HNC通过概念符号基元体系把自然语言映射到概念空间，数字化的概念表达式可以树形展开，这样才能充分利用概念符号化带来的优点对概念进行各种运算和操作。
3.决策树方法
决策树是通过一系列规则对数据进行分类的过程，其表现形式是类似于树形结构的流程图。首先，以信息论中的信息增益原理为基础，寻找数据库中最大信息量的字段，建立决策树的根节点；然后根据字段的不同属性值建立树的分枝，再在每个分枝子集中递归建立树的下层分枝和节点，非叶子节点表示属性，最下层的叶子节点表示数据集的子类类别，这样便生成一棵决策树；最后对决策树进行剪枝处理，通过树形结构产生一组规则，依照规则将数据集分类。它着眼于从一组无序、没有规则的数据中推理出决策树表示形式的分类规则。决策树方法的优点是决策制定的过程可见，不需要长时间构造过程，描述简单、易于理解、分类速度快；缺点是很难基于多个变量组合发现规则。决策树方法擅长处理非数值型数据，而且特别适合大规模的数据处理。常用的决策树算法有 CLS算法、ID3 算法、C4.5 算法等。
4.聚类分析方法
聚类分析方法是根据数据特征，按一定的距离或相似性系统，将数据分成一系列相互区分的类，划分的标准是类内差别最小、类间差别最大。即将实体对象或抽象对象的集合分组，这个由类似的对象组成的多个类的过程称为聚类。通过聚类以后，数据集就转化为类集，同类数据具有相似的变量值，不同类数据的变量值不具有相似性。在知识模式类型无法得知的情况下，可以运用聚类分析法进行分类、识别。按照模式间的相似程度进行自动分类的聚类分析法，能够将相似度大的模式归为一类。按聚类过程分，聚类分析法有凝聚算法、分裂算法、增量聚类和划分聚类。按相似性系统，聚类算法可以分成基于距离的方法、基于层次的方法、基于密度的方法以及基于网格的方法。例如，层次方法就是按照一定的层次分解给定的数据对象集合，可以分为分裂层次方法和凝聚层次方法。聚类分析法适用于分析样本之间的内部关系，合理的评价样本结构。此外，孤立点的检测也可以应用聚类分析。聚类是为了将某个对象从大量的数据中分离出来，而不是简单地将数据集合在一起。目前，聚类分析法已广泛应用于图像处理、模式识别、经济分析等多个研究领域。
5.人工神经网络方法
神经网络法是一种模拟生物神经系统的结构和功能，通过训练来学习的非线性预测模型，可完成分类、聚类、特征挖掘等多种数据挖掘任务。神经网络（Nerual Net）指由大量的神经元（PE）互连而成的网络，神经网路模型通常由输入层、中间层（亦称隐层）和输出层组成。在每个神经元求得输入值后，再汇总计算总输入值；由过滤机制比较总输入值，确定网络的输出值。可以通过连接一组神经元来模拟复杂行为，当修改连接层的“接度”或权值时，神经网络就进行了学习或“训练”。
神经网络的学习方法主要表现在上述权值的修改过程上。这种方法模拟了人脑神经元结构，通过大量神经元构成的网络来实现自适应的非线性动态系统，具有对非线性数据快速建模的能力，通过对训练集的反复学习来调节自身的网络结构和连接权值，并对未知的数据进行分类和预测。其优点是具有自学习、自组织、自适应、抗干扰、分布存储、联想记忆、非线性学习、大规模并行处理等功能，对复杂情况能得到精确的预测结果；缺点是不适合处理高维度变量，具有“黑箱”性，人们难以理解网络的学习和决策过程，输出结果也难以解释。目前，神经网络法主要用于数据挖掘的分类、聚类知识以及特征的挖掘过程。
数学建模聚类算法范文3
关键词：数据挖掘；簇；聚类算法
中图分类号：TP301.6文献标识码：A文章编号：1672-7800（2012）010-0033-03
基金项目：湖南省大学生研究性学习和创新性实验计划项目（JSU-CX-2011-28）
作者简介：张露（1991-），女，吉首大学软件服务外包学院学生，研究方向为计算机科学；张彬连（1978-），女，吉首大学软件服务外包学院讲师，研究方向为计算机科学。
0引言
随着信息和科学技术的高速发展，各行业积累的数据量迅速增长，而更重要的是如何从大量的、不完全的数据中提取出有用的信息。而在数据挖掘中充当重要角色的就是聚类，它在识别数据的内在结构方面具有独到的作用。而数据挖掘工具以及工具提供的可选择的算法是实现数据挖掘目的的垫脚石。数据的类型、聚类的目的应用决定了选择哪一类聚类算法，其中聚类是把物理或者抽象对象分组成为由类似对象构成的多个簇的过程，即把数据对象分成多个类或簇，在同一个簇中的对象具有较高的相似度，而不同簇中的对象差异较大。它对未知数据的分析和划分能起到非常有效的作用。此外，通过聚类，能够识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相互关系等。为了找到效率高、通用性强的聚类方法，人们从不同角度提出了许多种聚类算法，大致可分为层次方法、划分方法、基于密度的方法、基于网格的方法和基于模型的方法这五大类。
1典型聚类算法分类及其优缺点分析
1.1基于划分的聚类算法
首先，给定一个样本为n的数据集，然后根据给定要创建划分的数目k，将数据划分为k个组（kn），每个组相应地表示一个簇，同时满足以下的条件：①每个组至少包含一个样本；②每个样本属于且仅属于一个簇。算法要事先给出要创建的划分的数目k，创建一个初始划分，然后采用循环定位技术，通过根据簇类之间的差异把对象从一个划分移动到另一个划分的方法来改善划分质量。评价划分的好坏的标准一般是在同一个类中的对象尽可能“接近”，而不同类中的对象尽可能“远离”。为达到全局最优的目的，基于划分的聚类会要求穷举所有可能的划分。其中包括以下典型的划分方法：k-平均、k-中心点、CLARA、CLARANS等。
1.1.1基于簇的重心技术：k-平均算法
（2）k-平均算法的优缺点：①优点：当满足结果簇是紧凑的，并且簇与簇之间明显分离式的前提条件，k-平均算法能发挥较好的效果，而且在处理大数据集时，是有相对可伸缩的和有效率的；②缺点：该算法有其限制条件，只有在簇的平均值被定义的基础上才能使用，这就使得可能不适应某些应用的数据，要求用户必须事先给出k的取值。在大部分实际应用中，最终的聚类数量并不能得到一个确切的数目，且该算法遇到非凸面形状的簇，或者遇到在大小上存在很大差别的簇时，聚类效果不明显。而且，它对于带有“噪声”的空间数据和离群数据是敏感的。该算法经常止于局部最优。
1.1.2基于有代表性的对象的技术：k-中心点方法
1.1.3基于选择的k-中心点CLARANS方法
（1）CLARANS方法的处理流程：首先，不考虑整个数据集合，用实际数据的抽样来作为数据的样本；然后，用PAM方法从样本中选择中心点；返回最好的聚类结果作为输出。
（2）CLARANS方法的优缺点：①优点：该算法的效率较高，能够发现最“自然的”结果簇数目，且能够检测离群点，且相应地拓展了数据处理量的伸缩范围；②缺点：该方法的聚类质量对采取的抽样方法依赖性强，且最中心点的要求较高。而且对于大数据量、时间复杂度和空间复杂度都很大。
1.2基于层次的聚类算法
根据树的形成过程，层次分解的方向的不同可以分为以下两种类型：
（1）自底向上（凝聚）聚类方法。该方法一开始将每个对象作为单独的一个组，然后继续与相近的对象或组合并，直到所有单独的组都被合并，成为一个整体，或者达到一个终止条件。
（2）自顶向下（分裂）聚类方法。与凝聚法相反，该策略先将所有对象置于一个簇中，在迭代的每一步中，在一个簇的基础上分裂为更小的簇，直到最终每个单独的簇中包含一个对象，或者达到一个终止条件。下面介绍其代表算法。
1.2.1BIRCH算法
（1）BIRCH算法包括阶段：阶段一是BIRCH扫描数据库，建立初始化的CF树，尝试把数据内在的聚类结构保留下来；阶段二是BIRCH算法采用某个聚类算法对CF树的叶节点进行聚类。
（2）BIRCH算法的优缺点：①优点：引入的聚类特征树概括了聚类的有用信息，且占用空间较元数据集合小，只需要一次性访问数据库，速度快，伸缩性好，对增量或动态聚类也非常有效，不需要大量递归运算。②缺点：由于CF树每个节点的大小受限制，并不总是对应于用户所认为的一个自然聚类，而且算法的工作效率依赖于簇的球形要求。
1.2.2CURE算法
（1）CURE算法工作原理：选择了属于聚合方法和分解的中间做法。选择数据空间中具有代表性的点。且在选择簇中分散的对象中产生一个簇的代表点，然后根据一个特定的分数或者收缩因子向簇心“收缩”或移动它们。
（2）CURE算法优缺点：①优点：能识别非球状以及大小不一的聚类，能更好地处理孤立点。对于大型的数据库，它也具有良好的伸缩性，且不影响聚类的质量；②缺点：聚类结果容易受到参数设置的影响，且CURE算法对分类属性不进行处理工作。
1.3基于密度的聚类算法
基于密度的聚类算法并不是基于各种各样的距离而是基于密度的。这样就能克服基于距离的算法只能发现“圆形”类的缺点，它可以发现任意形状类的聚类结果。该方法的思想就是，只要一个区域中的点的密度大于某个阈值，就把它加到与之相近的聚类中。以下介绍其代表算法DBSCAN算法和OPTICS算法。
1.3.1DBSCAN算法
（1）DBSCAN算法思想：首先通过检查数据库中每个点的ε-邻域内的邻居点数衡量改点所在空间的密度。来寻找聚类。如果一个点p的ε-邻域名超过某个指定阈值MinPts个点，则建一个新簇以p作为核心对象，然后再反复地寻找从这些核心对象直接密度可达的对象，当没有新的点可以被添加时，该过程即结束。
（2）DBSCAN算法优缺点：①优点：能够把具有足够高密度的区域划分为簇，对带有“噪声”的空间数据比较敏感，可以发现任意形状的聚类；②缺点：参数的设置难以确定，对参数值是非常敏感的，容易导致误差很大的聚类结果，且全局密度参数不能刻画其内在的聚类结构。
1.3.2OPTICS算法
（1）OPTICS算法思想：采用影响函数，即用一个数字函数来形式化地模拟每个数据点的影响；所有数据点的影响函数的总和可以由数据空间的整体密度模型化得到；可以通过确定密度吸引点来得到聚类，且此时全局密度函数在密度吸引点达到局部最大。
（2）OPTICS算法优缺点：①优点：该算法的数据基础非常坚实，并且概括了其他的聚类算法；其良好的聚类特性在处理有大量“噪声”的数据集合时充分体现出来了；提供了简单而有效的数学技术给高维数据集合的任意形状的聚类；速度较快；②缺点：聚类结果会容易受到密度参数和噪声阈值等参数的影响。
1.4基于网格的聚类算法
基于网格的聚类方法采用的数据结构是一个多分辨率的网格。它将数据空间分为有限数目的单元，形成网结构，所有的处理对象是单个的数据单元，这种处理方法与目标数据库中记录的个数并不存在很大的关系。以下介绍其中的STING算法。
（1）STING算法工作原理：STING是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元由多个低一层的单元组成，且事先计算和存储关于每个网格单元属性的统计信息，在查询处理时就能使用这些统计参数，达到不一样的效果。
（2）STING算法优缺点：①优点：基于网格的计算与查询是相对独立的；在处理数据和增量更新方面能够更加方便；效率较高；②缺点：最底层的粒度影响算法的质量，且该算法在构建一个父单元时，忽略了子单元与相邻单元间的关系，导致结果簇的形状的边界不稳定。
1.5基于模型的聚类算法
基于模型的聚类算法尝试优化给定的数据和某些数学模型之间的适应性，是基于“数据是根据潜在的概率分布生成的”这一假设而提出的。该方法主要包括统计学方法和神经网络方法这两大类。以下介绍其中的COBWEB算法。
（1）COBWEB算法工作原理：COBWEB算法采用分类属性-值对来描述其输入对象，以一个分类树的形式来构造层次聚类，并且在启发式估算度量方法以及分类效用的指导下开展树的构建工作。
（2）COBWEB算法优缺点：①优点：对划分过程中类的数目能自动修正，不需要用户提供这样的输入参数，可以找到分类对象的最好结点；②缺点：该算法基于的“每个属性上的概率分布式彼此独立的”假设不总是成立的；更新和存储聚类代价相当高，可能导致时间和空间复杂性发生剧烈的变化。
2结语
分层聚类的突出亮点是它能够生成比较规整的类集合，聚类结果不依赖元素的初始排列或输入次序，与聚类过程的先后次序并没有直接的关系，聚类结果相对稳定，不易导致类的重构。但它也存在着部门缺点，如计算开销较大，对异常数据比较脆弱。划分聚类的优点是运算量小，能运用于处理庞大的样本数据，也为实时处理提供了一定的可能性。但要求用户必须预先给出聚类的参数，还要靠度量函数来判定所给出解的优劣程度。网格聚类处理速度快，处理时间与数据对象的数目无关，聚类时间独立于数据规模和数据次序，伸缩性极好。缺点是只能发现边界是水平或垂直的聚类，不能检测到斜边界，也不适用于高维情况，并存在量化尺度的问题。密度聚类多用于时空信息处理、消除奇异值，并且可以在带有“噪声”的空间数据库中发现形状任意、个数不定的聚类，适合大型、高维数据集等方面具有较好的特性。对于所提到的上述聚类算法，可以从可伸缩性、处理不同类型属性的能力、发现任意形状的簇、处理噪声数据的能力、对输入顺序的敏感性、处理高维数据的能力、需要决定的输入参数最少以及对输入记录顺序不敏感这些方面来进行比较分析，以更好地了解这些聚类算法。
参考文献：
[1]HUANGZX，MICHAELK.Anoteonk-modesclustering[J].JournalogClassification，2003（2）.
[2]PELLEGD，MOOREA.X-meansextendingk-meanswithefficientestimationofthenumberoftheclusters[C].Proceedingsofthe17thIC-ML，2000.
[3]ERTOZL，STEINBACHM，KUMARV.Findingclustersofdifferentsizes，shapesanddensitiesinnoisy，highdinensionaldata[R].MinneapolisUniversityofMinnesota，2002.
[4]MARQUESJP，WRITTEN，WUYF，etal.PatternRecognitionConcepts，MethodsandApplications（2nded）[M].Beijing：TsinghuaUniversityPress，2002.
[5]DHILONI.Co-clusteringDocumentsandwordsusingbipartitespec-tralgraphpartitioning[C].SanDiegaProceedingsofthe7thACMSIGKDD，2001.
[6]SAMBASIVAMS，THEODOSOPOULOSN.AdvanceddataclusteringminingWebdocuments[J].IssuesinInformingScienceandInformationTechnology，2006（3）.
[7]NANNIM，PEDRESCHID.Time-Focusedclusteringoftrajectoriesofmovingobjects[J].JournalofIntelligentInformationSystems，2006（3）.
[8]BIRANTD，KUTA.ST-DBSCAN：ANalgorithmforclusteringspatial-temporaldata[J].Data&KnowledgeEngineering，2007（1）.
[9]CRISTOFORD，SINOVICIDA.Aninformation-theoreticalapproachtoclusteringcategoricaldatabasesusinggeneticalgorithms[C].ArlingtonThe2ndSIAMICDM，WorkshoponClusteringHighDinen-sionalData，2001.
数学建模聚类算法范文4
关键词：网络；数据挖掘；教育资源
中图分类号：G640 文献标识码：A 文章编号：1007-9599 （2012） 19-0000-02
1 前言
构建交互式网络教务管理与学习环境就成为解决方案之一。利用现代网络技术、网络多媒体技术与现代学习理论相结合，通过构建交互式网络教务管理学习环境，来实现现有各种分散的教育教务管理资源充分共享，以有效实施个性化教育及实现教务管理双方之间的充分沟通交流，使传统模式下的封闭或半封闭的课堂教务管理环境变成一个充满交互与交流的网络虚拟学习社区。
2 交互式教务管理模式设计
新世纪的今天，利用网络技术、多媒体技术大力发展网络教育、远程教育，已成为教育发展的主流。从目前多媒体网络教务管理系统技术实现的形式和方法来看，大致可分为两种学习模式，一种是以视频会议系统为主的在线式网络教务管理，它是通过控制与传输基于视音频的教育教务管理信息，将在空间上分离的教师和学生联结在一起，进行实时的、可视的交互式教务管理。
3 通用Web教务管理模式设计
研究关于基于web的通用网络多媒体学习平台的系统模式的设计与实现，就具有十分重要的现实作用与意义。为了解决这个问题，本章实现了一个新颖的以Voronoi Diagram为基础的私有信息模型叫做Semi-Delaunay Diagram（SDD）和一个隐私保护聚类算法叫做Voronoi Diagram Clustering（VDC）。这个模型使用Voronoi cell的面积去代替相应点的准确信息。使用SDD和VDC，摘要：高校教务管理能够在数据隐私性和数据可用性两方面找到很好的平衡。VDC聚类算法与DBSCAN聚类算法具有共同的优点，那就是他们都可以发现任意形状的类。
4 聚类算法在教务管理中的应用
聚类在教务管理信息数据挖掘中是一个非常基础的问题，在过去的几十年的发展中已经有了非常多的聚类算法出现。那些算法大体可以分为这么几类：partitioning methods划分的，比如K-means[19-20]，k-modes等等。Hierarchical methods分层的比如ROCK[25]，CHAMELEON[26]，BIRCH[27]等等。Grid-based methods基于网格的比如STING[7]。
4.1 密度聚类算法教务管理研究
基于密度的聚类方法是以密度概念为基础的。我们的VDC聚类方法也是以基于密度为基础的。原有的基于密度的聚类方法有DBSCAN，DENCLUE和OPTICS。这些基于密度的聚类方法都能找到任意形状的类。一个好的聚类方法应该满足以下三条：第一，参数最少，因为对于大量数据来说确定一个好的参数是很困难的，同时参数的选定对最后结果又有很大的影响。第二，能找出任意形状的聚类，因为好多类是不规则的。第三，在进行聚类的同时能很好的保护数据的隐私。使用SDD和VDC，摘要：高校教务管理能够在数据隐私性和数据可用性两方面找到很好的平衡。VDC聚类算法与DBSCAN聚类算法具有共同的优点，那就是他们都可以发现任意形状的类。而像其它的聚类算法，比如著名的k均值算法都不能找出任意形状的类。这里需要注意的是，原始的DBSCAN算法需要两个参数Eps和MinPts，而我们的VDC只需要一个参数MaxArea。隐私保护教务管理信息数据挖掘大体上能够分为两类：安全多方计算和隐私保护数据。隐私保护数据是让使用者能够建立一个教务管理信息数据挖掘模型同时没有泄露准确信息。一个流行的方法是把原始数据加入噪音进行扰动，数据按一定函数分布对单个个体加入噪音，然后数据算法能够重构。一个基于压缩的方法在中实现，数据首先被聚类成组，让后从组中生成伪数据。隐私保护数据原则比如k-anonymity要求每一个等价类包含至少k个记录。最近，许多研究者意识到k-anonymity不能阻止隐私属性泄露。在中l-diversity实现了一个新的原则去克服这些问题。
4.2 面向对象协议解析教务管理方法研究
本课题综合采用面向对象和面向过程的设计方法，对不同的模块进行区别对待，原因是对LPD协议解析的过程中由于LPD协议自身的特点会涉及到连续多层次的信息交互，更适宜采用面向过程的设计方法，而其它模块则可以采用面向对象的设计方法，将每个模块进行单独封装设计和进行单元测试后，进行系统集成和进行集成测试。另外，由于本课题的打印管理子系统会涉及到对用户打印信息的存储、分析和展示。
5 系统设计思路
设计开发基于Web的通用网络多媒体教务管理平台的目的：一方面要求系统设计的体系结构合理，技术先进，充分体现现代教育与学习的需求；另一方面要尽量避免类似系统的重复开发，降低开发的成本，强调系统的通用性。因此，在进行系统设计时，必须坚持教务管理内容与技术手段相结合，以教务管理内容为主，立足于当今先进网络多媒体信息技术，同时又考虑未来技术发展，兼顾不同学科的教务管理特点，以适用于尽可能多的用户群的通用性要求，做到以尽可能低廉的投入而获得尽可能高效的教务管理效益的经济性要求。
6 功能与结构设计
根据现代学习理论与认知心理学的原理，学习过程是一个不断反复、螺旋式上升的过程，因此，作为一个网络虚拟学习环境，基于Web的通用网络多媒体教务管理平台，其功能与结构的实现也主要根据这一理论来进行设计，整个系统采用了以学习者自主学习为主的学习机制，计算机网络与教师只充当资源的提供者和学习帮助的作用。
7 总结
基于Web的通用网络多媒体教务管理平台，目的是为了建立一个学习者的学习与学习效果评价相结合的通用的跨学科、跨专业的网络学习环境，实质上是一个可操作的教务管理信息资源的数据库管理系统。基于3层B/S结构在数据处理方面的优越性，在进行基于Web的通用网络多媒体教务管理平台的技术方案设计时，就采用B/S三层结构的网络数据库方式来进行设计，根据三层结构的要求，系统平台分成3部分：教务管理信息表示层（在Web浏览器上完成，是学习者及教师操作的主要交互界面）、教务管理应用功能层（Web服务器，介于Web浏览器和数据库服务器之间，负责用户输入信息的接受和动态网页的形成，完成主要教务管理应用功能）和教务管理资源数据层（数据库服务器，实现对知识信息不断进行新的加工、组合和整理，完成知识重组，意义建构、资源整合等工作）。
参考文献：
[1]高登.教育信息化领域中开源软件的应用策略研究[J].计算机时代，2012，1.
[2]闫世刚.开源软件应用与电子政务建设[J].电子政务，2007，9.
[3]姚鹤岭，赖锴，吕晓东.开源软件与中小企业信息化建设[J].光盘技术，2006，5.
数学建模聚类算法范文5
时至今日，在数字学习系统中整合数据挖掘的探索仍处于初级阶段，但在过去的几年中，这方面的学术研究已有了很大进展，其中大部分涉及聚类方法的设计和应用。因此，笔者在本文回顾了最近应用于数字学习的聚类研究海外案例，期望能够通过对其基本算法和案例的介绍，为数字学习研究者和从业者提供借鉴。
教育数据挖掘中的基本聚类算法
数据挖掘是一种从数据收集、预处理和建模到过程评估与实施的数据分析的过程，为生物医学、工程学、经济学等多样化领域中的问题提供分析解决方案。教育数据挖掘可以通过分析用户生成的数据形式的可用信息，从数字学习系统中提取有用的知识。数据聚类分析是研究数字学习中最常使用的分析方法，以最简单的方式说，数据聚类是将N个数据项中的每一个数据分配给K个可能的集群中的一个。接下来，笔者将进一步详细地描述一些常用的聚类技术。
1.k-均值聚类算法
k-均值算法是最著名的并且使用最广泛的聚类算法之一，其主要特征是易于实施、简洁、高效。k-均值算法旨在将一个数据集D= {x1，…， xn}分为k个不相交的群集，C={C1，…，CK}，其中每个数据xi都被分配给一个唯一的集群Ck。该算法尝试找到用户指定数量的k个聚类。k-均值算法迭代地移动每一个集群的聚类中心，直到实现中心位置的收敛。
k-均值算法可以总结如下：
①随机选出k个元素作为聚类中心；
②根据相似性进行度量，将所有观察的样本分配给它们最接近的聚类中心；
③重新计算新的聚类中心；
④重复②③步骤，直到群组成员变得稳定。
k-均值算法的缺点是k值的不确定性，初始参数的聚类的数量k值的选取非常关键，不同的初始化会导致不同的聚类解决方案。为了改进k-均值算法初始值的缺点，研究者已经开发出了许多变体和扩展，其中两个著名的变体是ISODATA和FORGY。
2.模糊c-均值聚类（FCM）
传统的分层聚类的方法会生成分区，在分区内，每个数据样本都属于且仅属于一个集群，因此，在硬聚类方法中的集群是不相交的。模糊聚类算法扩展了这一概念，利用隶属函数将每个模式与每个聚类相关联。FCM就是一种模糊聚类方法，它允许一个数据样本属于具有隶属条件的两个或多个群集，是k-均值算法的一个模糊化版本。
在模糊聚类中，每一个群集都对应整个数据样本中的一个模糊集合。上页图1就解释了这一观点，它包含了数据集合的两个硬性分配群集的矩形：H1 = {1， 2， 3， 4， 5}和H2 = {6， 7， 8， 9}，FCM可以产生两个模糊群集，即F1和F2，由椭圆表示。每一个数据样本都会有每个模糊群集的0到1之间的隶属值，较大的隶属值表示在群集的观察分配中具有较高信度。
模糊c-均值算法可以总结为以下几个步骤：
①通过选择N×K个隶属矩阵U，选择N个对象的初始模糊分区成为K个群集，该矩阵的元素uij代表了群集Cj中对象xi的隶属度，其中uij的值介于0到1之间。
②将数据样本重新分配到群集以减少标准函数值，并且重新计算U值，在执行过程中，使用U值找出与相关分区相关联的模糊标准函数的值，如加权平方误差准则函数。
③重复步骤②，直到U中的元素具有稳定值。
3.自组织映射（SOM）
SOM是一种无监督学习模型，其以拓扑有序的方式将p维的输入数据点投影到q维离散图中。每一个格子单元都由具有相关联的p维权重向量的神经元代表，每个输入模式与每个神经元的权重向量进行比较，并且最接近的神经元获得激活。一个神经元被激活后，近邻区神经元也逐渐被激活，并且它们的权重向量被调整的更加类似于输入模式。最初，邻域的大小很大，但是在迭代期间，邻域大小逐渐减小。图2为基本SOM模型的架构。
SOM算法集中于保留数据中的邻域关系，而不是试图保留数据项之间的距离。SOM算法有两个基本版本，即序列处理和批量处理。
4.生成式拓扑映射（GTM）
GTM最初是作为一个替代SOM的概率聚类模型，并被作为一个高斯分布的约束混合而被创制出来的。正是这些约束创建了用于集群可视化的投影集合，克服了通用有限混合模型的限制。模型解释通常需要大大降低数据的维度，潜在变量模型可以通过可视化提供这样的解释，因为它们描述了本征的低维潜在空间中的数据。在潜在可视化空间中的每个潜在点uk都会被映射，yk点通常称为参考矢量或原型。每个参考向量元素对应输入到变量中相应的一个，并且它在潜在可视化空间上的值可以颜色编码，进而产生参考图，并提供关于每个变量的行为的信息及其对聚类结果的影响。每个潜在空间点本身可以被认为是一个聚类代表。
数字学习中的数据聚类分析海外案例
在学习中，学生经常通过团队协作来理解概念、分享观点，并且最终以一个整体完成学习的整个过程。教师可以对这些学生的能力进行评估，进而识别和分组，并对学生进行分组的过程实施数据聚类分析，其目的是发现数据的自然分组结构。
大多数处理数字学习环境中聚类问题的研究可分为三大类：一是，基于数字学习材料进行分组的研究；二是，基于学生的学习行为进行分组的研究；三是，提出聚类分析作为数字学习策略的一部分，但不提出任何实际应用结果的研究。
1.基于数字学习材料的数据聚类分析
基于数字学习材料的数据聚类分析的最终目标是改进学习材料的使用。
在海外，一些研究会在Web语义框架内实现一个基于本体的工具，目的是帮助数字学习用户发现和组织分布式的课件资源；另一些研究则实施了一个基于网络的测试和诊断系统，采用模糊逻辑理论，根据每个学生的学习状态和个人特征，确定测试项目的难度水平，然后应用模糊自适应共振理论（Fuzzy ART）进行分组。例如，Pirrone等人介绍了一个在数字学习应用中信息表示的方案和集成架，目标是使用它们包含的术语之间的相似性来度量聚类课程材料；Zhuhadar等人提出了一种在数字学习平台中进行个性化搜索的方法，使用导航日志的记录表示数字学习内容和学生的个人资料，然后应用聚类技术对文档进行分组。另外，为了改进虚拟课程资源，研究者可以使用与学习材料的评价相关的聚类方法。如果我们可以从其系统可用来评估学生，其结果也可以间接用于改善课程资源。
2.基于数字学习行为的数据聚类分析
基于学生学习行为的数据聚类分析的研究结果可以帮助教师为每个聚类的学生提供个性化的指导，增强学生的数字学习体验，进而提升学生的学习成绩。
海外的研究者基于学生的学习行为进行了不同类别的具体研究。例如，Tang和McCalla进行了关于如何将数据挖掘技术成功地纳入数字学习环境及如何改善学习过程的调查；Castro和Vellido将GTM模型的不同变体用于关于虚拟课程中学生行为数据的聚类和可视化，而且这些知识可以反馈到数字学习系统，以便教师根据学生们的不同需求，提供个性化的指导；还有一些研究者运用EM算法根据学生的行为将数据分成群集，教师再向每个群集的学生提供专门的建议；Christodoulopoulos和Papanikolaou设计了一个基于网络的学生分组的工具，该工具使用低复杂度算法对学生进行分组，帮助每个学生适应不同的组，同时，该聚类信息也给教师提供了参考依据，便于教师在组之间调换学生，FCM就是根据学生的个性和学习策略来将其聚类；另外，一些研究者提出了一个基于模糊集群算法的数字学习系统，该系统能将类似的学生分类到同类课程并向学生提供个性化学习指导；Mylonas和Tzouveli提出了一种通过网络接口收集和评估学生在教育领域的信息和通信技术水平的新方法。
3.聚类分析作为改善数字学习环境的工具
研究者认为互动是团队成功的一个重要因素，然而，普通课程往往缺乏影响信息交流和知识共享的团体协作。通常在线课程的班级规模要大于传统班级，由于互联网上交流互动的限制，大多数学生难以形成具有高互动级别的群体。因而，有研究者提出应用聚类分析技术来改进数字学习环境，整合了子空间聚类和概念聚类技术，并定义一种称为概念子空间聚类（CSC）的算法，该算法在密集子空间中提取概念集群，并通过重叠概念来描述集群。
在数字学习过程中，学生可以从数字学习课程中的电子邮件或论坛中搜集有价值的信息，然而现在仍然缺乏相关的自动化工具。而自然语言处理（NLP）方法在解决数字学习中的这些问题上具有潜在优势，因为它能够自动提取通过其他技术难以或几乎不可能获得的有用信息，遗憾的是NLP技术尚未广泛应用于数字学习。
结语
数学建模聚类算法范文6
摘 要 本文提出了一种利用用户浏览页面集的内容信息和浏览行为信息，隐式地创建用户兴趣描述文件的方法。通过对用户浏览的web页面进行兴趣度分析，并与对用户浏览网页时的浏览行为分析相合，得到了用特征矩阵表示的用户兴趣模型。并采用层次聚类算法和 k-means 聚类算法相结合的综合聚类算法进行聚类，得到用兴趣分类树表示的用户兴趣模型。由于采用的是隐式创建用户描述文件的方法，减少了因用户参于而带来的系统噪声，保证了所创建的用户兴趣模型的准确性。 关键词 用户兴趣模型；浏览内容；浏览行为；兴趣分类树 人们正在寻求一种将用户感兴趣的信息主动推荐给用户，对不同的用户提供不同的服务策略和服务内容的服务模式，即个性化服务的信息方式 。 用户兴趣模型是个性化服务系统的关键部分，用户兴趣描述的准确与否直接决定着个性化推荐服务的质量好坏。本文提出了一种利用用户浏览页面集的内容信息和浏览行为信息，隐式地创建用户兴趣描述文件的方法。该方法以用户浏览web页面的内容信息和行为信息作为数据源，采用web挖掘方法分析得到较准确的用户兴趣描述，减少了由于用户参与而带来的系统噪声，保证了所创建的用户兴趣模型的准确性。 1 基于web浏览内容和行为分析相结合的用户兴趣模型 整个用户兴趣模型的创建过程包括web浏览内容分析和web浏览行为分析两部分，流程图如图1所示。wWW.lw881.com 图1 用户兴趣模型创建流程图 web浏览内容分析，就是采用web聚类分析方法对用户已浏览的web页面集进行内容聚类，得到用户感兴趣的页面集；web浏览行为分析是对用户浏览页面时的行为信息进行分析，得到用户对单一页面的兴趣浓度。将二者相结合，就得到了用户感兴趣的主题类别及对每类主题的兴趣度，即用兴趣分类树表示的用户兴趣模型 2 基于web浏览内容的用户兴趣分析 本文中用户兴趣模型描述所基于的web浏览内容是指用户浏览页面的内容信息，它被用于基于内容的聚类分析。这些页面的内容信息主要来源于 web 服务器端，首先根据用户的浏览日志记录，得到单一用户的浏览历史页面 url，然后从数据库服务器中取出这些 url 对应的 web 页面，作为对浏览内容兴趣描述的数据源。 2.1 对浏览网页信息的数据预处理 与数据库中的结构化数据相比，web文档具有有限的结构，即使具有一些结构，也是着重于格式而非文档内容。此外，文档的内容是人类所使用的自然语言，计算机很难处理其语义。web 文本信息源的这些特殊性使得现有的数据挖掘技术无法直接应用于其上。这就需要对文本进行预处理，抽取代表其特征的元数据，作为文档的中间表示形式。 近年来应用较多且效果较好的特征表示法是向量空间模型(vector space modelvsm) 法。在vsm 中，将文本文档看成由一组词条 构成，对于每一词条 ，根据其在文章中的重要程度赋予一定的权重 。因此，所有用于挖掘的页面文档都可以用词条特征矢量 表示。要将文本表示为向量空间中的一个向量，就先要将文本分词，由这些特征词作为向量的维数来表示文本，最初的向量表示完全是0、l形式，即，如果文本中出现了该词，那么文本向量的该维为l，否则为0。这类方法无法体现这个词在文本中的作用程度，所以0、l逐渐被更精确的词频代替，词频分为绝对词频和相对词频。绝对词频，即使用词在文本中的出现频率表示文本；相对词频为规一化的词频，其计算方法主要运用tf-idf公式，目前存在多种tf-idf公式，我们可采用一种比较普遍的tf-ldf 公式： 我们把用于挖掘的页面文档作为一个文档集合。这样对于文档集合 d = 中的任一文档 ，采用向量空间模型表示为： = 其中m 为文档 特征向量的个数， 为文档 的第i个特征向量， 为文档 中 的权值。 2.2 页面相似度函数 采用向量空间模型表示的数据，必须选择计算两个特征矢量之间相似性的相似度函数。现在常用的方法有欧几里德距离、曼哈坦距离和夹角余弦函数。我们在这里采用夹角余弦函数。但是在计算时可能会遇到用于比较的两个特征矢量长度不一样，我们可以采用添零补齐的方法使两者长度一致。夹角余弦函数如下： 其中，c（x，y）表示页面x与y的相似度， 与 表示x与y对应的特征词的权值。页面x与y值越相似，c（x，y）值越大；反之则越小。 3 基于浏览行为的用户兴趣分析 研究表明，用户很多浏览行为都能很好地反映用户的兴趣。文献[6]指出用户的很多动作都能暗示用户的喜好，如查询、浏览页面和文章、标记书签、反馈信息、点击鼠标、拖动滚动条、前进、后退等。文献[7]的研究指出用户访问时的停留时问、访问次数、保存、编辑、修改等动作能够揭示用户兴趣。这些行为究竟怎样反映用户的兴趣，我们需要对其进行量化估算。 3 .1 浏览行为的分类 从表面上看能揭示用户对网页p兴趣度d（p）的浏览行为很多，但我们分析发现，起关键作用的是两种行为：在网页p上的浏览时间t（p）（简称t行为）和翻页/拉动滚动条的次数v（p）（简称v行为）。 原因有三：1）查询、编辑、修改等行为必定增加网页浏览时间和翻页次数，因此能够通过后者间接的得到反映。2）执行了保存、标记书签等动作的页面，若真为用户关心，通常以后会被多次调出来重新浏览，故可体现为访问次数。3）点击鼠标动作不被考虑，因为简单动作不能有效揭示用户兴趣。 3 .2 浏览行为参数的计算 为了找到t，v与网页兴趣度的定量关系，通过分析和实验，决定采用一元线性回归方法作为网页兴趣建模分析的工具。线性回归分析方法是在分析研究对象变化趋势的基础上建立函数模型，从而研究对象之间存在的相互依存关系。
用户浏览行为和网页兴趣度之间的回归方程可建立为： d(p)=a*t+b*v+c，其中，a，b，c是与t(p)和v(p)无关的未知参数，它们的估计可采用最小二乘法。这样通过该方程就可以计算用户对每个网页的行为兴趣度 bi (behavior interesting)。 4 用户兴趣模型的表示 4.1 内容分析和行为分析的结合 我们用得到的用户浏览的n张网页组成一个矩阵，每张网页表示为： = 这样，用户浏览网页的特征矩阵就可表示为： 的每个行向量表示的是网页 ，下标m=max ( )。 这样的表示在一定程度上代表了用户的兴趣，但也仅仅表示的是网页内容给用户带来的兴趣，真正反应用户兴趣的还应加上用户的行为兴趣数据.在矩阵d上加上用户的行为数据。将用户浏览的页面内容分析和用户的行为分析结合起来，就得到了完整的用户兴趣度模型。这样，改进后的用户的兴趣浓度就可表示为： = * bi。 4.2 用户兴趣的聚类及表示 聚类就是将数据对象分组成为多个类或簇，在同一簇中的对象之间具有较高的相似度，不同类中的对象差别较大。我们将层次聚类算法和 k-means 聚类算法相结合起来，利用层次聚类算法来产生 k-means 聚类算法所需的k值和初始聚类中心。这样大大提高了k-means 聚类算法的性能，能更准确地发现用户的兴趣所在。改进的 k-means 二次聚类算法描述如下： 输入：包含 n 张页面的特征向量表示矩阵c； 输出：一个已经分好类的用户兴趣树t； 算法： 1） 将c作为兴趣树的一个最大类，令t=c； 2） c作为一个类； 3） m = m+1； 4） 特征向量矩阵c中的每一行对象 （即每张页面文档）看作是一个具有单个成员的类，这些类构成了d的一个聚类c = ； 5） 计算c中每对类 之间的相似度 sim ； 6） 设定一阀值 ，选取具有最大相似度的类对值，如果max≤ ，将和合并为一个新的类 ，从而构成了d的一个新的聚类c= ，重复步骤(5)，(6)；如果max> ，凝聚算法结束，得到分为k个子类的聚类c = ； 7） 将 k 和c = {c1，c2，...，ck }分别作为 k-means 聚类要生成的簇的数目参数和初始聚类中心，执行 k-means 聚类，得到修正后的k个类 ； 8） 把k个类的 作为初始类的子类； 9） 对于每一个 ，令 ， 如果δ<θ（θ为给定的一个接近于1的数），令c= ，转向2） ；否则不对 做任何处理； 10） 输出t，即是所得的用户兴趣分类树。 通过采用上述的综合聚类算法，即层次聚类算法和k-means 聚类算法相结合的算法，对这些网页进行聚类，就得到用兴趣分类树表示的用户兴趣模型。这样就得到了较为精简的用户兴趣模型。 用户兴趣模型树可表示为如下结构： 5 结束语 随着internet的发展，个性化服务技术显的愈发重要。用户兴趣模型建立的准确与否，直接决定着个性化服务质量的好坏。本文通过对用户浏览的web页面进行兴趣度分析和对用户浏览行为分析相结合，得到用兴趣分类树表示的用户兴趣模型。由于采用的是隐式创建用户描述文件的方法，减少了因用户参于而带来的系统噪声，保证了所创建的用户兴趣模型的准确性。 参考文献 [1] 丁 浩，林 云. internet 上的个性化信息服务.中国计算机报. 2000.3. [2] 曾 春，刑春晓，周立柱. 个性化服务技术综述[j].软件学报. vol.13，no.10，2002. [3] 唐 倩，张 前，陈泓婕. 基于web的文本挖掘[j].计算机工程与应用，2002，21. [4] 鲁 松，白 硕. 文本中词语权重计算方法的改进[j].2000 international conference on multilingual information processing， 2000:31-36. [5] 高晓琴，蒋朝学，涂 瑞. web使用挖掘研究.微计算机信息，2006，21. [6] 史忠植 著，知识发现. 清华大学出版社.2002. [7] 谭 琼，李晓黎，史忠植. 一种实现搜索引擎个性化服务的方法[j]. 计算机科学， 2002，29(1):23-25.
