第04讲智能决策理论与方法ppt课件

决策理论与方法决策理论与方法(4)智能决策理论与方法智能决策理论与方法(1)合肥工业大学管理学院合肥工业大学管理学院合肥工业大学管理学院合肥工业大学管理学院Monday,May 6,2024Monday,May 6,2024决策理论与方法(4)智能决不确定性决策不确定性决策vv不确定性决策不确定性决策不确定性决策不确定性决策：指难以获得各种状态发生的概率，甚至对未指难以获得各种状态发生的概率，甚至对未指难以获得各种状态发生的概率，甚至对未指难以获得各种状态发生的概率，甚至对未来状态都难以把握的决策问题。来状态都难以把握的决策问题。来状态都难以把握的决策问题。来状态都难以把握的决策问题。vv特点特点特点特点：状态的不确定性。：状态的不确定性。：状态的不确定性。：状态的不确定性。不确定性不确定性不确定性不确定性：不确定性来自人类的主观认识与客观实际之不确定性来自人类的主观认识与客观实际之不确定性来自人类的主观认识与客观实际之不确定性来自人类的主观认识与客观实际之间存在的差异。事物发生的随机性、人类知识的不完全、间存在的差异。事物发生的随机性、人类知识的不完全、间存在的差异。事物发生的随机性、人类知识的不完全、间存在的差异。事物发生的随机性、人类知识的不完全、不可靠、不精确和不一致以及自然语言中存在的模糊性不可靠、不精确和不一致以及自然语言中存在的模糊性不可靠、不精确和不一致以及自然语言中存在的模糊性不可靠、不精确和不一致以及自然语言中存在的模糊性和歧义性，都反映了这种差异，都会带来不确定性。不和歧义性，都反映了这种差异，都会带来不确定性。不和歧义性，都反映了这种差异，都会带来不确定性。不和歧义性，都反映了这种差异，都会带来不确定性。不确定性就造成了具有相同描述信息的对象可能属于不同确定性就造成了具有相同描述信息的对象可能属于不同确定性就造成了具有相同描述信息的对象可能属于不同确定性就造成了具有相同描述信息的对象可能属于不同概念。概念。概念。概念。vv解决问题的主要理论方法解决问题的主要理论方法解决问题的主要理论方法解决问题的主要理论方法：人工智能与不确定性理论：人工智能与不确定性理论：人工智能与不确定性理论：人工智能与不确定性理论决策理论与方法-智能决策理论与方法不确定性决策不确定性决策：指难以获得各种状态发生的概率，甚至2智能决策理论与方法智能决策理论与方法1 1、智能决策理论的形成背景、智能决策理论的形成背景、智能决策理论的形成背景、智能决策理论的形成背景2 2、知识发现、知识发现、知识发现、知识发现3 3、机器学习、机器学习、机器学习、机器学习4 4、不确定性理论、不确定性理论、不确定性理论、不确定性理论决策理论与方法-智能决策理论与方法智能决策理论与方法1、智能决策理论的形成背景决策理论与方法-3智能决策理论与方法智能决策理论与方法形成背景形成背景vv人类面临越来越复杂的决策任务和决策环境人类面临越来越复杂的决策任务和决策环境人类面临越来越复杂的决策任务和决策环境人类面临越来越复杂的决策任务和决策环境：决策问题所涉及的变量规模越来越大；决策问题所涉及的变量规模越来越大；决策问题所涉及的变量规模越来越大；决策问题所涉及的变量规模越来越大；决策所依赖的信息具有不完备性、模糊性、不确定性等决策所依赖的信息具有不完备性、模糊性、不确定性等决策所依赖的信息具有不完备性、模糊性、不确定性等决策所依赖的信息具有不完备性、模糊性、不确定性等特点，使得决策问题难以全部定量化地表示出来；特点，使得决策问题难以全部定量化地表示出来；特点，使得决策问题难以全部定量化地表示出来；特点，使得决策问题难以全部定量化地表示出来；某些决策问题及其目标可能是模糊的、不确定的，使得某些决策问题及其目标可能是模糊的、不确定的，使得某些决策问题及其目标可能是模糊的、不确定的，使得某些决策问题及其目标可能是模糊的、不确定的，使得决策者对自己的偏好难以明确，随着决策分析的深入，决策者对自己的偏好难以明确，随着决策分析的深入，决策者对自己的偏好难以明确，随着决策分析的深入，决策者对自己的偏好难以明确，随着决策分析的深入，对决策问题的认知加深，自己原有的偏好对决策问题的认知加深，自己原有的偏好对决策问题的认知加深，自己原有的偏好对决策问题的认知加深，自己原有的偏好/倾向得到不断倾向得到不断倾向得到不断倾向得到不断地修正，使得决策过程出现不断调整的情况，地修正，使得决策过程出现不断调整的情况，地修正，使得决策过程出现不断调整的情况，地修正，使得决策过程出现不断调整的情况，vv这时，传统的决策数学模型已经难以胜任求解复杂度过高的这时，传统的决策数学模型已经难以胜任求解复杂度过高的这时，传统的决策数学模型已经难以胜任求解复杂度过高的这时，传统的决策数学模型已经难以胜任求解复杂度过高的决策问题、含有不确定性的决策问题以及半结构化、非结构决策问题、含有不确定性的决策问题以及半结构化、非结构决策问题、含有不确定性的决策问题以及半结构化、非结构决策问题、含有不确定性的决策问题以及半结构化、非结构化的决策问题，因而产生了智能决策理论、方法及技术。化的决策问题，因而产生了智能决策理论、方法及技术。化的决策问题，因而产生了智能决策理论、方法及技术。化的决策问题，因而产生了智能决策理论、方法及技术。决策理论与方法-智能决策理论与方法智能决策理论与方法形成背景人类面临越来越复杂的决策任务和决4智能决策理论与方法智能决策理论与方法AI的应用模式的应用模式vv智能决策方法智能决策方法智能决策方法智能决策方法是应用人工智能是应用人工智能是应用人工智能是应用人工智能(Artificial Intelligence,AI)(Artificial Intelligence,AI)相关理论方法，融合传统的决策数学模型和方法而产生的具相关理论方法，融合传统的决策数学模型和方法而产生的具相关理论方法，融合传统的决策数学模型和方法而产生的具相关理论方法，融合传统的决策数学模型和方法而产生的具有智能化推理和求解的决策方法，其典型特征是能够在不确有智能化推理和求解的决策方法，其典型特征是能够在不确有智能化推理和求解的决策方法，其典型特征是能够在不确有智能化推理和求解的决策方法，其典型特征是能够在不确定、不完备、模糊的信息环境下，通过应用符号推理、定性定、不完备、模糊的信息环境下，通过应用符号推理、定性定、不完备、模糊的信息环境下，通过应用符号推理、定性定、不完备、模糊的信息环境下，通过应用符号推理、定性推理等方法，对复杂决策问题进行建模、推理和求解。推理等方法，对复杂决策问题进行建模、推理和求解。推理等方法，对复杂决策问题进行建模、推理和求解。推理等方法，对复杂决策问题进行建模、推理和求解。AIAI应应应应用于决策科学主要有两种模式用于决策科学主要有两种模式用于决策科学主要有两种模式用于决策科学主要有两种模式：针对可建立精确数学模型的决策问题，由于问题的复杂针对可建立精确数学模型的决策问题，由于问题的复杂针对可建立精确数学模型的决策问题，由于问题的复杂针对可建立精确数学模型的决策问题，由于问题的复杂性，如组合爆炸、参数过多等而无法获得问题的解析解，性，如组合爆炸、参数过多等而无法获得问题的解析解，性，如组合爆炸、参数过多等而无法获得问题的解析解，性，如组合爆炸、参数过多等而无法获得问题的解析解，需要借助需要借助需要借助需要借助AIAI中的智能搜索算法获得问题的数值解；中的智能搜索算法获得问题的数值解；中的智能搜索算法获得问题的数值解；中的智能搜索算法获得问题的数值解；针对无法建立精确数学模型的不确定性决策问题、半结针对无法建立精确数学模型的不确定性决策问题、半结针对无法建立精确数学模型的不确定性决策问题、半结针对无法建立精确数学模型的不确定性决策问题、半结构化或非结构化决策问题，需要借助构化或非结构化决策问题，需要借助构化或非结构化决策问题，需要借助构化或非结构化决策问题，需要借助AIAI方法建立相应的方法建立相应的方法建立相应的方法建立相应的决策模型并获得问题的近似解。决策模型并获得问题的近似解。决策模型并获得问题的近似解。决策模型并获得问题的近似解。决策理论与方法-智能决策理论与方法智能决策理论与方法AI的应用模式智能决策方法是应用人工智能5智能决策理论与方法智能决策理论与方法1 1、智能决策理论的形成背景、智能决策理论的形成背景、智能决策理论的形成背景、智能决策理论的形成背景2 2、知识发现、知识发现、知识发现、知识发现3 3、机器学习、机器学习、机器学习、机器学习4 4、不确定性理论、不确定性理论、不确定性理论、不确定性理论决策理论与方法-智能决策理论与方法智能决策理论与方法1、智能决策理论的形成背景决策理论与方法-6知识发现知识发现动机动机vv智能决策的核心是如何获取支持决策的信息和知识。智能决策的核心是如何获取支持决策的信息和知识。智能决策的核心是如何获取支持决策的信息和知识。智能决策的核心是如何获取支持决策的信息和知识。vv问题问题问题问题知识获取是基于知识的系统知识获取是基于知识的系统知识获取是基于知识的系统知识获取是基于知识的系统(KBS)(KBS)(KBS)(KBS)的最大瓶颈的最大瓶颈的最大瓶颈的最大瓶颈推理机推理机知识工程师知识工程师领域专家领域专家决策者决策者知识库知识库问题请求问题请求推理结果推理结果决策理论与方法-智能决策理论与方法知识发现动机智能决策的核心是如何获取支持决策的信息和知识。7知识发现知识发现动机动机vv问题问题问题问题推理规则的获取与推理规则的获取与推理规则的获取与推理规则的获取与KBSKBSKBSKBS中知识获取一样难，因而基于中知识获取一样难，因而基于中知识获取一样难，因而基于中知识获取一样难，因而基于案例推理案例推理案例推理案例推理(Case-Based(Case-Based(Case-Based(Case-Based ReasoningReasoningReasoningReasoning)渐渐变成基于案例渐渐变成基于案例渐渐变成基于案例渐渐变成基于案例检索检索检索检索(Case-Based(Case-Based(Case-Based(Case-Based RetrievingRetrievingRetrievingRetrieving)。推理机推理机决策者决策者案例库案例库问题请求问题请求推理结果推理结果规则库规则库知识工程师知识工程师领域专家领域专家决策理论与方法-智能决策理论与方法知识发现动机问题推理机决策者案例库问题请求推理结果规则库知8知识发现知识发现动机动机决策者决策者数据分析师数据分析师数据中心数据中心不一定满意的决策不一定满意的决策决策支持查询决策支持查询查询结果查询结果vv问题问题问题问题数据分析师与决策者之间对问题的理解存在偏差数据分析师与决策者之间对问题的理解存在偏差数据分析师与决策者之间对问题的理解存在偏差数据分析师与决策者之间对问题的理解存在偏差缺少有创造性的决策建议缺少有创造性的决策建议缺少有创造性的决策建议缺少有创造性的决策建议技术问题：如查询效率技术问题：如查询效率技术问题：如查询效率技术问题：如查询效率(RDBMS)(RDBMS)(RDBMS)(RDBMS)决策理论与方法-智能决策理论与方法知识发现动机决策者数据分析师数据中心不一定满意的决策决策支9知识发现知识发现动机动机推理机推理机数据挖掘工具数据挖掘工具数据中心数据中心决策者决策者知识库知识库问题请求问题请求推理结果推理结果背景知识背景知识领域专家领域专家vv优点优点优点优点知识独立于问题本身知识独立于问题本身知识独立于问题本身知识独立于问题本身知识的获取主要通过数据挖掘实现知识的获取主要通过数据挖掘实现知识的获取主要通过数据挖掘实现知识的获取主要通过数据挖掘实现有创造性收获有创造性收获有创造性收获有创造性收获决策理论与方法-智能决策理论与方法知识发现动机推理机数据挖掘工具数据中心决策者知识库问题请求10知识发现知识发现动机动机vvKDDKDDKDDKDD带来的新问题带来的新问题带来的新问题带来的新问题知识发现问题：如何从数据中将知识挖掘出来？知识发现问题：如何从数据中将知识挖掘出来？知识发现问题：如何从数据中将知识挖掘出来？知识发现问题：如何从数据中将知识挖掘出来？面临许多技术问题：面临许多技术问题：面临许多技术问题：面临许多技术问题：如如如如数据异构问题数据异构问题数据异构问题数据异构问题、数据具有数据具有数据具有数据具有噪音且信息不完整、使用什么样的挖掘算法、知噪音且信息不完整、使用什么样的挖掘算法、知噪音且信息不完整、使用什么样的挖掘算法、知噪音且信息不完整、使用什么样的挖掘算法、知识如何表示等识如何表示等识如何表示等识如何表示等知识评价问题：知识评价问题：知识评价问题：知识评价问题：数据本身具有权威性、客观性，数据本身具有权威性、客观性，数据本身具有权威性、客观性，数据本身具有权威性、客观性，但知识不具备。知识如何评价？但知识不具备。知识如何评价？但知识不具备。知识如何评价？但知识不具备。知识如何评价？决策理论与方法-智能决策理论与方法知识发现动机KDD带来的新问题决策理论与方法-智能决策理论11知识发现知识发现基本概念基本概念vv知识发现知识发现知识发现知识发现(Knowledge Discovery in Databases,KDD)(Knowledge Discovery in Databases,KDD)：从：从：从：从大量数据中提取隐含的大量数据中提取隐含的大量数据中提取隐含的大量数据中提取隐含的(预先未知、新颖预先未知、新颖预先未知、新颖预先未知、新颖)、有潜在应用价值、有潜在应用价值、有潜在应用价值、有潜在应用价值的的的的(可信、有效可信、有效可信、有效可信、有效)并最终能被人理解的模式的非平凡过程。也并最终能被人理解的模式的非平凡过程。也并最终能被人理解的模式的非平凡过程。也并最终能被人理解的模式的非平凡过程。也称为数据挖掘称为数据挖掘称为数据挖掘称为数据挖掘(Data Mining)(Data Mining)。此过程主要包含三个阶段：。此过程主要包含三个阶段：。此过程主要包含三个阶段：。此过程主要包含三个阶段：数据准备阶段、数据挖掘阶段、解释评价阶段。数据准备阶段、数据挖掘阶段、解释评价阶段。数据准备阶段、数据挖掘阶段、解释评价阶段。数据准备阶段、数据挖掘阶段、解释评价阶段。抽样预处理数据挖掘解释/评价数据中心样本集预处理结果变换结果挖掘结果知识任务描述变换决策理论与方法-智能决策理论与方法知识发现基本概念知识发现(Knowledge Discov12知识发现知识发现基本概念基本概念vv数据准备阶段数据准备阶段数据准备阶段数据准备阶段一般包含数据选取、预处理和数据变换等任务：一般包含数据选取、预处理和数据变换等任务：一般包含数据选取、预处理和数据变换等任务：一般包含数据选取、预处理和数据变换等任务：数据选取：数据选取：数据选取：数据选取：根据用户的需要从原始数据集中抽取一组样根据用户的需要从原始数据集中抽取一组样根据用户的需要从原始数据集中抽取一组样根据用户的需要从原始数据集中抽取一组样本数据确定挖掘任务的操作对象。本数据确定挖掘任务的操作对象。本数据确定挖掘任务的操作对象。本数据确定挖掘任务的操作对象。常见数据源常见数据源常见数据源常见数据源：vv关系型数据库数据：如营销数据库关系型数据库数据：如营销数据库关系型数据库数据：如营销数据库关系型数据库数据：如营销数据库vv文本数据：内容挖掘文本数据：内容挖掘文本数据：内容挖掘文本数据：内容挖掘(如如如如WebWeb内容挖掘，寻找相似页内容挖掘，寻找相似页内容挖掘，寻找相似页内容挖掘，寻找相似页面面面面)vvWebWeb数据：站点结构数据数据：站点结构数据数据：站点结构数据数据：站点结构数据(如如如如WebWeb结构挖掘，优化站结构挖掘，优化站结构挖掘，优化站结构挖掘，优化站点设计，站点导航，自适应站点点设计，站点导航，自适应站点点设计，站点导航，自适应站点点设计，站点导航，自适应站点)；站点使用数据或点；站点使用数据或点；站点使用数据或点；站点使用数据或点击流数据击流数据击流数据击流数据(如如如如WebWeb使用挖掘，用户聚类、页面聚类，个使用挖掘，用户聚类、页面聚类，个使用挖掘，用户聚类、页面聚类，个使用挖掘，用户聚类、页面聚类，个性化推荐等性化推荐等性化推荐等性化推荐等)vv空间数据、图像数据、视频数据等。空间数据、图像数据、视频数据等。空间数据、图像数据、视频数据等。空间数据、图像数据、视频数据等。决策理论与方法-智能决策理论与方法知识发现基本概念数据准备阶段一般包含数据选取、预处理和数据13知识发现知识发现基本概念基本概念数据预处理数据预处理数据预处理数据预处理：噪音数据处理、空值处理、属性类型转化：噪音数据处理、空值处理、属性类型转化：噪音数据处理、空值处理、属性类型转化：噪音数据处理、空值处理、属性类型转化vv噪音数据处理：噪音数据处理：噪音数据处理：噪音数据处理：噪音数据往往是因输入错误而导致的、噪音数据往往是因输入错误而导致的、噪音数据往往是因输入错误而导致的、噪音数据往往是因输入错误而导致的、或受某种外界因素干扰而有意识提供的错误数据。如或受某种外界因素干扰而有意识提供的错误数据。如或受某种外界因素干扰而有意识提供的错误数据。如或受某种外界因素干扰而有意识提供的错误数据。如何剔除噪音数据？噪音数据与系统中的一些小概率数何剔除噪音数据？噪音数据与系统中的一些小概率数何剔除噪音数据？噪音数据与系统中的一些小概率数何剔除噪音数据？噪音数据与系统中的一些小概率数据统称为据统称为据统称为据统称为“异常数据异常数据异常数据异常数据(Outlier)(Outlier)”，如何区分噪音数据，如何区分噪音数据，如何区分噪音数据，如何区分噪音数据和小概率数据？和小概率数据？和小概率数据？和小概率数据？vv空值处理空值处理空值处理空值处理：有些数据由于：有些数据由于：有些数据由于：有些数据由于“不重要不重要不重要不重要”、不知道或、不知道或、不知道或、不知道或“不不不不愿意愿意愿意愿意”而没有获得，引起某些属性值未知，称此类值而没有获得，引起某些属性值未知，称此类值而没有获得，引起某些属性值未知，称此类值而没有获得，引起某些属性值未知，称此类值为为为为空值空值空值空值。如何处理这些缺失值？。如何处理这些缺失值？。如何处理这些缺失值？。如何处理这些缺失值？vv属性类型转化属性类型转化属性类型转化属性类型转化：连续属性离散化或将离散属性拟合成：连续属性离散化或将离散属性拟合成：连续属性离散化或将离散属性拟合成：连续属性离散化或将离散属性拟合成连续属性等。连续属性等。连续属性等。连续属性等。决策理论与方法-智能决策理论与方法知识发现基本概念数据预处理：噪音数据处理、空值处理、属性类14知识发现知识发现基本概念基本概念数据变换数据变换数据变换数据变换(数据约简数据约简数据约简数据约简)：通过某种方法降低算法的搜索空通过某种方法降低算法的搜索空通过某种方法降低算法的搜索空通过某种方法降低算法的搜索空间。间。间。间。vv垂直约简垂直约简垂直约简垂直约简(也称特征选择、属性约简也称特征选择、属性约简也称特征选择、属性约简也称特征选择、属性约简)：使用降维或变：使用降维或变：使用降维或变：使用降维或变换方法减少变量数目，是典型的组合优化问题。换方法减少变量数目，是典型的组合优化问题。换方法减少变量数目，是典型的组合优化问题。换方法减少变量数目，是典型的组合优化问题。vv水平约简水平约简水平约简水平约简是通过对对象的分析是通过对对象的分析是通过对对象的分析是通过对对象的分析(包括离散化、泛化等包括离散化、泛化等包括离散化、泛化等包括离散化、泛化等)，合并具有相同属性值的对象，减少对象数目。，合并具有相同属性值的对象，减少对象数目。，合并具有相同属性值的对象，减少对象数目。，合并具有相同属性值的对象，减少对象数目。决策理论与方法-智能决策理论与方法知识发现基本概念数据变换(数据约简)：通过某种方法降低算法15知识发现知识发现基本概念基本概念vv数据挖掘阶段数据挖掘阶段数据挖掘阶段数据挖掘阶段：应用相关算法从准备好的数据中寻找数据中：应用相关算法从准备好的数据中寻找数据中：应用相关算法从准备好的数据中寻找数据中：应用相关算法从准备好的数据中寻找数据中隐含的对信息利用如预测、决策等有价值的模式。需要考虑隐含的对信息利用如预测、决策等有价值的模式。需要考虑隐含的对信息利用如预测、决策等有价值的模式。需要考虑隐含的对信息利用如预测、决策等有价值的模式。需要考虑的问题：的问题：的问题：的问题：任务的确定任务的确定任务的确定任务的确定：分类、聚类、关联规则发现等。：分类、聚类、关联规则发现等。：分类、聚类、关联规则发现等。：分类、聚类、关联规则发现等。方法的选择方法的选择方法的选择方法的选择：统计方法、机器学习方法、不确定性方法、：统计方法、机器学习方法、不确定性方法、：统计方法、机器学习方法、不确定性方法、：统计方法、机器学习方法、不确定性方法、数据库技术等。是知识发现的核心，也是被研究最广泛数据库技术等。是知识发现的核心，也是被研究最广泛数据库技术等。是知识发现的核心，也是被研究最广泛数据库技术等。是知识发现的核心，也是被研究最广泛的内容。数据挖掘方法很多，需要我们对它们的适用条的内容。数据挖掘方法很多，需要我们对它们的适用条的内容。数据挖掘方法很多，需要我们对它们的适用条的内容。数据挖掘方法很多，需要我们对它们的适用条件、前提假设有充分的了解。件、前提假设有充分的了解。件、前提假设有充分的了解。件、前提假设有充分的了解。运行效率分析运行效率分析运行效率分析运行效率分析：不同的算法其效率存在很大差异。算法：不同的算法其效率存在很大差异。算法：不同的算法其效率存在很大差异。算法：不同的算法其效率存在很大差异。算法设计与选择往往就是精度与效率之间的权衡。设计与选择往往就是精度与效率之间的权衡。设计与选择往往就是精度与效率之间的权衡。设计与选择往往就是精度与效率之间的权衡。决策理论与方法-智能决策理论与方法知识发现基本概念数据挖掘阶段：应用相关算法从准备好的数据中16知识发现知识发现基本概念基本概念vv数据挖掘任务及常采用的方法数据挖掘任务及常采用的方法数据挖掘任务及常采用的方法数据挖掘任务及常采用的方法：归纳总结归纳总结归纳总结归纳总结：从泛化的角度总结数据，即从低层次数据抽：从泛化的角度总结数据，即从低层次数据抽：从泛化的角度总结数据，即从低层次数据抽：从泛化的角度总结数据，即从低层次数据抽象出高层次的描述的过程。象出高层次的描述的过程。象出高层次的描述的过程。象出高层次的描述的过程。主要方法：归纳学习。主要方法：归纳学习。主要方法：归纳学习。主要方法：归纳学习。发现关联规则发现关联规则发现关联规则发现关联规则：关联规则的形式为：关联规则的形式为：关联规则的形式为：关联规则的形式为ABAB，A A为前件，为前件，为前件，为前件，B B为为为为后件。后件。后件。后件。(Day=Friday)and(Product=Nappies)(Day=Friday)and(Product=Nappies)(Product=Beer)(Product=Beer)为一典型关联规则为一典型关联规则为一典型关联规则为一典型关联规则 A A为满足前件的对象集，为满足前件的对象集，为满足前件的对象集，为满足前件的对象集，B B为满足后件的对象，为满足后件的对象，为满足后件的对象，为满足后件的对象，N N为全部为全部为全部为全部对象集。对象集。对象集。对象集。典型方法：典型方法：典型方法：典型方法：AprioriApriori算法。算法。算法。算法。决策理论与方法-智能决策理论与方法知识发现基本概念数据挖掘任务及常采用的方法：决策理论与方法17知识发现知识发现基本概念基本概念分类分类分类分类(等价关系，判别等价关系，判别等价关系，判别等价关系，判别)：按类标签：按类标签：按类标签：按类标签(为数据库中的某属性为数据库中的某属性为数据库中的某属性为数据库中的某属性集，一般仅包含一个属性集，一般仅包含一个属性集，一般仅包含一个属性集，一般仅包含一个属性)对数据库中的对象进行分类，对数据库中的对象进行分类，对数据库中的对象进行分类，对数据库中的对象进行分类，具有相同标签值或标签值在指定区间内的对象属于同类。具有相同标签值或标签值在指定区间内的对象属于同类。具有相同标签值或标签值在指定区间内的对象属于同类。具有相同标签值或标签值在指定区间内的对象属于同类。分类规则是判断某个对象属于某类的充分条件即对象具分类规则是判断某个对象属于某类的充分条件即对象具分类规则是判断某个对象属于某类的充分条件即对象具分类规则是判断某个对象属于某类的充分条件即对象具有某类的属性时则表示该对象属于该类。其规则形式一有某类的属性时则表示该对象属于该类。其规则形式一有某类的属性时则表示该对象属于该类。其规则形式一有某类的属性时则表示该对象属于该类。其规则形式一般为般为般为般为IF LogicExp Then AIF LogicExp Then A类类类类 Else B Else B类。类。类。类。主要方法：逻辑主要方法：逻辑主要方法：逻辑主要方法：逻辑回归、判别分析、决策树、回归、判别分析、决策树、回归、判别分析、决策树、回归、判别分析、决策树、ANNANN、粗糙集、粗糙集、粗糙集、粗糙集、SVMSVM等。等。等。等。聚类聚类聚类聚类(相容关系相容关系相容关系相容关系)：聚类也叫分段，就是将数据库中的实：聚类也叫分段，就是将数据库中的实：聚类也叫分段，就是将数据库中的实：聚类也叫分段，就是将数据库中的实体分成若干组或簇，每簇内的实体是相似的。规则形式体分成若干组或簇，每簇内的实体是相似的。规则形式体分成若干组或簇，每簇内的实体是相似的。规则形式体分成若干组或簇，每簇内的实体是相似的。规则形式为为为为IF O1IF O1IF O1IF O1与与与与O2O2O2O2相似相似相似相似 Then O1 Then O1 Then O1 Then O1、O2O2O2O2在同一簇。对象相似的判在同一簇。对象相似的判在同一簇。对象相似的判在同一簇。对象相似的判断方法有多种如距离法。断方法有多种如距离法。断方法有多种如距离法。断方法有多种如距离法。典型方法：典型方法：典型方法：典型方法：K-meansK-meansK-meansK-means决策理论与方法-智能决策理论与方法知识发现基本概念分类(等价关系，判别)：按类标签(为数据库18知识发现知识发现基本概念基本概念发现特征规则发现特征规则发现特征规则发现特征规则：特征规则是刻划某个概念的特征的断言，：特征规则是刻划某个概念的特征的断言，：特征规则是刻划某个概念的特征的断言，：特征规则是刻划某个概念的特征的断言，它相当于分类规则的逆命题。例如病症是某种疾病的特它相当于分类规则的逆命题。例如病症是某种疾病的特它相当于分类规则的逆命题。例如病症是某种疾病的特它相当于分类规则的逆命题。例如病症是某种疾病的特征。规则一般形式是：征。规则一般形式是：征。规则一般形式是：征。规则一般形式是：IF AIF A类类类类 Then Then 特征表达式。特征表达式。特征表达式。特征表达式。序列模式发现序列模式发现序列模式发现序列模式发现：它与关联规则相似，不同之处在于事件：它与关联规则相似，不同之处在于事件：它与关联规则相似，不同之处在于事件：它与关联规则相似，不同之处在于事件的发生有前后顺序，该规则一般形式为：的发生有前后顺序，该规则一般形式为：的发生有前后顺序，该规则一般形式为：的发生有前后顺序，该规则一般形式为：A At(i)t(i)BBt(j)t(j)其中其中其中其中t(i)t(j)t(i)1 THEN ELSE 决策理论与方法-智能决策理论与方法知识发现空值估算对于每个对象x 计算其相容类SB(x)决32知识发现知识发现空值估算空值估算若数据集内容不再变化至，否则返回。若数据集中存在a(x)=?，则用投票策略确定a(x)，否则退出。a a1 1 a a2 2a a3 3a a4 4p p1 13 33 34 46 6p p2 2?3 34 46 6p p3 35 53 34 46 6p p4 44 43 34 46 6p p5 54 43 34 46 6p p6 64 43 34 46 6p p7 76 6*2 27 7a a1 1 a a2 2a a3 3a a4 4p p1 13 33 34 46 6p p2 24 43 34 46 6p p3 35 53 34 46 6p p4 44 43 34 46 6p p5 54 43 34 46 6p p6 64 43 34 46 6p p7 76 6*2 27 7该方法既没有将含空值的对象移去，也没有形成多个数据集，与统计方法相比充分考虑了数据之间的相容性和属性之间的依赖关系。决策理论与方法-智能决策理论与方法知识发现空值估算若数据集内容不再变化至，否则返回。a33知识发现知识发现连续属性离散化连续属性离散化问题描述 设 为一样本数据集，为非空有限集合，C是条件属性集，D是决策属性集。假设对于任意有 ，R是实数集，则 为连续属性。设 是 上的分割点集合，记为其中 ，为一整数，表示离散化程度，可以看作按属性将论域中的对象分成 类。3kik ki i-121决策理论与方法-智能决策理论与方法知识发现连续属性离散化问题描述3kiki-121决策理34知识发现知识发现连续属性离散化连续属性离散化对于需要离散化的连续属性集 ，其分割点集合记为将ci属性的连续取值映射到离散空间，即对于任意若其属性ci 的取值在区间 内，则将属性值重新标记为j。这样就把原来含有连续属性的样本数据集A转换成离散化的数据集 。因此离散化问题本质上可归结为利用选取的分割点对属性的值域空间进行划分的问题。决策理论与方法-智能决策理论与方法知识发现连续属性离散化对于需要离散化的连续属性集 35知识发现知识发现连续属性离散化连续属性离散化离散化方法典型的有等区间方法、等信息量方法、基于信息熵的方法、Holte的1R离散化方法、统计试验方法、超平面搜索方法以及用户自定义区间等。应用不同的准则可将现有的离散化方法分为局部与全局方法(论域空间)、静态与动态方法(属性空间)和有导师与无导师方法(是否依赖决策属性)。(1)等区间离散化方法等区间分割是将连续属性的值域等分成 ()个区间,一般由用户确定。决策理论与方法-智能决策理论与方法知识发现连续属性离散化离散化方法决策理论与方法-智能决策理36知识发现知识发现连续属性离散化连续属性离散化 假设某个属性的最大属性值为假设某个属性的最大属性值为假设某个属性的最大属性值为假设某个属性的最大属性值为x xmaxmax，最小属性值为，最小属性值为，最小属性值为，最小属性值为x xminmin，用，用，用，用户给定的分割点参数为户给定的分割点参数为户给定的分割点参数为户给定的分割点参数为k k，则分割点间隔为，则分割点间隔为，则分割点间隔为，则分割点间隔为=(=(x xmaxmax-x xminmin)/)/k k，所得到的属性分割点为所得到的属性分割点为所得到的属性分割点为所得到的属性分割点为x xminmin+i+i ，i=1,2,i=1,2,k k。(2)(2)等信息量离散化方法等信息量离散化方法等信息量离散化方法等信息量离散化方法 等信息量分割首先将测量值进行排序，然后将属性值域分成等信息量分割首先将测量值进行排序，然后将属性值域分成等信息量分割首先将测量值进行排序，然后将属性值域分成等信息量分割首先将测量值进行排序，然后将属性值域分成k k个区间，每个区间包含相同数量的测量值。假设某个属性个区间，每个区间包含相同数量的测量值。假设某个属性个区间，每个区间包含相同数量的测量值。假设某个属性个区间，每个区间包含相同数量的测量值。假设某个属性的最大属性值为的最大属性值为的最大属性值为的最大属性值为x xmaxmax ，最小属性值为，最小属性值为，最小属性值为，最小属性值为x xminmin ，用户给定的分割，用户给定的分割，用户给定的分割，用户给定的分割点参数为点参数为点参数为点参数为k k，样本集中的对象个数为，样本集中的对象个数为，样本集中的对象个数为，样本集中的对象个数为n n，则需要将样本集中的，则需要将样本集中的，则需要将样本集中的，则需要将样本集中的对象按该属性的取值从小到大排列，然后按对象数平均划分对象按该属性的取值从小到大排列，然后按对象数平均划分对象按该属性的取值从小到大排列，然后按对象数平均划分对象按该属性的取值从小到大排列，然后按对象数平均划分为为为为k k段即得到分割点集，每两个相邻分割点之间的对象数均段即得到分割点集，每两个相邻分割点之间的对象数均段即得到分割点集，每两个相邻分割点之间的对象数均段即得到分割点集，每两个相邻分割点之间的对象数均为为为为n/kn/k。决策理论与方法-智能决策理论与方法知识发现连续属性离散化 假设某个属性的最大属性值为37知识发现知识发现连续属性离散化连续属性离散化(3)统计试验方法统计试验方法根据决策属性分析区间划分之间的独立程度，确定分割点的有效性。对于任意分割点 ，均可将 分成2个区间 和 ，两区间的独立程度为：其中：r是决策类数目nij是在第l区间中属于第j决策类的对象数决策理论与方法-智能决策理论与方法知识发现连续属性离散化(3)统计试验方法决策理论与方法-智38知识发现知识发现连续属性离散化连续属性离散化 若 ，则取 基于统计试验的离散化方法是将 值较大的分割点作为有效分割点。决策理论与方法-智能决策理论与方法知识发现连续属性离散化决策理论与方法-智能决策理论与方法39知识发现知识发现关联规则发现关联规则发现(Apriori算法算法)vvThe The AprioriApriori method:method:Proposed by Agrawal&Srikant 1994Proposed by Agrawal&Srikant 1994A similar level-wise algorithm by Mannila et al.1994A similar level-wise algorithm by Mannila et al.1994vvMajor idea:Major idea:A subset of a frequent itemset must be frequentA subset of a frequent itemset must be frequentvvE.g.,if E.g.,if beer,diaper,nutsbeer,diaper,nuts is frequent,is frequent,beer,diaperbeer,diaper must must be.be.Anyone is infrequent,its superset cannot be!Anyone is infrequent,its superset cannot be!A powerful,scalable candidate set pruning technique:A powerful,scalable candidate set pruning technique:vvIt reduces candidate k-itemsets dramatically(for k 2)It reduces candidate k-itemsets dramatically(for k 2)决策理论与方法-智能决策理论与方法知识发现关联规则发现(Apriori算法)The Apri40知识发现知识发现关联规则发现关联规则发现(Apriori算法算法)vv关联规则的例子关联规则的例子关联规则的例子关联规则的例子For rule For rule A A C C:support=support(support=support(A A C C)=50%)=50%confidence=support(confidence=support(A A C C)/support()/support(A A)=66.6%)=66.6%The Apriori principle:The Apriori principle:Any subset of a frequent itemset must be frequent.Any subset of a frequent itemset must be frequent.Min.support 50%Min.confidence 50%决策理论与方法-智能决策理论与方法知识发现关联规则发现(Apriori算法)关联规则的例子F41知识发现知识发现关联规则发现关联规则发现(Apriori算法算法)ProcedureProcedureFind the Find the frequent itemsetsfrequent itemsets:the sets of items that:the sets of items that have minimum support(Apriori)have minimum support(Apriori)uuA subset of a frequent itemset must also be a A subset of a frequent itemset must also be a frequent itemsetfrequent itemset,i.e.,if,i.e.,if A A B B is is a frequent a frequent itemset,both itemset,both A A and and B B should be a frequent should be a frequent itemsetitemsetuuIteratively find frequent itemsets with cardinality Iteratively find frequent itemsets with cardinality from 1 to from 1 to k(k-k(k-itemsetitemset)Use the frequent itemsets to generate association Use the frequent itemsets to generate association rules.rules.决策理论与方法-智能决策理论与方法知识发现关联规则发现(Apriori算法)Procedur42知识发现知识发现关联规则发现关联规则发现(Apriori算法算法)vvAlgorithmAlgorithmJoin StepJoin Step C Ck k is generated by joining Lis generated by joining Lk-1k-1with itselfwith itselfPrune StepPrune Step Any(k-1)-itemset that is not frequent cannot be a Any(k-1)-itemset that is not frequent cannot be a subset of a frequent k-itemset,hence should be subset of a frequent k-itemset,hence should be removed.removed.(C Ck k:Candidate itemset of size k):Candidate itemset of size k)(L (Lk k:frequent itemset of size k):frequent itemset of size k)决策理论与方法-智能决策理论与方法知识发现关联规则发现(Apriori算法)Algorith43知识发现知识发现关联规则发现关联规则发现(Apriori算法算法)vvPseudocodePseudocode（正式代码见附件（正式代码见附件（正式代码见附件（正式代码见附件1 1）C Ck k:Candidate itemset of size k:Candidate itemset of size kL Lk k:frequent itemset of size k:frequent itemset of size kL L1 1=frequent items;=frequent items;forfor (k k=1;=1;L Lk k!=!=;k k+)+)do begindo begin C Ck+1k+1=candidates generated from =candidates generated from L Lk k;for eachfor each transaction transaction t t in database do in database do increment the count of all candidates in increment the count of all candidates in C Ck+1k+1 that are contained in that are contained in t t L Lk+1k+1 =candidates in =candidates in C Ck+1k+1 with min_support with min_support end endreturnreturn k k L Lk k;决策理论与方法-智能决策理论与方法知识发现关联规则发现(Apriori算法)Pseudoco44知识发现知识发现关联规则发现关联规则发现(Apriori算法算法)Database DScan DC1L1L2C2C2Scan DC3L3Scan D决策理论与方法-智能决策理论与方法知识发现关联规则发现(Apriori算法)Database45知识发现知识发现聚类聚类(K-means算法算法)vv聚类分析是把研究对象按照一定的规则分成若干类聚类分析是把研究对象按照一定的规则分成若干类聚类分析是把研究对象按照一定的规则分成若干类聚类分析是把研究对象按照一定的规则分成若干类别，并使类之间的差别尽可能地大，类内的差别尽别，并使类之间的差别尽可能地大，类内的差别尽别，并使类之间的差别尽可能地大，类内的差别尽别，并使类之间的差别尽可能地大，类内的差别尽可能地小，换句话说，使类间的相似性最小、而类可能地小，换句话说，使类间的相似性最小、而类可能地小，换句话说，使类间的相似性最小、而类可能地小，换句话说，使类间的相似性最小、而类内的相似性最大。内的相似性最大。内的相似性最大。内的相似性最大。vv聚类方法的核心问题是样品间的相似性度量，通常聚类方法的核心问题是样品间的相似性度量，通常聚类方法的核心问题是样品间的相似性度量，通常聚类方法的核心问题是样品间的相似性度量，通常用距离来度量。用距离来度量。用距离来度量。用距离来度量。决策理论与方法-智能决策理论与方法知识发现聚类(K-means算法)聚类分析是把研究对象按照46知识发现知识发现聚类聚类(K-means算法算法)聚类分析中的常用距离聚类分析中的常用距离聚类分析中的常用距离聚类分析中的常用距离(1)(1)欧氏欧氏欧氏欧氏(Euclidean)(Euclidean)距离距离距离距离(2)(2)绝对距离绝对距离绝对距离绝对距离(3)Minkowski(3)Minkowski距离距离距离距离显然当显然当显然当显然当mm=1=1时就是绝对距离，时就是绝对距离，时就是绝对距离，时就是绝对距离，mm=2=2时就是欧氏距离。时就是欧氏距离。时就是欧氏距离。时就是欧氏距离。在实际应用时常分析两个样品之间的相对距离，这时需在实际应用时常分析两个样品之间的相对距离，这时需在实际应用时常分析两个样品之间的相对距离，这时需在实际应用时常分析两个样品之间的相对距离，这时需要对样品数据进行标准化处理，然后用标准化数据计算要对样品数据进行标准化处理，然后用标准化数据计算要对样品数据进行标准化处理，然后用标准化数据计算要对样品数据进行标准化处理，然后用标准化数据计算距离。距离。距离。距离。决策理论与方法-智能决策理论与方法知识发现聚类(K-means算法)聚类分析中的常用距离决策47知识发现知识发现聚类聚类(K-means算法算法)vv对于给定的对于给定的对于给定的对于给定的n n个样品，先粗略地形成个样品，先粗略地形成个样品，先粗略地形成个样品，先粗略地形成k k(k k n n)个分割，使得每个分割，使得每个分割，使得每个分割，使得每个分割对应一个类、每个类至少有一个样品并且每个样品精个分割对应一个类、每个类至少有一个样品并且每个样品精个分割对应一个类、每个类至少有一个样品并且每个样品精个分割对应一个类、每个类至少有一个样品并且每个样品精确地属于一个类，然后按照某种原则进行修正，直至分类比确地属于一个类，然后按照某种原则进行修正，直至分类比确地属于一个类，然后按照某种原则进行修正，直至分类比确地属于一个类，然后按照某种原则进行修正，直至分类比较合理为止。具体步骤如下：较合理为止。具体步骤如下：较合理为止。具体步骤如下：较合理为止。具体步骤如下：(1)(1)聚点的选择聚点的选择聚点的选择聚点的选择：聚点是一批有代表性的样品，它的选择决：聚点是一批有代表性的样品，它的选择决：聚点是一批有代表性的样品，它的选择决：聚点是一批有代表性的样品，它的选择决定了初始分类。首先确定分类数定了初始分类。首先确定分类数定了初始分类。首先确定分类数定了初始分类。首先确定分类数k k，然后选择，然后选择，然后选择，然后选择k k个有代表个有代表个有代表个有代表性的样品作为每个类的初始元素即聚点。聚点可由用户性的样品作为每个类的初始元素即聚点。聚点可由用户性的样品作为每个类的初始元素即聚点。聚点可由用户性的样品作为每个类的初始元素即聚点。聚点可由用户根据经验选择，也可将全部样品人为地或随机地分成根据经验选择，也可将全部样品人为地或随机地分成根据经验选择，也可将全部样品人为地或随机地分成根据经验选择，也可将全部样品人为地或随机地分成k k类，类，类，类，以每类的重心作为聚点。以每类的重心作为聚点。以每类的重心作为聚点。以每类的重心作为聚点。决策理论与方法-智能决策理论与方法知识发现聚类(K-means算法)对于给定的n个样品，先粗48知识发现知识发现聚类聚类(K-means算法算法)聚点的最小最大原则选择法：聚点的最小最大原则选择法：聚点的最小最大原则选择法：聚点的最小最大原则选择法：设将设将设将设将n n个样品分成个样品分成个样品分成个样品分成k k类，先选择所有样品中相距最远的两个样类，先选择所有样品中相距最远的两个样类，先选择所有样品中相距最远的两个样类，先选择所有样品中相距最远的两个样品品品品 为前两个聚点，因此有为前两个聚点，因此有为前两个聚点，因此有为前两个聚点，因此有设已经找到了设已经找到了设已经找到了设已经找到了l l l l个个个个(2(2(2(2l l l lk k k k)聚点，则第聚点，则第聚点，则第聚点，则第l l l l+1+1+1+1个聚点个聚点个聚点个聚点 的选择方法是使得的选择方法是使得的选择方法是使得的选择方法是使得 与前与前与前与前l l l l个聚点的距离最小者等于所有个聚点的距离最小者等于所有个聚点的距离最小者等于所有个聚点的距离最小者等于所有其余的与前其余的与前其余的与前其余的与前l l l l个聚点的较小距离的最大者，直至选定个聚点的较小距离的最大者，直至选定个聚点的较小距离的最大者，直至选定个聚点的较小距离的最大者，直至选定k k k k个聚点，