聚类贪心算法

㈠ 数据挖掘的数据分析方法有哪些

回归分析、聚类、关联规则、特征、变化和偏差分析、Web页挖掘等， 它们分别从不同的角度对数据进行挖掘。 ①分类。分类是找出数据库中一组数据对象的共同特点并按照分类模式将其划分为不同的类，其目的是通过分类模型，将数据库中的数据项映射到某个给定的类别。它可以应用到客户的分类、客户的属性和特征分析、客户满意度分析、客户的购买趋势预测等，如一个汽车零售商将客户按照对汽车的喜好划分成不同的类，这样营销人员就可以将新型汽车的广告手册直接邮寄到有这种喜好的客户手中，从而大大增加了商业机会。 ②回归分析。回归分析方法反映的是事务数据库中属性值在时间上的特征，产生一个将数据项映射到一个实值预测变量的函数，发现变量或属性间的依赖关系，其主要研究问题包括数据序列的趋势特征、数据序列的预测以及数据间的相关关系等。它可以应用到市场营销的各个方面，如客户寻求、保持和预防客户流失活动、产品生命周期分析、销售趋势预测及有针对性的促销活动等。 ③聚类。聚类分析是把一组数据按照相似性和差异性分为几个类别，其目的是使得属于同一类别的数据间的相似性尽可能大，不同类别中的数据间的相似性尽可能小。它可以应用到客户群体的分类、客户背景分析、客户购买趋势预测、市场的细分等。 ④关联规则。关联规则是描述数据库中数据项之间所存在的关系的规则，即根据一个事务中某些项的出现可导出另一些项在同一事务中也出现，即隐藏在数据间的关联或相互关系。在客户关系管理中，通过对企业的客户数据库里的大量数据进行挖掘，可以从大量的记录中发现有趣的关联关系，找出影响市场营销效果的关键因素，为产品定位、定价与定制客户群，客户寻求、细分与保持，市场营销与推销，营销风险评估和诈骗预测等决策支持提供参考依据。 ⑤特征。特征分析是从数据库中的一组数据中提取出关于这些数据的特征式，这些特征式表达了该数据集的总体特征。如营销人员通过对客户流失因素的特征提取，可以得到导致客户流失的一系列原因和主要特征，利用这些特征可以有效地预防客户的流失。 ⑥变化和偏差分析。偏差包括很大一类潜在有趣的知识，如分类中的反常实例，模式的例外，观察结果对期望的偏差等，其目的是寻找观察结果与参照量之间有意义的差别。在企业危机管理及其预警中，管理者更感兴趣的是那些意外规则。意外规则的挖掘可以应用到各种异常信息的发现、分析、识别、评价和预警等方面。 ⑦Web页挖掘。随着Internet的迅速发展及Web 的全球普及， 使得Web上的信息量无比丰富，通过对Web的挖掘，可以利用Web 的海量数据进行分析，收集政治、经济、政策、科技、金融、各种市场、竞争对手、供求信息、客户等有关的信息，集中精力分析和处理那些对企业有重大或潜在重大影响的外部环境信息和内部经营信息，并根据分析结果找出企业管理过程中出现的各种问题和可能引起危机的先兆，对这些信息进行分析和处理，以便识别、分析、评价和管理危机。
来源:数据堂

㈡ 算法设计的目录

