谱聚类
谱聚类
七月算法邹博
2015年11月15日
9月机器学习班2/21
谱和谱聚类
?方阵作为线性算子，它的所有特征值的全体统称方阵的谱。
?方阵的谱半径为最大的特征值
?矩阵A 的谱半径：(A T A)的最大特征值
?谱聚类是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类，从而达到对样本数据聚类的目的。
9月机器学习班3/21
谱分析的整体过程
?给定一组数据x 1,x 2,...x n ，记任意两个点之间的相似度(“距离”的减函数)为s ij =
?接下来，可以用相似度图来解决样本数据的聚类问题：找到图的一个划分，形成若干个组(Group)，使得不同组之间有较低的权值，组内有较高的权值。
9月机器学习班4/21
若干概念
?无向图G=(V,E)
?邻接矩阵
?顶点的度di →度矩阵D (对角阵)
9月机器学习班5/21
若干概念
?子图A 的指示向量
?A 和B 是图G 的不相交子图，则定义子图的连接权：
9月机器学习班6/21
相似度图G 的建立方法
?全连接图
?高斯相似度函数：距离越大，相似度越小
?ε近邻图
?给定参数ε
?思考：如何选择ε？
?图G 的权值的均值
?图G 的最小生成树的最大边
?k 近邻图(k-nearest neighbor graph)
?若vi 的k 最近邻包含vj ，vj 的k 最近邻不一定包含vi ：有向图?忽略方向的图，往往简称“k 近邻图”
?两者都满足才连接的图，称作“互k 近邻图(mutual)”
9月机器学习班
7/21
相似度图G 的举例
9月机器学习班8/21
权值比较
?ε近邻图：ε=0.3，“月牙部分”非常紧的连接了，但“高斯部
分”很多都没连接。当数据有不同的“密度”时，往往发生这种问题。
?k 近邻图：可以解决数据存在不同密度时有些无法连接的问题，
甚至低密度的“高斯部分”与高密度的“月牙部分”也能够连接。同时，虽然两个“月牙部分”的距离比较近，但k 近邻还可以把它们区分开。
?互k 近邻图：它趋向于连接相同密度的部分，而不连接不同密度
的部分。这种性质介于ε近邻图和k 近邻图之间。如果需要聚类不同的密度，这个性质非常有用。
?全连接图：使用高斯相似度函数可以很好的建立权值矩阵。但缺点是建立的矩阵不是稀疏的。
?总结：首先尝试使用k 近邻图。
9月机器学习班9/21
拉普拉斯矩阵及其性质
?拉普拉斯矩阵：L = D –W
?L 是对称半正定矩阵；
?L 的最小特征值是0，相应的特征向量是?L 有n 个非负实特征值
9月机器学习班10/21
拉普拉斯矩阵的定义
?计算点之间的邻接相似度矩阵W
?若两个点的相似度值越大，表示这两个点越相似；?同时，定义w ij =0表示v i ,v j 两个点没有任何相似性(无穷远)
?W 的第i 行元素的和为v i 的度。形成顶点度对角阵D
?d ii 表示第i 个点的度
?除主对角线元素，D 其他位置为0?未正则的拉普拉斯矩阵：L=D-W
?正则拉普拉斯矩阵?对称拉普拉斯矩阵
?随机游走拉普拉斯矩阵
?Random walk
9月机器学习班11/21
谱聚类算法：未正则拉普拉斯矩阵?输入：n 个点{p i }，簇的数目k
?
计算n ×n 的相似度矩阵W 和度矩阵D ；?
计算拉普拉斯矩阵L=D-W ；?
计算L 的前k 个特征向量u 1,u 2,...,u k ；?
将k 个列向量u 1,u 2,...,u k 组成矩阵U ，U ∈R n ×k ；?
对于i=1,2,...,n,令y i ∈R k 是U 的第i 行的向量；?使用k-means 算法将点(y i )i=1,2,...,n 聚类成簇
C 1,C 2,...C k ；
?输出簇A 1,A 2,...A k ，其中，Ai={j|y j ∈Ci}
9月机器学习班12/21
谱聚类算法：随机游走拉普拉斯矩阵?输入：n 个点{p i }，簇的数目k
?
计算n ×n 的相似度矩阵W 和度矩阵D ；?
计算正则拉普拉斯矩阵L rw =D -1(D-W)；?
计算L rw 的前k 个特征向量u 1,u 2,...,u k ；?
将k 个列向量u 1,u 2,...,u k 组成矩阵U ，U ∈R n ×k ；?
对于i=1,2,...,n,令y i ∈R k 是U 的第i 行的向量；?使用k-means 算法将点(y i )i=1,2,...,n 聚类成簇
C 1,C 2,...C k ；
?输出簇A 1,A 2,...A k ，其中，Ai={j|y j ∈Ci}
9月机器学习班13/21
谱聚类算法：对称拉普拉斯矩阵?输入：n 个点{p i }，簇的数目k
?
计算n ×n 的相似度矩阵W 和度矩阵D ；?
计算正则拉普拉斯矩阵L sym =D -1/2(D-W) D -1/2；?
计算L sym 的前k 个特征向量u 1,u 2,...,u k ；?
将k 个列向量u 1,u 2,...,u k 组成矩阵U ，U ∈R n ×k ；?
对于i=1,2,...,n,令y i ∈R k 是U 的第i 行的向量；?
对于i=1,2,...,n,将y i ∈R k 依次单位化，使得|y i |=1；?
使用k-means 算法将点(y i )i=1,2,...,n 聚类成簇C 1,C 2,...C k ；
?输出簇A 1,A 2,...A k ，其中，Ai={j|y j ∈Ci}
9月机器学习班14/21
一个实例
9月机器学习班15/21
Code
9月机器学习班16/21
聚类效果
9月机器学习班17/21
聚类失败的情况
9月机器学习班18/21
进一步思考
?谱聚类中的K ，如何确定？
?考察计算得到的各个特征值λ：选择k ，使得λ1, λ2,…,λk 很小，而λk+1相对比较大。
?最后一步的K-Means ，作用是什么？
?事实上，目标函数是关于子图划分指示向量的函数，该向量的值根据子图划分确定，是离散的若干值。但由于问题是NP 的，转换成求连续实数域上的解，最后再用K-Means 的办法离散化。
?可以用其他方法代替。如使用超平面，或者使用k 个特征向量张成的子空间达到同样的目的。
?未正则拉普拉斯矩阵、对称拉普拉斯矩阵、随机游走拉普拉斯矩阵，首选哪一个？
?随机游走拉普拉斯矩阵
?拉普拉斯矩阵除了通过切割图的方法，可以通过随机游走、扰动论等理论来解释。
9月机器学习班19/21
随机游走和拉普拉斯矩阵的关系
?图论中的随机游走是一个随机过程，它从一个顶点跳转到另外一个顶点。谱聚类即找到图的一个划分，使得随机游走在相同的簇中停留而几乎不会游走到其他簇。
?
转移矩阵：从顶点vi 跳转到顶点vj 的概率正比于边的权值wij
9月机器学习班20/21我们在这里
?https://www.docsj.com/doc/8b4937659.html,/
?视频/课程/社区
?七月题库APP：Android/iOS
?https://www.docsj.com/doc/8b4937659.html,/
?微博
?@研究者July
?@七月题库
?@邹博_机器学习
?微信公众号
?julyedu
基于谱聚类的图像分割
本科生毕业设计 姓名：学号： 学院：计算机科学与技术学院 专业：计算机科学与技术 设计题目：基于谱聚类的图像分割 专题：图像分割的设计与实现 指导教师：职称：副教授
大学毕业设计任务书 学院计算机专业年级学生姓名 任务下达日期： 毕业设计日期： 毕业设计题目： 毕业设计专题题目 毕业设计主要内容和要求： 院长签章：指导教师签字：
中国矿业大学毕业设计指导教师评阅书 指导教师评语（①基础理论及基本技能的掌握；②独立解决实际问题的能力；③研究内容的理论依据和技术方法；④取得的主要成果及创新点；⑤工作态度及工作量；⑥总体评价及建议成绩；⑦存在问题；⑧是否同意答辩等）： 成绩：指导教师签字： 年月日
中国矿业大学毕业设计评阅教师评阅书 评阅教师评语（①选题的意义；②基础理论及基本技能的掌握；③综合运用所学知识解决实际问题的能力；③工作量的大小；④取得的主要成果及创新点；⑤写作的规范程度；⑥总体评价及建议成绩；⑦存在问题；⑧是否同意答辩等）： 成绩：评阅教师签字： 年月日
中国矿业大学毕业设计答辩及综合成绩
需求分析 一、利用前台，得到一张原始JPG图片； 二、把这张图片传到后台，JAVA通过JRI调用R； 三、利用R调用K-Means的改进算法，实现对这张图片的处理，由于一张图片的 像素值是一个矩阵，可以得到一组关于像素值的数据； 四、把这组像素值进行分类，对各类赋予不同的颜色进行标记，从而区分出需要的 图片信息； 五、把得到的新图片传到前台； 六、前台对进行处理后的图片进行显示，从图像中得到需要的信息，从而实现图像 的分割。
近似谱聚类算法描述
二、近似谱聚类算法描述 本节论文阐述基于相似矩阵稀疏化方法稀疏化后离群点的优化处理，并将该处理步骤应用于谱聚类算法中。基于上述分析近似谱聚类算法整体流程总结描述如表3.2所示。 表3.2 近似谱聚类算法（ASCA） 算法：近似谱聚类算法（ASCA） 输入：数据点，待聚类数目 输出：聚类 1. 使用公式，（其中，是的个最近邻按距离排序后第个邻居，同理，），构建相似矩阵； 2. 使用稀疏化矩阵获得半正定矩阵，找出矩阵对称位置不一致的相似度，并将对称元素设置为0，调整为对称半正定矩阵； 3. 使用优化公式对矩阵进行离群点调优； 4. 计算对称半正定拉普拉斯矩阵； 5. 计算的特征向量分解，找出第k个最小非零特征特征量，并按列排列k个特征向量构建特征向量矩阵； 6. 计算标准化矩阵（）； 7. 使用粗糙集模型选择k-means初始化聚类中心位置并对矩阵进行k-means聚类，把其聚类成k组（）。 基于近似谱聚类算法整体步骤描述，为进行近似谱聚类算法Matlab辅助实验铺垫，绘制近似谱聚类算法流程示意图如图3.1所示。Matlab辅助实验主要是将示意图3.1中的所示的算法与正交化Nystr?m低阶子矩阵抽样近似相似矩阵谱聚类算法（ONSP: Orthogonalization Nystr?m Spectral Clustering）和最近邻稀疏化近似相似矩阵谱聚类算法（tNNSC: Spectral Clustering）进行对比，并验证其聚类效果。 图3.1 近似谱聚类算法流程示意图 三、近似谱聚类算法时间复杂度分析 现对基于相似矩阵稀疏化方法离群点优化的近似谱聚类算法时间复杂度简单分析，步骤1：使用高斯函数公式构建相似矩阵的时间复杂度是，其中表示数据点数目、表示数据维数，计算数据点和之间的相似度的时间复杂度是，则计算整个数据集的时间复杂度是；步骤2：使用稀疏化矩阵获得半正定矩阵并调整为对称半正定矩阵借助于最大堆，其时间复杂度是，其中是最近邻数；步骤3：优化离群点步骤是非确定性多项式困难问题NP-hard （Non deterministic Ploynomial Hard）问题，其时间复杂度随近似相似度矩阵维数按指数增长；步骤4与步骤5：计算对称半正定拉普拉斯矩阵并找出k个最小非零特征值的特征向量的时间复杂度在论文第二章第二节中已经详细分析过，即；步骤6：计算标准化矩阵的时间复杂度是；步骤7：执行k-means聚类时间复杂度是：，其中表示k-means聚类过程迭代的次数，指待聚类数目。 第三节近似谱聚类算法实验分析 一、近似谱聚类算法辅助实验 （1）Matlab辅助实验环境描述 为验证表3.2所示近似谱聚类算法与正交化Nystr?m低阶子矩阵抽样近似相似矩阵谱聚类算法和最近邻稀疏化近似相似矩阵谱聚类算法的性能，鉴于Hadoop MapReduce并行实验对
大数据建模与挖掘应用
关于举办“大数据建模与分析挖掘应用”实战培训班的通知地点北京上海 时间12月 23-26 1月 12-15 一、课程简介 大数据建模与分析挖掘技术已经逐步地应用到新兴互联网企业（如电子商务网站、搜索引擎、社交网站、互联网广告服务提供商等）、银行金融证券企业、电信运营等行业，给这些行业带来了一定的数据价值增值作用。 本次课程面向有一定的数据分析挖掘算法基础的工程师，带大家实践大数据分析挖掘平台的项目训练，系统地讲解数据准备、数据建模、挖掘模型建立、大数据分析与挖掘算法应用在业务模型中，结合主流的Hadoop与Spark大数据分析平台架构，实现项目训练。 结合业界使用最广泛的主流大数据平台技术，重点剖析基于大数据分析算法与BI技术应用，包括分类算法、聚类算法、预测分析算法、推荐分析模型等在业务中的实践应用，并根据讲师给定的数据集，实现两个基本的日志数据分析挖掘系统，以及电商（或内容）推荐系统引擎。 本课程基本的实践环境是Linux集群，JDK1.8， Hadoop 2.7.*，Spark 2.1.*。 学员需要准备的电脑最好是i5及以上CPU，4GB及以上内存，硬盘空间预留50GB（可用移动硬盘），基本的大数据分析平台所依赖的软件包和依赖库等，讲师已经提前部署在虚拟机镜像（VMware镜像），学员根据讲师的操作任务进行实践。 本课程采用技术原理与项目实战相结合的方式进行教学，在讲授原理的过程中，穿插实际的系统操作，本课程讲师也精心准备的实际的应用案例供学员动手训练。 二、培训目标 1.本课程让学员充分掌握大数据平台技术架构、大数据分析的基本理论、机器学习的常用算法、国内外主流的大数据分析与BI商业智能分析解决方案、以及大数据分析在搜索引擎、广告服务推荐、电商数据分析、金融客户分析方面的应用案例。 2.本课程强调主流的大数据分析挖掘算法技术的应用和分析平台的实施，让学员掌握主流的基于大数据Hadoop和Spark、R的大数据分析平台架构和实际应用，并用结合实际的生产系统案例进
谱聚类Clustering -
聚类分析 1.聚类分析定义： 2.聚类方法： 3.谱聚类： 3.1 常见矩阵变换 3.2 谱聚类流程 3.3 谱聚类理论前提、证明 3.4 图像分割实例结果 4.总结：
聚类分析： ?聚类分析（Cluster analysis，亦称为群集分析）是对于静态数据分析的一门技术，在许多领域受到广泛应用，包括机器学习，数据挖掘，模式识别，图像分析以及生物信息。
算法分类： ?数据聚类算法可以分为结构性或者分散性。 ?结构性算法以前成功使用过的聚类器进行分类。结构性算法可以从上至下或者从下至上双向进行计算。从下至上算法从每个对象作为单独分类开始，不断融合其中相近的对象。而从上至下算法则是把所有对象作为一个整体分类，然后逐渐分小。 ?分散型算法是一次确定所有分类。K-均值法及衍生算法。 ?谱聚类（spectral clustering）
结构型：层次聚类的一个例子：
分散型：K-均值算法：
分散型k-means 及其衍生算法的比较：K-means K-Medoids K-Means算法： 1. 将数据分为k个非空子集 2. 计算每个类中心点（k-means
网络社区划分算法
网络社区划分算法 目录 ? 1 简介 ? 2 构建一个点击流网络 ? 3 网络社区划分的两种主要思路：拓扑分析和流分析 ? 4 拓扑分析 o 4.1 计算网络的模块化程度Q-Modularity o 4.2 计算网络的连边紧密度Edge betweenness o 4.3 计算网络拉普拉斯矩阵的特征向量Leading eigenvector o 4.4 通过fast greedy方法搜索网络模块化程度Q-Modularity的最大值 o 4.5 通过multi level方法搜索网络模块化程度Q-Modularity的最大值 ? 5 流分析 o 5.1 随机游走算法Walk Trap o 5.2 标签扩散算法label propagation o 5.3 流编码算法the Map Equation o 5.4 流层级算法Role-based Similarity ? 6 总结 [1]简介 使用许多互联网数据，我们都可以构建出这样的网络，其节点为某一种信息资源，如图片，视频，帖子，新闻等，连边为用户在资源之间的流动。对于这样的网络，使用社区划分算法可以揭示信息资源之间的相关性，这种相关性的发现利用了用户对信息资源的处理信息，因此比起单纯使用资源本身携带的信息来聚类（例如，使用新闻包含的关键词对新闻资源进行聚类），是一种更深刻的知识发现。 假设我们手头有一批用户在一段期间内访问某类资源的数据。为了减少数据数理规模，我们一般只考虑最经常被访问的一批资源。因此在数据处理中，我们考虑UV（user visit）排名前V的资源，得到节点集合|V|，然后对于一个用户i在一段时间内（例如一天）内访问的资源，选择属于|V|的子集vi。如果我们有用户访问资源的时间，就可以按照时间上的先后顺序，从vi中产生vi-1条有向边。如果我们没有时间的数据，可以vi两两间建立联系，形成vi(vi-1)/2条无向边。因为后者对数据的要求比较低，下文中，暂时先考虑后者的情况。对于一天内的n个用户做这个操作，最后将得到的总数为的连边里相同的边合并，得到|M|个不同的边，每条边上都带有权重信息。这样，我们就得到了V个节点，M条边的一个加权无向网络，反应的是在一天之内用户在主要的信息资源间的流动情况。在这个网络上，我们可以通过社区划分的算法对信息资源进行分类。 社区划分的算法比较多，但我个人认为大致可以分为两大类：拓扑分析和流分析。前者一般适用于无向无权网络，思路是社区内部的连边密度要高于社区间。后者适用于有向有权网络，思路是发现在网络的某种流动（物质、能量、
应用层DDOS攻击检测技术研究
应用层DDOS攻击检测技术研究 熊俊 (湖南警察学院湖南长沙410138) 【摘要】随着检测底层DDoS攻击的技术不断成熟和完善，应用层DDoS攻击越来越多。由于应用层协议的复杂性，应用层DDoS攻击更具隐蔽性和破坏性，检测难度更大。通过研究正常用户访问的网络流量特征和应用层DDoS攻击的流量特征，采用固定时间窗口内的请求时间间隔以及页面作为特征。通过正常用户和僵尸程序访问表现出不同的特点，对会话进行聚类分析，从而检测出攻击，经过实验，表明本检测算法具有较好的检测性能。 【关键词】DDOS；应用层；聚类；异常检测 Xiong Jun (Hunan Police Academy HunanChangsha410138) 0引言 根据世界著名网络安全公司ＡｒｂｏｒＮｅｔｗｏｒｋｓ在２０１１年发布的安全报告显示，分布式拒绝服务攻击是运 营商、服务提供商以及密切依赖网络的企业最大的威 胁。国内的网络安全公司—绿盟科技２０１１年发布的 网络安全回顾指出，目前网络攻击者逐渐将目标聚集到 实施破坏和信息窃取上来，而实施破坏的主要途径就是 针对网络空间发动ＤＤｏＳ攻击。国家互联网应急中心ＣＮＣＥＲＴ在２０１１发布的安全态势综述中指出，ＤＤｏＳ攻 击仍然呈频率高、规模大等特点，我国日均发生流量大 于１Ｇ的ＤＤｏＳ攻击事件达３６５起。大多数攻击针对网 站如政府网站、游戏服务器以及ＤＮＳ服务器，造成受害 者损失大量收入，对ＤＮＳ服务器的攻击会导致大片地区互联网用户不能使用网络服务，典型案例如２００９年 暴风事件，导致江西、河北等９个省市大量用户遭遇上 网故障。安全公司卡巴斯基发布的２０１１下半年安全监 控报告中指出，ｈｔｔｐ类型的ＤＤｏＳ攻击占据了所有的 ＤＤｏＳ攻击类型的８０％，可见应用层ＤＤｏＳ危害之大。 ＤＤｏＳ攻击最早开始于１９９６年，２００２年开始在国 内出现，２００３年便初具规模。ＤＤｏＳ攻击发展趋势为从 低层协议向高层协议发展，传统ＤＤｏＳ攻击利用协议漏 洞或者洪水攻击等对受害者发起攻击，如网络层Ｎｕｋｅ 攻击利用发送畸形的ＩＣＭＰ数据包使得受害者当机，网 络层泪滴攻击利用发送重叠的ＩＰ分片使得目标主机 ＴＣＰ／ＩＰ协议栈崩溃而拒绝服务。ＵＤＰＦｌｏｏｄ、ＴＣＰＦｌｏｏｄ等传输层的洪水攻击利用发送超出受害者服务能力的 大量数据包，消耗掉受害者的网络带宽、ＣＰＵ处理能力、
宁波老三区街道社区划分
江北区街道： 中马街道：槐树社区、新马社区、浮石社区、外滩社区、盐仓社区、咸宁社区 白沙街道：白沙社区、北站社区、大庆社区、正大社区、桃源社区 孔浦街道：绿梅、怡江、红梅、百合、白杨、孔浦一村、孔浦二村、文竹 文教街道：双东坊社区、范江岸社区、育才社区、翠柏社区、大闸社区、繁景社区、北岸琴森社区，永红村 甬江街道：白杨社区、百合社区、梅堰社区，北郊、湾头，河西村、畈里塘村、外漕村、夏家村、河东村、压赛村、孔浦村、甄隘村、下江村、姚江村 庄桥街道：河东社区、河西社区、广厦社区、广庭社区、天水社区、天合社区、费市社区、天成社区；（7个居民点）车站、镇北、费市、马径、镇南、上邵、袁陈；（25个行政村）孔家村、葛家村、李家村、马径村、西卫桥村、童家村、姚家村、东邵村、西邵村、袁陈村、谢家村、颜家村、邵家村、冯家村、费市村、居陆村、灵山村、胡家村、苏冯村、上邵村、邵余村、应家村、洪家村、联群村、塘民村 洪塘街道：洪塘社区、姚江社区、亲亲社区、洪都社区、宁沁社区、洋市社区、裘市社区、北欣社区、逸嘉社区（22个行政村）洪塘村、荪湖村、安山村、周陈村、后张村、上沈村、旧宅村、赵家村、下沈村、前后潘村、林家村、叶家斗村、洋市村、孙家村、上宅村、西江村、横山村、郎家村、裘市村、朱界村、邵家渡村、西洪村 海曙区街道： 灵塔街道：新街社区、郡庙社区、天封社区、莲桥社区。 月湖街道：太阳社区、梅园社区、桂井社区、县学社区、迎凤社区、平桥社区、天一社区。 鼓楼街道：苍水社区、秀水社区、孝闻社区、文昌社区、中山社区、和义社区。 南门街道：澄浪社区、柳锦社区、万安社区、红起社区、周江岸社区、朝阳社区、车站社区、马园社区、朗官社区、尹江岸社区、迎春社区。 西门街道：汪弄社区、北郊社区、文化社区、龙柏社区、柳庄社区、新高社区、永丰社区、芝红社区、新芝社区、翠南社区、胜丰社区、翠中社区、东社区。 白云街道：云和社区、云乐社区、联南社区(泰丰街10号)、牡丹社区、云丰社区、联北社区、安丰社区、宝善社区、安泰社区、南雅社区。 段塘街道：南苑社区、华兴社区、新典社区、南塘社区、洞桥社区、雄镇社区、小漕社区、南都社区。 望春街道：天一家园社区、泰安社区、徐家漕社区、西成社区、信谊社区、新星村、后孙村、徐家漕村、望春桥村、双杨村、西成村、胜丰村、姚丰村、前丰村、甬丰村、联丰村、震丰村。 江东区街道： 白鹤街道：孔雀、黄鹂、丹凤、镇安、王隘、白鹤、贺丞、丹顶鹤、紫鹃、周宿渡、日月星辰。百丈街道：后塘、朱雀、七塔、宁舟、舟孟、演武、华严、潜龙、中山、划船。 东胜街道：张斌、庆安、史家、曙光、大河、泰和、樱花、戎家、王家。 明楼街道：辖惊驾、林家、徐家、东海、明南、徐戎、明北、朝晖、明东、常青藤。 东柳街道：辖园丁、锦苑、东柳坊、太古城、华侨城、幸福苑、华光城、安居、中兴、月季、东海花园。 东郊街道：仇毕、宁丰社区。 福明街道：江南、明一、南余、余隘、戚隘桥、七里垫、史魏家、张隘、柳隘、松下、桑家、邵家、王家园、福明家园、新源、陆嘉、波波城、碧城、新城、福城、东城、江城、宁城、明城。新明街道：辖老庙、朱一、新晖、明月、滨江。
谱聚类报告
机器学习报告 一．绪论 聚类是探索性数据分析中广泛采用的一种技术，其应用范围包括统计学、计算机科学、生物学、社会科学和心理学等等。在处理经验数据的时候，我们可能倾向于根据数据的“近似表现”将数据确定到一定的类别。而本次我们小组的实验主要是基于聚类算法中的谱聚类方法，通过对两种谱聚类方法的实验和一些应用，验证算法的效果，加深对该方法的理解。 由于谱聚类的数值实现很简单，利用简单的线性代数学方法就能有效解决，而且相比传统的K 均值方法等聚类方法有很多优点，所以谱聚类方法称为了很流行的现代聚类算法之一。 以K 均值方法为例，正如我们所知，该方法主要存在这样一些问题：首先，其只适用于凸球形的样本空间，如果样本空间非凸，则会陷入局部最优，导致聚类效果不佳；再有，由于该方法计算使用的是欧氏空间中的原始数据向量，所以在样本维数很大的时候，K 均值算法的计算量会很大，导致了计算的困难；聚类数K 难以确定等等。而谱聚类则能很好地解决这些问题。 在本次实验中，我们小组根据相关文献，认真学习和讨论了谱聚类的先关概念。首先，我们研究了一般的谱聚类和标准化谱聚类的概念和它们的异同，并通过实验对比，验证了谱聚类的效果，其中标准化谱聚类有显著的优势。接下来，将谱聚类应用于图像分割问题，显示出谱聚类良好的应用价值。最后，我们查阅相关文献，尝试从另外一个角度去理解谱聚类方法。通过这次学习，我们对谱聚类的理解得到了大大加深，对于很多疑难的地方也通过查看有关文献和小组讨论得到了解决，并通过小组合作锻炼了自身的团队意识和配合工作的能力。 二．谱聚类基本思想 谱聚类是一种基于图论的聚类方法，把样本看作图的顶点，样本间的相似度对应带权值的边（其中相似度可以通过高斯核函数等方法构造），根据类间相似度最小，类内相似度最大的原则，便可以将样本聚类问题变成了图的分割问题：分割使得连接不同类之间的边的权值尽可能小，而类内点之间的边的权值尽可能高。虽然这样对应的最小化图分割问题是一个NP-HARD 问题，但是我们可以将其转化为最小化图的Laplace 矩阵的特征值问题。 具体地，给定样本特征之后，我们首先要计算样本两两之间的相似度值，并通过这些值构造出近邻矩阵。以高斯核函数为例，计算公式如下： 22||||(2)i j x x ij w e σ--= 作为第i 个样本和第j 个样本之间相似度的度量。而近邻矩阵如下： ()ij W w =。
数据仓库复习题
第一章概述 1.数据挖掘的定义？（书P2，PPT_P8） 从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。 2.数据挖掘的源是否必须是数据仓库的数据？可以有哪些来源？（PPT_P14） 关系数据库、数据仓库、事务数据库、高级数据等 3.数据挖掘的常用方法？（P4、PPT_P29） 聚类分析、决策树、人工神经网络、粗糙集、关联规则挖掘、统计分析等 4.数据挖掘的过程包括哪些步骤，每一步具体包括哪些内容？（书P2-3，PPT_P17-19） 确定业务对象、数据准备、数据挖掘、结果分析与知识同化。 5.数据挖掘与数据仓库的关系（联系和区别）？书P6-7，PPT_P45-46 联系：1，数据仓库为数据挖掘提供了更好的，更广泛的数据源 2，数据仓库韦数据挖掘提供了新的支持平台。 3，数据仓库为更好地使用数据挖掘工具提供了方便 4，数据挖掘对数据仓库提供了更好的决策支持。 5，数据挖掘对数据仓库的数据组织提出了更高的要求 6，数据挖掘还为数据仓库提供了广泛的技术支持 区别：数据仓库是一种存储技术，它包含大量的历史数据、当前的详细数据以及综合数据，它能为不同用户的不同决策需要提供所需的数据和信息。~~数据挖掘是从人工智能机器学习中发展起来的，它研究各种方法和技术，从大量的数据中挖掘出有用的信息和知识。 第二章数据仓库 1.数据仓库的定义 数据仓库——是一个面向主题的、集成的、随时间而变化的、不容易丢失的数据集合，支持管理部门的决策定制过程。 2.数据仓库数据的四大基本特征： 面向主题的、集成的、不可更新的、随时间变化的。 3.数据仓库体系结构有三个独立的数据层次： 信息获取层、信息存储层、信息传递层。 4.粒度的定义？它对数据仓库有什么影响？ （1）是指数据仓库的数据单位中保存数据细化或综合程度的级别。粒度越小，细节程度越高，综合程度越低，回答查询的种类就越多。 （2）影响存放在数据仓库中的数据量大小；影响数据仓库所能回答查询问题的细节程度。 5.在数据仓库中，数据按照粒度从小到大可分为四个级别： 早期细节级、当前细节级、轻度细节级和高度细节级。 6.数据分割的标准：可按日期、地域、业务领域、或按多个分割标准的组合，但一般包括日期项。 7.数据仓库设计中，一般存在着三级数据模型： 概念数据模型、逻辑数据模型、物理数据模型 8.数据仓库设计步骤 （1）概念模型设计 （2）技术准备工作 （3）逻辑模型设计 （4）物理模型设计 （5）数据仓库的生成
谱聚类算法(Spectral Clustering)原理分析
谱聚类算法(Spectral Clustering) 谱聚类(Spectral Clustering, SC)是一种基于图论的聚类方法——将带权无向图划分为两个或两个以上的最优子图，使子图内部尽量相似，而子图间距离尽量距离较远，以达到常见的聚类的目的。其中的最优是指最优目标函数不同，可以是割边最小分割——如图1的Smallest cut(如后文的Min cut)，也可以是分割规模差不多且割边最小的分割——如图1的Best cut(如后文的Normalized cut)。 图1 谱聚类无向图划分——Smallest cut和Best cut 这样，谱聚类能够识别任意形状的样本空间且收敛于全局最优解，其基本思想是利用样本数据的相似矩阵(拉普拉斯矩阵)进行特征分解后得到的特征向量进行聚类。 1 理论基础 对于如下空间向量item-user matrix： 如果要将item做聚类，常常想到k-means聚类方法，复杂度为o(tknm)，t为迭代次数，k为类的个数、n为item个数、m为空间向量特征数： 1 如果M足够大呢？ 2 K的选取？ 3 类的假设是凸球形的？ 4 如果item是不同的实体呢？ 5 Kmeans无可避免的局部最优收敛？ …… 这些都使常见的聚类问题变得相当复杂。 1.1 图的表示
如果我们计算出item与item之间的相似度，便可以得到一个只有item的相似矩阵，进一步，将item看成了Graph(G)中Vertex(V)，歌曲之间的相似度看成G中的Edge(E)，这样便得到我们常见的图的概念。 对于图的表示(如图2)，常用的有： 邻接矩阵：E，e ij表示v i和v i的边的权值，E为对称矩阵，对角线上元素为0，如图2-2。 Laplacian矩阵：L = D – E，其中d i (行或列元素的和)，如图2-3。 图2 图的表示 1.2 特征值与L矩阵 先考虑一种最优化图像分割方法，以二分为例，将图cut为S和T两部分，等价于如下损失函数cut(S, T)，如公式1所示，即最小(砍掉的边的加权和)。 假设二分成两类，S和T，用q(如公式2所示)表示分类情况，且q满足公式3的关系，用于类标识。 那么：
谱聚类
谱聚类 七月算法邹博 2015年11月15日
9月机器学习班2/21 谱和谱聚类 ?方阵作为线性算子，它的所有特征值的全体统称方阵的谱。 ?方阵的谱半径为最大的特征值 ?矩阵A 的谱半径：(A T A)的最大特征值 ?谱聚类是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类，从而达到对样本数据聚类的目的。
9月机器学习班3/21 谱分析的整体过程 ?给定一组数据x 1,x 2,...x n ，记任意两个点之间的相似度(“距离”的减函数)为s ij =
9月机器学习班4/21 若干概念 ?无向图G=(V,E) ?邻接矩阵 ?顶点的度di →度矩阵D (对角阵)
9月机器学习班5/21 若干概念 ?子图A 的指示向量 ?A 和B 是图G 的不相交子图，则定义子图的连接权：
9月机器学习班6/21 相似度图G 的建立方法 ?全连接图 ?高斯相似度函数：距离越大，相似度越小 ?ε近邻图 ?给定参数ε ?思考：如何选择ε？ ?图G 的权值的均值 ?图G 的最小生成树的最大边 ?k 近邻图(k-nearest neighbor graph) ?若vi 的k 最近邻包含vj ，vj 的k 最近邻不一定包含vi ：有向图?忽略方向的图，往往简称“k 近邻图” ?两者都满足才连接的图，称作“互k 近邻图(mutual)”
谱聚类算法 算法简介
谱聚类算法算法简介 谱聚类算法建立在谱图理论基础上，与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。 该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并且计算矩阵的特征值和特征向量，然后选择合适的特征向量聚类不同的数据点。谱聚类算法最初用于计算机视觉、VLS I 设计等领域，最近才开始用于机器学习中，并迅速成为国际上机器学习领域的研究热点。 谱聚类算法建立在图论中的谱图理论基础上，其本质是将聚类问题转化为图的最优划分问题，是一种点对聚类算法，对数据聚类具有很好的应用前景。 算法步骤 谱聚类算法将数据集中的每个对象看作是图的顶点V，将顶点间的相似度量化作为相应顶点连接边E的权值，这样就得到一个基于相似度的无向加权图G(V, E)，于是聚类问题就可以转化为图的划分问题。基于图论的最优划分准则就是使划分成的子图内部相似度最大，子图之间的相似度最小。 虽然根据不同的准则函数及谱映射方法，谱聚类算法有着不同的具体实现方法，但是这些实现方法都可以归纳为下面三个主要步骤： 1) 构建表示对象集的相似度矩阵W； 2) 通过计算相似度矩阵或拉普拉斯矩阵的前k个特征值与特征向量，构建特征向量空间； 3) 利用K-means或其它经典聚类算法对特征向量空间中的特征向量进行聚类。 上面的步骤只是谱聚类算法的一个总体框架，由于划分准则、相似度矩阵计算方法等因素的差别，具体的算法实现同样会有所差别，但其本质依然是图划分问题的连续放松形式。 划分准则 谱聚类算法将聚类问题就可以转化为图的划分问题之后，基于图论的划分准则的优劣直接影响到聚类结果的好坏。常见的划分准则有Mini cut，Average cut，Normalized cut，Min-max cut，Ratio cut，MNcut等。最小割集准则 在对图像分割中产生了较好的效果，但是该准则容易产生分割出只包含几个顶点的较小子图的歪斜分割现象。 规范割集准则 在2000年Shi和Malik根据谱图理论建立了2-way划分的规范割目标函数，此方法通过计算分割之后的连接边损失值在各个子图与所有顶点之间的连接边权重总值中所占比例之和来衡量划分的优劣。 比例割集准则 对于超大规模集成电路设计中的电路层次设计和分支划分问题，最
网络社区划分算法
网络社区划分算法 目录 ?1简介 ?2构建一个点击流网络 ?3网络社区划分的两种主要思路：拓扑分析和流分析 ?4拓扑分析 o 4.1计算网络的模块化程度Q-Modularity o 4.2计算网络的连边紧密度Edge betweenness o 4.3计算网络拉普拉斯矩阵的特征向量Leading eigenvector o 4.4通过fast greedy方法搜索网络模块化程度Q-Modularity的最大值 o 4.5通过multi level方法搜索网络模块化程度Q-Modularity的最大值 ?5流分析 o 5.1随机游走算法Walk Trap o 5.2标签扩散算法label propagation o 5.3流编码算法 the Map Equation o 5.4流层级算法 Role-based Similarity ?6总结 []简介 使用许多互联网数据，我们都可以构建出这样的网络，其节点为某一种信息资源，如图片，视频，帖子，新闻等，连边为用户在资源之间的流动。对于这样的网络，使用社区划分算法可以揭示信息资源之间的相关性，这种相关性的发现利用了用户对信息资源的处理信息，因此比起单纯使用资源本身携带的信息来聚类（例如，使用新闻包含的关键词对新闻资源进行聚类），是一种更深刻的知识发现。 假设我们手头有一批用户在一段期间内访问某类资源的数据。为了减少数据数理规模，我们一般只考虑最经常被访问的一批资源。因此在数据处理中，我们考虑UV（user visit）排名前V的资源，得到节点集合|V|，然后对于一个用户i在一段时间内（例如一天）内访问的资源，选择属于|V|的子集vi。如果我们有用户访问资源的时间，就可以按照时间上的先后顺序，从vi中产生vi-1条有向边。如果我们没有时间的数据，可以vi两两间建立联系，形成vi(vi-1)/2条无向边。因为后者对数据的要求比较低，下文中，暂时先考虑后者的情况。对于一天内的n个用户做这个操作，最后将得到的总数为的连边里相同的边合并，得到|M|个不同的边，每条边上都带有权重信息。 这样，我们就得到了V个节点，M条边的一个加权无向网络，反应的是在一天之内用户在主要的信息资源间的流动情况。在这个网络上，我们可以通过社区划分的算法对信息资源进行分类。
谱聚类算法及其在图像分割中的应用
谱聚类算法及其在图像分割中的应用 1 引言 在对图像的研究和应用中，人们往往仅对图像中的某些部分或者说某些区域感兴趣。这些部分常称为目标或前景（其他部分称为背景），它们一般对应图像中特定的具有独特性质的区域。为了辨识和分析目标，需要将它们从图像中分离提取出来，在此基础上才有可能对目标进一步利用。图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。这里的特性可以是像素的灰度、颜色和纹理等，预先定义的目标可以对应单个区域，也可以对应多个区域。 多年来，对图像分割的研究一直是图像技术研究中的热点和焦点，它不但是从图像处理到图像分析的关键步骤[1]，而且是计算机视觉领域低层次视觉中的主要问题。图像分割的结果是图像特征提取和识别等图像理解的基础，只有在图像被分割后，图像的分析才成为可能。 图像分割在实际应用中已得到了广泛的应用，如图像编码、模式识别、位移估计、目标跟踪、大气图像、军用图像、遥感图像、生物医学图像分析等领域。同时，图像分割也在计算机视觉和图像识别的各种应用系统中占有相当重要的地位，它是研制和开发计算机视觉系统、字符识别和目标自动获取等图像识别和理解系统首先要解决的问题。概括地说只要需对图像目标进行提取测量等都离不开图像分割。 对分割算法的研究已经有几十年的历史，至今借助于各种理论已经提出了数以千计的分割算法[2]，而且这方面的研究仍然在积极进行。尽管人们在图像分割方面做了许多工作，但至今仍无通用的分割算法，也不存在一个判断分割是否成功的客观标准。因此已经提出的分割算法大都是针对具体问题的，并没有一种适合于所有图像的通用的分割算法。实际上由于不同领域的图像千差万别，也不可能存在万能的通用算法。 现有的分割算法非常多，大体上可以分为以下几类：阈值化分割、基于边缘检测的、基于区域的、基于聚类的和基于一些特定理论工具的分割方法。从图像的类型来分最常见的：有灰度图像分割、彩色图像分割和纹理图像分割等等。本
Python大数据机器实战
关于举办“Python大数据机器学习实战”高级工程师 实战培训班的通知 地点：北京--时间：12月25-12月28 一、课程学习目标 1.每个算法模块按照“原理讲解→分析数据→自己动手实现→特征与调参”的顺序。 2.“Python数据清洗和特征提取”，提升学习深度、降低学习坡度。 3.增加网络爬虫的原理和编写，从获取数据开始，重视将实践问题转换成实际模型的能力，分享工作中的实际案例或Kaggle案例：广告销量分析、环境数据异常检测和分析、数字图像手写体识别、Titanic乘客存活率预测、用户-电影推荐、真实新闻组数据主题分析、中文分词、股票数据特征分析等。 4.强化矩阵运算、概率论、数理统计的知识运用，掌握机器学习根本。 5.阐述机器学习原理，提供配套源码和数据。 6.以直观解释，增强感性理解。 7.对比不同的特征选择带来的预测效果差异。 8.重视项目实践，重视落地。思考不同算法之间的区别和联系，提高在实际工作中选择算法的能力。 9.涉及和讲解的部分Python库有：Numpy、Scipy、matplotlib、Pandas、scikit-learn、XGBoost、libSVM、LDA、Gensim、NLTK、HMMLearn。 二、课程目标 本课程特点是从数学层面推导最经典的机器学习算法，以及每种算法的示例和代码实现（Python）、如何做算法的参数调试、以实际应用案例分析各种算法的选择等。 三、培训对象 大数据分析应用开发工程师、大数据分析项目的规划咨询管理人员、大数据分析项目的IT项目高管人员、大数据分析与挖掘处理算法应用工程师、大数据分析集群运维工程师、大数据分析项目的售前和售后技术支持服务人员
社区门店规划原则(二)!区域划分很重要
手把手教您怎么把店开起来， 避过跳过的坑、踩过的雷， 减少投资风险、快速开店、提前盈利 对于初次开店的创业者来说，要想在短时间内把店面规划合理，可谓是犯愁。不过没有关系，【智家兔】现带来第二期门店规划攻略。 【详细规划】 根据门店装修情况和户型大小将门店划分为以下几个区域：收银区、食品区、非食区域、堆头区域、库房，并且对各个区域进行提前规划。 货架选择 市面上常见的货架材质有铁制货架、钢制货架和钢木货架，其中铁制货架价格实惠，但是容易锈蚀，使用寿命不长;钢制货架耐磨防损，承重强，价格也合理;钢木货架高档美观，质量好，但价格较高。总体看来，社区门店选择钢制货架最合适。 收银台 收银台一般设置在出入口，根据营业规模配备收银机，结账通道一般设计1-2米，这是两个顾客的最佳尺寸，收银台与最近货架之间的距离最少4米以上，保证有足够的空间让用户排队。 食品区 食品区一般位于在门店的中间区域，可以使用便利店双面货架和便利店端头架组合成中岛货架，不仅美观大方，而且实用性更高。不过要想呈现更好的效果，就要注意食品陈列的原则，保证商品整齐一致，相同规格摆在一起，做好分类工作。 非食品区 食品属于快消品，一般会在门店中占比较大的空间，剩下的空间留给日常生活用品，对于社区门店来说，1-2个货架基本够用，需求较大的商品放在黄金陈列区，减少顾客寻找商品的时间，提高成交的机率。 堆头区 收银台与货架之间的空间以及商品入口通道的中间一般为堆头位，用来放置新商品、推广期商品、品牌商品等重点物品，由于堆头的特殊位置，不能堆太高，不然会造成对顾客视线的阻挡。堆头区是促销商品的好位置，能够增加店里的纯利润。
社区及社区商业业态划分说明
社区及社区商业业态划分说明一、社区划分说明 （一）按规模划分 1、大型社区—居住区，是指大规模、公建设施配套完整的聚居地，人口规模3万人以上或用地规模60公顷以上。 2、中型社区—小区，人口规模10000-30000人或用地规模15-60公顷。 3、小型社区—组团，规模一般较小，人口10000人以下或用地规模15公顷以下，是单纯的居住形式。 （二）按社区建设时间划分 1、老社区 是指2000年以前建成的、社区商业建设尚无充分规划的社区。 2、新建社区 是指2000年（含）以后建成的、社区商业建设有比较完善规划的社区。3、在建社区 是指已完成社区商业建设规划，且正在建设当中的社区。 二、社区商业业态划分说明
（一）社区商业中心、商业街 社区商业中心是在城市的区域中心建立的，面积在5万平方米以内，集购物、餐饮及其他服务等多业态为一体的商业中心。 商业街是指社区内配置包括购物、餐饮及其他商业服务设施的街道，商业服务设施一般临街设立。 （二）餐饮店 是指即时加工制作、商品销售和服务性劳动等手段，向消费者提供饮料、食品、菜肴、消费场所和设备的经营单位。包括各种酒家、酒楼、饭店、饭馆、餐馆、面馆、早餐店、糕点店、咖啡店、休闲吧、酒吧、烧烤店等。 （三）超市、大型超市 超市是开架售货，集中收款，满足社区消费者日常生活需要的零售业态。根据商品结构不同，可分为食品超市和综合超市。 大型超市是实际营业面积6000平方米以上，品种齐全，满足顾客一次性购齐的零售业态。 （四）便利店 满足顾客便利性需求为主要目的的零售业态。 （五）食杂店
是以香烟、酒、饮料、休闲食品为主，独立传统的无明显品牌形象的零售业态。 （六）维修店 是指社区内配备的家电维修、自行车摩托车修理、汽车维修服务、修鞋、配钥匙等店铺。 （七）洗染店 从事洗衣、烫衣、染色、织补以及皮革衣物的清洗、上光等服务项目的经营单位。 （八）美容美发店 美发：根据宾客头型、脸型、发质和要求，为其设计、剪修、制作发型，提供肩部以上按摩及其相关服务。 美容：根据宾客的面型、皮肤特点和要求，运用多种美容技术、器械和化妆品，为其提供真皮层以上的护肤美容、化妆美容及其相关服务。 （九）旧货废弃物回收站 是指社区内配置的收取居民废品的单位。 （十）家庭服务 是指提供家庭钟点工、家政服务、家庭护理等服务的机构。
基于校园大数据构建大学生画像的技术实现
152 ?电子技术与软件工程 Electronic Technology & Software Engineering 数据库技术 ? Data Base Technique 【关键词】校园大数据 大学生画像 用户建模 谱聚类 随着社会步入大数据时代，高校不可避免的需要在教学及管理方面进行一系列改革。这其中最大的变化在于，学生的一切行为在学校面前都将是“可视化”的，随着大数据技术的深入研究与应用，高校在教学及管理领域的专注点将聚焦于如何利用教育大数据为学生提供优质的课程设计、良好的学习环境、精准的生活服务。于是，“大学生画像”概念应运而生。 1 关于大学生画像 1.1 大学生画像之定义 用户画像(persona)的概念最早由交互设计之父Alan Cooper 在《About Face ：交互设计精髓2》一书中提出：“Personas are a concrete representation of target users.” 是指真实用户的虚拟代表，是建立在一系列真实属性数据之上的目标用户模型。 大学生画像来自于用户画像，其定义目前尚无统一标准。[1]李光耀等描述为“基于大数据技术，通过整理搜集学生在网上的浏览、点击、留言、评论等碎片化的行为轨迹，研究学生言行，这些学生的言行轨迹直接或间接反映了用户的性格、习惯、态度等信息”。[2]董潇潇等描述“大学生行为画像是利用校园数据将学生行为信息标签化。” 本文将大学生画像描述成“基于以学生为中心的理念和校园大数据，根据其人口学特征、学习行为、社交活动、消费行为、思想动态、兴趣爱好等信息抽象出来并标签化的一系列学生模型集合。”1.2 大学生画像之意义 大学生画像对于高校的教学、管理和服务等方面均有着重要的指导意义和现实价值。 在课程设置方面，分析学生学业画像， 基于校园大数据构建大学生画像的技术实现 文/张海华1 郭田友2 张非3 可以帮助教学管理部门更加客观的了解学生对 大学课程的真实需求，更加科学的设置课程体系，能够精准的评价每一名学生。成都电子科技大学通过构建“学生画像”成功实现大学生学习挂科预警机制。 在学生工作方面，分析学生消费画像，可以帮助学工部门了解学生的经济和消费状况，从而设计精准、科学的帮扶机制，帮助贫困生顺利完成学业。南京大学成功将大数据技术应用于贫困生帮扶。安徽师范大学利用大数据挖掘技术为科学资助和精准资助提供了决策支持。 在毕业指导方面，分析学生职业画像，根据学生的能力模型进行职业发展轨迹推荐和“学生-企业”双向推荐，实现毕业生个人素质、求职意愿和企业岗位需求信息的“人岗精准对接”。海南师范大学利用大数据技术实现学生精准就业，提升了聘效率，拓宽学生就业渠道，有效管控就业数据。 2 大学生画像之构建 2.1 构建类别 根据大学生在校期间各项活动和数据，我们可以构建学生基础画像、学业画像、消费画像、心理画像、思想政治画像、职业画像、人格画像、评优助困画像、健康画像等一系列大学生画像集合。2.2 构建方法 构建大学生画像主要包括数据采集、数据清洗、用户建模、标签挖掘、画像聚类、可视化等工作。 数据采集按实时性分为在线采集和离线采集，其中在线采集包含个人基础数据和使用智慧校园系统发生的行为数据（如学习、消费、交流、上网等）。离线采集包括对各类系统交互日志和网络爬虫数据按照一定的算法规则进行挖掘收集。 通过数据采集得到的原始数据源存在“脏数据”，为了保证后期标签挖掘的准确性，需要进行填空、去噪、删重、修正、规范化等预处理。通过文本挖掘算法得到标签元数据和标签数据集并使之标准化，基于前述画像维度进行用户建模，并通过聚类算法对学生画像分类。 3 关键技术实现 3.1 数据处理 在进行用户建模之前，需要进行数据采集和清洗，我们选择Python 中的Sklearn 和Pandas 等模块作为数据清洗工具。 分析结构化数据的构成，我们做了如下清洗工作：通过使用常量替换、均值填充、回归预测等方法处理如考试成绩、三餐消费等缺失值、异常值问题；筛选并删除重复数据；利用分箱技术的箱体均值法处理图书借阅的噪音数据问题；通过格式转换处理数据编码和日期表示不一致问题；最后对清洗结果中同一维度的数据进行归一化和正则化处理，如家庭收入、学习成绩均处理成[0,1]之间的数字。3.2 用户建模 一个事件模型包括时间、地址、人物、内容四要素，每一次学生行为均是一次随机事件，可以描述为谁在何时何地址做何操作。因此数据模型概括为如下公式：学生标识+时间+行为类型+应用系统+内容。 学生标签的权重可能随时间增加而衰减，因此定义时间衰减因子为r ，行为类型、应用系统决定权重，内容决定了标签，可转换为公式：标签权重=衰减因子×行为权重×应用权重。 如某学生上月10日在图书馆系统查询了主题为大数据研究的论文，假设时间衰减因子公式r=1-(m-m0)*0.05（即每隔一个月衰减0.05），图书馆系统的权重为0.8，则其数据模型为： 学生学术标签为：科研，大数据，权重为(1-0.05)*0.8=0.76。 通过定义各类行为的时间衰减因子和系统以及内容权重，就可以对学生的全部行为建模。3.3 标签挖掘 标签元数据是用于描述标签分类的数据，我们将标签元数据划分为基本标签、经济标签、成绩标签、知识标签、体育标签、消费标签、饮食标签、社交标签、性格标签、心理标签、学习标签、思想标签等。 从数据提取维度来看，标签分为事实标签、模型标签和策略标签。事实标签来源于真实数据，定性描述学生的基本属性等，如家庭好、消费高、学霸。模型标签是对学生属性及行为进行抽象和聚类概况出来的，如足球迷群体、电竞迷群体。策略标签是根据学生信息和行为配合一定的规则策略设定，如可能挂科、有自杀倾向等。 在实践中，通过抓取校园论坛挖掘思想动态标签，抓取百度贴吧挖掘社交标签，分析 学习成绩设置成绩标签，分析图书借阅数据设置知识标签，分析消费行为和消费水平设置消 <<下转153页