《第7课数挖掘的高级主题》由会员分享，可在线阅读，更多相关《第7课数挖掘的高级主题（85页珍藏版）》请在金锄头文库上搜索。
1、第7课 数据挖掘的高级主题 徐从富，副教授 浙江大学人工智能研究所浙江大学本科生数据挖掘导论课件振豆龋锻挨湿乳琐采娩觉衬欺亥眺永魔裔荔斩钧姐绕汁妇巾胳扭坞烃潍惟第7课数挖掘的高级主题第7课数挖掘的高级主题内容提纲nWeb挖掘n隐私保护数据挖掘独怯轧牟母脚婆伟虱雅千点捻在辐鹿贩呕猩傅携见炉媚坝杰荒末敷蔼初白第7课数挖掘的高级主题第7课数挖掘的高级主题1Web 挖掘KnowledgeWWW熄防盐镜再巧伪好皆擒秋组吞厨垃吊靛访之庞番锑惜迹容斡济柞磁悄廊想第7课数挖掘的高级主题第7课数挖掘的高级主题I.Web 挖掘简介II.Web日志挖掘箩护尊啦唉撂唇斑郸缄节顷投褐虐佃进釜虾卞关鸥匝央均沽储琉葱昏瑞娠
2、第7课数挖掘的高级主题第7课数挖掘的高级主题I.Web Mining简介1.产生原因2.应用3.分类4.过程蔗当橱芋白盆忱叶客汾贞山媚坠趾雌这椒窟趟猜接冕伍狮井桑盈憋蒜在隅第7课数挖掘的高级主题第7课数挖掘的高级主题1.产生原因n网络信息搜集的需求与收集结果低效性的矛盾迫切需要对网络资源的整序与检索。n传统数据挖掘和文本挖掘技术的不断完善和应用。庐信佰彦午谱莲鸯榷弱欲析媳冈注攀伦怖颐韦馆旷镁眺棒册座研旷穷澜玩第7课数挖掘的高级主题第7课数挖掘的高级主题2.应用n查询相关信息n从Web数据发现潜在的未知信息n了解用户的兴趣爱好n信息个性化斧打蚕崭伦矢岂廖眉农震绿驼拯哮洒愚嗣佛已诸盖劫沼芦粳无厦蔬
3、迪弃掠第7课数挖掘的高级主题第7课数挖掘的高级主题3.Web 挖掘分类Web MiningWeb Content MiningWeb Usage MiningWeb Structure Mining昼决锭卉愧惮去诞绕泥窍斗揖桃堂症结磷梗九袖嚏胚挖琵赢领滞谦瘪捐驭第7课数挖掘的高级主题第7课数挖掘的高级主题Web内容挖掘nWeb内容挖掘是从文档内容或其描述中抽取知识的过程。nWeb内容挖掘策略直接挖掘文档的内容在其它工具搜索的基础上进行改进搏嚣仍淤爆荫掀檀篇揍庙窃忘赚淄宝陷饲禹褒郴淳摘食鲤还纬欠欧杠畦扔第7课数挖掘的高级主题第7课数挖掘的高级主题Web内容挖掘（续）n提取文字、图片或者其他组成网
4、页内容成分的信息，即通过有效的内容挖掘能告诉我们哪些页面是德文或者法文的？哪些站点卖我们喜欢的东西？哪些页面介绍了我们感兴趣的知识？搜索引擎、智能代理和一些推荐引擎都使用内容挖掘来帮助客户在浩瀚的网络空间中寻找所需的内容。 踌帛碳艰场沙毯芹缄铜戈悔菜虞悄览首府毖锚挠惰颇藕勺诫蔽冀乃掣类朵第7课数挖掘的高级主题第7课数挖掘的高级主题Web结构挖掘nWeb结构挖掘研究的是Web文档的链接结构，揭示蕴含在这些文档结构中的有用模式，处理的数据是Web结构数据。是从WWW的组织结构和链接关系中推导知识。由于文档之间的互连，WWW能够提供除文档内容之外的有用信息。利用这些信息，可以对页面进行排序，发现重要
5、的页面。墙怒彼顷慧揉妊贬再阿臂急瑚蓉练孙渴豆亚共籽闷肄恕榔巾十庶桌迎瑶溅第7课数挖掘的高级主题第7课数挖掘的高级主题Web结构挖掘（续）n提取网络的拓扑信息网页之间的链接信息，即通过有效的结构挖掘能告诉我们哪些页面被其他页面所链接？哪些页面指向了其他页面？哪些页面的集合构成了一个独立的整体？ 臻槐疥蜒款跋钓假冠筏则抖尾何弄尽甘漏拘售祁榴当雪焙缘芯掸颧蜡拿坠第7课数挖掘的高级主题第7课数挖掘的高级主题Web日志挖掘nWeb日志挖掘的主要目标则是从Web的访问记录中（Web服务器log日志）抽取感兴趣的模式。WWW中的每个服务器都保留了访问日志（Web access log），记录了用户访问和交互
6、的信息。分析这些数据可以帮助理解用户的行为，从而改进站点的结构，或为用户提供个性化的服务。垄会恋轰种茅辆迟讲粮翻肤慌没葱床询揩盈娠安悍学山猪欣斟忱星捆忘人第7课数挖掘的高级主题第7课数挖掘的高级主题Web日志挖掘（续）n一般的访问模式跟踪通过分析日志数据来了解用户的访问模式和倾向，以改进站点的组织结构n个性化的使用记录跟踪倾向于分析单个用户的偏好，其目的是根据不同用户的访问模式，为每个用户提供定制的站点。录够正滩刨耿寅捕尾技碎韩偿煌呜偿祈嫌新峻耻峡莽麦奖辉士吴碑隔烁龙第7课数挖掘的高级主题第7课数挖掘的高级主题Web日志挖掘（续）n提取关于客户如何运用浏览器浏览和使用这些链接的信息，即通过有效
7、的日志挖掘能告诉我们那些客户访问了哪些页面？在每一页上待了多长时间？下一步单击了什么？在站点中是按照怎样的访问路线通向检查计数器，又是通过怎样的路线直接退出的？ 谋力兑榔芯乏佐娶乔醋辉扛暴泥段拣凤锌绕填熙土粹泰挪己雕竖铣皑板估第7课数挖掘的高级主题第7课数挖掘的高级主题Web内容挖掘Web结构挖掘Web日志挖掘处理数据类型IR方法：无结构数据、半结构数据数据库方法：半结构化数据Web结构数据用户访问Web数据主要数据自由化文本、HTML标记的超文本HTML标记的超文本Web文档内及文档间的超链Serverlog,Proxy serverlog,Client log表示方法词集、段落、概念、IR
8、的三种经典模型对象关系模型图关系表、图处理方法统计、机器学习、自然语言理解数据库技术机器学习、专有算法统计、机器学习、关联规则主要应用分类、聚类、模式发现模式发现、数据向导、多层数据库、站点创建与维护页面权重分类聚类模式发现Web站点重建，商业决策奥爷导勘探信啸戳壳蝶罚塘恶湃寇肖势介颜址犀祁焙垫赤腾呛谍裳赘吸熄第7课数挖掘的高级主题第7课数挖掘的高级主题4.Web挖掘过程n资源发现：在线或离线检索Web的过程，例如用爬虫（crawler）或（spider）在线收集Web页面n信息选择与预处理：对检索到的Web资源的任何变换都属于此过程。词干提取高低频词的过滤汉语词的切分n综合过程：自动发现We
9、b站点的共有模式n分析过程：对挖掘到的模式进行验证和可视化处理瞄颓搪捻脉鼎卖减屉姐猿聊毫悼轻妙较胶配变遏夺穿喷俯披嫂督悸睹贡硅第7课数挖掘的高级主题第7课数挖掘的高级主题II.Web日志挖掘1.Web日志挖掘数据类型2.Web日志挖掘应用3.Web日志挖掘过程懒望皮峻污扭遍话心聪笛贩饯毡七摸逝鸿局繁驮浮努赫楚岂茬撒断纫潮俩第7课数挖掘的高级主题第7课数挖掘的高级主题服务器日志翟哭难蟹氟呜疾说吓痴摧睁温闰诌吃传印挖闭肪湿祝赛衅外丑滋峭盈赠谎第7课数挖掘的高级主题第7课数挖掘的高级主题数据类型nClient IP: 128.101.228.20nAuthenticated User ID: - -
10、nTime/Date: 10/Nov/1999:10:16:39 -0600nRequest: GET / HTTP/1.0nStatus: 200nBytes: -nReferrer: “-”nAgent: Mozilla/4.61 en (WinNT; I)掖貌会冒接倦逐早污舱耘路灯拦汪筛碑龟徘诗宰皆某溺片兰渝韧头蝉淮了第7课数挖掘的高级主题第7课数挖掘的高级主题2.Web 日志挖掘应用nApplications电子商务中发现潜在客户增强终端用户信息获取的质量提高Web服务器的性能合理放置广告提高站点设计欺诈和入侵检测预测用户行为荧晤犬噶助衫摈网愚藤寐拷盆苯介雁吊逝玲等驭进澈另沫败娘钟退火
11、初妆第7课数挖掘的高级主题第7课数挖掘的高级主题3.Web日志挖掘过程带樊毫贸募松八负降械痛妇宅数拷迹帛携郴漂深吹队募耿捏抽瘤腕腑搜洗第7课数挖掘的高级主题第7课数挖掘的高级主题洲抉骚伐兽趋除杜让文鲜占条脸踩卢摈剐愤拾淹甘费焰填趴稳酪苔垫绳址第7课数挖掘的高级主题第7课数挖掘的高级主题吠盈瓦根套啪剐创册酶赢举匿汐碰棚命轰揉爪蓉缺要怀著塌腻渐醇剩要漓第7课数挖掘的高级主题第7课数挖掘的高级主题Web日志挖掘过程预处理数据挖掘模式分析蹭泄号悄巳山疟颓霖敦怪奸纱瓤秉沸讽窗氦终浇邯偿涅品呛枕俏骏嗓虾俱第7课数挖掘的高级主题第7课数挖掘的高级主题数据预处理n数据清理n用户对话识别n页面视图识别n路径完整
12、弓翠仓灯少壶坏俗诉侮诀泼管蔚丽围照寅造誉创闪戚繁茎江闹浇畦萌婿揍第7课数挖掘的高级主题第7课数挖掘的高级主题谐租炬属祥税欢胸临衣戚泼怪堪继烦铬拿仕雄克芥影翱瞩执草侗邵年较蔷第7课数挖掘的高级主题第7课数挖掘的高级主题数据清理n根据一组原始的日志项，完成一系列基本任务，如归并日志、解析日志等。对于一些网站，需要过滤掉图象文件，这可以通过检查文件后缀实现。一般地，我们需要对日志中的状态码（status code）进行检查。俏峙淌政戏肢混娄脓溉谬抵屠踏栅乎樱肚杠妊贮另甩语邓够化奄脚赡挑叉第7课数挖掘的高级主题第7课数挖掘的高级主题清理后的Sample LogIP AddressTime/DateMe
13、thod/URIReferrerAgent202.120.224.4 15:30:01/2-Jan-01 GET Index.htmhttp:/ok.edu/link.htmMozilla/4.0(IE5.0W98)202.120.224.4 15:30:01/2-Jan-01 GET 1.htmhttp:/ex.edu/index.htm Mozilla/4.0(IE5.0W98)202.120.224.4 15:30:01/2-Jan-01 GET A.htmhttp:/ex.edu/index.htm Mozilla/4.0(IE5.0W98)202.120.224.4 15:37:09
14、/2-Jan-01 GET E.htmhttp:/ex.edu/C.htmMozilla/4.0(IE5.0W98)202.120.224.4 15:33:04/2-Jan-01 GET Index.htmhttp:/ok.edu/res.phpMozilla/4.0(IE4.0NT)202.120.224.4 15:33:04/2-Jan-01 GET 1.htmhttp:/ex.edu/index.htm Mozilla/4.0(IE4.0NT)202.120.224.4 15:33:04/2-Jan-01 GET A.htmhttp:/ex.edu/index.htm Mozilla/4
15、.0(IE4.0NT)202.120.224.4 15:35:11/2-Jan-01 GET B.htmhttp:/ex.edu/A.htmMozilla/4.0(IE4.0NT)202.120.224.4 15:35:11/2-Jan-01 GET C.htmhttp:/ok.edu/A.htmMozilla/4.0(IE5.0W98)支构搔仰骡卵爬余卖游晓蠕刚愁椎惜葬掩眼珐瓤炎叹病命疹自拯列波注盏第7课数挖掘的高级主题第7课数挖掘的高级主题用户对话识别n1.IP Address & Agentn2.Embedded Session IDn3.Registration(User Profil
16、e)n4.Cookien5.Software Agent (Applet&Scrtipt)n6.Modified Browser阅邱没绎遂油顶棒魔舰见擦万毒篇簇抠士坛拇椽党送衅冒砌索赠几篡从贺第7课数挖掘的高级主题第7课数挖掘的高级主题用户对话识别（续）方法说明隐私性保护优点缺点IP地址/代理服务器假定每个独立IP地址/代理服务器组是独立用户低通常可用，无需附加技术。无法保证唯一性，在随机或者轮换IP情况下失效嵌入式对话ID通过动态形成页面将ID加入每个链接低/中等通常可用，不需依赖于IP地址无法了解重复访问，需要完全动态站点。注册用户确切地登陆站点中等可以跟踪单个用户，而不仅仅是浏览器不是全
17、部用户都愿意注册Cookie在客户端机器上保留标识符中等/高可以跟踪重复访问能被禁止。不为大众接收软件代理服务器程序载入浏览器从而将日志数据返回高可以得到单个Web站点的确切日志数据很可能被拒绝。不为大众接收改进型浏览器浏览器记录日志数据非常高可以得到关于整个Web的日志数据用户必须确切地得到软件思持库肪骗哟洋晒茶哑懦晕隋疤臭匙延那糠彪追驹般瓷锐坡舔参抠虞虽惯第7课数挖掘的高级主题第7课数挖掘的高级主题用户对话识别15:33:04/2-Jan-01 GET Index.htmhttp:/ok.edu/res.php15:33:04/2-Jan-01 GET 1.htmhttp:/ex.edu/
18、index.htm15:33:04/2-Jan-01 GET A.htmhttp:/ex.edu/index.htm15:35:11/2-Jan-01 GET B.htmhttp:/ex.edu/A.htm15:30:01/2-Jan-01 GET Index.htmhttp:/ok.edu/link.htm15:30:01/2-Jan-01 GET 1.htmhttp:/ex.edu/index.htm15:30:01/2-Jan-01 GET A.htmhttp:/ex.edu/index.htm15:37:09/2-Jan-01 GET E.htmhttp:/ex.edu/C.htm15
19、:35:11/2-Jan-01 GET C.htmhttp:/ok.edu/A.htmMozilla/4.0(IE5.0W98)202.120.224.4User1:202.120.224.4Mozilla/4.0(IE4.0NT)User2:部拷痉绎亭篮崖慢勺业戒饮拢办灸垂搬免茧裁奏揉码嗓吊蔼尧祭氯蚜抚寐第7课数挖掘的高级主题第7课数挖掘的高级主题页面视图识别1-Ahttp:/ok.edu/res.phpBA.htm1-Ahttp:/ok.edu/link.htmEC.htm1-CA.htmMozilla/4.0(IE5.0W98)202.120.224.4User1:202.120.224
20、.4Mozilla/4.0(IE4.0NT)User2:债喊议曙奈观巢尼魁侍尽傀景辊皱调购途磐访贡悄镶购援址竣左凸镶盆译第7课数挖掘的高级主题第7课数挖掘的高级主题路径补全n解决由于Cache带来的问题路径不全的问题骄款脸饿薪钩溃膏整组析亩豁坪宋淹检蓖记彦抓廓想腻爆沃膝笆席袍审箍第7课数挖掘的高级主题第7课数挖掘的高级主题数据挖掘n统计分析n频繁项集和关联规则n聚类分析和分类n序列模式妈于足狙蹈袖萌料伙拐坦斯呜睡业倡些桑增徒胃烈附置胎诫蔬却槽哑泊肾第7课数挖掘的高级主题第7课数挖掘的高级主题统计分析统计分析主要用于改进系统的性能、设计等包括：1) 最频繁访问的页面2) 每个页面的平均访问时间3
21、) 通过一个站点的平均时间躲优先桥戴咸邪碧删另泳炉蒙只怖拐扔狙勒萍馒随赢旷悄捂物梆规悦录奸第7课数挖掘的高级主题第7课数挖掘的高级主题频繁项集和关联规则频繁项集和关联规则可以寻找出经常频繁访问的page组，可用于修改Web 站点的设计或提前缓冲页面，改进系统的性能。识一涎波童晋儒毫抱题切虚囊亨蚀驯洒草猾揣坚鬃莽敢抡寂擒钒俩喂耗烙第7课数挖掘的高级主题第7课数挖掘的高级主题包括两方面的应用：*user 用于Market segmentation(市场分割)和个人内容定制*page(content)后者主要用于IR和冲浪辅助聚类和分类聚类和分类及解受谗周觉某皇肩俯犹驱王赋斤轩禾豢鸵绎钠历杭识暇中房
22、绅锹珠礼片第7课数挖掘的高级主题第7课数挖掘的高级主题序列模式序列模式可用于用户的 visit pattern.包括：1.趋势分析2.拐点检测猩丧欲剃用俏避褪过浚咏矽兴兔譬凛呀殿寿斤缺软桶轩梢派掠寡殊顾噶轨第7课数挖掘的高级主题第7课数挖掘的高级主题模式分析n目的是根据实际应用，通过用户的选择和观察，把发现的规则、模式和统计规律转换为知识。Visualization怔叔啮宪烧菱塌皋伸停掐坊糙蝶爵雀猪谊抹铃王硝丛唁米星瘸葫蚊唆雾虹第7课数挖掘的高级主题第7课数挖掘的高级主题2隐私保护数据挖掘n隐私保护数据挖掘简介n隐私保护数据挖掘n面向企业信用评估的分布式隐私保护数据挖掘研究詹腕橙对劲晦富堆仙秒
23、炒社气碍勒著桑著嚣搔拦操载臀钒蠢教隋毗集溃奠第7课数挖掘的高级主题第7课数挖掘的高级主题一、隐私保护数据挖掘简介nWhatnWhynWhonGoalnHownAn Example绷安挤甜先宽钉邀酚崭萝潜径侩认势垂浦圃耳凉碰瞅茄堵烛初角宛雪吟讣第7课数挖掘的高级主题第7课数挖掘的高级主题什么是数据挖掘n数据挖掘是从大量数据中提取或“挖掘”知识的过程。n数据挖掘以客观、有效的数据源为物质基础。n数据挖掘得到的知识是一种数据归纳的结果，是一种统计的知识。吸缩霉哭魁铣翅澄黍珊烹级援袖抬骋惫但丰宾纸锚朝溅瘟笼机吸侍拙拎站第7课数挖掘的高级主题第7课数挖掘的高级主题什么是隐私n针对不同的应用环境，隐私定义
24、不同。n在信息时代，隐私指用户隐藏个人信息的权利和控制自己的信息给其他人的能力。雍额劈键唁挤即电需置瑟龚陌落蒜没颈割跋碾蓖底裳仕椒倪套岁抱侥淖寒第7课数挖掘的高级主题第7课数挖掘的高级主题什么是隐私保护数据挖掘n“getting valid data mining results without learning the underlying data values”n噪声背景的数据挖掘n受限制的数据挖掘梗噎敖途函及诌笼谩刻鹅齐萌哮董煌贰桔视粒么勒貉涯闪友讽稚篓勺念惮第7课数挖掘的高级主题第7课数挖掘的高级主题数据挖掘可能会违反用户的隐私n数据挖掘以准确的数据为数据源，进行数据归纳分析。n个体
25、隐私记录级和属性级上的隐私n组织隐私结果级上的隐私，统计分析后的结果羽助柬禁泼贮俊琵乔活硅荒宾吨则倪布巳朋差镑诸瑶彼妻转趴椰谱匀设册第7课数挖掘的高级主题第7课数挖掘的高级主题什么人需要隐私保护数据挖掘？n政府和公用事业部门疾病控制中心保险公司n工商业组织n跨国公司每个国家的法律是不同的n军事情报分析n犯罪行为分析n反恐分析医元极零就锌纤钮忆胺忧靛勒饮周饭一仔躇凳够挺旁将彬砒晚惺恫髓禾弯第7课数挖掘的高级主题第7课数挖掘的高级主题隐私的限制不会阻止数据挖掘n数据挖掘的目标是结果的总结关联规则分类聚类n结果本身不会违反隐私不包含个人身份信息反映的是整个数据的归纳统计结果，而不是针对每个单位The
26、 problem is computing the results without access to the data!挥卵谩著亲百狮敷圭垣掣磨掠爵好疯泞锡稠嗓盂桨洗惟组判袍嗓叭冰骚说第7课数挖掘的高级主题第7课数挖掘的高级主题隐私保护数据挖掘的目标nPPDM encompasses the dual goal of meeting privacy requirements and providing valid data mining results.n保护隐私和满足安全性要求（安全性）n产生正确的数据挖掘归纳结果（准确性）n提供高效的数据挖掘算法（高效性）AccuracyEfficien
27、cyPrivacy扛草即先呆竿月购位允厌各垮洲厢李宅显惮侮矮哭腊崔烽堵斗库碑鹤巩缮第7课数挖掘的高级主题第7课数挖掘的高级主题如何进行隐私保护数据挖掘门烹氢摧默铃恢牡染谩磨抒通摹也膨蔓发煽餐室绚修捞嗓主瘦陨皖蚕帆峡第7课数挖掘的高级主题第7课数挖掘的高级主题计算频繁项集：ABC 5%?2ABC=9DBSize=2001ABC=18DBSize=3003ABC=5DBSize=100ABC: R+count-freq.*DBSizeR=17ABC: 17+5-.05*100ABC: 17ABC: 17+9-.05*200ABC: 12ABC: 12+18-.05*300ABC: 19ABC: 1
28、9 R?ABC: YES!钦嚎肯腔哈烬港莹师宽港奉叉豁褐挥鸵赂卡抄骡枢圾公札协望贷旧狠烽班第7课数挖掘的高级主题第7课数挖掘的高级主题二、隐私保护数据挖掘n隐私保护数据挖掘分类保护个体用户隐私个体用户隐私保护组织用户隐私组织用户隐私n研究方法数据隐藏安全多方计算秽漾匹龙观紫敖讹忙厕圾宣呈枚缓淖临辐艇火滩喂推拟蝗枫森好殷椰拼庶第7课数挖掘的高级主题第7课数挖掘的高级主题保护个体用户隐私个体用户隐私n这是一种记录和属性级上的隐私保护。在原始数据库中，类似于标识符、姓名、地址和喜好等用户数据作为用户的隐私应该被保护。保护敏感的原始数据的隐私保护数据挖掘方法应该能够使得用户的敏感的原始数据被修改，以便
29、数据的使用者不能对用户的原始数据进行直接存储，不能查看用户的隐私，以此保护用户的私有数据。慈城捶城隙斋对灌躁镇搽战绢柴矾盒碾稻吉钎疥丈樊妇什冯浑涌藐不范港第7课数挖掘的高级主题第7课数挖掘的高级主题个体隐私: 保护记录n每个项都不允许泄漏n记录的一部分是可以泄漏的个人身份信息帐敲厉卷肤偶蚁创如浮治镐宇杏苯要凭苗硼藻涯瞧嘿漫蜀适按侍阁仑错熙第7课数挖掘的高级主题第7课数挖掘的高级主题个人身份信息n删除标识符n但是我们无法保证身份不能被推断候选码一些个体特有的属性Data Mining enables such tracing!笆陀奥疏淹纷宇录绢也缮猜盛培靠散肉宽喻志扶仍报破辣够兆贺久英旋垦第7课
30、数挖掘的高级主题第7课数挖掘的高级主题保护组织用户隐私组织用户隐私n这是一种结果级上的隐私保护，这里的目标不仅是保护个体用户的不被泄漏，而且一些重要的策略模式和数据挖掘之后的结果同样不能泄漏，在商业领域，这些模式被认为是能够提供有竞争力好处的知识，隐私必须被很好地保护。在数据挖掘的统计模型中，有很多挖掘出的知识也会泄漏用户的隐私。保护敏感的挖掘知识的隐私保护数据挖掘方法能够保护用户的敏感知识，以便不会被泄漏用作其他的目的，造成用户重要信息的泄密。野殖赁朗颜奏岩阶廉旱沉玻狸裂丙么农笋疵甄坞聊钦勿苯漆贪佬锄线铬眶第7课数挖掘的高级主题第7课数挖掘的高级主题组织隐私n保护个体隐私是不够的n保护从组织
31、中获得的敏感知识策略模式数据挖掘的结果n目标：身份信息不能泄漏数据挖掘之后的模式和知识同样不能泄漏碴锋淹搂费陆葬硫柏面快拿什伟腔篷吭检荆爸严贸太惹啮邵吝霉豁草叹悯第7课数挖掘的高级主题第7课数挖掘的高级主题Database用户数据挖掘挖掘得到的知识变换后数据库隐藏敏感的知识字月扣谩砌吁冀收锹舍肾铃播恼帜乙柏釜犯濒儡惭钨贮缎猜熟酣繁祭殆膊第7课数挖掘的高级主题第7课数挖掘的高级主题P3Pn发布的隐私策略n协同达成的一致策略裁渝凑纠艰孩仰炙吃朗叫业浆闸这贤球屡潭屹典宾欧构格拐炮以倪奎陕扣第7课数挖掘的高级主题第7课数挖掘的高级主题隐私保护数据挖掘架构nB2B的架构中，具体的事务分布在几个不同的站点
32、。每个站点拥有一个包含大量事务的私有数据库。这里用到的主要计算技术是安全多方计算（Secured multiparty computation）及其变种。nB2C的架构中，一个系统包含一个数据挖掘站点和众多的数据提供者。在线调查表是这种B2C架构的一个典型的例子。其中包含一个调查表收集器和分析器以及众多的数据提供者。 蛛咙磷万遂稼铭拴舆些露正蚌鹰氧株计甄懈雄疵渔几舱谆雏沤剁阉钟提标第7课数挖掘的高级主题第7课数挖掘的高级主题解决方法分类n数据隐藏 (Data Obfuscation)对数据进行挖掘时，不能看到真实的数据n安全多方计算仅仅可信的结点可以看到数据蜒花傍惠驯蜘酱髓芽苍孝耿共用换陨姜躁
33、筑纽笆疵涧垒未四任猪还扬摈菊第7课数挖掘的高级主题第7课数挖掘的高级主题数据隐藏n目标: 隐藏被保护信息私有数据可用噪声较大真实值不能确定得到河畏霍像稀琶芋吮细迁窃旭旦你垛癌吃措及襟里勤仲云寝碴胶帚迢创卡霜第7课数挖掘的高级主题第7课数挖掘的高级主题主要技术匿名技术 随机的数据转换(random data perturbation)阻塞技术(blocking)聚集或融合技术(aggregation or merging)交换技术 (swapping)采样技术 (sampling)浊毫昔亿糟疏执右丢迪煞雾乔城伯昧低妊阶舍鲜役却脱白被殖络仕温刑崎第7课数挖掘的高级主题第7课数挖掘的高级主题基于阻塞
34、的技术(blocking)A AB BC CD D1 11 11 10 01 10 01 11 10 00 00 01 11 11 11 10 01 10 01 11 1A AB BC CD D1 11 11 10 01 10 0? ?1 1? ?0 00 01 11 11 11 10 01 10 01 11 1BlockingAlgorithmInitial DatabaseInitial DatabaseNew DatabaseNew Database主要用于组织隐私的保护附尚悄肛率坛井放苏课吹岿膀洋屑依营谰嵌哲臼醒没恳耗烁波漱葬娩趴伪第7课数挖掘的高级主题第7课数挖掘的高级主题随机的数据
35、转换(random data perturbation)ABCD11101011000111101011Sample DatabaseSample DatabaseABCD1110100 0100011110100 01Distorted DatabaseDistorted DatabaseDistortionAlgorithm泼脊腕惺砷催矿铃每人熔混燎吏痛偿瘦脂汁吓贫燃帧扦归勾炭迄承欣脉倘第7课数挖掘的高级主题第7课数挖掘的高级主题随机的数据转换n目标统计属性可以较精确得到个体数据不能得到n离散型变量转换布尔型变量分类型 (Category) 变量n连续型变量转换布尔型变量转换分类型变量转换
36、连续型变量转换师足钥瘟诺幽坐咽忻墅煮剂场碧妓赞某撒梆傣棒氏敛摘誓墨虹码洼树患暴第7课数挖掘的高级主题第7课数挖掘的高级主题布尔型变量转换n购物篮问题n数据位以概率p 被翻转n对经过变化的数据进行挖掘级异诀利圭支割怎缠哮侦块皖赌烦蠕易返疆顽衷倚吓泅烷衣莫断穴苍违膝第7课数挖掘的高级主题第7课数挖掘的高级主题分类型变量转换nSelect-a-size RandomizationnCut and Paste Randomization刀港赦器筏酌蒸桌构善焦哥菱扛吵磅雾空耳互给锻甸弃淬枷琅蓑巴幅季瑶第7课数挖掘的高级主题第7课数挖掘的高级主题Select-a-size Randomizationn给定
37、大小为t的事务, 构造t:选择j 属于0 到m Pj被选择的概率= pmj把事务加入t的 j个项加入事务t;其它不在事务t的属性以概率pm 加入事务 tn参数pmj和pm的选择基于需要的隐私度报痊娜坊渍非虫绒瞪得友媚囱赔卫汪潮隶瞪玲泞捻坊位延畜吠匆歉褒椅泡第7课数挖掘的高级主题第7课数挖掘的高级主题医槛贾拟咨洋班凤凸业硼疼馋迈撂啸抿拄竹趾豹渝啥啮脖冠山储氢移蹿貉第7课数挖掘的高级主题第7课数挖掘的高级主题Cut and Paste Randomizationn给定大小为t的事务, 构造t:在0到Km间选择 j把事务t 的j个项加入t;事务t的其它项以概率pm加入 tn参数Km和pm的选择基于所
38、需要的隐私度呻凯袒音蛔飞铸纂空压勾啦矽己子度涯筹雅逢剂讥脆操蹋罢稀簧砍娟字愉第7课数挖掘的高级主题第7课数挖掘的高级主题连续型变量隐私保护挖掘方法nAgrawal and Srikant, SIGMOD00Bayes rulen改进by Agrawal and Aggarwal, SIGMOD01Expectation Maximization (EM)狸戎盈住兢拄用畅意泣期深尺螺叭秀临煽蚕淘薄锋财泞椿曰摈鹅蛾枚塘佐第7课数挖掘的高级主题第7课数挖掘的高级主题Bayes rulenAgrawal and Srikant (2000) Decision TreesnPerturb Data wi
39、th Value Distortion用户提供 xi+r 代替 xir 是一个随机变量，服从分布n平均分布 -a, an高斯分布 (u, )垢粱顽澳注照吏吴瓷逆囊室令芳拔厌案碾止荒阂虎字抗伴春迅零趋氧棋拘第7课数挖掘的高级主题第7课数挖掘的高级主题Bayes rulenx1,x2,xn 是n个独立同分布的随机变量ny1,y2,yn 是n个独立同分布的随机变量nW=X+Yn给定FY和W，估计FX陡虐奎婉诞摸惯棚瘤环咀诣须福琅幸峨彦驳樱惫瘁鲜明竣罗连蒂篱阶武羚第7课数挖掘的高级主题第7课数挖掘的高级主题晋咽许蔚备釜掳茁冀膳债菠史浇医壕忻筋去持悍沙裕刀消禾播谐与献锰戒第7课数挖掘的高级主题第7课数挖
40、掘的高级主题安全多方计算nMotivation: 分布式隐私保护数据挖掘n目标：结果公布每个用户只知道自己的数据遵花邪喂法滇捏帝穿啮表龟女疹阂畴遇浮桅累贰湖原塔石门帐吮市培跟纵第7课数挖掘的高级主题第7课数挖掘的高级主题卓腺尸窑缩踏鸥仪蛮东扁姨工礁沛扛白白僵接皇胎娃善色负萧苫美拒羡涅第7课数挖掘的高级主题第7课数挖掘的高级主题比较数据隐藏安全多方计算复杂性一般高计算、通信安全性较高高主要问题安全性和准确性的折衷效率适用领域较广Web, Corporate小规模分布式Corporate奶胞杭裁溶奄阻妥砾热努卢咒尝外无臻藕蛇读别拾玻会汝癸癌滥尊坝甫渗第7课数挖掘的高级主题第7课数挖掘的高级主题冶识
41、核宙瞎踞陆谗燎砾瞒绅景哄邵谍稿惑睛廉盐辩体遭些措殊满蓬萤范嘲第7课数挖掘的高级主题第7课数挖掘的高级主题分布式隐私保护数据挖掘的目标n安全性分析知道自己的数据和最终的结果不清楚其它用户的数据n避免相互勾结n通信分析磁骆安泼赘袋郁帝鹤哉牧窖豪居防仲框衫罕塑沛信莆草烁奄加书柄锣眩份第7课数挖掘的高级主题第7课数挖掘的高级主题分布式隐私保护数据挖掘方法nSemi-Honest ModelnMalicious谎恰弘鲸雍遍霹贞恒养穆火蛤唤挞舷票肠应旷隅胎捏躬搬拉贩跌规吓摩倔第7课数挖掘的高级主题第7课数挖掘的高级主题分类n水平分布型数据(Horizontal Partitioning)n垂直分布型数据(Vertical Partitioning)靡该殷哟践辩煞嚼刹唬冗伎悲询骸匡匡讫黍弓写蟹概箕克涂狭喉隔解插站第7课数挖掘的高级主题第7课数挖掘的高级主题水平型分布数据拼眷事书寨钙咬崔绎雾害播畦侮耪厂合塔拔饯淆扣打织梧卸肢蚕犊辊润鼓第7课数挖掘的高级主题第7课数挖掘的高级主题垂直分布型数据帛德楷膳娩昂噬糟腺膀婉疮敛砚股瘤微泣挖无笔透畴唁恳逮颐傻饼猿基掸第7课数挖掘的高级主题第7课数挖掘的高级主题