第1章引言：某些典型的问题
1.1第一个问题：稳定匹配
1.2五个典型问题
带解答的练习
练习
注释和进一步的阅读
第2章算法分析基础
2.1计算可解性
2.2增长的渐近阶
2.3用表和数组实现稳定匹配算法
2.4一般运行时间的概述
2.5更复杂的数据结构：优先队列
带解答的练习
练习
注释和进一步的阅读
第3章图
3.1基本定义与应用
3.2图的连通性与图的遍历
3.3用优先队列与栈实现图的遍历
3.4二分性测试：宽度优先搜索的一个应用
3.5有向图中的连通性
3.6有向无圈图与拓扑排序
带解答的练习
练习
注释和进一步的阅读
第4章贪心算法
4.1区间调度：贪心算法领先
4.2最小延迟调度：一个交换论证
4.3最优高速缓存：一个更复杂的交换论证
4.4一个图的最短路径
4.5最小生成树问题
4.6实现Kruskal算法：Unoin－Find数据结构
4.7聚类
4.8Huffman码与数据压缩
4.9最小费用有向树：一个多阶段贪心
带解答的练习
练习
注释和进一步的阅读
第5章分治策略
5.1第一个递推式：归并排序算法
5.2更多的递推关系
5.3计数逆序
5.4找最接邻近的点对
5.5整数乘法
5.6卷积与快速傅里叶变换
带解答的练习
练习
注释和进一步的阅读
第6章动态规划
6.1带权的区间调度：一个递归过程
6.2动态规划原理：备忘录或者子问题迭代
6.3分段的最小二乘：多重选择
6.4子集和与背包：加一个变量
6.5RNA二级结构：在区间上的动态规划
6.6序列比对
6.7通过分治策略在线性空间的序列比对
6.8图中的最短路径
6.9最短路径和距离向量协议
6.10图中的负圈
带解答的练习
练习
注释和进一步的阅读
第7章网络流
第8章Ng与计算的难解性
第9章一个超出
第10章扩展易解性的界限
第11章近似算法
第12章局部搜索
第13章随机算法
后记：永不停止运行的算法
索引

㈢ 数学之美总结

1.信息度量

信息就是不确定性的多少，信息就是要减少不确定性；

熵: 信息的混杂程度，越大，信息越杂，越不纯；

条件熵: 一个信息确定的条件下，另外一个信息不确定度的减少量；

互信息: 在一个信息的条件下，为了是另外一个信息不确定度减少所需要提供的信息量；

相对熵: 衡量两个函数值为正数的函数的相关性。

2.指纹信息

指纹: 每段信息包括文字，图片，音频，等都可以对应一组不太长的随机数

伪随机数:压缩

基于加密的伪随机数:密码

集合的判定，文章，网页的判定，视频的判定

指纹可能重复，但可能性很小

相似哈希:词，权重，指纹，二进制的结合(提供了一种思路)

3.最大熵模型

最大熵原理: 保留全部的不确定性，让风险降到最小；

最大熵模型: 在所有满足约束条件的模型中选出熵最大的模型；

模型学习: 任何一组不自相矛盾的信息，最大熵模型存在并且唯一，都具有相同的形式，指数形式；

特点: 能同时满足成千上万的中不同条件的模型(有效的组合很多特征)

参数训练: 对数似然函数求极大

4.期望最大

如果模型的变量都是观测变量，用极大似然估计或贝叶斯估计

如果存在隐含变量，用EM迭代，最大后验概率

典型:kmeans聚类，隐马的参数训练，最大熵模型的训练

特点: 局部最优，计算速度慢

5.散列表与布隆过滤器

散列表的核心:哈希函数hashcode(),equals()函数；

散列表的特点:时间复杂度o(1),浪费空间，冲突；

布隆过滤器核心: 一组二进制数和随机映射函数；

布隆过滤器的特点: 时间复杂度o(1)，节约空间，到存在错误率

6.文本分类

相似性: 余弦定理，距离

方法: k近邻思想，自底向上的两两合并，EM迭代，奇异值分解；

技巧: 计算时存储重复计算的变量，只考虑非零元素，删除虚词

余弦定理和奇异分解:余弦定理多次迭代，计算量大，消耗资源多；svd无需多次迭代，时间短，但存储空间需求大，适合超大规模分类；建议svd粗分类，余弦定理细分类

TF-IDF解决两个重要问题:词的预测能力越强，权重越大；停止词的权重为零

7.隐马尔可夫

马尔可夫假设: t时刻的状态只取决于t-1时刻

马尔可夫链: 状态链

隐马模型: 初始概率分布，状态转移概率分布，观测概率分布(马尔可夫假设，观测独立)

3个问题:

参数估计-baum-uelch算法

