混合属性数据范文
混合属性数据范文（精选5篇）
混合属性数据 第1篇
关键词：异常检测,k-原型算法,聚类,决策树,混合属性
0、引言
入侵检测系统是网络安全技术的一个重要组成部分。目前入侵检测的方法主要有两种, 即滥用检测和异常检测。研究聚类分析和分类的算法对入侵检测数据进行挖掘处理, 提高异常检测效率, 降低误报率, 检测出未知入侵攻击是目前网络安全防御体系研究的热点之一。
基于聚类的异常检测是异常检测中较为常用的方法之一, 它是一种无监督的检测方法[1][2]。
k-prototypes[3][4]聚类算法可以处理含有数值属性和类别属性的数据, 但该算法存在局部最优的问题, 对初始模式的选取及聚类数的选取有较强的依赖性。本文提出一种基于k-prototypes与ID3相结合的异常检测算法。该算法即能处理包含数值属性和类别属性的数据, 同时能够有效地解决k-prototypes的上述缺点, 并且具有较高的检测率, 成功实现了对未知攻击的检测。
1、k-prototypes聚类算法和ID3决策树算法在异常检测中的应用
1.1 基于k-prototypes聚类的异常检测
k-prototypes聚类算法在考虑数值属性也考虑分类属性的基础上重新定义了差异度函数, 并引入了参数γ来控制数值属性和分类属性对聚类过程的作用。
差异度函数定义如下:
其中, xjr, yjr分别表示数据对象X和聚类l的原型Y的数值属性的取值, 而xjc和yjc是分类属性的取值, p和m分别时数值属性和总属性的个数。对数值属性采用欧式距离, 第一项为数值属性上欧式距离的平方, 第二项为分类属性上的简单匹配相异度。γ为权重系数, 通过数值属性上的平均标准偏差计算得到, 从而使总体相异度不偏向于某一种数据类型。对数值属性采用欧式距离, 上式变为:
其中Elr是基于聚类l中所有数据对象数值属性的代价。设Cj是分类属性j上的所有取值的集合, P (cj∈Cj|l) 是聚类l中数据对象在分类属性j上的取值为cj的频率。则:
nl是聚类l中的数据对象个数。对一个指定的聚类l, 其原型的分类属性只有在取聚类中数据对象的分类属性中出现最频繁的值, 才使目标函数代价最小。
聚类一个具有数值属性和分类属性的数据集的代价函数可写作:
每个聚类原型的数值属性是由k-均值确定, 其分类属性可由上述原则选取。
综上所述, 基于k-prototypes的异常检测算法步骤描述如下:
(1) 从训练数据集中随即选取k条记录作为初始聚类C1, C2, …, Ck的原型。
(2) 对于任意一个训练记录X:
a.计算训练数据与每个聚类原型的差异度, 按照上述定义的差异度最小原则, 将数据集中的数据对象划分到离它最近的聚类原型所代表的聚类Cq中;
b.对于聚类Cq, 重新计算聚类原型;
(3) 重新计算每个记录与当前所有聚类原型间的距离, 如果发现一个记录距离其他聚类原型的距离比它本身所在聚类原型的距离要小, 那么把此对象分配给距离它最近的聚类, 并更新这两个聚类。
(4) 重复第三步, 直到没有一个记录改变聚类原型为止。
(5) 对于每个测试记录Z:
a.计算测试记录Z与聚类Ci (i=1…k) 原型的差异度, 根据差异度最小的原则, 找出差异度最小的聚类Cr;
b.通过阈值规则判断测试记录Z是否异常;
1.2 基于ID3决策树的异常检测
1986年Quinlan提出的ID3算法[5]是基于决策树学习中最重要的一种算法, 最具代表性。
对于每个属性A, 信息增益G表示为:
S为s个训练记录的集合, Sv为属性A的值为v时S的子集。假设有m个类, 对每一个训练记录分类所需的信息熵为:
pi表示训练记录属于类Ci的概率, pi定义为:
Nx表示在类Cx中训练记录的个数。
综上所述, 基于ID3决策树的异常检测算法步骤描述如下:
1.计算所有属性的信息增益, 选择信息增益最大的属性, 标记为B, 作为根节点;
2. 由根节点属性的不同取值建立分支;
3.采用递归 (Recursively) 的方法, 对各分支的子集S-{SB}仍然选择信息增益最大的属性作为子节点, 直到所有的子集包含同一类别的记录为止;
4.在入侵检测中, 使用正常行为的记录作为训练数据。对于每一个测试记录Z, 根据决策树转换为IF…THEN这样的规则, 通过规则匹配来预测数据, 如果可以到达叶子结点, 则该测试记录正常, 反之则异常。
2、基于k-prototypes+ID3的异常检测
在异常检测方法中, 大多数采用的训练方法是从一个完全正常的数据集中学习和建立正常行为的模型, 然后根据新的数据偏离正常模型的程度, 判断是否为异常数据。本文使用正常行为数据集作为训练数据。
给定训练数据集Xi, 每一个记录都是n维向量。基于k-prototypes+ID3的异常检测算法分为两个阶段:1) 训练阶段;2) 检测阶段。
训练阶段:首先应用k-prototypes将训练数据分为k个不相交的聚类C1, C2, …, Ck;然后, 在每一个聚类Ci使用ID3算法建立决策树DTi。kprototypes算法保证每一个训练记录仅与一个聚类相关联, 如果一个聚类中出现重叠和子组的情况, 第二步建立决策树的分类过程可以进一步的细致化分类。
两种算法的有效结合, 可以提高任一种算法单独使用时的性能。例如:对于k-prototypes算法, 如何选择合适的参数k很重要, 如果选择不当, 将会带来算法精确度的下降。如果k值选择过小, 在聚类的过程中, 就会出现重叠子组在一个聚类中的情况。这个问题将在对每个聚类进行决策树创建的过程中得到解决。
检测过程具体如下:
DT1, DT2, …, DTk为在聚类C1, C2, …, Ck上创建的决策树。Q1, Q2, …, Qk为聚类C1, C2, …, Ck的原型。
每一个测试记录Zi (1≤i≤n) :
1.计算测试记录Zi与聚类Ci (i=1…k) 原型Qi的差异度, 根据差异度最小的原则, 找出差异度最小的f个聚类G1, G2, …, Gf, 作为候选聚类。
2. 在候选聚类中, 计算k-prototypes异常度值AS (anomaly scores) 。计算方法如下:
Q1, Q2, …, Qf为聚类G1, G2, …, Gf的原型, 测试记录Zi相对于每个候选聚类的差异度由下式确定:
每个候选聚类的异常度值定义如下:
上式表示候选聚类Cj中训练记录的数量占总训练记录数的比例。
上式中的为转换因子 (SF) 。
3. 对于测试记录Zi, 候选聚类G1, G2, …, Gf所关联的决策树的规则, 判断记录是否异常, 记录异常度值Dj。
4.将候选聚类k-prototypes异常度值和决策树的异常度值作为整体异常度值候选集保存到矩阵AS[f×2]中, 根据一定规则将两种算法的异常度值Pj和Dj结合起来判断, 得到最终的异常度值AS。
5.组合规则
表1为一个测试记录异常度值AS矩阵的实例。在矩阵AS中, 异常度值Pj和Dj的存放顺序按照Q1, Q2, …, Qf的大小排列, 满足条件Q1<Q2<…<Qf。根据最近一致的规则[6], 选择最先符合以下条件的组合作为最终AS的值。
规则如下:
τ为事先设定的阈值。例如:如表1所示, 如果P1大于τ则继续向后检查, 如果P2大于τ, D2等于1, 则确定AS的值为1, 即标志检测记录为异常。
3、仿真实验
3.1 实验数据集
选取由MIT林肯实验室公开提供的DARPA入侵检测评价计划中的网络通信数据集经处理后最终形成的KDDCup99[7]训练数据集进行仿真。该数据集是模拟局域网上采集来的9个星期的网络连接数据, 包含了约4 900 000条模拟攻击记录, 总共22种攻击, 分为DoS、R2L、U2R、PROBE四大类。每条记录由41个特征刻画, 其中包括7个分类特征和34个数值型特征。
实验开始前从原始数据集中过滤掉了一些攻击, 过滤后的数据集包含1.2%左右的攻击记录。过滤后的数据集分成两个部分, 一部分作为训练数据集。训练数据集中均为正常数据记录, 共20000条, 同时在剩余的数据中选取相同数目的数据作为测试集, 测试集中异常数据的比例为5%。
3.2 参数的选择
γ是分类属性与数值属性对整体相异度的影响的权重。如果γ偏大, 表示聚类过程中整体相异度偏重依赖分类属性;反之, 如果γ偏小, 表示整体相异度偏重依赖于数值属性。文献[8][9]指出γ与σ有关, σ定义为聚类中数值属性的平均标准差, γ的值可以由σ来参考确定, 一般选择范围为1/3σ～2/3σ。文献[9]的实验表明, γ取值1/2σ时实验效果最好。
3.3 实验结果分析
入侵检测系统的性能主要由系统的检测率和误报率两个方面的值来体现。通过描绘检测率和误报率的ROC曲线, 可以对入侵检测算法的性能有一个感性的认识。
检测率 (TPR) =检测正确数/实验总数;
误报率 (FPR) =被检测为攻击的正常数据数/正常数据;
在相同的实验环境和相同的实验数据下, 对本文算法, k-prototypes, ID3算法进行试验, K=100, 并进行对比, 最终得到的ROC曲线如图1所示;
由图1可以看到在误报率相同的情况下, 本文提出的方法相对于k-prototypes和ID3方法而言具有更高的检测率, 并且本方法的检测率与误报率的相对值较为合理, 因此具有更高的执行效率。
4、结束语
本文针对目前异常检测技术训练时处理混合属性数据能力欠缺, 误报率高的问题, 提出一种改进的无监督异常检测算法。在对训练集进行无监督学习的过程中, 能够有效地处理数值型属性和分类属性。与ID3决策树算法的结合能够有效地解决k-prototypes算法局部最优的问题以及对初始聚类数的选取有较强的依赖性等缺陷。本文所提出的方法在实践中还需根据实际应用情况作进一步的改进, 如初始聚类原型随机选取对聚类结果的影响等, 以提高其性能。
参考文献
[1]Portnoy L, Eskin E, Stolfo S J.Intrusion Detection withUnlabeled Data Using Clustering[C].Proceedings of ACMCSS Workshop on Data Mining Applied to Security, NewYork:ACM Press, 2001:123-130.
[2]朱岸青, 张昌城.基于数据挖掘的网络入侵检测技术研究[J].计算机工程与设计, 2008, 29 (2) :318-322.
[3]赵恒.数据挖掘中聚类若干问题研究[D].西安:西安电子科技大学, 2005.
[4]赵立江, 黄永青等.改进的混合属性数据聚类算法[J].计算机工程与设计, 2007, 28 (20) :4850-4852.
[5]黄文.决策树的经典算法:ID3与C4.5[J].四川文理学院学报 (自然科学) , 2007, 17 (5) :16-18.
[6]Shekhar R.Gaddam, Vir V.Phoha, Kiran S.Balagani, “K-means+ID3:A Novel Method for Supervised AnomalyDetection by Cascding K-means Clustering and ID3 De-tection Tree Learning Methods”[J], IEEE Transactions onKnowledge and Data Engineering, Vol.19, No.3, March2007:345-354.
[7]KDD-CUP-99 data set[EB/OL]http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html.
[8]刘惟一, 李维华, 岳昆.智能数据分析[M].北京:科学出版社, 2007:137-138.
混合属性数据 第2篇
[关键词]大数据挖掘技术；侦查；法律属性；技术侦查措施；强制侦查措施
[中图分类号]D901 [文献标识码]A [文章编号]1671-8372（2015）02-0071-03
随着人类社会快步迈入海量数据信息交换、处理和应用的计算机大数据时代，与其伴生的大数据挖掘技术正得到最广泛运用。大数据挖掘技术，指在大数据环境下，从大型数据库或数据仓库中提取人们需要的知识和信息的各类技术之总称。大数据挖掘技术在当代犯罪侦查活动中也得到了广泛的应用。以当今世界科技和法律最发达的美国为例，美国所有银行都被强制要求安装基于大数据挖掘技术而设计的金融犯罪人工智能识别网络。但是，对于该技术的法律属性学界探讨的并不多，而这又是一个牵涉大数据挖掘技术在侦查中科学合理运用的前提。若其法律属性界定不够清晰，则会令实践操作束手束脚。笔者认为，大数据挖掘技术法律属性界定主要需辨析两方面问题：其一，大数据挖掘技术究竟是技术侦查措施还是仅仅属于辅助统计分析手段？其二，若属于技术侦查措施，那它究竟系任意侦查措施抑或强制侦查措施？
一、技术侦查措施抑或辅助统计分析手段
所谓技术侦查措施，即公安机关、人民检察院等依照侦查犯罪需要，经过严格审批程序后借助技术设备收集证据或查获犯罪嫌疑人的一类特殊侦查措施。毫无疑问，大数据挖掘技术主要依靠高度发达的计算机和互联网来展开数据整合分析，以完成取证工作，它理当属于一种技术手段。但该技术手段是否达到了技术侦查措施的高度呢？毕竟对侦查中的大数据挖掘技术来说，其用途多集中于从碎片化的信息中归纳汇总，进而分析出信息的共性和个性，从而找到亟须的侦查情报。从汇总归类的视角看，大数据挖掘技术具备统计分析的特征。虽然如此，笔者仍认为，将大数据挖掘技术界定为技术侦查措施更为合适。
首先，大数据挖掘技术在信息社会的侦查活动中独立运用的范围愈发广泛。伴随人类全面进入大数据环境下的信息社会，信息俨然已成为人们学习、工作、生活最重要的资源。而犯罪作为最广义的人类行为之一，它的进行也无法离开信息。如此一来，当今时代若要实现对犯罪行为的有效遏制，侦查活动中就必然需要大数据挖掘技术对各类信息展开高质量解读。且大数据挖掘技术的这类广泛运用是一种独立性的运用，因为若单独从使用范围来说，EXCEL、SPSS、EVIEWS等软件工具在数据统计汇总方面的使用范围更广，但这些软件工具仅仅只是一类“工具”，根本无法上升到“技术”的高度，他们只是帮助人们进行初步数据资料整合。大数据挖掘技术作为一整套数据信息整合技术，早就具备了较高的智能化色彩，相关通讯信息、身份信息、住宿信息、车辆通行信息、存贷款信息等均自动纳入了它的分析汇总整合范畴，以助于打击犯罪。如英国格洛斯特郡警察局便是启用数据挖掘分类和预测功能成功找到了辖区抢劫罪的犯罪根源，弥补了传统刑侦手段的不足；近年，我国公安机关在“向科技要警力”等目标指引下，也逐渐建构起了较全面的综合信息化网络，以收集的大量基础业务数据为基石实施了富有成效的犯罪规律分析工作。由此可见，大数据挖掘技术在侦查活动中的独立运用范围日益广泛，绝非寻常辅助统计分析手段可比。
第二，大数据挖掘技术的运用难免造成对普通民众正当权益的侵害。大数据挖掘技术系对浩如烟海的数据信息进行提炼整合的新兴计算机技术，信息的获取难免会令相关普通民众的正当权益受到侵害，其中最易受到侵犯的权益包括普通民众隐私权、言论自由权、通讯自由权以及私有财产权。毕竟在信息社会各类人际交往活动都会留下信息的痕迹，这些信息有相关人员自愿公开的（如个人未作任何访问限制的微博日记），也有相关人员刻意或必须隐瞒的（如个人家庭地址、银行卡密码等）。倘若普通民众不愿意外人知晓的信息在数据整合过程中被获取了，这无疑是对他们隐私权的侵犯。而隐私权受侵害多了，言论自由和通讯自由权也会随之受到侵害。因为当普通民众觉察到自己的隐私有可能被侦查机关借助大数据挖掘技术以打击犯罪的名义肆意践踏时，他们便会人人自危，不敢畅所欲言，遑论言论自由权和通讯自由权。兼之被收集的信息很多与个人财产密切相关，如网络购物消费信息、私人存贷款信息等等，通过获取此类信息，普通民众私人财产甚至有可能被窃取，其私有财产权便无法得到妥善保护。所以，倘若大数据挖掘技术仅仅是一种类似于EXCEL、SPSS软件工具的辅助统计分析手段，就绝不可能造成如此大的权益侵害，这种巨大危害性必然要求将其升格为技术侦查措施，使其受到法律的严格约束。“法律对权利来讲是一种稳定器，而对于失控的权力来讲则是一种抑制器。”
第三，大数据挖掘技术符合当前学界和司法实务界对技术侦查措施的主流界定。现今学界和司法实务界对技术侦查措施的界定主要包括两种观点：其一是以侦查措施的技术含金量作为参照，需要启用现代高科技装备查清案情的都属技术侦查措施；其二是以侦查措施实施的隐密程度作为参照，秘密侦查措施均可称为技术侦查措施。大数据挖掘技术是随着电子计算机和互联网高速发展而产生的，故从技术含金量角度它完全符合技术侦查措施的要求；绝大多数情况下，借助大数据挖掘技术展开的相关数据信息收集很难被非专业人士察觉，特别是当电子计算机和互联网发展到“云”阶段，依靠自身公权力的便利和高技术设备，侦查机关能更容易地绕开个人PC终端直接在“云端”（网络服务提供商的服务器）获取大量信息，所以从隐秘程度上看，大数据挖掘技术也可界定为技术侦查措施。
二、任意侦查措施抑或强制侦查措施
从前述可知，大数据挖掘技术在法律属性界定上理当属于技术侦查措施而非简单的辅助统计分析手段。但这种定性还仅是初步的前提性认定，只解决了大数据挖掘技术是否应纳入技术侦查措施范畴的问题。侦查措施广义上又包括任意侦查措施和强制侦查措施，前者系被侦查人同意或允诺下进行的侦查，后者则系未征得被侦查人同意或允诺而强行违背其意愿展开的侦查。任意侦查措施体现了对被侦查人的尊重，被侦查人的正当权益被侵害程度相对较轻；强制侦查措施带有较大的强迫特征，被侦查人正当权益遭受侵害程度相对较大，故强制侦查措施历来都是法律规制的重点。因此，是否要对具体侦查措施实施有效法律规制，首先应先在法律属性上完成其任意性或强制性的准确认定。笔者认为，将大数据挖掘技术定性成强制侦查措施更符合侦查措施划分的法理要求。
对任意侦查措施和强制侦查措施的划分，日本学界走在世界前列。迄今为止，日本学界就此形成了传统见解、权利侵害说、新强制处分说和私生活秘密保障说等几种主流法理观点。传统见解认为，必须有物理上的有形强制力存在方可构成强制侦查措施；权利侵害说主张，只要被侦查人正当权益遭受侵害即构成强制侦查措施；新强制处分说主张，强制侦查措施必须以事实上的强迫行为和课以法律义务为基本构成要件；私生活秘密保障说则认为，大凡对个人私生活秘密造成侵犯便构成强制侦查措施。这几种主流观点中，传统见解因更多着眼物理有形强制力，伴随人权保障意识的增强和技术侦查手段的运用，现已逐步被淡化。而根据其他三种观点，侦查中的大数据挖掘技术无疑符合强制侦查措施的判定。首先，从权利侵害说来看，大数据挖掘技术的运用，导致普通民众隐私权、言论自由权、通讯自由权和私有财产权这些正当权益极易遭受损害。其次，从新强制处分说来看，尽管大数据挖掘技术作为一类看不见摸不着的计算机虚拟技术，不可能给被侦查人带来物理有形强制力，但它依旧会出现事实上的强迫行为（以现代高科技信息技术强行去获取被侦查人及相关人员私密信息）并课以法律义务（在打击犯罪的正当目的下迫使相关人员私密信息被获取的结果合法化）。再次，从私生活秘密保障说来看，既然大数据挖掘技术的应用极易损伤普通民众隐私权、言论自由权、通讯自由权和私有财产权，个人私生活秘密自会大受侵害。以2012年闹得沸沸扬扬的美国“棱镜门”事件为例，美英情报机构利用网络监听、大数据挖掘等高科技信息获取技术，甚至成功实施了对各国首脑戒备森严的电子邮件的截获。连国家政要都不能幸免，普通民众个人私生活就更无秘密可言了。
即便侦查机关采用大数据挖掘技术进行数据整合获取的某些信息系被侦查人等相关人员自愿提供的，也不能否定大数据挖掘技术的强制侦查措施性质。主要原因有三：一是大多普通民众并不具备专业计算机和互联网知识，不少场合下的所谓“同意”或“允诺”未必真的就是其本意。譬如非计算机专业的普通网友就很难知晓服务器端自发生成的cookie用途，即便网络服务商明确告知可以禁用cookie，普通网友也不一定能够完全掌握删除这些易泄露自身隐私数据的cookie的技巧。在这种情形下，若普通网友做出了允许侦查机关通过cookie以大数据挖掘技术收集整合其信息的承诺，那么自愿性在很大程度上也是大打折扣的；二是即便某些信息是相关人员自愿公布并不带有私密色彩，但受过专业训练的侦查人员依然能够凭借此类信息解读出众多关键或敏感话题，这往往是自愿公布信息的当事人所料不及的。例如2010年央视体育频道女记者徐莉在某论坛上随意发布了几张自己购买的鞋架照片，竟被好事网友从鞋的尺码、房屋布局等不起眼的信息推断出了她的毕业院校、身高、工作单位、姓名和婚姻状况等隐私。2012年原陕西省安全生产监督管理局局长“表哥”杨达才也因在互联网中公开披露的为数不多的几张照片，被细心的网友发现其有10多块名表和价值不菲的皮带、眼镜，从而推断出他的消费远远超过同级别公务员工资水平，必然有严重的经济问题。非专业人士尚且能发挥出“福尔摩斯”的奇效，训练有素的侦查人员借助数据挖掘技术的效果就更可想而知了。三是即便信息收集整合是在个别被侦查人等相关人员真正同意或允诺下进行的，不存在丝毫正当权益遭受侵害的现象，但考虑到大数据挖掘技术运用整体上带来的负面效应，也宜将其纳入强制侦查措施范畴，使其受到法律严格规制，从而确保其能得到合理使用。不过，对被侦查人等相关人员真正同意或允诺下使用的大数据挖掘技术，考虑到当事人的自愿性，未来司法实践中的监管不妨适当灵活些。
三、结语
混合属性数据 第3篇
粗糙集(Rough Set,RS)理论是波兰科学家Zdzislaw Pawak在20世纪80年代初提出的一种新的处理模糊和不确定性知识的数学工具。它的主要思想是将数据分为条件属性和决策属性,通过知识约简分析属性的重要性。其特点是不需要预先给定某些属性的数量描述,直接从给定问题的描述集合出发,通过不可分辨关系找出该问题的内在规律。目前,粗糙集理论已被成功运用在机器学、决策分析、过程控制、模式识别与数据挖掘等领域。
粗糙集中,属性约简是其核心问题。一般来讲,在决策表中,有些属性是冗余的,若将这些属性删除,不仅不会改变决策表的分类或决策能力,反而会提高系统潜在知识的清晰度。因此,属性选择一直是机器学习和数据挖掘的重要内容。
目前,对于粗糙集属性约简的方法有很多,例如,基于差别矩阵的启发式粗糙集属性约简算法[1]、基于信息熵的属性约简算法[2]、基于重要度的属性约简算法[3] 、基于相容度的属性约简算法等。
针对目前粗糙集属性约简算法中时间效率较低的问题,本文利用相容度和重要度模型,通过相容度模型的快速筛选和重要度模型的完善、补充,使得算法在保证约简集完整性的基础上,算法效率得到提高。
1 粗糙集属性约简法
1.1 知识表达系统
知识表达系统也称为信息系统,通常信息系统可以用四元组S=(U,A,V,f)来表示,其中[4]
U:对象的非空有限集合,称为论域;
A:属性的非空有限集合;
f:UAV,是对每个对象x的每个属性ai赋予一个信息值Vai,即∀ai∈A,x∈U, f(x,ai)∈V。
1.2 决策算法的相容度
设S=(U,A,V,f)是一个信息系统,令C是条件属性,D是决策属性,且C,D⊆A,称D完全依赖于C。如果在S中存在C1⇒D1,C2⇒D2,,Cn⇒Dn且Cx≠Cy(x,y=1,2,,n)则说明Cx与Cy相容。
任何一个蕴含式φψ称为一个决策规则。φ,ψ分别是φψ的前件和后件。若φψ在S中为真,则称φψ在S中相容。否则不相容。对决策规则φψ,如果φ是一个C的基本公式,ψ是一个D的基本公式,则称φψ是一个CD基本决策规则,简称CD规则。
任何一个决策规则的有限集称为一个决策算法,对应的,任何一个基本规则的有限集称为一个基本决策算法。如果一个基本决策算法中,其所有的决策规则都是CD规则,则称该算法是一个CD决策算法,简称CD算法,记作(C,D)。
设(C,D)是S中的一个CD算法,相容的CD规则所构成的集合称为该算法的正区域,记作PosC(D)。则属性ai的相容度计算如式(1)。
式(1)中,当kai=1时,该算法是相容的;当kai≠1时,D部分依赖于C,这时称D对C的依赖度为kai,即相容度为kai。
1.3 决策属性的重要度[5]
为了找出某些属性的重要性,通常的方法是从决策表中去除某些属性,再考察没有该属性后分类是否产生大的变化。若去除该属性后,分类产生了大的变化,说明该属性的强度大,即重要度大;若去除该属性后,分类没有产生大的变化,说明该属性强度小,即重要度小。
令C和D分别为条件属性集和决策属性集,属性子集C'⊆C关于D的重要度定义为式(2)。
式(2)中,γC(D)=kai,特别当C′={ai}时,属性ai∈C关于D的重要度为式(3)。
2 算法设计
2.1 算法基本思想
由于粗糙集在很多领域均有应用,使得前人在经典的粗糙集模型基础上进行了很多探索,发展出各种适用于各个领域的粗糙集约简算法。本文在经典粗糙集理论上,有效地结合了属性的相容度算法和重要度算法,首先利用相容度算法快速便捷从众多属性中将核集筛选出来,然后利用重要度算法将从非核集中选择最优、最好、最重要的属性加入核集中,使得核集变得更有说服力,更具完整性。
基于之前的分析,本文提出了一种新的约简方法,设信息系统S=(U,V,A,f),A=C∪D,C∩D=∅,利用相容度定义,当Cx≠Cy⇒Cx与Cy相容,即相容度kai为:
当且仅当kai≠1时,将ai放入Core(P)。设C'=C-Core(P),因为
按照重要度定义计算求解重要度σCD(ai),把重要度σCD(ai)值,按照从大到小的顺序排列,将最大的σCD(ai)值所对应的属性ai加入Core(P)中,最终得到约简核集Core(P)。
2.2 算法描述
通过分析本文算法的基本思路,现将本文详细算法描述如下:
Input:某已知信息系统,记为S。
Output:信息系统S的约简值。
本文所设计方法步骤如下:
Step1:利用公式(4),求解各属性的相容度kai。
Step2:通过所求出的各属性的相容度kai,确定kai≠1的属性,将kai≠1的属性记作:
Core(P)={ai|kai≠1}。
Step3:去除k≠1的属性,将k=1的属性按照属性重要度方法,利用公式(3),计算剩余属性的重要度。通过属性重要度计算,把σC'D(ai)值按照从大到小排列,将σC'D(ai)的最大值的属性加入Core(P)中。若σC'D(ai)值相等,则舍弃其余属性,保持Core(P)不变。
Step4:输出信息系统最简约简值,终止。
2.3 算法实现
算法流程图,如图1所示。
3 实验验证与结果
由于柴油发动机子系统在使用过程中,会因诸多因素造成发动机子系统出现故障。利用本文提出的算法对柴油发动机子系统出现故障的因素的进行分析与研究。
3.1 实例验证
为了验证算法的正确性和性能。选取柴油发动机子系统故障决策表[6],如表1所示。决策表中所列的数据在Windows XP 2002版,CPU 2.60 Hz,内存988 MB上编程实现。
根据本文算法,利用相容度计算求出k≠1的属性值,并把属性值加入Core(P)集合中,求出Core(P)={Z1,Z2,Z3,Z4,Z6,Z7}。当得到核集后,去除核集,求剩余属性的重要性:
σC′D(e)=σC′D(h)=σC′D(i)=0,根据算法中Step3,最终得到Core(P)={Z1,Z2,Z3,Z4,Z6,Z7},最终约简表如表2所示。
3.2 实验结果
利用表1数据,分别采用本文算法、重要度(SIG)算法[7]、可辨识矩阵的快速约简算法[8]进行计算,结果如表3所示。
由表3可见,三种算法得出的最终约简核集均为{Z1,Z2,Z3,Z4,Z6,Z7},而本文算法运行时间最少。
本文还采用大量数据进行了多次实验均可得到相同的核集。实验结果表明:①本文算法保证了约简核集的完整性;②如果使用重要度约简算法进行属性约简,算法效率很低;③若使用可辨识矩阵快速约简算法,在算法时间效率上与本文算法相比,本文算法时间效率要高于可辨识矩阵快速算法;④本文的时间效率均高于另外两种算法,运行效率比较如图2为所示。
由图2可以看出,本文的相容度与重要度混合算法的运行时间变化微小,时间效率变化曲线相对平稳;而文献[7]和文献[8]给出的算法运行时间增长过快,当处理较大数据量时,可能会出现计算时间较长的现象,等待时间过长。
4 结论
以高效快捷的方式获得约简属性集是粗糙集约简知识获取的关键步骤。本文将相容度和重要度很好地融合,使得粗糙集的属性约简效率得到了提高。特别在数据样本迅速增大时,本文算法的运行时间增加并不明显,且能保证属性约简结果的完整性。
参考文献
[1]田志军,李芳芳.基于差别矩阵的启发式粗糙集属性约简算法研究.科技通报,2012;28(2):134—136
[2]丁守祯,桑琳,朱全英,等.基于信息熵的粗糙集属性约简及其应用.计算机工程与应用,2007;43(35):245—248
[3]陈林,邓大勇,闫电勋.基于属性重要度并行约简算法的优化.南京大学学报(自然科学),2012;48(4):376—382
[4]钱锋,陈海山,姜青山.结合模糊集理论的粗糙集属性约简算法.计算机应用研究,2007;24(11):93—95
[5]张文修,吴伟志,梁吉业,等.粗糙集理论与方法.北京:科学出版社,2003
[6]Jagerskupper J,Witt C.Rigorous runtime analysis of a(u+1)ES for the sphere function.Evolutionary Strategies and Evolutionary Programming.New York:ACM Press,2005:849—856
[7]李伟涛,刘琼荪.粗糙集属性约简的一种新算法.电脑知识与技术,2010;6(35):10153—10155
混合属性数据 第4篇
随着互联网的快速发展,Web服务得以广泛运用,相关技术不断进步和发展。在Internet上涌现了大量的服务,为了选择最合适的服务,服务请求者通常首先搜索满足自身功能性需求的服务,发布在Internet上的多个服务(功能相似)都符合服务请求者功能性需求时,用户需要依据服务的非功能性属性尤其是服务质量Qo S来进行服务选择。
从公开文献中可以发现,支持Qo S的服务选择方法有基于Qo S语义
然而,目前基于Qo S的服务选择方法中大都假设Qo S属性的取值为一个确定的实数,未考虑Qo S属性的模糊性。事实上,由于Qo S属性的多样性以及服务资源调度的灵活性,使得服务提供者很难公布Qo S属性的精确信息
1 Qo S属性描述
为了对比功能相似服务质量却不同的服务,需要构建服务的Qo S属性模型。服务的质量信息可以采用不同的Qo S属性进行描述,本文通过费用、可用性、响应时间、可靠性和声誉等5个属性来建立Qo S属性模型:
1)费用(Price):费用是服务请求者调用服务时必须支付的货币量,在短期内基本不会发生变化,该值可用精确数值型表示。
2)可用性(Availability):可用性是服务在给定的一段时间内可访问的概率,因此将其表示为一个介于[0,1]区间的精确实数。
3)响应时间(Time):响应时间表示从服务请求者发出调用申请到最终获取服务执行结果所需时间。由于网络环境的动态性以及用户请求数的变化,响应时间T具有一定的波动特性,因此本文将响应时间T表示成一个区间型数值。
4)可靠性(Reliability):可靠性是衡量服务整体性能的指标量;其属性值来源于用户在调用服务过程中,对该服务的性能指标所作出的主观反馈。对于一个普通用户来说,通常都会以极高、很高、高、较高、一般、较低、低、很低、极低等语言型数值来表达可靠性。虽然语言型的数据具有合理的描述能力,但是无法直接参与Qo S的度量计算,因此本文采用三角模糊数型对其量化。Re=(al,am,au),其中al,am,au分别表示三角模糊数的下界、核和上界值。三角模糊数的取值一般由领域专家(Qo S专家和用户专家)给出
5)声誉(Reputation):声誉是衡量服务可信赖性的Qo S属性,它主要依赖客户使用该服务的经历,由客户反馈得到,但是由于一些恶意打击,客户主观的声誉值缺少一定的可信性。因此,本文采用文献
2 主观权重的序关系向量表示
由于服务存在多个Qo S属性,因此,当用户面临多个Qo S需求间进行比较决策时,需要考虑用户对不同Qo S属性的需求偏好
对于用户给出的序关系型权重信息vi,最终的权重值应该尽可能地与它贴近,以此确保属性的主观权重wis能够充分反映用户对Qo S属性的偏好,即主观权重wis尽可能地贴近vi。将某候选服务第i个属性与第j个属性间的序关系型权重信息的贴近度定义为:
那么候选服务所有m个Qo S属性的序关系型权重信息的总贴近度和为:
为了获得各Qo S属性最优的主观权重,需要保证总贴近度值最小,据此可构造如下最优化模型:
求解该二次规划模型,可得到最优解,即主观权重为ws=(w1s,w2s,…,wms)。由式(1)可知,w1s:w2s,…,:wms=v1:v2,…,:vm,即所有的dij全部为0,目标函数达到最优值0(目标函数是非负的,最小值至少取零)。因此,只需知道用户的偏好次序o,易得序关系向量vi和主观权重wis。
3 客观权重的熵权型表示
为了能让Qo S属性的度量结果确切地体现服务的整体性能,以避免服务选择中用户偏好的局限性,本文提出客观权重的熵权法。熵权法
设现有n个功能相似的候选服务WS={ws1,ws2,…,wsn},对于每个候选服务都有以上的5个通用属性,其中,可用性、可靠性、声誉为正向属性(表现值越大越好的属性),费用和响应时间为负向属性(表现值越大越劣的属性)。那么n个服务的Qo S属性值可以构成一个矩阵A=[aij]n×5,aij表示第i个服务的第j个属性的Qo S取值。
为了统一数据量纲,需要将决策矩阵A=[aij]n×5规范为标准化决策矩阵B=(bij)n×5。
步骤如表1所示。
表1 客观权重步骤示意
熵权的定义如下:
定义1对于一个具有n个候选服务、m个属性的多属性决策问题,属性j(1≤j≤m)的熵定义为:
定义2目前对于区间数值型、三角模糊数值型的客观赋权方法主要有区间数指标熵值法,它通过对各端点值求平均值,将区间型和三角模糊数型数值转化为实数型数值。然后利用平均值的信息熵来反映,但是这种方法显然不能充分反映各端点值间的偏差程度,存在一定的不足。在这里,本文综合利用各端点值输出的信息熵,以其平均值Ej来反映
这里,常数且当f=0,fijlnfij=0。属性j的客观权重wjo定义为:,其中,Ej*=1-Ej。于是得到各属性的客观权重为wo=(w1o,w2o,…,wmo),显然0≤wjo≤1,且符合权重的基本要求。
将主观权重和客观权重相结合,可得到各属性的综合权重:wj=αwjs+(1-α)wjo,j=1,2,…,m,其中α∈[0,1]值可根据用户主观偏好的重要性而定。该系数表示服务选择中对用户偏好的依赖程度,即基于Qo S的服务选择结果中主观与客观的比值,若忽略用户偏好,α取0;若服务选择完全依赖用户偏好,α取1。其值可依据用户主观偏好的重要性而定。显然,当α越大,主观权重对于综合权重的影响也就越明显。
4 基于相对优势度算法的服务排序
现有的针对混合Qo S属性的服务选择问题的解决方法主要有两种:一种是先将混合的属性信息进行一致化,然后进行排序度量。所谓一致化就是将混合的属性信息转换成同一种数据类型,在这个过程中会造成混合属性信息的丢失,最后的决策结果很难具有较高的精确性。另一类则是利用扩展TOPSIS算法(technique for order preference by similarity to a ideal solution),依据不同类型数据之间的距离
为了有效解决现有方法的不足,本文采用相对优势度算法解决服务选择问题。相对优势是国际贸易学的重要理论,它的原理是指一个生产者提供相同的服务或生产相同的商品时成本优于另一个生产者。因而,相对优势原理借用到服务选择过程中,就可以理解成在服务提供者提供的众多功能相同的候选服务集中,比较各个服务的服务质量,从中筛选出服务质量(Qo S)相对最具优势的服务,即优势度最高的服务。
根据服务Qo S属性之间可以相互补偿的特点,建立基于相对优势度的排序方法
图1 基于相对优势度的Web服务排序
下面分别定义了精确数值型、区间数值型、三角模糊数值型中任意两个数据之间的相对优势。
定义3设a、b是两个实数,则a对于b的优势可以表示为:
定义4设是两个正区间数,则的优势可以表示为:
定义5设a=(al,am,au)、b=(bl,bm,bu)是两个三角模糊数,其中0<al≤am≤au,0<bl≤bm≤bu,则a对于b的优势可以表示为:
其中,la=au-al,lb=bu-bl。
相对优势度的排序方法:
第一步依据有限候选服务的各个属性值,计算服务wsi相对于服务wsj在每个属性at上的优势s(wsit,wsjt)=s(ait,ajt),i,j=1,2,…,n,i≠j;
当at属性值是实数时,s(ait,ajt)按式(5)计算;
当at属性值是区间时,s(ait,ajt)按式(6)计算;
当at属性值是三角模糊数时,s(ait,ajt)按式(7)计算。
第二步集结所有的s(wsit,wsjt)值,计算服务wsi相对于服务wsj在每个属性at上的优势度Dt(wsit,wsjt);
若at是正向属性,则
若at是负向属性,则
第三步计算服务wsi相对于服务wsj在所有属性上的优势度:
其中,wt是属性at的综合权重。
第四步计算每个服务wsi相对于其他所有服务的总优势度:
第五步根据D(wsi)排序。D(wsi)越大,说明服务wsi相对于其他服务的总优势度值越大,该服务排序越靠前。
5 实例及实验
基于文献
表2 候选服务的Qo S属性值
1)为了验证本文算法的可行性,分别利用本文相对优势度算法、混合信息一致化算法(通过求区间型和三角模糊型数值各端点值的平均数,将混合的属性信息转换成精确实数)和文献
图2 三种算法的排序结果
可以看出,基于相对优势度算法与基于TOPSIS算法的排序结果基本相同,基于混合信息一致化算法排序结果却有较明显的差异。基于混合信息一致化算法所获取的最优服务是ws1,而利用本文的相对优势度算法与TOPSIS算法获取的最优服务均是ws7。由表2知,服务ws7与服务ws1相比,尽管服务ws1响应时间的最小值优于ws7,但它们在费用、可靠性这两个属性上取值相同,且ws7在可用性与声誉属性上的Qo S值均明显优于ws1。因此,ws7明显优于ws1,从而说明本文相对优势度算法不仅可行且有效,而混合信息一致化算法精确性不高。
2)不同算法执行效率的对比。由图3可以看到,随着候选服务数目的增加,两种算法的平均运行时间呈递增形式,这是符合实际情况的。另外,基于相对优势度算法的执行效率要优于基于TOPSIS算法的执行效率,因为TOPSIS算法要对属性矩阵进行归一化,而且需计算较复杂的欧氏距离,在运行时间上明显大于相对优势度算法。
图3 两种算法运行效率的对比
3)分析基于需求偏好的不同赋权模式的服务选择。当α=0时,即在计算Qo S属性权重时,完全依赖于用户对Qo S的需求偏好,称其为需求偏好的主观赋权模式;当α=1时,即在计算Qo S属性权重时,忽略用户的需求偏好,仅考虑Qo S属性值客观数据,称其为需求偏好的客观赋权模式;当α=0.5时,即在计算Qo S属性权重时,既考虑用户的需求偏好又考虑Qo S属性值,称为需求偏好的主客观赋权模式。候选服务的总优势度如表3所示。
表3 候选服务的总优势度
选取排序前四的4个候选服务,计算它们在各个Qo S属性上的均值(在计算响应时间时,取区间左右两端值的平均值)。为了能在一个图中直观显示与比较基于不同赋权模式的服务选择的排序结果,将可用性、声誉的属性值放大100倍,费用和响应时间的属性值缩小10倍,如图4所示。
图4不同赋权模式的服务选择结果对比
由图4可知,主观赋权模式分别在费用、声誉达到最大,但可用性偏低,响应时间偏高,用户偏好使得服务Qo S属性信息的实际效用不一致;客观赋权模式在可用性、响应时间达到最优,但声誉、费用不是最佳;而主客观赋权模式在各个Qo S属性信息上表现了很好的中间性,既能表达用户偏好又能反映服务Qo S的客观特征,显示出更强的灵活特性。
6 结语
在开放的Internet环境中,描述服务Qo S属性的方式具有多样性。本文使用精确数值型、区间数值型、三角模糊数值型对Qo S属性值分别进行描述,利用序关系向量表示用户的主观偏好,同时利用熵权表示Qo S属性的客观权重。在此基础上,采用相对优势度算法给出混合型Qo S属性的服务选择过程。
混合属性数据 第5篇
随着信息技术的快速发展, 推荐技术作为信息过滤的一个重要手段, 已经成为电子商务领域里的一个重要的研究内容。目前, 几乎所有的大型商务网站, 比如国外的Amazon, Ebay, 国内的淘宝网, 当当网, 阿里巴巴等网站, 都采用各自的推荐系统。
协同过滤作为目前最成功的推荐算法被广泛地应用, 其目标是根据具有相似偏好的用户的观点向目标用户推荐新的商品。Sarwar等人[1]依据协同过滤所使用的事物之间的关联性, 将其区分为基于用户的协同过滤算法 (User-based) 与基于项目的协同过滤算法 (Item-based) 。
传统的基于用户的协同过滤, 没有考虑用户特征对推荐结果的影响, 同时忽视了项目之间的相似性;而传统基于项目的协同过滤算法, 没有考虑项目中属性之间的关联, 同时忽视了用户之间的相似性。不管是基于用户的协同过滤还是基于项目的协同过滤, 都存在数据稀疏性问题。针对这些问题, 本文提出一种基于用户特征和项目属性的混合协同过滤。仿真实验结果表明, 基于用户特征和项目属性的混合协同过滤能有效解决数据稀疏问题, 提高推荐系统的推荐精度。
本文组织结构如下:第二部分概述相关概念;第三部分介绍本文提出的算法;第四部分为实验分析;最后对本文进行总结。
1 相关概念
1.1 用户-项目评分矩阵
用户对项目的评分数据, 可以用一个m*n的矩阵表示, 其中行表示各个用户, 列表示相对应的项。m行代表共有m个用户, n列代表共有n个项目, 矩阵中的第i行第j列值表示第i个用户对项目j的评分, 用户-项目评分矩阵如图1所示。
1.2 基于用户的协同过滤
基于用户的协同过滤推荐技术 (User-based) [2]是指兴趣相似的用户感兴趣的商品也比较相似。因此, 为了得到目标用户喜爱的商品, 可以在不询问目标用户的同时分析与目标用户兴趣相似的其他所有用户, 其他所有用户最喜欢的商品可以被认为是目标用户喜爱的。
1.3 基于项目的协同过滤
基于项目的协同过滤推荐技术 (Item-based) 是由Sarwar教授于2001年在第十届国际www会议上提出的[3], 基于项目的协同过滤推荐技术的出发点是寻找与目标项目相似的其他项目集合, 假如用户对与目标项目相似的其他项目感兴趣, 那么用户对目标项目也感兴趣。
1.4 相关公式
基于用户的协同过滤推荐技术中, 用户相似性之间的度量方法主要有三种:余弦相似性、修正的余弦相似性和相关相似性。已有文献比较了三种度量方法, 我们根据结论选取相关相似性作为用户相似性的度量方法。
相关相似性又称为Pearson相关相似性, 用户i和j共同评分的项目集合用∩ij表示, 则用户i与用户j的相似性通过Pearson相关相似性度量方法为:
其中Ri, n表示用户-项目评分矩阵中用户i对项目n的评分, Rj, n表示用户j对项目n的评分, Ri和Rj分别表示用户i和用户j对项目的平均评分。设Ni是用户i的最近邻居用户集合, 则目标用户i对项目t预测评分Pi, t为:
同样, 基于项目的协同过滤推荐技术中也有三种计算项目相似性的度量方法:余弦相似性、修正的余弦相似性和相关相似性。我们也采用Pearson相关相似性作为项目相似性的度量方法。
项目i和j共同评分的用户集合用∪ij表示, 则项目i与项目j的相似性sim (i, j) 通过Pearson相关相似性度量方法为:
其中Rn, i表示用户n对i的评分, Ri和Rj分别表示用户i和用户j对项目的平均评分。
设Ni是项目i的最近邻居项目集合, 则目标用户u对项目i预测评分Pu, i为:
其中Ru, j表示用户u对j的评分, Rj表示用户j对项目的平均评分。
2、基于用户特征和项目属性的混合协同过滤
%不管是基于用户的协同过滤还是基于项目的协同过滤都存在着以下一些问题:
1) 精确性 (accuracy) 问题:基于用户的协同过滤在计算用户之间的相似性时只考虑用户单纯评分关系, 导致相似性结果不精确, 从而导致产生的最近邻居不准确;同样基于项目的协同过滤, 由于计算相似性结果不精确, 从而导致推荐的结果不准确。
2) 稀疏性 (sparsity) 问题:在许多推荐系统中, 每个用户涉及的信息量相当有限, 在一些大的推荐系统中, 用户的评估项目一般只占总项目的1%-2%, 造成评估矩阵数据相当稀疏, 难以找到相似用户集, 导致推荐效果大大降低。
在原有计算用户之间的相似性中加入用户特征的相似性, 在原有计算项目相似性的基础上加入项目属性之间的相似性, 这些在一定程度上都能够提高了算法的精确性。基于用户的协同过滤有时可以产生一些令人意想不到的推荐结果, 而不仅仅是用户原来就已经想到的推荐项目。将基于项目和基于用户协同过滤方法结合起来, 不但能够继承基于用户协同过滤奇异性发现的优点, 还能够缓解稀疏性问题。
2.1 用户特征和项目属性
传统的基于用户的协同过滤推荐技术只考虑用户单纯评分关系, 最终导致产生的推荐结果不准确。不同用户特征的人他们的兴趣爱好可能不一样, 而具有相同类别用户特征的人, 他们的兴趣爱好具有一定的相似性, 例如:女大学生可能都比较喜欢校园情景剧, 男孩子比较喜欢动画片, 老年人喜欢纪录片等等, 所以将用户特征的相似性与传统的基于用户的计算相似性方法相结合, 能够提高推荐系统的推荐精度。因此, 修改过后的计算用户a和用户b相识性度量方法sim User (a, b) 为:
其中, simA (a, b) 表示用户特征的相似性,
N表示所有参与计算的用户特征数, ai圮bi表示用户a在第i项特征上与用户b在第i项特征上的双向蕴涵, 即确定用户a和用户b的在i项上是否具有共同特征。本文中N取3, 即考虑用户特征三种, 年龄、用户性别、职业;φ表示影响因子, 这里我们取0.05;simB (a, b) 表示传统的基于用户的相似性计算方法, 这里即上述的公式 (1) 。
同样, 传统的基于项目的协同过滤技术只考虑了用户-项目评分矩阵数据, 从而得出不准确的邻居项目集合, 最终导致推荐结果不准确。一个项目可能包含多种属性, 例如一部电影它可能即是喜剧片也是动作片。目标项目的邻居项目的属性与目标项目的属性应当具有一定的相似性, 例如目标项目如果是喜剧片, 则我们产生的邻居项目中是喜剧片的可能性更高。所以将项目属性的相似性与传统的基于项目的计算相似性方法相结合, 能够提高推荐系统的推荐精度。因此, 修改过后的计算项目a和项目b相似性度量方法sim Item (a, b) 为:
其中, simM (a, b) [5]表示项目属性的相似性,
K表示项目a和项目b属性并集的数目, 表示ai和bi的双向蕴涵, 即确定ai和bi是否具有共同属性;σ为影响因子, 这里我们取0.15;即传统的计算项目相似性方法, 这里即上述公式 (3) 。
2.2 混合协同过滤
项目属性和用户特征在一定程度上都能够提高推荐的精度, 但是原本的用户评分矩阵依然存在稀疏性问题。为了进一步缓解稀疏性问题, 本文采用基于项目属性的协同过滤方法预测评分, 将所预测的评分填充用户评分矩阵, 最后在已填充的用户评分矩阵上采用基于用户特征的协同过滤方法预测目标用户的评分, 这样就将用户特征和项目属性结合起来。
算法描述:基于用户特征和项目属性的混合协同过滤
输入:用户-项目评分矩阵R (m, n) , 目标用户H, 最近邻项目数M及其最近邻用户数K。
输出:目标用户H的Top-N推荐集{i1, i2, …in}
步骤:
(1) 在用户-项目评分矩阵R (m, n) 中, 将项目分为已处理集合IR和未处理集合IS, 最初状态所有的项目都属于IS。
(2) 对于任意的项目Im∈IS, 根据公式 (7) 计算项目Im与其他项目In的相似度, 并将相似度按从大到小排序, 选取前M个作为项目Im的最近邻居项目集合。
(3) 对用户-项目评分矩阵中对Im未评分的用户, 根据公式 (4) 来预测用户对Im的评分, 其中sim (i, j) 用公式 (7) 中的sim Item (a b) 代替。Im上所有的未评分用户预测结束后, 将Im置入已处理集合IR中。
(4) 重复2和3, 直至用户-项目评分矩阵中所有未评分的项均被预测填充, 填充完的用户-项目评价矩阵为R′ (m, n) 。
(5) 在新的已填充的用户-项目评价矩阵R′ (m, n) 中, 根据公式 (5) 计算目标用户与其他用户之间的相似度, 并按从大到小顺序排序, 选取前K个作为目标用户的最近邻居用户集合N。
(6) 最后用户-项目评分矩阵R (m, n) 对目标用户H未评分的项进行再次预测, 根据公式 (2) 在最近邻居用户集合N中预测目标用户对目标项目的评分, 其中sim (i, u) 用公式 (5) sim User (a, b) 代替。
(7) 按照预测值的高低选择前n个目标项目推荐给目标用户H。
3、实验及分析
本文的数据集取自Movielens站点 (Http://movielens.umn.edu) , Movie Lens是一个基于Web的研究型推荐系统。Movie Lens数据包括3952部电影和6040个用户的基本信息, 以及用户对这些电影的100多万条评分数据。其中电影的总类属数为18, 用户的评分为1到5。每个用户至少对15部以上的电影进行评分, 分数越高表示用户越喜欢这部电影。本实验中用到的数据只是MovieLens站点上数据的一部分, 包含了943位用户对1682部电影的100000条评价数据, 评分数据的稀疏等级为1-100000/ (943×1682) =0.936953。其中选取数据集的80%作为训练集T, 剩余的20%作为测试集M。
本文采用平均绝对偏差MAE作为度量标准, 平均绝对偏差通过计算预测的用户评分与实际评分之间的偏差度量预测的准确性, 其MAE[6,7]定义为
其中pi是用户的实际评分, qi是系统对评分的预测值, N为总的预测评分条数。
为了检验本文算法的有效性, 我们采用项目属性结合传统的计算项目之间相似性方法计算项目之间的相似度并将预测结果填充用户-项目评分矩阵, 采用用户特征结合传统的计算用户之间相似性方法来计算用户之间的相似度, 在此基础上产生推荐集。将本文的算法与传统的基于用户的协同过滤和传统的基于项目的协同过滤相比较, 实验结果如图2所示。
由图2可知, 本文提出的算法相比传统的方法明显具有较小的MAE。因此, 本文所提出的算法在推荐精度上有所提高。这一方面由于引用了用户特征和项目属性, 使产生的最近邻居集合更加准确。另一方面用基于项目的协同过滤方法预测评分填充用户-项目评分矩阵, 一定程度上缓解了稀疏性问题, 同时也提高了推荐精度。
4、总结
本文针对传统的协同过滤方法精确性问题和稀疏性问题, 提出一种用户特征和项目属性的混合协同过滤推荐方法。实验结果表明, 本文所提出的算法明显优于传统的基于用户和项目的协同过滤方法, 先比传统方法, 混合协同过滤方法产生的推荐结果更加准确。
摘要：协同过滤技术在电子商务领域里已经得到广泛的研究和应用, 但是传统的协同过滤方法的精确性问题以及数据稀疏性问题, 严重影响了最终的推荐质量。针对这些问题, 本文提出一种结合用户特征和项目属性的混合协同过滤方法。该方法不但能够继承基于用户协同过滤奇异性发现的优点, 还能够缓解稀疏性问题, 同时提高推荐精度。实验结果表明, 本文所提出的方法明显优于传统的基于用户和项目的协同过滤方法, 产生的推荐结果更加准确。
关键词：用户特征,项目属性,协同过滤,推荐系统
参考文献
[1]Sarwar, B.M., Karypis, G., Konstan, J.A., and Ricdl, J., Item-based Collabora-tive filtering Recommendation Algoriths[C], Proceedings of the 10th Inter-national World Wide Web Conference, pp.285-295, ACM Press, 2001.
[2]Sarwar B, Konstan J, Borchers A, et a1.Using filtering agents to improveprediction quality in the groupLens research collaborative filtering system[C].In:Proc.ACM Conf.Computer Supported Cooperative Work (CSCw) .New York:ACM Press, 1998, 345～354.
[3]邓爱林, 朱扬勇, 施伯乐.基于项目评分预测的协同过滤推荐算法[J].软件学报, 2003, 14 (9) :1621-1628..
[4]赵亮, 胡乃静, 个性化推荐算法设计.计算机研究与发展, 2002.39 (8) :986-991.
[5]彭玉, 程小平.基于属性相似性的Item-based协同过滤算法[J].计算机工程与应用, 2007, 43 (14) :144-147.
[6]Breese J, Heckerman D, Kadie C.Empirical Analysis of Predictive Algo-rithms for Collaborative Filtering[A].Proceedings of the 14th Conference onUncertainty in Artificial Intel ligence[C].Madison:Morgan Kaufmann, 1998, p43-52.
混合属性数据范文
声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。如若本站内容侵犯了原著者的合法权益，可联系本站删除。