计算概率-直接，前向，后向算法

预测状态-维特比算法(动态规划)

8.贝叶斯网络

是马尔可夫链的推广(链状-拓扑)

又称信念网络: 弧+可信度

训练: 结构和参数训练，交叉进行

方法: 贪心算法，蒙卡，互信息

9.条件随机场

特点:观测值可能和前后的状态都有关

条件随机场是无向图，贝叶斯网络是有向图

核心:找到符合所有边缘分布的最大熵模型

10.有限状态机和动态规划

有限状态机: 开始，终止状态，有向弧，条件

常见:  建立状态机，已知状态机匹配字符串

区别: 基于概率的有限状态机和离散马尔可夫链等效

动态规划: 把全程路径最短锁定到局部路径最短

㈣ 倪志伟的论文专着

近五年来，在国内外学术期刊上公开发表论文30多篇，其中有15篇论文被EI或ISTP收录。出版的教材或专着有：
1．《Foxpro实用教程》，南京大学出版社，1994年（主编）
2．《用C++建造专家系统》，电子工业出版社，1996年 （副主编）3．《机器学习与智能决策支持系统》，科学出版社，2004年5月（副主编）
4．《编译原理》，北京希望电子出版社，2005年11月（主编）
5．《现代物流技术》，中国物资出版社，2006年1月（主编）（被评为国家“十一五”规划教材）
6．《物流信息系统》，中国物资出版社，2006年2月（副主编）
7. 《智能管理技术与方法》，科学出版社，2007年10月（主编）
8. 《动态数据挖掘》，科学出版社，2010年8月（主编）
近年来，发表的主要学术论文如下： [1] Zhangjun Wu, Xiao Liu, Zhiwei Ni, Dong Yuan, Jinjun Chen, Yun Yang: A Market-Oriented Hierarchical Scheling Strategy in Cloud Workflow Systems, Journal of Supercomputing, Volume 63,Issue 1,pp.256-293,2013.(UT WOS:000313166000013).[2] Xiao Liu,Zhiwei Ni,et al.A Novel Statistical Time-Series Pattern based Interval Forecastting Strategy for Activity Durations in Workflow Systems.Journal of Software and system,2011,(84),354-376.(SCI indexed)[3] Liping Ni, Zhiwei Ni, YaZhuo Gao.Stock trend Prediction Based on Fractal Feature Selection and Support Vector Machine.Expert system with applications,2011,(38),5569-5576.(SCI indexed)[4]Xiao Liu,Zhiwei Ni,et al.A probabilistic strategy for temporal constraint management in scientisfic workflow systems.Concurrrency and Computation :Pratice and Experience,2011,23(16),1893-1919.(SCI indexed) [5] Xiao Liu, Zhiwei Ni, Zhangjun Wu, Dong Yuan, Jinjun Chen, Yun Yang: A Novel General Framework for Automatic and Cost-Effective Handling of Recoverable Temporal violations in Scientific Workflow Systems, Journal of Software and System,2011,(84),492-509. (SCI indexed ) [6]Zhiwei Ni,Junfeng guo ,et al.An Efficient Method for Improving Query Efficiency in Data Warehouse.Journal of software,2011,6(5),857-865.[7]高雅卓， 倪志伟等.连续属性上的OLAP查询建模方法研究.情报学报，2011，30(4),372-379.[8]张以文，倪志伟等.云计算环境下动态虚拟企业伙伴选择模型.计算机科学，2011，38(7),212-215.[9]倪志伟，公维峰等.数据流中随机型分型维数计算方法研究.计算机科学，2011，38(4),209-212.[10]倪志伟，吴昊等.基于改进的经验模态分解的时间序列匹配算法.系统仿真学报，2011，23(11),2395-2399.[11]姜苗，倪志伟等.数据流时间窗口中闭频繁项集的在线挖掘.中国科学技术大学学报，2011，(8),729-745.[12] Zhangjun Wu, Zhiwei Ni, Lichuan Gu, Xiao Liu: A Revised Discrete Particle Swarm Optimization for Cloud Workflow Scheling, 2010 International Conference on Computational Intelligence and Security (CIS2010), Nanning, China, 11-14 Dec. 2010 (EI indexed) [13] Xiao Liu, Zhiwei Ni, Zhangjun Wu, Dong Yuan, Jinjun Chen, Yun Yang: A Framework for Handling Fine-Grained Recoverable Temporal Violations in Scientific Workflows, 16th IEEE International Conference on Parallel and Distributed Systems (ICPADS2010), Shanghai, China, December 7-11, 2010, on Sept. 05, 2010 (EI indexed). [14] Yazhuo Gao, Zhiwei Ni, Yuxiao Zhao.A scheling strategy for OLAM tasks and its application in a financial BI system Business Intelligence and Financial Engneering .2009会议论文集: 435-440 (EI收录) [15] Zhiwei Ni, Dan Han, Gongrang Zhang, Yazhuo Gao.Extension CBR Retrieval.AICI2009:224—227 (EI收录) [16] Zhangjun Wu, Zhiwei Ni，Chang Zhang, Lichuan Gu. A Novel PSO for Multi-stage Portfolios Planning, IEEE International Conference on Artificial Intelligence and Computational Intelligence (AICI2009)，71—77 (EI收录) [17] Chang Zhang, Zhiwei Ni, Zhangjun Wu,Lichuan Gu. A Novel Swarm Model with Quasi-Oppositional Particle, International Forum on Information Technology and Applications (IFITA 2009), pp.325-330 (EI收录) [18] Li Fenggang, Wang Xiaolu, Ni Zhiwei, Ni Liping. Semantic Analysis Based Literature Transaction System of Xi-An Medical Authority, Intelligent Information Management Systems and Technologies (2010),Volume6,No.3 ,219—226 [19] Xiao Liu, Jinjun Chen, Zhangjun Wu, Zhiwei Ni, Dong Yuan, Yun Yang.Handling Recoverable Temporal Violations in Scientific Workflow Systems: A, Workflow Rescheling Based Strategy,2010,pp.534-537 [20]Chao Wang ,Zhi-wei Ni ,Jun-fen Guo.A Fast Bidirectional Method for Mining Maximal Frequent Itemsets，The Third International Joint Conference on Computational Sciences and Optimization (CSO 2010),447—450 [21]倪志伟,高雅卓,李伟东,束建华.基于矩阵的增量式关联规则挖掘算法.计算机工程与应用, 2008,44(13):153-155 [22]刘斌,倪志伟,赵敏.基于属性重要性的贪心算法的改进算法.合肥工业大学学报,2010,33(8):1185-1188 [23]王丽红,倪志伟, 高雅卓.改进的蚁群算法求解多目标车间作业调度问题.计算机技术与发展,2008 ,18(10):49—52 [24]吴姗,倪志伟,罗贺,郑盈盈.一种基于密度的无监督联系发现方法.中国管理科学,2008,16:29—32 [25]梁敏君,倪志伟,倪丽萍,杨葛钟啸.基于网格与分形维数聚类算法.计算机应用,2009,29(3):830-833 [26]倪丽萍,倪志伟,吴昊,叶红云.基于分形维数和蚁群算法的属性选择方法.模式识别与人工智能, 2009,22(2):293—298(EI收录) [27]倪志伟,倪丽萍,杨葛钟啸.分形技术在案例库维护中的应用.计算机应用,2009,29(6):1598—1604 [28]倪志伟,吴姗,胡汤磊.联系发现在证券客户划分中的应用研究.计算机工程与应用, 2009, 45(18):201--204 [29]Dan Han, Zhiwei Ni, Gongrang Zhang, Hongyu Wang, Jun Yan. Research and Design the Extension Case BaseBased on CBR. BIFE International meeting, 2009，:210—214 (EI收录) [30]郑盈盈,倪志伟,吴姗,王丽红.基于移动网格和密度的数据流聚类算法.计算机工程与应用,2009,45(8):129--131 [31]王园园,倪志伟,赵裕啸,伍章俊.基于决策树的模糊聚类评价算法及其应用.计算机技术与发展, 2009,19(9):232-235 [32]严军,倪志伟,王宏宇,韩丹.案例推理在汽车诊断中的应用.计算机应用研究. 2009,26(10):3846-3848 [33]刘慧婷,倪志伟.基于EMD与交叉覆盖算法的个人信用的评估.计算机工程与设计,2009,10:4472—4491 [34]刘慧婷,倪志伟.基于EMD与K-means算法的时间序列聚类.模式识别与人工智能,2009.10 :803—808 [35]倪志伟,李建洋,李锋刚, 杨善林.案例决策技术及案例决策支持系统研究综述.计算机科学,2009,36(11):18—23 [36]郭峻峰, 倪志伟, 高雅卓, 伍章俊.一种提高数据仓库查询效率的有效方法.计算机集成制造系统, 2009,15(12):2451-2457 (EI收录) [37]高雅卓,倪志伟,郭峻峰,胡汤磊.用户兴趣驱动的冰山数据立方体构建及更新方法研究.计算机科学, 2009,36(12):179-182 [38]赵裕啸,倪志伟,王园园,伍章俊.SQL Server 2005数据挖掘技术在证券客户忠诚度的应用.计算机技术与发展, 2010,20(2):229-232 [39]李锋刚,倪志伟, 郜峦.案例推理和多策略相似性检索的中医处方自动生成.计算机应用研究,2010, 27(2):544—547 [40]李建洋,倪志伟,郑金彬,谢秀珍.案例知识维护技术的研究进展.武汉工程大学学报,2010,32(3):96-99 [41]赵敏,倪志伟,刘斌.K-means与朴素贝叶斯在商务智能中的应用.计算机技术与发展, 2010,20(4):179-182 [42]王宏宇,倪志伟,严军,韩丹.灰度关联理论在CBR中的应用研究.计算机技术与发展, 2010,20(5):96-100 [43]罗义钦,倪志伟,杨葛钟啸.一种新的数据流分形聚类算法.计算机工程与应用, 2010,46 (6): 136-13 [44]查春生，倪志伟，倪丽萍，公维峰.基于相空间重构的股指时间序列相关性分析,计算机技术与发展，计划在2010年第8期刊载 [45]姜苗，倪志伟，王超，戴奇波.在线挖掘数据流混合窗口中闭频繁项集，系统仿真学报， [46]辜丽川，倪志伟，张友华.一种基于核矩阵迭代学习的范例相似度算法，模式识别与人工智能。 [47] Case base maintenance based on outlier data mining，Proc. 4th Intl. Conf. on Machine Learning and Cybernetics，IEEE Press, China, 2005.8 ，2861-2864 [48] 基于相似粗糙集的案例特征项的约简维护, 计算机科学，Vol.32,No.8.A , 2005，93-96 [49] 数据流管理与挖掘研究, 合肥工业大学学报(自然科学版), Vol.28, No.9 , 2005，1157-1162 [50] Case-Based Reasoning Framework Based On Data Mining Technique. Proceedings of the Third International Conference on Machine Learning and Cybernetics, Shanghai, August，2004，2511-2514 [51] 基于案例和规则相结合的推理技术,小型微型计算机系统，2004,Vol.25，No.7,1155-1158 [52] 集成范例推理系统的研究，系统仿真学报，2004，Vol.16，No.4， 803-806 [53] 范例推理中范例自动获取的数据挖掘技术，天津大学学报，2003年，Vol.36,No.1，82-86 [54] 基于知识发现的范例推理系统，计算机科学，Vol.30,No.5,2003年，26-29 [55] 范例推理系统中的范例库维护，小型微型计算机系统，Vol.24, No.10，2003年10月，1825-1828 [56] Integrated case-based reasoning，Proceedings of 2003 International Conference on Machine Learning and Cybernetics ,Xi’an,2003，1845-1849 [57]范例推理中的知识发现技术，小型微型计算机系统，Vol.23,No.2，2002年2月，159-162 [58]范例库中特征项权重的发现技术，厦门大学学报， Vol.41,No.2,2002年3月，168-172 [59]用神经网络来实现基于范例的推理系统，计算机工程，2002年7月，Vol.28,No.7 [60]A neural network case-based reasoning and its application , Proceedings of 2002 International Conference on Machine Learning and Cybernetics ,Beijing, 2002.11，529-532 [61]范例库上的知识发现，南开大学学报，2002年12月，Vol.35,No.4 [62]神经网络专家系统及其数据挖掘技术的探讨，系统工程学报，2001年，Vol.16, No.1, 61-65

㈤ 用类似贪心算法实现基于传统聚类方法的试卷质量分析研究

可参阅文本分类的方法。

㈥ 用于数据挖掘的聚类算法有哪些

一部专着的篇幅。即使是做综述性的介绍，一篇三五十页的论文也可以写成了。所以我一直想怎么能从头到尾把这个问题logically串连起来。正好这段时间我在修改我做的交易策略里面关于聚类的部分。就我的理解而言，如果想全面的了解聚类算法并对其进行区别和比较的话，最好能把聚类的具体算法放到整个聚类分析的语境中理解。那我接下来主要谈谈我的理解，就不搬弄教科书里的概念了。相似性衡量（similarity measurement）相似性衡量又可以细分为直接法和间接：直接法是直接求取input data的相似性，间接法是求取data中提取出的features的相似性。但无论是求data还是feature的相似性，方法都是这么几种：距离。距离主要就是指Minkovski距离。这个名字虽然听起来陌生，但其算法就是Lp norm的算法，如果是L1 norm，那就是绝对值/曼哈顿距离（Manhattan distance）；如果是L2 norm，那就是着名的欧式距离（Euclidean distance）了，也是应用最广泛的；如果，supremum距离，好像也有叫切比雪夫距离的，但就很少有人用了。另外，还有Mahalanobis距离，目前来看主要应用于Gaussian Mixture Model（GMM），还有Lance&Williams距离等等，但几乎没见过求距离的时候会专门用这个的。相似系数。主要有夹角余弦和相关系数。相关系数的应用也非常广泛，其主要优势是它不受原线性变换的影响，而且可以轻松地转换为距离，但其运算速度要比距离法慢得多，当维数很高的时候。

㈦ 英语翻译 将下面的文字翻译成英文

Data mining is found implied, novel, from the database on decision has the potential value of knowledge and rules of procere, has now has been widely applied in many areas. Cluster analysis is one of the most important technology in the area of data mining, clustering is the collection of physical or abstract objects into multiple clusters of similar objects. Generated by clustering cluster is a collection of objects, similar to the objects to each other in the same cluster, different objects in a different family. And in the many clustering algorithms, clustering algorithm is the most classic K-means.
K-means clustering algorithm is a typical clustering algorithm based on partition, the algorithm has a simple, for large-scale data mining of high performance and scalability, advantages of close to linear time complexity. But there were disadvantages to the algorithm: algorithm sensitive to initial; initial value using stochastic, algorithm is not stable enough; algorithm into a local minimum, and generally only found globular clusters; number of clusters k need to be given in advance.
This article is mainly to introce and analyze traditional clustering algorithm based on K-means and understand the advantages and disadvantages of clustering algorithm based on K-means, and improvements to clustering algorithm based on K-means. The improvement is intended primarily for k-means clustering algorithm to improve initial value dependency of this feature. Improved mainly through some initial point selection algorithms, thus overcoming shortcomings such as the K-means algorithm is not stable, and be able to make the clustering results more precise.
Study on the main work content and outcomes are as follows:
1. introction and analysis of clustering algorithm based on K-means thought and realization of the algorithm. And then some data to understand the advantages and disadvantages of algorithms.
2. improvements to disadvantage of clustering algorithm based on K-means, primarily for k-means clustering algorithm to improve initial value dependency of this feature. Two improved methods, the first thought of using Huffman, the second reference to greedy algorithm and Kruskal algorithm for thoughts.