基于群体智能的行为聚类系统的制作方法
基于群体智能的行为聚类系统的制作方法
【技术领域】
[0001] 本发明涉及互联网技术领域，尤其涉及基于群体智能的行为聚类系统。
【背景技术】
[0002] 目前，互联网行业发展到一定的程度以后，专业化分工的过程也使其内部结构中 产生了比较细致的分化，从而形成了整个互联网产业从低到高分成几个层次：处于不同层 次的互联网企业具有不同的客户对象、服务手段和利润来源，这就自然地形成了目前互联 网企业的不同商业模式。从目前互联网业界比较通用的角度来划分互联网产业的结构层 次，或者说互联网企业的商业模式主要有以下几种：
[0003] (1)接入与平台（Access and Platforms):这是互联网企业最初的业务形式之一。 服务主要包括互联网接入(有线、无线接入服务)、虚拟主机、主机托管等。同时，部分这类企 业还提供网站制作、维护等服务。
[0004] (2)网上内容提供服务（InternetContentProvide):这项服务是指通过在互联 网上建立网站向网络的用户（包括个人用户与企业用户）提供各种资讯、信息和社区服务的 互联网服务。内容和社区服务类网站根据其所提供内容的广度和深度的不同又可以分为综 合类网站和专业类网站两个大类；依据其提供内容的不同类别，又可以分为搜索引擎、门户 以及虚拟社区等。
[0005] (3)电子商务（E-Commerce):是利用Wbe技术、电子化手段在Internet网上完 成商业贸易活动的新型方式。电子商务的发展非常迅速，根据商务活动产生的资为电子事 物处理(无支付、无物流，如网上报税、网上办公等）和电子贸易处理(有支付、或者有物流， 如网上购物、网上直销等商务活动）；根据交易对象的不同，电子商务又可以分为企业一企 业（BtoB，如电子贸易、电子数据交换、电子资金调拨等应用）、企业一个人（BtoC)、个人 一个人（CtoC，如网络拍卖交易）、政府一个人（CtoC，如通过网络实现个人身份核实、报 税、收税等政府对个人的事务性处理)、政府一企业（GtoB，实现网上报关、报税、网上产权 交易等企业与政府之间的行为）等形式。
[0006] 而WWW上信息的爆炸性增长，使得人们迫切需要开发自动挖掘技术从大量的WWW 数据中发现人们感兴趣的模式和知识，因此Web挖掘越来越成为一个热门的研究领域。但 是如何在如此复杂数据类型的数据中找到需要的知识，就提出了一个新的挑战。
[0007] 随着WWW用户的快速增长，人们淹没在网络信息中渴求着有用的知识，在线分 析用户的浏览行为以及浏览模式已成为越来越重要的研究领域。Tseng、Petrounias和 Chountas给出了一种web挖掘的方法介绍，讨论了在各种限定条件下，如浏览限定、时间的 限定(包括浏览时间、会话期、时间区间等)、个性限定等，如何发现频繁的用户浏览模式及 行为。Srivastava等人详细描述了web使用挖掘的每个阶段，即预处理、模式发现和模式分 析。
[0008] 有些研究者们使用基于关联规则挖掘的方法挖掘web用户浏览模式挖掘。在web 日志挖掘中利用关联规则可以发现用户所访问页面间的关联。有些研究者们把用户浏览访 问模式的发现归属于序列模式挖掘的范畴。WWW用户在访问感兴趣的信息时，倾向于通过连 接或图标来漫游网页。例如，用户为了到达当前主题的一个兄弟主题，总是利用"backward" 图标后退至父主题(起源主题)，再向前作出选择，而不是打开一个新的URL从头开始。因此 在用户日志中的某些结点，被重复访问并非因其内容相关，而是因其结构特殊。为了从原始 日志库中抽取有意义的用户访问模式，我们要消除反向关联的影响，因为反向关联旨在方 便用户访问，而非满足用户的检索需求。Chen等人中采用的寻找最大向前关联路径的思想 与WWW的超链结构特点相结合，用以挖掘用户访问模式。
[0009] 挖掘用户浏览模式的全过程如下：
[0010] (1)从原始日志库中寻找所有最大向前关联路径；
[0011] (2)由找到的最大向前关联路径求出频繁关联路径浏览；
[0012] (3)由频繁关联路径浏览求出最大频繁关联路径浏览。
[0013] 各步骤思想如下：
[0014] 步骤1 :当用户访问一个曾经访问过的URL时，称出现了反向关联。反向关联的发 生意味着一个正向关联路径的结束，并产生最大向前关联路径。然后回溯到该前向关联路 径的起点，再继续寻找其他的前向关联路径。另外，源结点（即无父结点的结点)的出现也意 味着前向关联路径的结束及新路径的开始。
[0015] 步骤2 :找到所有用户的最大前向关联路径后，我们将发现用户访问模式的间题 映射为从所有最大向前关联路径中找最常出现的连续子浏览问题。频繁关联路径浏览定义 为出现次数达到某一阂值的序列。这里我们提出了增量式有序概念格算法。
[0016] 步骤3 :称一个频繁关联路径浏览为最大的，如果它不包含于任何一个其他的最 大频繁关联路径中。
[0017] 关于用户分类的方法很多。目前，很多研究都是从用户价值，特别是用户生命周期 价值对用户分类。如最常见的单因素分类方法ABC，其原理是根据网站运营商利润额构成区 分用户。我们按照网站运营商利润额来源大小对用户进行排序后发现，网站运营商80%以 上的利润来源于20%的用户（A)，70%的用户提供了不足20%的利润（B)，另有10%的用户不 仅不会为网站运营商带来任何利益，甚至会削弱网站运营商的赢利水平（C)。这种方法的缺 陷是只考虑用户给网站运营商带来的利润总额度，而没有区分本网站运营商经营中不同用 户所带来的利润高低，以及用户的成长情况。
[0018] 另外，常用的还有因素结合的方法。影响到网站运营商赢利能力的因素有多种，有 些来自于网站运营商内部，有些来自用户方，因素组合用户分类方法就是根据相关因素组 合结果来区分用户类型。双因素结合方法的主要缺陷是分类过程中一般没有考虑用户的动 态描述数据，没有充分利用用户数据。而多因素结合方法的不足之处在于影响用户分类的 因素选取上。
[0019] 综上所述，针对以上互联网行业的阐述，特别需要基于群体智能的行为聚类系统， 以解决现有技术的不足。
【发明内容】
[0020] 本发明的目的是提供互联网行业的基于群体智能的行为聚类系统，解决实际运行 中存在的不足。
[0021] 本发明为解决其技术问题所采用的技术方案是，
[0022] 基于群体智能的行为聚类系统，该系统的数据表示包括数据结构和数据类型，采 用K均值混合聚类算法；
[0023] 数据类型是一组值的集合和定义在这个值集合之上的一组操作的总称，与数据本 身相关，包括数值性、布尔型、可分类型、混合型等；
[0024] 数据结构是数据的组织形式，通常指存储在计算机内存中的数据；本系统采用的 聚类算法所用的数据主要有以下两种数据结构：
[0025] 1、矢量表示；2、相似矩阵表示；
[0026] 采用k均值混合聚类算法，将蚁群聚类算法与k均值聚类算法结合起来，该算法主 要分成两个部分，第一部分进行蚁群聚类，第二部分用k均值算法收集蚁群聚类的结果，在 k均值混合聚类算法中，相似度公式与蚁群聚类的基本模型及LF算法类似，但采用了更为 简单的概率转换函数，它是两条斜率为k的直线，如下所示；
[0029] 在基本模型中，概率转换函数的参数包括两个阈值常数&和k2，并且阈值常数的 选取和实验数据相关密切，而在k均值混合聚类算法中，概率转换函数只有k，并且通过实 验证明，简化后概率转换函数的参数k并没有根据实验数据变化而变化，因此新算法的概 率转换函数变化同样减轻了算法参数选取的复杂度，提高了算法的实用性，K均值混合聚类 算法的运行过程如下：
[0030] 算法：K均值混合聚类算法
[0031] 输入：P个模式矢量
[0032] 输出：被标记聚类类别的p个模式
[0033] 方法：
[0034] 步骤1 :参数初始化，a，ant_number，k，R，size,dist.最大循环次数n，标注类别 值clusterno等；
[0035] 步骤2 :将待聚类模式随机分散于一个平面上，即随机赋给每一个模式一对（x，y) 坐标；
[0036] 步骤3 :给一组蚂蚁赋初始模式值，初始状态为无负载；
[0037] 步骤 4:fori=l，2...，n;
[0038] 步骤 4.lforj=l，2,…ant_number;
[0039] 步骤4. 1. 1以本只蚂蚁初始模式对应坐标为中心，r为观察半径，利用群体相似度 公式计算此模式在观察半径范围内的群体相似度；
[0040] 步骡4. 1. 2若本只蚂蚁无负载，则计算拾起概率pp;
[0041] 步骤4. 1. 3与一随机概率匕相比较，若pp〈h，则蚂蚁不拾起此模式，再随机赋给蚂 蚁一个模式值，否则蚂蚁拾起此模式，蚂蚁状态改为有负载，随机给蚂蚁一个新坐标；
[0042] 步骤4. 1. 4若本只蚂蚁有负载，则计算放下概率pd ;
[0043] 步骤4. 1. 5与一随机概率&相比较，若pd>h则蚂蚁放下此模式，将蚂蚁的坐标赋 给此模式，蚂蚁状态改为无负载，再随机赋给蚂蚁一个模式值.否则蚂蚁继续携带此模式， 蚂蚁状态仍为有负载，再次随机给蚂蚁一个新坐标；
[0044]步骤 5:fori=l，2…，pattern_num;// 对于每一个模式
[0045] 步骤5. 1若此模式未被标注类别；
[0046] 步骤5. 1. 1标注此模式的类别；
[0047] 步骤5. 1. 2用同一类别标注值递归标注所有相距小于dist的模式，即在平面上收 集所有属于同一集簇的模式；
[0048] 步骤5. 1. 3if同一集簇模式数大于1，类别标注值clusterno++ ;
[0049]else标注此模式为例外；
[0050] 步骤6 :生成聚类中心模板，即计算不包括例外的每一个聚类中心的平均值；
[0051]步骤 7:Repeat;
[0052] 步骤7. 1 (再次）将每一个模式以距离最近的规则划分到所属聚类中心；
[0053] 步骤7. 2更新聚类中心模板；
[0054] 步骤8Until聚类中心模板没有变化；
[0055] k均值混合聚类算法主要包括两个阶段，第一阶段是实现基于群体智能的聚类过 程，第二阶段是以第一阶段得到的聚类中心均值模板和聚类中心个数为参数，实现K均值 聚类过程，当然在收集第一阶段聚类结果的时候，由单个模式形成的聚类中心将不列为第 二阶段的初始聚类中心模板。
[0056] 进一步，所述的矢量表示是通过一个多维空间中的矢量来描述一个对象多方面 的特征，矢量的每个维度对应对象的一个特征，多个对象的矢量可以构成一个模式矩阵 (patternmatrix),矩阵的每一行描述一个对象，每一列对应一个特征，即（Xij)；^，m为特征 的个数，为矢量i在特征j上的特征值，这种表示方法的缺陷之一在于不同的特征有不 同的度量标准和尺度，对聚类结果产生不同的影响，为了消除这种差别，通常采用标准化变 换，使所有的特征能够在一个共同的标准下进行度量，常用的标准化变换如下：
[0057] (1)
'将所有的特征全部规范到[_1，1]区间中，
[0058] (2)
可以数据标 准化为服从标准正态分布，
[0059] (3)
这种变换有更 广泛的适用范围，并且受异常数据的干扰较小。
[0060] 进一步，所述的相似矩阵表示它由表示n个对象两两之间的近似性，表现形式为 一个nXn维对称矩阵，S卩（dij)m，且对角线元素为0,dij是对象i和对象j之间相异性的 量化表示，通常为一个非负的数值，对象i与对象j之间相似程度越 大，其值越接近0;相异 程度越大，其值也越大，
[0061] 通常用对象间的距离来表示对象之间的相似(相异）程度，对距离的度量有很多种 不同的方法，最常用的是欧式距离，它的定义如下：
[0063]其中Xi=(xn，xi2, ? ? ?，xip,)和XjKxji,xj2, ? ? ?，xjp,)是两个p维的数据对象，
[0064] 另一种常见的度量方法是曼哈顿距离，其定义如下：
[0065] (1^-= |Xji-Xj! |+| xi2-xJ21+.. .+ |xip-xJp
[0066] 而明考斯基距离是对欧式距离和曼哈顿距离的概化，它的定义如下：
[0068] 另一种应用的比较多的距离度量方法是马氏距离：
[0069] dij: (Xi-Xj) 'S-1 (Xi-Xj)
[0070] 其中S4为样本协方差阵的逆矩阵，
[0071] 对于文本类型的数据的相似度，通常采用余弦距离来进行度量，定义如下：
[0072] cos (X，y) =x?y/ | | x || ? || y | |
[0073] 其中x，y分别表示两矢量。
[0074] 进一步，所述的蚁群聚类中采用优化蚁群聚类算法，优化蚁群聚类算法基于经典 算法--LF算法，但引入了新的相似度度量公式和概率转换函数，采用了新的距离公式，使 算法能够很好的处理可分类性数据，在参考其他的优化改进算法的基础上，综合了原有的 各种算法的优点，并创新性地引入了调整过程，对蚁群搬运过程形成的聚类进行迭代调整， 优化蚁群聚类算法的公式及函数定义如下：
[0075] 定义一：相似度度量公式
[0076] 相似度是指一个对象与其所在一定的局部的环境中所有的对象的综合也相似度， 设数据集中包含n个对象，其中对象Xi的相似度是指该对象的各个属性的属性概率的算术 平均值，即Xi的相似度f(XJ定义为：
[0078] 定义二：概率转换函数
[0079] 概率转换函数是将相似度转换为简单个体的移动待聚类对象概率的函数，它是以 群体相似度为自变量的函数，函数的值域为[0, 1]，概率转换函数的主要原则是相似度越 大，对象拾起转换概率越小，相似度越小，对象拾起转概率越大；而对象放下转换概率遵循 相反的规律，
[0080] 蚁群聚类算法中，概率转换函数定义如下：
[0083] 其中pp是指概率拾起函数，pd指概率放下函数，概率放下函数为一向上凸的函数， 且对于不同的c值，函数收敛速度不同，C值越大，函数收敛得越快
[0084] 定义三：距离
[0085] 设数据集中包含对象\和X」，则\和X」的距离定义为：
[0088] 本发明的优点在于：
[0089] (1)引入调整过程，传统的蚁群算法是没有调整过程中，仅依靠蚂蚁反复的搬运过 程，导致算法的效率难以提高，并易于导致陷入局部最优和停滞等。而引入调整过程不仅可 以显著改进算法效率，且可以避免局部最优和停滞等。
[0090] (2)动态的观察半径调整。在聚类过程中，前期和后期所适应的观察半径是不一样 的，固定的观察半径无法同时兼顾精度和效率，而采用动态的观察半径，经过试验证明能够 有效的改进效率和精度。
[0091] (3)采用新的相似度度量公式，本发明提出的优化蚁群聚类算法采用了与传统蚁 群聚类算法不一样的相似度度量公式。
[0092] (4)短期记忆，赋予了蚂蚁一个短期记忆，减少蚂蚁所作的一些重复动作。
[0093] 后续的实验证明，这些改进之处使得算法无论是在精度还是效率上都比现有算法 表现更为优异。
【附图说明】
[0094] 下面结合附图和【具体实施方式】来详细说明本发明：
[0095] 图1是本发明优化蚁群聚类算法流程图；
[0096] 图2是本发明基于聚类的用户行为分析过程图；
[0097] 图3是本发明元数据获得过程图；
[0098] 图4是本发明数据预处理过程图；
[0099] 图5是本发明文本特征向量抽取图；
[0100] 图6是本发明用户行为分类的研究模型图；
【具体实施方式】
[0101] 为了使本发明实现的技术手段、创作特征、达成目的与功效易于明白了解，下面结 合图示与具体实施例，进一步阐述本发明。
[0102] 本发明提出的基于群体智能的行为聚类系统，该系统的数据表示包括数据结构和 数据类型，采用K均值混合聚类算法；
[0103] 数据类型是一组值的集合和定义在这个值集合之上的一组操作的总称，与数据本 身相关，包括数值性、布尔型、可分类型、混合型等；
[0104] 数据结构是数据的组织形式，通常指存储在计算机内存中的数据；本系统采用的 聚类算法所用的数据主要有以下两种数据结构：
[0105] 1、矢量表示；2、相似矩阵表示；
[0106] 采用k均值混合聚类算法，将蚁群聚类算法与k均值聚类算法结合起来，该算法主 要分成两个部分，第一部分进行蚁群聚类，第二部分用k均值算法收集蚁群聚类的结果，在 k均值混合聚类算法中，相似度公式与蚁群聚类的基本模型及LF算法类似，但采用了更为 简单的概率转换函数，它是两条斜率为k的直线，如下所示；
[0109] 在基本模型中，概率转换函数的参数包括两个阈值常数匕和匕，并且阈值常数的 选取和实验数据相关密切，而在k均值混合聚类算法中，概率转换函数只有k，并且通过实 验证明，简化后概率转换函数的参数k并没有根据实验数据变化而变化，因此新算法的概 率转换函数变化同样减轻了算法参数选取的复杂度，提高了算法的实用性，K均值混合聚类 算法的运行过程如下：
[0110] 算法：K均值混合聚类算法
[0111] 输入：p个模式矢量
[0112] 输出：被标记聚类类别的p个模式
[0113] 方法：
[0114] 步骤1 :参数初始化，a，ant_number，k，R，size,dist.最大循环次数n，标注类别 值clusterno等；
[0115] 步骤2 :将待聚类模式随机分散于一个平面上，即随机赋给每一个模式一对（x，y) 坐标；
[0116] 步骤3 :给一组蚂蚁赋初始模式值，初始状态为无负载；
[0117] 步骤 4:fori=l，2...，n;
[0118] 步骤 4.lforj=l，2,…ant_number;
[0119] 步骤4. 1. 1以本只蚂蚁初始模式对应坐标为中心，r为观察半径，利用群体相似度 公式计算此模式在观察半径范围内的群体相似度；
[0120] 步骡4. 1. 2若本只蚂蚁无负载，则计算拾起概率pp ;
[0121] 步骤4. 1. 3与一随机概率p,相比较，若pp〈p,，则蚂蚁不拾起此模式，再随机赋给蚂 蚁一个模式值，否则蚂蚁拾起此模式，蚂蚁状态改为有负载，随机给蚂蚁一个新坐标；
[0122] 步骤4. 1. 4若本只蚂蚁有负载，则计算放下概率pd;
[0123] 步骤4. 1. 5与一随机概率p,相比较，若pd>p,则蚂蚁放下此模式，将蚂蚁的坐标赋 给此模式，蚂蚁状态改为无负载，再随机赋给蚂蚁一个模式值.否则蚂蚁继续携带此模式， 蚂蚁状态仍为有负载，再次随机给蚂蚁一个新坐标；
[0124]步骤 5:fori=l，2...，pattern_num;//对于每一个模式
[0125] 步骤5. 1若此模式未被标注类别；
[0126] 步骤5. 1. 1标注此模式的类别；
[0127] 步骤5. 1.2用同一类别标注值递归标注所有相距小于dist的模式，即在平面上收 集所有属于同一集簇的模式；
[0128] 步骤5. 1. 3if同一集簇模式数大于1，类别标注值clusterno++;
[0129]else标注此模式为例外；
[0130] 步骤6 :生成聚类中心模板，即计算不包括例外的每一个聚类中心的平均值；
[0131]步骤 7:Repeat;
[0132] 步骤7. 1(再次）将每一个模式以距离最近的规则划分到所属聚类中心；
[0133] 步骤7. 2更新聚类中心模板；
[0134] 步骤8Until聚类中心模板没有变化；
[0135]k均值混合聚类算法主要包括两个阶段，第一阶段是实现基于群体智能的聚类过 程，第二阶段是以第一阶段得到的聚类中心均值模板和聚类中心个数为参数，实现K均值 聚类过程，当然在收集第一阶段聚类结果的时候，由单个模式形成的聚类中心将不列为第 二阶段的初始聚类中心模板。
[0136] 进一步，所述的矢量表示是通过一个多维空间中的矢量来描述一个对象多方面 的特征，矢量的每个维度对应对象的一个特征，多个对象的矢量可以构成一个模式矩阵 (patternmatrix),矩阵的每一行描述一个对象，每一列对应一个特征，即（Xij)；^，m为特征 的个数，为矢量i在特征j上的特征值，这种表示方法的缺陷之一在于不同的特征有不 同的度量标准和尺度，对聚类结果产生不同的影响，为了消除这种差别，通常采用标准化变 换，使所有的特征能够在一个共同的标准下进行度量，常用的标准化变换如下：
[0137] (1)
'将所有的特征全部规范到[_1，1]区间中，
[0138] (2)
，可以数据标 准化为服从标准正态分布，
[0139] (3)
这种变换有 更广泛的适用范围，并且受异常数据的干扰较小。
[0140] 进一步，所述的相似矩阵表示它由表示n个对象两两之间的近似性，表现形式为 一个nXn维对称矩阵，S卩（dij)m，且对角线元素为0, &是对象i和对象j之间相异性的 量化表示，通常为一个非负的数值，对象i与对象j之间相似程度越大，其值越接近0 ;相异 程度越大，其值也越大，
[0141] 通常用对象间的距离来表示对象之间的相似(相异）程度，对距离的度量有很多种 不同的方法，最常用的是欧式距离，它的定义如下：
[0143]其中Xi=(xn，xi2, ? ? ?，xip,)和XjKxw，xj2, ? ? ?，xjp,)是两个p维的数据对象，
[0144] 另一种常见的度量方法是曼哈顿距离，其定义如下：
[0145] (1^-= |Xji-Xj!|+|xi2-xJ21+.. . + | xip-xJp
[0146] 而明考斯基距离是对欧式距离和曼哈顿距离的概化，它的定义如下：
[0148] 另一种应用的比较多的距离度量方法是马氏距离：
[0149] (1^= (xj-Xj) ' S_1 (xj-Xj)
[0150] 其中S4为样本协方差阵的逆矩阵，
[0151] 对于文本类型的数据的相似度，通常采用余弦距离来进行度量，定义如下：
[0152] cos (X，y) =x?y/| |x| | ? | |y| |
[0153] 其中x, y分别表不两矢量。
[0154] 进一步，所述的蚁群聚类中采用优化蚁群聚类算法，优化蚁群聚类算法基于经典 算法--LF算法，但引入了新的相似度度量公式和概率转换函数，采用了新的距离公式，使 算法能够很好的处理可分类性数据，在参考其他的优化改进算法的基础上，综合了原有的 各种算法的优点，并创新性地引入了调整过程，对蚁群搬运过程形成的聚类进行迭代调整， 优化蚁群聚类算法的公式及函数定义如下：
[0155] 定义一：相似度度量公式
[0156] 相似度是指一个对象与其所在一定的局部的环境中所有的对象的综合也相似度， 设数据集中包含n个对象，其中对象Xi的相似度是指该对象的各个属性的属性概率的算术 平均值，即Xi的相似度f(XJ定义为：
[0158 ] 定义二：概率转换函数
[0159] 概率转换函数是将相似度转换为简单个体的移动待聚类对象概率的函数，它是以 群体相似度为自变量的函数，函数的值域为[0, 1]，概率转换函数的主要原则是相似度越 大，对象拾起转换概率越小，相似度越小，对象拾起转概率越大；而对象放下转换概率遵循 相反的规律，
[0160] 蚁群聚类算法中，概率转换函数定义如下：
[0163]其中pp是指概率拾起函数，pd指概率放下函数，概率放下函数为一向上凸的函数， 且对于不同的C值，函数收敛速度不同，C值越大，函数收敛得越快
[0164] 定义三：距离
[0165] 设数据集中包含对象\和X」，则\和X」的距离定义为：
[0168] 蚁群聚类算法的过程为：
[0169] 搬运过程：蚁群聚类算法的主要过程为蚂蚁的搬运过程。蚂蚁通过判断当前对象 的相似程度，通过概率转换函数决定是否拾起当前对象；同样，蚂蚁搬运对象到目的地之 后，需要判断所负载对象与周围对象的相似程度，决定是否将当前负载对象放下。在此过程 中，蚂蚁并不知晓其它的蚂蚁位置分布，负载情况，也不知道除观察范围之外的其他对象的 分布情况。可以说，蚂蚁的搬运过程是简单的、独立的个体行为。但是正是由于蚂蚁的简单 主体行为，在长期的、协作的过程中将对象逐渐分成了不同的聚类。
[0170] 影响蚂蚁的搬运过程的重要因素除了相似度以及概率转换函数外，还有蚂蚁的观 察半径。蚂蚁的观察半径越小，聚类的效果越好。这是由于蚂蚁的观察半径越小，对周围对 象的比较越精细，聚类的准确程度越高。但是，观察半径过小也会导致形成很多孤立点，影 响聚类的合并，并最终导致聚类性能的下降。而观察半径较大时，虽然会使得聚类结果比较 粗糙，但由于蚂蚁的观察范围大，加快了算法的收敛速度。
[0171] 在常规蚁群算法中，蚂蚁在搬运过程中，是没有任何记忆的。因此，蚂蚁可能会反 复将同一个对象拾起、放下，造成了大量的无用功。为了改善搬运过程的效率，算法考虑赋 予蚂蚁一定的"记忆"。即蚂蚁在搬运对象时，将会记住该对象在原位置的相似度，及原位置 的坐标。蚂蚁在搬起该对象后，必须找到比原位置相似度更大的位置，才会将对象放下。如 果在多次尝试后仍旧没有找到更优的位置，蚂蚁将会将原对象送回原来的位置。经过试验 检验，这种引导方式可以使得蚂蚁的搬运过程更加有效，避免因反复的拾起放下对象导致 效率的下降。
[0172] 对观察半径的调整和赋予蚂蚁"记忆"的功能是本算法中不同于传统蚁群算法的 特点之一，也是算法的重要改进方面。
[0173] 调整过程：在蚁群聚类过程中，蚂蚁所观察的范围仅限于观察半径内，缺乏对全局 信息的了解，因此算法容易陷入局部最优在传统蚁群聚类算法中，仅依赖于蚂蚁的搬运过 程，无法避免算法陷入局部最优和早熟中。这种局部最优体现在两个方面：
[0174] ( 1)无法合并两个相似堆。如果在搬运过程中，形成了两个非常相似的堆，且两个 堆的规模相差不大。对蚂蚁而言，这两个堆的对象的相似度也相差不大，因此，蚂蚁很难将 这两个相似堆合并成同一堆；
[0175] (2)无法分开混合程度大的堆，混合程度大的堆是指堆包含对象数目比较大，且包 含对象种类很多，特别是堆的范围比观察半径更大的情形。这种混合程度较大的堆，相似对 象可能在局部分布集中，因此，蚂蚁在该局部内会判断对象的相似度很大，从而无法将对象 从该堆中搬离或者不断的加入对象，使得堆的规模越来越大。
[0176]为了改善蚂蚁聚类的效果，不少学者采用了混合聚类方法，通常是采用其他的聚 类方法，如k_均值、图划分的方法对蚁群聚类形成的堆进行调整。这种做法能够改善蚁群 聚类的效果。同样，为了避免算法陷入局部最优，本文提出了通过在蚁群聚类算法中引入调 整过程来进行改善。这种调整过程主要包括对同类簇的合并以及重分配异常点两部分。
[0177]为了能够对蚁群聚类的结果进行调整，首先需要将聚类的结果形成簇，再将各个 簇之间的对象进行调整。迭代生成簇的步骤如下：
[0178] (1)设定观察半径R，对于待聚类空间中的对象；
[0179] (2)若该对象周围半径为R的领域内没有其他的点，则将该对象标记为孤立点。
[0180] 否则在半径为R的领域内搜索所有点，是否能够找到其他已被标记簇的对象，如 果找到被标记簇的对象，则将该对象的簇标记赋予观察对象；若领域内所有点都没有被标 注簇，建立一个新簇，将领域内所有点以及观察对象均标记为该簇。
[0181] (3)迭代直到所有的对象都被归入簇中。
[0182] 待形成所有的簇之后，对每一个簇，计算每个簇的聚类中心。对每一个簇，比较该 簇与其他的簇的簇心，如果两个簇的聚类中心相同，说明这两个簇非常相似，因此，将其中 较小的簇合并到较大的簇，形成的新簇以较大的簇的聚类中心为簇心。通过这种调整方法， 可以将相似程度较大的不同簇合并成同一个簇。
[0183] 对聚类中的异常点的调整是通过将簇中相似度较小的对象调整到其他的簇中。对 簇中的每一个对象，计算该对象在簇中的相似度，并且对象按照相似度大小进行排序。通过 设定一个比例，将聚类中的相似度排名较小的对象加入到待调整对象数据子集中来。对该 数据子集中的对象：
[0184] (1)计算该对象与各个簇的簇心的距离，寻找与该对象距离最小的簇的簇心；
[0185] (2)将对象分配到该簇心周围半径为R的领域内，并随机赋予对象坐标。
[0186]为了改善算法对孤立点的聚类效果，算法设定将所有的孤立点也加入到待调整对 象，使得所有的孤立点能够被尽快分配到合适的簇中。
[0187] 由于该调整计算的时间复杂度和空间复杂度都相对较高，并且在算法开始阶段， 由于蚂蚁搬运过程的无序性，基本没有形成有效的簇。因此，算法的调整过程从算法运行中 期开始，且只在每次调整观察半径时进行。经过试验比较，这种策略能够满足异常点调整要 求。
[0188]由图1所不：优化蚁群聚类算法（Optimized Ant Cluster Algorithm，0ACA)算法 的主线是蚂蚁的搬运过程--通过蚂蚁的反复搬运将对象搬到合适的位置；而调整过程是 辅助路线，通过调整过程避免算法陷入早熟和局部优化。调整过程占整个运行阶段的迭代 次数的0. 1%不到。因此，算法的运行效率不会受到调整过程太大的影响。
[0189] 一般的聚类散发评价标准：
[0190] 聚类的目标是将数据对象分组成为多个簇，使得同簇中的对象之间距离尽可能 小，而不同簇中的对象距离尽可能大。对聚类算法有一般的标准，这些标准主要有：
[0191] (1)可伸缩性：算法在模式数增大的情况下的表现。有些算法在模式数小的条件 下，算法的性能很好，但是模式数增大后，算法性能下降。如k-means算法，它对小的数据集 合非常有效，但对大的数据集合没有良好的可伸缩性。
[0192] (2)高维性：算法在模式属性个数增大的情况下的表现。同样，有些算法只擅长处 理低维数据。在高维空间中聚类数据对象是一个挑战，特别是数据有可能非常稀疏和偏斜。
[0193] (3)发现任意形状的聚类：一个簇可能是任意形状的，但一般的聚类算法基于欧式 距离和曼哈顿距离度量来聚类，这样更趋于发现球状簇。在这方面基于密度的方法有较好 的特征。
[0194] (4)处理噪声数据的能力：噪声数据可能是数据本身不完整，也可能是例外数据。 有些算法不擅于处理例外数据，因此还专门出现了发现例外数据的算法。
[0195] (5)用于决定输入参数的领域知识最小化和输入记录顺序敏感性：一方面主要要 求降低算法对输入参数的敏感程度，另一方面要求输入记录顺序对算法的结果影响小。如 经典k均值算法，需要预先给出簇的数目。这个参数对聚类结果有非常大的影响
[0196] (6)可解释性和可用性：要求聚类结果可解释，易理解。这一点与可视化有密切联 系，同时也与实际应用有关。
[0197] 算法评价
[0198] 为了检验算法的有效性以及聚类结果的准确性，同时也为了将优化蚁群聚类算法 与其他经典算法进行比较，算法提出者采用了多组来源于UCI机器学习数据库中的实验数 据进行实验。将0ACA算法与k-modes算法、LF算法、基于信息熵的聚类算法（Entropy-based ClusteringAlgorithm，ECA)进行了对比分析。
[0199] 这里对聚类算法的效果衡量可以从两个方面来考虑。第一个方面是聚类的有效 性，即聚类算法是否能够寻找到数据集中所有的内在分类；第二个方面是聚类的准确度，即 聚类算法能否正确的将同类的数据归为同一个簇，而不同类的数据归入到不同的簇中。为 了度量聚类的效果，我们采用了聚类收缩率和聚类正确率来度量聚类效果。
[0200] 聚类收缩率的定义如下：
[0202] 其中mbest是指数据集的最佳聚类数目，mMsult指聚类完成后的实际聚类数目。聚 类收缩率度量了各个对象被归入各个簇的程度。对于固定聚类数目的算法，如k-modes，基 于信息熵的聚类算法等，由于结果类的数目始终是固定的，且一般与最佳聚类数目相同，聚 类收缩率的度量意义不大。但对于蚁群算法，由于聚类结果的簇数目不固定，因此聚类收缩 率能够在一定程度上反映聚类的收缩效果。
[0203] 聚类正确率的定义如下：
[0205] 其中nvight为正确聚类的对象数目，而man是指所有对象的数目。聚类正确率能够 度量算法的有效性。显然，聚类正确率越高，算法的效果越好。
[0206] 通过实验优化蚁群聚类算法（0ACA)在聚类收缩率和准确度上基本都优于其它算 法。
[0207] 网络市场环境下用户行为特征：
[0208] 网络环境下，用户处于一种比传统用户更强势的地位。在网络市场上，用户获得和 掌握信息的能力越来越强；同时产品的差别越来越难以区分，趋于同质化；另外，用户也更 重视在消费的过程中心灵上的满足感，而不再是仅仅关注商品本身。
[0209] 网络用户的行为特征呈现出以下特点：
[0210] (1) "Self"，即追求个性化需求。当前，用户日益不满足于大众化消费，而是呈现 出差异化、个性化的要求，特别是一些购买力水平高的高端用户，更是追求量身定做的一对 一的服务，网络无疑为满足消费者的差异化需求提供了良好的平台和路径。
[0211] (2)"Instability"，即用户心理稳定性变小，忠诚度下降。在传统模式下，因受制 于信息传递渠道所决定的时间与空间因素，用户很难在较短的时间内广泛获取产品信息并 加以选择。互联网提供了一个平台，信息传递更快捷、更透明，用户时刻面对着多样化的信 息，用户的选择性大大增强。因此其行为表现出不稳定性，很容易在品牌、产品或供应商、销 售商之间进行转换，转换成本降低。转换成本是指用户重新选择一个新的服务提供商时所 花费的代价，它不仅包括货币成本，还包括由不确定而引发的心理和时间成本。转换成本越 高，用户就越不容易转向其他商家，也就越有利于网站运营商建立和维持长期的用户关系。 过去由于信息的不对称使得用户需要花费较大的成本才能转向其他商家，而现在通过网络 只要鼠标一点就能轻易地转向其他商家。
[0212] (3)"Initiative"，即主动性加强。传统模式下，用户通常是等待商家传达商品信 息，接受消费教育。而网络用户则开始表现出强势的主动性，在网络的协助下，积极地寻找 自己感兴趣的商品和信息，并主动联系商家，进行一系列的消费活动。网站运营商要正视这 种变化，分析用户动态的需求。
[0213] (4) "Trust"，即网络消费的信用问题。信任是获得并维持用户关系的前提条件。 进行网络消费时，交易双方并不见面，其交易完全通过网络进行，网络的距离性、虚拟性使 得用户承担着很大的风险。因此，交易主体间的信任受到特别的重视。
[0214] 现在网络消费的核心还是产品或品牌，然而，在竞争 趋于同质化的环境下，"产品" 和"品牌"的生存空间越来越狭窄，"用户"才是制胜的法宝。综合以上网络用户的行为特征， 可以看出在网络经济时代，市场竞争实质上就是一场争夺用户资源的竞争，在这场竞争中， 拥有用户就意味着拥有市场。为此，以用户为中心，分析用户行为尤其是用户网络浏览行 为，不断满足用户需求并为用户创造价值，与用户建立和保持一种长期、良好的合作关系， 赢得用户信任，就成为成功与否的关键要素。
[0215] 用户分类的定义
[0216] 用户分类的主要思想是每个人作为消费者，其对同一种产品的具体功能需求和关 注点是不同的，作为为用户提供服务的网站运营商，必须尽可能的考虑这些差异，发现这些 存在于用户整体内部的具有不同特征或消费习惯的用户群体，然后再根据每个群体的特征 执行针对性的管理或营销策略。这个把用户分成不同群体的过程称之为"用户分类"。
[0217] 用户分类是用户关系经济学的基本原则之一。对网站运营商而言，不同的用户具 有不同的价值，网站运营商用户关系管理作为一个获取、保持和增加可获利顾客的过程，其 最主要的任务之一是采取有效的方法对用户进行分类，发现内在价值高的用户，将网站运 营商有限的资源集中于这些用户，更好地为他们提供服务，培育用户忠诚度，防止优质用户 被挤压而失去。因此，网站运营商能否维系住老用户和优质用户，是决定网站运营商赢利能 力大小的关键，也是网站运营商核心竞争力的重要组成部分。
[0218] 对用户行为进行分类研究的必要性
[0219]网站运营商的资原是有限的，因此必须根据市场的状况，根据用户的消费行为进 行划分，以采取更有效的营销策略；同时对用户进行了细分，可以使网站运营商深刻认识用 户，对不同的用户群提供相应的个性化服务，使双方都受益。对用户的划分可根据地理环 境、产品利润、使用率、品牌忠诚度、购买阶段等因素进行，划分的手段可根据网站运营商的 营销战略选择适当的挖掘技术，如聚类技术等。
[0220] 作为网络营销管理的基础，细分与目标市场的思想始终贯穿于营销管理的全过 程。从本质上看，细分与市场的思想实际上就是认为同类用户具有同样的行为特征即同质 性特征，因此可以根据这类用户的共同的行为特征采取适当的有针对性的策略；还可以根 据已知用户行为模式，通过对其它用户类型的判断来推测其行为。
[0221] 在用户关系管理理念下，用户行为模式的研究注重于每一个用户的个体差异性特 征。但显然，孤立地研究个体行为模式不仅在经济上是高成本的，而且忽视了个体间客观存 在共同的行为特征。因此，依据市场细分理论，在首先研究网络细分市场同类用户的共同行 为模式的基础上，进一步研究个体行为模式的差异性是符合逻辑的。
[0222] 基于聚类的用户行为分析过程：
[0223]用户行为分析，特别是群体分析的基础是根据用户行为的相关数据对用户进行聚 类和分类，形成具有不同特征的用户群体，进而分析各个用户群体，根据他们的特点再制定 相应的市场策略。用户聚类是用户行为分析的一个重要分析手段，用户聚类是把大量的用 户聚成不同的类，在每个类里的用户拥有相似的属性，而不同类里的用户的属性则不同，细 致而切实可行的用户聚类对网站运营商的经营策略有很大益处。
[0224]基于聚类的用户行为分析的一般过程如图2所示。首先，从数据仓库中抽取原始 数据并进行转换和清洁等预处理，形成待聚类的模式；然后，应用聚类算法获得细分的用户 群，进而对用户按群组进行针对性分析，发现关键用户，并提出相应得经营策略。
[0225]具体分析过程如下：
[0226] 1、元数据
[0227]为了对用户的浏览行为进行研究，我们要通过各种途径获得用于Web挖掘的有效 数据信息。如用户的注册信息、浏览行为信息、浏览日志信息、页面超链信息、页面内容等 等。根据采集用户行为数据的位置不同可以分为：基于服务器端采集、基于客户端采集和基 于代理服务器端采集3种；根据数据采集的策略不同，即为了采集用户行为数据是否对服 务器中Web页面进行专门的修改可分为：主动方式和被动方式。
[0228]服务器端Log分析技术是目前发展最快的分支之一，已经有了很多商业化的产品 出现：他1：1'四〇1^1'、16131：代11(18、361€41(1、11^等。它们的主要功能是针对原始1^文件对用 户访问行为数据进行统计和查询。另一种服务器方式为帧嗅探器（Sniffer)检测网络传输 的信息，并从TCP/IP帧中直接抽取出相关的使用数据。客户端采集数据的方式主要利用远 程Agent(用Javaapplet或JavaScript编写而成）来帮助收集客户端(单用户/多网站） 访问浏览情景，或者修改浏览器，让浏览器直接获取用户浏览行为信息。从代理服务器端来 看，由于一个Web代理（Proxy)作为用户浏览器与Web服务器之间通讯的主要通道，代理端 可以跟踪来自多个客户访问多个服务器的请求，但建立在代理服务器端的用户行为分析软 件较少。
[0229]服务器端、代理服务器端、客户端都很好地提供了不同种类的数据源。服务器端 所提供的数据记录了所有用户访问服务器的详细资料；代理服务器记录了多个用户在多个Web站点间的浏览行为；而用户端数据则很直接地反映了某个个体的单一的浏览行为。所 以三个不同的数据源分别反映了不同的研究对象群体。
[0230] 本发明中用于用户兴趣挖掘的元数据主要是用户浏览页面的内容信息，它被用于 基于内容的聚类分析。这些页面的内容信息主要来源于Web服务器端，首先根据用户的浏 览日志记录，得到单一用户的浏览历史页面URL，然后从数据库服务器中取出这些URL对应 的Web页面另存于该用户的浏览页面文件夹中如图3所示。
[0231] 2、数据预处理
[0232]Web页面本身具有一定的复杂性，基于用户浏览内容的挖掘对象是一组HTML格式 的文档集，与数据库中数据的结构化和组织性相比，Web页面缺乏同一的结构，即使具有一 些结构，也是着重于格式而非文档内容，它包含了远比任何一组书籍或其它文本发明档多 得多的风格和内容。此外，一个中文文本表现为一个由汉字和标点符号组成的字符串，由字 构成词，由词构成短语，进而形成句、段、节、章、篇等结构。这里，把字、词、短语等等称为语 义特征项。这些语义特征项是人类所使用的自然语言，计算机很难处理其语义。所以，在进 行聚类分析之前需要对文本进行预处理，用结构化的形式保存作为文档的中间表示形式。 从文本所蕴含信息的角度来看，一个中文文本可以由特征项的频率及其相互之间的顺序来 完整表达。要表示文本中特征项之间的顺序信息，就必然要使用有向的指针结构，整个文本 就变成了一个复杂的图，比如树或者网；与之相反的是表示文本中特征项的频率信息，仅 仅使用一个向量就足够了。然而信息检索和文本聚类/分类处理要求定义一种距离函数， 以表示文本之间的相似程度。如果使用复杂的图结构表示文本的话，则很难定义一种合理 的距离函数，因为存在这样的问题：怎样的两棵树才能说很相似？又是什么样的两个网才 能说是距离比较小呢？而使用向量来表示文本，则不会遇到这种困难，数学中有很多种定 义距离的方式可资使用，比如欧式距离、相关系数等。正因为存在以上的困难，所以不得不 舍弃不好利用的顺序信息，只使用特征项的频率向量表示文本。
[0233] 1988年G.Salton提出的向量空间模型VSM(VectorSpaceModel)即是使用向量 来表示文本，并成功应用到SMART系统中，是应用最成功的模型。该模型及相关的技术在文 本分类、自动索引、信息检索等领域得到了广泛的应用，向量空间模型已逐渐成为最简便最 高效的文本表示模型之一。
[0234] 用于聚类分析的数据预处理过程如下图所示。首先，将从用户的浏览历史记录中 获取用户所浏览的HTML页面集合进行清理和规范化处理。然后，采用抽取算法对文本集进 行特征抽取，得到代表文本的特征向量列表。接着，计算特征向量在文本之中的重要性，即 特征权重。最后，采用向量空间模型来表示文本页面，每张文本页面表示为一个特征向量矩 阵。数据预处理是进行Web挖掘的基础，它将非数值型的样本表示为数值形式，这样就可以 采用一般的数据挖掘方法对它们进行分析。数据预处理的好坏，即页面文本表示的正确与 否，直接影响到下一步聚类分析的效果，它是进行用户兴趣挖掘的基础。只有准确地描述了 页面文本，第四章数据预处理才能得到准确的聚类结果，基于聚类结果所得到的用户兴趣 模型才能准确地表示用户的兴趣和喜好行为，如图4、图5所示。
[0235] (1) HTML页面规范化
[0236] 现在因特网上的很多页面都是HTML格式，这些页面由一系列的HTML标记内容组 成。近年来很多学者对Web的数据模型进行了研究，大多数学者倾向于将Web作为一种半 结构化的数据源。
[0237] 根据W3C组织对HTML语言的定义，HTML页面是一层层标记的嵌套体，诸如 〈html>〈head>〈/head>〈body>〈/body>〈/html>的形式，有一个开始标记就应该有一个结束 标记与它相对应。但是实际中的HTML并不完全遵循这样的规范化格式，就算只有开始没有 结束，往往也能显示正确的内容。这就使得因特网中存在了大量的不规范的网页，这给网页 内容分析工作带来了极大的困难。因此，在进行网页内容抽取工作之间必须对网页进行规 范化，提高特征抽取的准确性。
[0238] 规范化网页主要包括两部分，首先要进行一系列的语法和词法分析，将缺少的tag 标记符号补全。该任务可以使用tidy分析工具来完成。第二部分就是删除与文本内容信 息无关的网页信息，包括某些脚本语句、框架结构信息、超链接信息等等。由于这些信息对 接下来的文本内容抽取没贡献，而且还可能产生干扰，所以必须将它们清理，保留有用的内 容信息。
[0239] (2)文本特征向量的抽取
[0240] 向量空间模型表达效果的优劣直接依赖于特征项的选取，以及权重的计算。对于 其中的关键技术，选取特征项有以下几个原则：一是应当选取那些包含语义信息较多，对 文本的表示能力较强的语言单位作为特征项；二是文本在这些特征项上的分布应当有比 较明显的统计规律性；三是这种选取过程本身应当比较容易实现，其时间和空间开销都不 应当太大。一篇中文文本有字、词、短语、句、段等各个层次，在实际应用中常常采用字、词或 短语作为特征项。
[0241] 在对文档进行特征提取之前，需要先进行文本信息的预处理一一特征词条的选 择。从分类文本中有意义地抽取关键词项的相关信息，是非常重要的技术，也是文本处理的 基本要求。从自然语言理解的角度来看，名词及名词短语、动词及动词短语是一个文本的核 心，它们的简单组合可以作为整个文档的简单表示。目前，文本信息预处理所采用的方法主 要包括英文文档的Stemming处理和中文文档的词条切分处理。本发明采用基于词典的正 向匹配、逐词遍历的分词方法。
[0242] 词、词组和短语组成文档的基本元素，并且在不同内容的文档中，各词条出现频率 有一定的规律性，因此可以根据词条的频率特性进行目标特征提取。不同的词条在文档中 的作用是不同的，常用词在所有文档中都有很高的出现频率，无法体现目标内容，而稀有词 在所有文档中出现的次数都很少，其词频统计特性很难确定，这两类词都不能作为特征项， 还有一些词在所有文档中出现的频率都基本相同，区分性差，也不能作为特征项。
[0243] -个有效的特征项集必须具备以下两个特征：
[0244] 1)完全性：特征项能够确实表示目标内容；
[0245] 2)区分性：根据特征项集，能够将目标同其它文档相区分。
[0246] 经过分词处理后获得的原始特征向量维数通常都非常大，这样的高维特征向量使 得系统在运行过程中需要大量的时间和空间，极大地影响了系统的效率；另一方面，在自然 语言中，有很多表达语气的虚词、助词等是没有实际意义的，将它们也纳入特征项集合中不 但增加了系统处理时间，还给系统带来了噪音影响。因此，在不降低 系统性能的前提下，将 高维特征向量转变为低维特征向量是必须的。
[0247]目前对WWW文档特征所采取的特征子集抽取算法一般是构造一个权重评价函数， 对特征集中的每个特征进行独立的评估，这样每个特征都获得一个评估分，然后对所有的 特征按照其评估分大小进行排序，选取预定数目的最佳特征作为结果的特征子集。所以，选 取多少个最佳特征以及采取什么评估函数都需要针对一个具体的问题通过实验来决定。一 些已被广泛采用的评估函数有信息增益、期望交叉嫡、相互信息、文本证据权、词频等。这些 评估函数可大致分为：基于统计分析的方法和基于机器学习的方法。
[0248] (3)文本向量矩阵
[0249] 在向量空间模型中，页面文本用特征向量集来表示
[0250] 文档集合这样表示后，使得计算页面之间的相似度变得很容易，两张页面文档之 间的相似度就是矩阵中所对应的两行数据之间的距离值。由于页面之间的相似度在进行聚 类分析时经常调用，所以在第一次计算时就进行保存，避免以后每次用到都重新计算。
[0251] 综上，经过以上的数据预处理，将非结构、非数值型的Web页面文档用结构化的、 数值型的矩阵来表示，对页面文档的Web聚类分析就可以采用经典的数值型聚类算法，从 页面文档中发现隐含的用户兴趣信息。
[0252] 用户行为分类的研究模型
[0253] 根据基于聚类的用户行为分析过程，将用户行为的研究框架概括如图6所示。
[0254] 数据收集
[0255] 用于Web数据挖掘的数据很多，包括日志信息、用户行为数据、页面超链信息、页 面内容数据、用户注册信息、站点拓扑结构信息等，这些数据一般可以从以下数据源获得： 服务器端、客户端、代理服务器端。在获得用于数据挖掘的元数据后，将它们进行整理并以 适当的格式进行保存，供聚类分析和用户兴趣模型建立使用。
[0256] 与数据库中的结构化数据相比，Web文档具有有限的结构，或者根本就没有结构。 即使具有一些结构，也是着重于格式而非文档内容。不同类型文档的结构也不一致。此外， 文档的内容是人类所使用的自然语言，计算机很难处理其语义。Web文本信息源的这些特殊 性使得现有的数据挖掘技术无法直接应用于其上。这就需要对文本进行预处理，抽取代表 其特征的元数据，这些特征可以用结构化的形式保存作为文档的中间表示形式。文本特征 指的是关于文本的元数据，分为描述性特征和语义性特征。描述性特征诸如文本的名称、日 期、大小、类型等易于获得，而语义性特征较难得到，包括文本的作者、机构、标题、内容等。 W3C近来制定的MXL、RDF等规范提供了对Web文档资源进行描述的语言和框架。在此基础 上，可以从半结构化的Web文档中抽取作者、机构等语义性特征。
[0257] 基于上述，本发明的优点为：引入调整过程，传统的蚁群算法是没有调整过程中， 仅依靠蚂蚁反复的搬运过程，导致算法的效率难以提高，并易于导致陷入局部最优和停滞 等。而引入调整过程不仅可以显著改进算法效率，且可以避免局部最优和停滞等。态的观察 半径调整。在聚类过程中，前期和后期所适应的观察半径是不一样的，固定的观察半径无法 同时兼顾精度和效率，而采用动态的观察半径，经过试验证明能够有效的改进效率和精度。 采用新的相似度度量公式，本发明提出的优化蚁群聚类算法采用了与传统蚁群聚类算法不 一样的相似度度量公式。短期记忆，赋予了蚂蚁一个短期记忆，减少蚂蚁所作的一些重复动 作。后续的实验证明，这些改进之处使得算法无论是在精度还是效率上都比现有算法表现 更为优异。
[0258] 以上显示和描述了本发明的基本原理、主要特征和本发明的优点。本行业的技术 人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是说明本 发明的原理，在不脱离本发明精神和范围的前提下本发明还会有各种变化和改进，这些变 化和改进都落入要求保护的本发明范围内。本发明要求保护范围由所附的权利要求书及其 等同物界定。
【主权项】
1.基于群体智能的行为聚类系统，其特征在于，该系统的数据表示包括数据结构和数 据类型，采用K均值混合聚类算法； 数据类型是一组值的集合和定义在这个值集合之上的一组操作的总称，与数据本身相 关，包括数值性、布尔型、可分类型、混合型等； 数据结构是数据的组织形式，通常指存储在计算机内存中的数据；本系统采用的聚类 算法所用的数据主要有以下两种数据结构： 1、矢量表示；2、相似矩阵表示； 采用k均值混合聚类算法，将蚁群聚类算法与k均值聚类算法结合起来，该算法主要分 成两个部分，第一部分进行蚁群聚类，第二部分用k均值算法收集蚁群聚类的结果，在k均 值混合聚类算法中，相似度公式与蚁群聚类的基本模型及LF算法类似，但采用了更为简单 的概率转换函数，它是两条斜率为k的直线，如下所示；在基本模型中，概率转换函数的参数包括两个阈值常数Ic1和k2，并且阈值常数的选取 和实验数据相关密切，而在k均值混合聚类算法中，概率转换函数只有k，并且通过实验证 明，简化后概率转换函数的参数k并没有根据实验数据变化而变化，因此新算法的概率转 换函数变化同样减轻了算法参数选取的复杂度，提高了算法的实用性，K均值混合聚类算法 的运行过程如下： 算法：K均值混合聚类算法 输入：P个模式矢量 输出：被标记聚类类别的P个模式 方法： 步骤1 :参数初始化，a，ant_number，k，R，size, dist.最大循环次数n，标注类别值 clusterno 等； 步骤2 :将待聚类模式随机分散于一个平面上，即随机赋给每一个模式一对（x，y)坐 标； 步骤3 :给一组蚂蚁赋初始模式值，初始状态为无负载； 步骤 4 :for i=l，2...，η ; 步骤 4. Ifor j=l, 2, ··· ant_number ； 步骤4. I. I以本只蚂蚁初始模式对应坐标为中心，r为观察半径，利用群体相似度公式 计算此模式在观察半径范围内的群体相似度； 步骡4. 1. 2若本只蚂蚁无负载，则计算拾起概率pp ; 步骤4. 1. 3与一随机概率&相比较，若pPk，则蚂蚁不拾起此模式，再随机赋给蚂蚁一 个模式值，否则蚂蚁拾起此模式，蚂蚁状态改为有负载，随机给蚂蚁一个新坐标； 步骤4. 1. 4若本只蚂蚁有负载，则计算放下概率pd ; 步骤4. 1. 5与一随机概率&相比较，若pd>h则蚂蚁放下此模式，将蚂蚁的坐标赋给此 模式，蚂蚁状态改为无负载，再随机赋给蚂蚁一个模式值.否则蚂蚁继续携带此模式，蚂蚁 状态仍为有负载，再次随机给蚂蚁一个新坐标； 步骤 5 :for i=l，2···，pattern_num ;// 对于每一个模式 步骤5. 1若此模式未被标注类别； 步骤5. I. 1标注此模式的类别； 步骤5. 1. 2用同一类别标注值递归标注所有相距小于dist的模式，即在平面上收集所 有属于同一集簇的模式； 步骤5. I. 3if同一集簇模式数大于1，类别标注值clusterno++ ; else标注此模式为例外； 步骤6 :生成聚类中心模板，即计算不包括例外的每一个聚类中心的平均值； 步骤 7 :Repeat ; 步骤7. 1 (再次）将每一个模式以距离最近的规则划分到所属聚类中心； 步骤7. 2更新聚类中心模板； 步骤8Until聚类中心模板没有变化； k均值混合聚类算法主要包括两个阶段，第一阶段是实现基于群体智能的聚类过程，第 二阶段是以第一阶段得到的聚类中心均值模板和聚类中心个数为参数，实现K均值聚类过 程，当然在收集第一阶段聚类结果的时候，由单个模式形成的聚类中心将不列为第二阶段 的初始聚类中心模板。2. 根据权利要求1所述的基于群体智能的行为聚类系统，其特征在于，所述的矢量表 示是通过一个多维空间中的矢量来描述一个对象多方面的特征，矢量的每个维度对应对象 的一个特征，多个对象的矢量可以构成一个模式矩阵（pattern matrix)，矩阵的每一行描 述一个对象，每一列对应一个特征，即（XiPnm,m为特征的个数，Xu为矢量i在特征j上的特 征值，这种表示方法的缺陷之一在于不同的特征有不同的度量标准和尺度，对聚类结果产 生不同的影响，为了消除这种差别，通常采用标准化变换，使所有的特征能够在一个共同的 标准下进行度量，常用的标准化变换如下： (1) ^将所有的特征全部规范到[_1，1]区间中， (2)可以数据标准 化为服从标准正态分布， (3)这种变换有更广泛 的适用范围，并且受异常数据的干扰较小。3. 根据权利要求1所述的基于群体智能的行为聚类系统，其特征在于，所述的相似矩 阵表示它由表示η个对象两两之间的近似性，表现形式为一个η X η维对称矩阵，即（dip m， 且对角线元素为〇，dh是对象i和对象j之间相异性的量化表示，通常为一个非负的数值， 对象i与对象j之间相似程度越大,其值越接近O ;相异程度越大,其值也越大， 通常用对象间的距离来表示对象之间的相似(相异）程度，对距离的度量有很多种不同 的方法，最常用的是欧式距离，它的定义如下：其中 Xi= (Xn, Xi2, ···，Xip,)和 Xj= (Xj1, Xj2, ···，Xjp,)是两个 p 维的数据对象， 另一种常见的度量方法是曼哈顿距离，其定义如下： dij= I XiI-Xji I + I Xi2-Xj21+---+1 xIP-xJp 而明考斯基距离是对欧式距离和曼哈顿距离的概化，它的定义如下：另一种应用的比较多的距离度量方法是马氏距离： Clij= (Xi-Xj) ' S-1 (Xi-Xj) 其中P为样本协方差阵的逆矩阵， 对于文本类型的数据的相似度，通常采用余弦距离来进行度量，定义如下： cos (x, y)=x · y/| |x| I · | |y 其中x，y分别表示两矢量。4.根据权利要求1所述的基于群体智能的行为聚类系统，其特征在于，所述的蚁群聚 类中采用优化蚁群聚类算法，优化蚁群聚类算法基于经典算法--LF算法，但引入了新的 相似度度量公式和概率转换函数，采用了新的距离公式，使算法能够很好的处理可分类性 数据，在参考其他的优化改进算法的基础上，综合了原有的各种算法的优点，并创新性地引 入了调整过程，对蚁群搬运过程形成的聚类进行迭代调整，优化蚁群聚类算法的公式及函 数定义如下： 定义一：相似度度量公式 相似度是指一个对象与其所在一定的局部的环境中所有的对象的综合也相似度，设数 据集中包含η个对象，其中对象Xi的相似度是指该对象的各个属性的属性概率的算术平均 值，即Xi的相似度f (Xi)定义为：定义二：概率转换函数 概率转换函数是将相似度转换为简单个体的移动待聚类对象概率的函数，它是以群体 相似度为自变量的函数，函数的值域为[〇, 1]，概率转换函数的主要原则是相似度越大，对 象拾起转换概率越小，相似度越小，对象拾起转概率越大；而对象放下转换概率遵循相反的 规律， 蚁群聚类算法中，概率转换函数定义如下：其中Pp是指概率拾起函数，Pd指概率放下函数，概率放下函数为一向上凸的函数，且对 于不同的C值，函数收敛速度不同，C值越大，函数收敛得越快 定义三：距离 设数据集中包含对象Xi和Xp则Xi和\的距离定义为：
【专利摘要】本发明提出基于群体智能的行为聚类系统，该系统的数据表示包括数据结构和数据类型，采用K均值混合聚类算法；采用k均值混合聚类算法，将蚁群聚类算法与k均值聚类算法结合起来，该算法主要分成两个部分，第一部分进行蚁群聚类，第二部分用k均值算法收集蚁群聚类的结果，在k均值混合聚类算法中，相似度公式与蚁群聚类的基本模型及LF算法类似，但采用了更为简单的概率转换函数，它是两条斜率为k的直线，后续的实验证明，这些改进之处使得算法无论是在精度还是效率上都比现有算法表现更为优异。
【IPC分类】G06N3/00, G06F17/30
【公开号】CN104899229
【申请号】CN201410084026
【发明人】李臻, 纪敏
【申请人】上海市玻森数据科技有限公司
【公开日】2015年9月9日
【申请日】2014年3月7日
【技术领域】
[0001] 本发明涉及互联网技术领域，尤其涉及基于群体智能的行为聚类系统。
【背景技术】
[0002] 目前，互联网行业发展到一定的程度以后，专业化分工的过程也使其内部结构中 产生了比较细致的分化，从而形成了整个互联网产业从低到高分成几个层次：处于不同层 次的互联网企业具有不同的客户对象、服务手段和利润来源，这就自然地形成了目前互联 网企业的不同商业模式。从目前互联网业界比较通用的角度来划分互联网产业的结构层 次，或者说互联网企业的商业模式主要有以下几种：
[0003] (1)接入与平台（Access and Platforms):这是互联网企业最初的业务形式之一。 服务主要包括互联网接入(有线、无线接入服务)、虚拟主机、主机托管等。同时，部分这类企 业还提供网站制作、维护等服务。
[0004] (2)网上内容提供服务（InternetContentProvide):这项服务是指通过在互联 网上建立网站向网络的用户（包括个人用户与企业用户）提供各种资讯、信息和社区服务的 互联网服务。内容和社区服务类网站根据其所提供内容的广度和深度的不同又可以分为综 合类网站和专业类网站两个大类；依据其提供内容的不同类别，又可以分为搜索引擎、门户 以及虚拟社区等。
[0005] (3)电子商务（E-Commerce):是利用Wbe技术、电子化手段在Internet网上完 成商业贸易活动的新型方式。电子商务的发展非常迅速，根据商务活动产生的资为电子事 物处理(无支付、无物流，如网上报税、网上办公等）和电子贸易处理(有支付、或者有物流， 如网上购物、网上直销等商务活动）；根据交易对象的不同，电子商务又可以分为企业一企 业（BtoB，如电子贸易、电子数据交换、电子资金调拨等应用）、企业一个人（BtoC)、个人 一个人（CtoC，如网络拍卖交易）、政府一个人（CtoC，如通过网络实现个人身份核实、报 税、收税等政府对个人的事务性处理)、政府一企业（GtoB，实现网上报关、报税、网上产权 交易等企业与政府之间的行为）等形式。
[0006] 而WWW上信息的爆炸性增长，使得人们迫切需要开发自动挖掘技术从大量的WWW 数据中发现人们感兴趣的模式和知识，因此Web挖掘越来越成为一个热门的研究领域。但 是如何在如此复杂数据类型的数据中找到需要的知识，就提出了一个新的挑战。
[0007] 随着WWW用户的快速增长，人们淹没在网络信息中渴求着有用的知识，在线分 析用户的浏览行为以及浏览模式已成为越来越重要的研究领域。Tseng、Petrounias和 Chountas给出了一种web挖掘的方法介绍，讨论了在各种限定条件下，如浏览限定、时间的 限定(包括浏览时间、会话期、时间区间等)、个性限定等，如何发现频繁的用户浏览模式及 行为。Srivastava等人详细描述了web使用挖掘的每个阶段，即预处理、模式发现和模式分 析。
[0008] 有些研究者们使用基于关联规则挖掘的方法挖掘web用户浏览模式挖掘。在web 日志挖掘中利用关联规则可以发现用户所访问页面间的关联。有些研究者们把用户浏览访 问模式的发现归属于序列模式挖掘的范畴。WWW用户在访问感兴趣的信息时，倾向于通过连 接或图标来漫游网页。例如，用户为了到达当前主题的一个兄弟主题，总是利用"backward" 图标后退至父主题(起源主题)，再向前作出选择，而不是打开一个新的URL从头开始。因此 在用户日志中的某些结点，被重复访问并非因其内容相关，而是因其结构特殊。为了从原始 日志库中抽取有意义的用户访问模式，我们要消除反向关联的影响，因为反向关联旨在方 便用户访问，而非满足用户的检索需求。Chen等人中采用的寻找最大向前关联路径的思想 与WWW的超链结构特点相结合，用以挖掘用户访问模式。
[0009] 挖掘用户浏览模式的全过程如下：
[0010] (1)从原始日志库中寻找所有最大向前关联路径；
[0011] (2)由找到的最大向前关联路径求出频繁关联路径浏览；
[0012] (3)由频繁关联路径浏览求出最大频繁关联路径浏览。
[0013] 各步骤思想如下：
[0014] 步骤1 :当用户访问一个曾经访问过的URL时，称出现了反向关联。反向关联的发 生意味着一个正向关联路径的结束，并产生最大向前关联路径。然后回溯到该前向关联路 径的起点，再继续寻找其他的前向关联路径。另外，源结点（即无父结点的结点)的出现也意 味着前向关联路径的结束及新路径的开始。
[0015] 步骤2 :找到所有用户的最大前向关联路径后，我们将发现用户访问模式的间题 映射为从所有最大向前关联路径中找最常出现的连续子浏览问题。频繁关联路径浏览定义 为出现次数达到某一阂值的序列。这里我们提出了增量式有序概念格算法。
[0016] 步骤3 :称一个频繁关联路径浏览为最大的，如果它不包含于任何一个其他的最 大频繁关联路径中。
[0017] 关于用户分类的方法很多。目前，很多研究都是从用户价值，特别是用户生命周期 价值对用户分类。如最常见的单因素分类方法ABC，其原理是根据网站运营商利润额构成区 分用户。我们按照网站运营商利润额来源大小对用户进行排序后发现，网站运营商80%以 上的利润来源于20%的用户（A)，70%的用户提供了不足20%的利润（B)，另有10%的用户不 仅不会为网站运营商带来任何利益，甚至会削弱网站运营商的赢利水平（C)。这种方法的缺 陷是只考虑用户给网站运营商带来的利润总额度，而没有区分本网站运营商经营中不同用 户所带来的利润高低，以及用户的成长情况。
[0018] 另外，常用的还有因素结合的方法。影响到网站运营商赢利能力的因素有多种，有 些来自于网站运营商内部，有些来自用户方，因素组合用户分类方法就是根据相关因素组 合结果来区分用户类型。双因素结合方法的主要缺陷是分类过程中一般没有考虑用户的动 态描述数据，没有充分利用用户数据。而多因素结合方法的不足之处在于影响用户分类的 因素选取上。
[0019] 综上所述，针对以上互联网行业的阐述，特别需要基于群体智能的行为聚类系统， 以解决现有技术的不足。
【发明内容】
[0020] 本发明的目的是提供互联网行业的基于群体智能的行为聚类系统，解决实际运行 中存在的不足。
[0021] 本发明为解决其技术问题所采用的技术方案是，
[0022] 基于群体智能的行为聚类系统，该系统的数据表示包括数据结构和数据类型，采 用K均值混合聚类算法；
[0023] 数据类型是一组值的集合和定义在这个值集合之上的一组操作的总称，与数据本 身相关，包括数值性、布尔型、可分类型、混合型等；
[0024] 数据结构是数据的组织形式，通常指存储在计算机内存中的数据；本系统采用的 聚类算法所用的数据主要有以下两种数据结构：
[0025] 1、矢量表示；2、相似矩阵表示；
[0026] 采用k均值混合聚类算法，将蚁群聚类算法与k均值聚类算法结合起来，该算法主 要分成两个部分，第一部分进行蚁群聚类，第二部分用k均值算法收集蚁群聚类的结果，在 k均值混合聚类算法中，相似度公式与蚁群聚类的基本模型及LF算法类似，但采用了更为 简单的概率转换函数，它是两条斜率为k的直线，如下所示；
[0029] 在基本模型中，概率转换函数的参数包括两个阈值常数&和k2，并且阈值常数的 选取和实验数据相关密切，而在k均值混合聚类算法中，概率转换函数只有k，并且通过实 验证明，简化后概率转换函数的参数k并没有根据实验数据变化而变化，因此新算法的概 率转换函数变化同样减轻了算法参数选取的复杂度，提高了算法的实用性，K均值混合聚类 算法的运行过程如下：
[0030] 算法：K均值混合聚类算法
[0031] 输入：P个模式矢量
[0032] 输出：被标记聚类类别的p个模式
[0033] 方法：
[0034] 步骤1 :参数初始化，a，ant_number，k，R，size,dist.最大循环次数n，标注类别 值clusterno等；
[0035] 步骤2 :将待聚类模式随机分散于一个平面上，即随机赋给每一个模式一对（x，y) 坐标；
[0036] 步骤3 :给一组蚂蚁赋初始模式值，初始状态为无负载；
[0037] 步骤 4:fori=l，2...，n;
[0038] 步骤 4.lforj=l，2,…ant_number;
[0039] 步骤4. 1. 1以本只蚂蚁初始模式对应坐标为中心，r为观察半径，利用群体相似度 公式计算此模式在观察半径范围内的群体相似度；
[0040] 步骡4. 1. 2若本只蚂蚁无负载，则计算拾起概率pp;
[0041] 步骤4. 1. 3与一随机概率匕相比较，若pp〈h，则蚂蚁不拾起此模式，再随机赋给蚂 蚁一个模式值，否则蚂蚁拾起此模式，蚂蚁状态改为有负载，随机给蚂蚁一个新坐标；
[0042] 步骤4. 1. 4若本只蚂蚁有负载，则计算放下概率pd ;
[0043] 步骤4. 1. 5与一随机概率&相比较，若pd>h则蚂蚁放下此模式，将蚂蚁的坐标赋 给此模式，蚂蚁状态改为无负载，再随机赋给蚂蚁一个模式值.否则蚂蚁继续携带此模式， 蚂蚁状态仍为有负载，再次随机给蚂蚁一个新坐标；
[0044]步骤 5:fori=l，2…，pattern_num;// 对于每一个模式
[0045] 步骤5. 1若此模式未被标注类别；
[0046] 步骤5. 1. 1标注此模式的类别；
[0047] 步骤5. 1. 2用同一类别标注值递归标注所有相距小于dist的模式，即在平面上收 集所有属于同一集簇的模式；
[0048] 步骤5. 1. 3if同一集簇模式数大于1，类别标注值clusterno++ ;
[0049]else标注此模式为例外；
[0050] 步骤6 :生成聚类中心模板，即计算不包括例外的每一个聚类中心的平均值；
[0051]步骤 7:Repeat;
[0052] 步骤7. 1 (再次）将每一个模式以距离最近的规则划分到所属聚类中心；
[0053] 步骤7. 2更新聚类中心模板；
[0054] 步骤8Until聚类中心模板没有变化；
[0055] k均值混合聚类算法主要包括两个阶段，第一阶段是实现基于群体智能的聚类过 程，第二阶段是以第一阶段得到的聚类中心均值模板和聚类中心个数为参数，实现K均值 聚类过程，当然在收集第一阶段聚类结果的时候，由单个模式形成的聚类中心将不列为第 二阶段的初始聚类中心模板。
[0056] 进一步，所述的矢量表示是通过一个多维空间中的矢量来描述一个对象多方面 的特征，矢量的每个维度对应对象的一个特征，多个对象的矢量可以构成一个模式矩阵 (patternmatrix),矩阵的每一行描述一个对象，每一列对应一个特征，即（Xij)；^，m为特征 的个数，为矢量i在特征j上的特征值，这种表示方法的缺陷之一在于不同的特征有不 同的度量标准和尺度，对聚类结果产生不同的影响，为了消除这种差别，通常采用标准化变 换，使所有的特征能够在一个共同的标准下进行度量，常用的标准化变换如下：
[0057] (1)
'将所有的特征全部规范到[_1，1]区间中，
[0058] (2)
可以数据标 准化为服从标准正态分布，
[0059] (3)
这种变换有更 广泛的适用范围，并且受异常数据的干扰较小。
[0060] 进一步，所述的相似矩阵表示它由表示n个对象两两之间的近似性，表现形式为 一个nXn维对称矩阵，S卩（dij)m，且对角线元素为0,dij是对象i和对象j之间相异性的 量化表示，通常为一个非负的数值，对象i与对象j之间相似程度越 大，其值越接近0;相异 程度越大，其值也越大，
[0061] 通常用对象间的距离来表示对象之间的相似(相异）程度，对距离的度量有很多种 不同的方法，最常用的是欧式距离，它的定义如下：
[0063]其中Xi=(xn，xi2, ? ? ?，xip,)和XjKxji,xj2, ? ? ?，xjp,)是两个p维的数据对象，
[0064] 另一种常见的度量方法是曼哈顿距离，其定义如下：
[0065] (1^-= |Xji-Xj! |+| xi2-xJ21+.. .+ |xip-xJp
[0066] 而明考斯基距离是对欧式距离和曼哈顿距离的概化，它的定义如下：
[0068] 另一种应用的比较多的距离度量方法是马氏距离：
[0069] dij: (Xi-Xj) 'S-1 (Xi-Xj)
[0070] 其中S4为样本协方差阵的逆矩阵，
[0071] 对于文本类型的数据的相似度，通常采用余弦距离来进行度量，定义如下：
[0072] cos (X，y) =x?y/ | | x || ? || y | |
[0073] 其中x，y分别表示两矢量。
[0074] 进一步，所述的蚁群聚类中采用优化蚁群聚类算法，优化蚁群聚类算法基于经典 算法--LF算法，但引入了新的相似度度量公式和概率转换函数，采用了新的距离公式，使 算法能够很好的处理可分类性数据，在参考其他的优化改进算法的基础上，综合了原有的 各种算法的优点，并创新性地引入了调整过程，对蚁群搬运过程形成的聚类进行迭代调整， 优化蚁群聚类算法的公式及函数定义如下：
[0075] 定义一：相似度度量公式
[0076] 相似度是指一个对象与其所在一定的局部的环境中所有的对象的综合也相似度， 设数据集中包含n个对象，其中对象Xi的相似度是指该对象的各个属性的属性概率的算术 平均值，即Xi的相似度f(XJ定义为：
[0078] 定义二：概率转换函数
[0079] 概率转换函数是将相似度转换为简单个体的移动待聚类对象概率的函数，它是以 群体相似度为自变量的函数，函数的值域为[0, 1]，概率转换函数的主要原则是相似度越 大，对象拾起转换概率越小，相似度越小，对象拾起转概率越大；而对象放下转换概率遵循 相反的规律，
[0080] 蚁群聚类算法中，概率转换函数定义如下：
[0083] 其中pp是指概率拾起函数，pd指概率放下函数，概率放下函数为一向上凸的函数， 且对于不同的c值，函数收敛速度不同，C值越大，函数收敛得越快
[0084] 定义三：距离
[0085] 设数据集中包含对象\和X」，则\和X」的距离定义为：
[0088] 本发明的优点在于：
[0089] (1)引入调整过程，传统的蚁群算法是没有调整过程中，仅依靠蚂蚁反复的搬运过 程，导致算法的效率难以提高，并易于导致陷入局部最优和停滞等。而引入调整过程不仅可 以显著改进算法效率，且可以避免局部最优和停滞等。
[0090] (2)动态的观察半径调整。在聚类过程中，前期和后期所适应的观察半径是不一样 的，固定的观察半径无法同时兼顾精度和效率，而采用动态的观察半径，经过试验证明能够 有效的改进效率和精度。
[0091] (3)采用新的相似度度量公式，本发明提出的优化蚁群聚类算法采用了与传统蚁 群聚类算法不一样的相似度度量公式。
[0092] (4)短期记忆，赋予了蚂蚁一个短期记忆，减少蚂蚁所作的一些重复动作。
[0093] 后续的实验证明，这些改进之处使得算法无论是在精度还是效率上都比现有算法 表现更为优异。
【附图说明】
[0094] 下面结合附图和【具体实施方式】来详细说明本发明：
[0095] 图1是本发明优化蚁群聚类算法流程图；
[0096] 图2是本发明基于聚类的用户行为分析过程图；
[0097] 图3是本发明元数据获得过程图；
[0098] 图4是本发明数据预处理过程图；
[0099] 图5是本发明文本特征向量抽取图；
[0100] 图6是本发明用户行为分类的研究模型图；
【具体实施方式】
[0101] 为了使本发明实现的技术手段、创作特征、达成目的与功效易于明白了解，下面结 合图示与具体实施例，进一步阐述本发明。
[0102] 本发明提出的基于群体智能的行为聚类系统，该系统的数据表示包括数据结构和 数据类型，采用K均值混合聚类算法；
[0103] 数据类型是一组值的集合和定义在这个值集合之上的一组操作的总称，与数据本 身相关，包括数值性、布尔型、可分类型、混合型等；
[0104] 数据结构是数据的组织形式，通常指存储在计算机内存中的数据；本系统采用的 聚类算法所用的数据主要有以下两种数据结构：
[0105] 1、矢量表示；2、相似矩阵表示；
[0106] 采用k均值混合聚类算法，将蚁群聚类算法与k均值聚类算法结合起来，该算法主 要分成两个部分，第一部分进行蚁群聚类，第二部分用k均值算法收集蚁群聚类的结果，在 k均值混合聚类算法中，相似度公式与蚁群聚类的基本模型及LF算法类似，但采用了更为 简单的概率转换函数，它是两条斜率为k的直线，如下所示；
[0109] 在基本模型中，概率转换函数的参数包括两个阈值常数匕和匕，并且阈值常数的 选取和实验数据相关密切，而在k均值混合聚类算法中，概率转换函数只有k，并且通过实 验证明，简化后概率转换函数的参数k并没有根据实验数据变化而变化，因此新算法的概 率转换函数变化同样减轻了算法参数选取的复杂度，提高了算法的实用性，K均值混合聚类 算法的运行过程如下：
[0110] 算法：K均值混合聚类算法
[0111] 输入：p个模式矢量
[0112] 输出：被标记聚类类别的p个模式
[0113] 方法：
[0114] 步骤1 :参数初始化，a，ant_number，k，R，size,dist.最大循环次数n，标注类别 值clusterno等；
[0115] 步骤2 :将待聚类模式随机分散于一个平面上，即随机赋给每一个模式一对（x，y) 坐标；
[0116] 步骤3 :给一组蚂蚁赋初始模式值，初始状态为无负载；
[0117] 步骤 4:fori=l，2...，n;
[0118] 步骤 4.lforj=l，2,…ant_number;
[0119] 步骤4. 1. 1以本只蚂蚁初始模式对应坐标为中心，r为观察半径，利用群体相似度 公式计算此模式在观察半径范围内的群体相似度；
[0120] 步骡4. 1. 2若本只蚂蚁无负载，则计算拾起概率pp ;
[0121] 步骤4. 1. 3与一随机概率p,相比较，若pp〈p,，则蚂蚁不拾起此模式，再随机赋给蚂 蚁一个模式值，否则蚂蚁拾起此模式，蚂蚁状态改为有负载，随机给蚂蚁一个新坐标；
[0122] 步骤4. 1. 4若本只蚂蚁有负载，则计算放下概率pd;
[0123] 步骤4. 1. 5与一随机概率p,相比较，若pd>p,则蚂蚁放下此模式，将蚂蚁的坐标赋 给此模式，蚂蚁状态改为无负载，再随机赋给蚂蚁一个模式值.否则蚂蚁继续携带此模式， 蚂蚁状态仍为有负载，再次随机给蚂蚁一个新坐标；
[0124]步骤 5:fori=l，2...，pattern_num;//对于每一个模式
[0125] 步骤5. 1若此模式未被标注类别；
[0126] 步骤5. 1. 1标注此模式的类别；
[0127] 步骤5. 1.2用同一类别标注值递归标注所有相距小于dist的模式，即在平面上收 集所有属于同一集簇的模式；
[0128] 步骤5. 1. 3if同一集簇模式数大于1，类别标注值clusterno++;
[0129]else标注此模式为例外；
[0130] 步骤6 :生成聚类中心模板，即计算不包括例外的每一个聚类中心的平均值；
[0131]步骤 7:Repeat;
[0132] 步骤7. 1(再次）将每一个模式以距离最近的规则划分到所属聚类中心；
[0133] 步骤7. 2更新聚类中心模板；
[0134] 步骤8Until聚类中心模板没有变化；
[0135]k均值混合聚类算法主要包括两个阶段，第一阶段是实现基于群体智能的聚类过 程，第二阶段是以第一阶段得到的聚类中心均值模板和聚类中心个数为参数，实现K均值 聚类过程，当然在收集第一阶段聚类结果的时候，由单个模式形成的聚类中心将不列为第 二阶段的初始聚类中心模板。
[0136] 进一步，所述的矢量表示是通过一个多维空间中的矢量来描述一个对象多方面 的特征，矢量的每个维度对应对象的一个特征，多个对象的矢量可以构成一个模式矩阵 (patternmatrix),矩阵的每一行描述一个对象，每一列对应一个特征，即（Xij)；^，m为特征 的个数，为矢量i在特征j上的特征值，这种表示方法的缺陷之一在于不同的特征有不 同的度量标准和尺度，对聚类结果产生不同的影响，为了消除这种差别，通常采用标准化变 换，使所有的特征能够在一个共同的标准下进行度量，常用的标准化变换如下：
[0137] (1)
'将所有的特征全部规范到[_1，1]区间中，
[0138] (2)
，可以数据标 准化为服从标准正态分布，
[0139] (3)
这种变换有 更广泛的适用范围，并且受异常数据的干扰较小。
[0140] 进一步，所述的相似矩阵表示它由表示n个对象两两之间的近似性，表现形式为 一个nXn维对称矩阵，S卩（dij)m，且对角线元素为0, &是对象i和对象j之间相异性的 量化表示，通常为一个非负的数值，对象i与对象j之间相似程度越大，其值越接近0 ;相异 程度越大，其值也越大，
[0141] 通常用对象间的距离来表示对象之间的相似(相异）程度，对距离的度量有很多种 不同的方法，最常用的是欧式距离，它的定义如下：
[0143]其中Xi=(xn，xi2, ? ? ?，xip,)和XjKxw，xj2, ? ? ?，xjp,)是两个p维的数据对象，
[0144] 另一种常见的度量方法是曼哈顿距离，其定义如下：
[0145] (1^-= |Xji-Xj!|+|xi2-xJ21+.. . + | xip-xJp
[0146] 而明考斯基距离是对欧式距离和曼哈顿距离的概化，它的定义如下：
[0148] 另一种应用的比较多的距离度量方法是马氏距离：
[0149] (1^= (xj-Xj) ' S_1 (xj-Xj)
[0150] 其中S4为样本协方差阵的逆矩阵，
[0151] 对于文本类型的数据的相似度，通常采用余弦距离来进行度量，定义如下：
[0152] cos (X，y) =x?y/| |x| | ? | |y| |
[0153] 其中x, y分别表不两矢量。
[0154] 进一步，所述的蚁群聚类中采用优化蚁群聚类算法，优化蚁群聚类算法基于经典 算法--LF算法，但引入了新的相似度度量公式和概率转换函数，采用了新的距离公式，使 算法能够很好的处理可分类性数据，在参考其他的优化改进算法的基础上，综合了原有的 各种算法的优点，并创新性地引入了调整过程，对蚁群搬运过程形成的聚类进行迭代调整， 优化蚁群聚类算法的公式及函数定义如下：
[0155] 定义一：相似度度量公式
[0156] 相似度是指一个对象与其所在一定的局部的环境中所有的对象的综合也相似度， 设数据集中包含n个对象，其中对象Xi的相似度是指该对象的各个属性的属性概率的算术 平均值，即Xi的相似度f(XJ定义为：
[0158 ] 定义二：概率转换函数
[0159] 概率转换函数是将相似度转换为简单个体的移动待聚类对象概率的函数，它是以 群体相似度为自变量的函数，函数的值域为[0, 1]，概率转换函数的主要原则是相似度越 大，对象拾起转换概率越小，相似度越小，对象拾起转概率越大；而对象放下转换概率遵循 相反的规律，
[0160] 蚁群聚类算法中，概率转换函数定义如下：
[0163]其中pp是指概率拾起函数，pd指概率放下函数，概率放下函数为一向上凸的函数， 且对于不同的C值，函数收敛速度不同，C值越大，函数收敛得越快
[0164] 定义三：距离
[0165] 设数据集中包含对象\和X」，则\和X」的距离定义为：
[0168] 蚁群聚类算法的过程为：
[0169] 搬运过程：蚁群聚类算法的主要过程为蚂蚁的搬运过程。蚂蚁通过判断当前对象 的相似程度，通过概率转换函数决定是否拾起当前对象；同样，蚂蚁搬运对象到目的地之 后，需要判断所负载对象与周围对象的相似程度，决定是否将当前负载对象放下。在此过程 中，蚂蚁并不知晓其它的蚂蚁位置分布，负载情况，也不知道除观察范围之外的其他对象的 分布情况。可以说，蚂蚁的搬运过程是简单的、独立的个体行为。但是正是由于蚂蚁的简单 主体行为，在长期的、协作的过程中将对象逐渐分成了不同的聚类。
[0170] 影响蚂蚁的搬运过程的重要因素除了相似度以及概率转换函数外，还有蚂蚁的观 察半径。蚂蚁的观察半径越小，聚类的效果越好。这是由于蚂蚁的观察半径越小，对周围对 象的比较越精细，聚类的准确程度越高。但是，观察半径过小也会导致形成很多孤立点，影 响聚类的合并，并最终导致聚类性能的下降。而观察半径较大时，虽然会使得聚类结果比较 粗糙，但由于蚂蚁的观察范围大，加快了算法的收敛速度。
[0171] 在常规蚁群算法中，蚂蚁在搬运过程中，是没有任何记忆的。因此，蚂蚁可能会反 复将同一个对象拾起、放下，造成了大量的无用功。为了改善搬运过程的效率，算法考虑赋 予蚂蚁一定的"记忆"。即蚂蚁在搬运对象时，将会记住该对象在原位置的相似度，及原位置 的坐标。蚂蚁在搬起该对象后，必须找到比原位置相似度更大的位置，才会将对象放下。如 果在多次尝试后仍旧没有找到更优的位置，蚂蚁将会将原对象送回原来的位置。经过试验 检验，这种引导方式可以使得蚂蚁的搬运过程更加有效，避免因反复的拾起放下对象导致 效率的下降。
[0172] 对观察半径的调整和赋予蚂蚁"记忆"的功能是本算法中不同于传统蚁群算法的 特点之一，也是算法的重要改进方面。
[0173] 调整过程：在蚁群聚类过程中，蚂蚁所观察的范围仅限于观察半径内，缺乏对全局 信息的了解，因此算法容易陷入局部最优在传统蚁群聚类算法中，仅依赖于蚂蚁的搬运过 程，无法避免算法陷入局部最优和早熟中。这种局部最优体现在两个方面：
[0174] ( 1)无法合并两个相似堆。如果在搬运过程中，形成了两个非常相似的堆，且两个 堆的规模相差不大。对蚂蚁而言，这两个堆的对象的相似度也相差不大，因此，蚂蚁很难将 这两个相似堆合并成同一堆；
[0175] (2)无法分开混合程度大的堆，混合程度大的堆是指堆包含对象数目比较大，且包 含对象种类很多，特别是堆的范围比观察半径更大的情形。这种混合程度较大的堆，相似对 象可能在局部分布集中，因此，蚂蚁在该局部内会判断对象的相似度很大，从而无法将对象 从该堆中搬离或者不断的加入对象，使得堆的规模越来越大。
[0176]为了改善蚂蚁聚类的效果，不少学者采用了混合聚类方法，通常是采用其他的聚 类方法，如k_均值、图划分的方法对蚁群聚类形成的堆进行调整。这种做法能够改善蚁群 聚类的效果。同样，为了避免算法陷入局部最优，本文提出了通过在蚁群聚类算法中引入调 整过程来进行改善。这种调整过程主要包括对同类簇的合并以及重分配异常点两部分。
[0177]为了能够对蚁群聚类的结果进行调整，首先需要将聚类的结果形成簇，再将各个 簇之间的对象进行调整。迭代生成簇的步骤如下：
[0178] (1)设定观察半径R，对于待聚类空间中的对象；
[0179] (2)若该对象周围半径为R的领域内没有其他的点，则将该对象标记为孤立点。
[0180] 否则在半径为R的领域内搜索所有点，是否能够找到其他已被标记簇的对象，如 果找到被标记簇的对象，则将该对象的簇标记赋予观察对象；若领域内所有点都没有被标 注簇，建立一个新簇，将领域内所有点以及观察对象均标记为该簇。
[0181] (3)迭代直到所有的对象都被归入簇中。
[0182] 待形成所有的簇之后，对每一个簇，计算每个簇的聚类中心。对每一个簇，比较该 簇与其他的簇的簇心，如果两个簇的聚类中心相同，说明这两个簇非常相似，因此，将其中 较小的簇合并到较大的簇，形成的新簇以较大的簇的聚类中心为簇心。通过这种调整方法， 可以将相似程度较大的不同簇合并成同一个簇。
[0183] 对聚类中的异常点的调整是通过将簇中相似度较小的对象调整到其他的簇中。对 簇中的每一个对象，计算该对象在簇中的相似度，并且对象按照相似度大小进行排序。通过 设定一个比例，将聚类中的相似度排名较小的对象加入到待调整对象数据子集中来。对该 数据子集中的对象：
[0184] (1)计算该对象与各个簇的簇心的距离，寻找与该对象距离最小的簇的簇心；
[0185] (2)将对象分配到该簇心周围半径为R的领域内，并随机赋予对象坐标。
[0186]为了改善算法对孤立点的聚类效果，算法设定将所有的孤立点也加入到待调整对 象，使得所有的孤立点能够被尽快分配到合适的簇中。
[0187] 由于该调整计算的时间复杂度和空间复杂度都相对较高，并且在算法开始阶段， 由于蚂蚁搬运过程的无序性，基本没有形成有效的簇。因此，算法的调整过程从算法运行中 期开始，且只在每次调整观察半径时进行。经过试验比较，这种策略能够满足异常点调整要 求。
[0188]由图1所不：优化蚁群聚类算法（Optimized Ant Cluster Algorithm，0ACA)算法 的主线是蚂蚁的搬运过程--通过蚂蚁的反复搬运将对象搬到合适的位置；而调整过程是 辅助路线，通过调整过程避免算法陷入早熟和局部优化。调整过程占整个运行阶段的迭代 次数的0. 1%不到。因此，算法的运行效率不会受到调整过程太大的影响。
[0189] 一般的聚类散发评价标准：
[0190] 聚类的目标是将数据对象分组成为多个簇，使得同簇中的对象之间距离尽可能 小，而不同簇中的对象距离尽可能大。对聚类算法有一般的标准，这些标准主要有：
[0191] (1)可伸缩性：算法在模式数增大的情况下的表现。有些算法在模式数小的条件 下，算法的性能很好，但是模式数增大后，算法性能下降。如k-means算法，它对小的数据集 合非常有效，但对大的数据集合没有良好的可伸缩性。
[0192] (2)高维性：算法在模式属性个数增大的情况下的表现。同样，有些算法只擅长处 理低维数据。在高维空间中聚类数据对象是一个挑战，特别是数据有可能非常稀疏和偏斜。
[0193] (3)发现任意形状的聚类：一个簇可能是任意形状的，但一般的聚类算法基于欧式 距离和曼哈顿距离度量来聚类，这样更趋于发现球状簇。在这方面基于密度的方法有较好 的特征。
[0194] (4)处理噪声数据的能力：噪声数据可能是数据本身不完整，也可能是例外数据。 有些算法不擅于处理例外数据，因此还专门出现了发现例外数据的算法。
[0195] (5)用于决定输入参数的领域知识最小化和输入记录顺序敏感性：一方面主要要 求降低算法对输入参数的敏感程度，另一方面要求输入记录顺序对算法的结果影响小。如 经典k均值算法，需要预先给出簇的数目。这个参数对聚类结果有非常大的影响
[0196] (6)可解释性和可用性：要求聚类结果可解释，易理解。这一点与可视化有密切联 系，同时也与实际应用有关。
[0197] 算法评价
[0198] 为了检验算法的有效性以及聚类结果的准确性，同时也为了将优化蚁群聚类算法 与其他经典算法进行比较，算法提出者采用了多组来源于UCI机器学习数据库中的实验数 据进行实验。将0ACA算法与k-modes算法、LF算法、基于信息熵的聚类算法（Entropy-based ClusteringAlgorithm，ECA)进行了对比分析。
[0199] 这里对聚类算法的效果衡量可以从两个方面来考虑。第一个方面是聚类的有效 性，即聚类算法是否能够寻找到数据集中所有的内在分类；第二个方面是聚类的准确度，即 聚类算法能否正确的将同类的数据归为同一个簇，而不同类的数据归入到不同的簇中。为 了度量聚类的效果，我们采用了聚类收缩率和聚类正确率来度量聚类效果。
[0200] 聚类收缩率的定义如下：
[0202] 其中mbest是指数据集的最佳聚类数目，mMsult指聚类完成后的实际聚类数目。聚 类收缩率度量了各个对象被归入各个簇的程度。对于固定聚类数目的算法，如k-modes，基 于信息熵的聚类算法等，由于结果类的数目始终是固定的，且一般与最佳聚类数目相同，聚 类收缩率的度量意义不大。但对于蚁群算法，由于聚类结果的簇数目不固定，因此聚类收缩 率能够在一定程度上反映聚类的收缩效果。
[0203] 聚类正确率的定义如下：
[0205] 其中nvight为正确聚类的对象数目，而man是指所有对象的数目。聚类正确率能够 度量算法的有效性。显然，聚类正确率越高，算法的效果越好。
[0206] 通过实验优化蚁群聚类算法（0ACA)在聚类收缩率和准确度上基本都优于其它算 法。
[0207] 网络市场环境下用户行为特征：
[0208] 网络环境下，用户处于一种比传统用户更强势的地位。在网络市场上，用户获得和 掌握信息的能力越来越强；同时产品的差别越来越难以区分，趋于同质化；另外，用户也更 重视在消费的过程中心灵上的满足感，而不再是仅仅关注商品本身。
[0209] 网络用户的行为特征呈现出以下特点：
[0210] (1) "Self"，即追求个性化需求。当前，用户日益不满足于大众化消费，而是呈现 出差异化、个性化的要求，特别是一些购买力水平高的高端用户，更是追求量身定做的一对 一的服务，网络无疑为满足消费者的差异化需求提供了良好的平台和路径。
[0211] (2)"Instability"，即用户心理稳定性变小，忠诚度下降。在传统模式下，因受制 于信息传递渠道所决定的时间与空间因素，用户很难在较短的时间内广泛获取产品信息并 加以选择。互联网提供了一个平台，信息传递更快捷、更透明，用户时刻面对着多样化的信 息，用户的选择性大大增强。因此其行为表现出不稳定性，很容易在品牌、产品或供应商、销 售商之间进行转换，转换成本降低。转换成本是指用户重新选择一个新的服务提供商时所 花费的代价，它不仅包括货币成本，还包括由不确定而引发的心理和时间成本。转换成本越 高，用户就越不容易转向其他商家，也就越有利于网站运营商建立和维持长期的用户关系。 过去由于信息的不对称使得用户需要花费较大的成本才能转向其他商家，而现在通过网络 只要鼠标一点就能轻易地转向其他商家。
[0212] (3)"Initiative"，即主动性加强。传统模式下，用户通常是等待商家传达商品信 息，接受消费教育。而网络用户则开始表现出强势的主动性，在网络的协助下，积极地寻找 自己感兴趣的商品和信息，并主动联系商家，进行一系列的消费活动。网站运营商要正视这 种变化，分析用户动态的需求。
[0213] (4) "Trust"，即网络消费的信用问题。信任是获得并维持用户关系的前提条件。 进行网络消费时，交易双方并不见面，其交易完全通过网络进行，网络的距离性、虚拟性使 得用户承担着很大的风险。因此，交易主体间的信任受到特别的重视。
[0214] 现在网络消费的核心还是产品或品牌，然而，在竞争 趋于同质化的环境下，"产品" 和"品牌"的生存空间越来越狭窄，"用户"才是制胜的法宝。综合以上网络用户的行为特征， 可以看出在网络经济时代，市场竞争实质上就是一场争夺用户资源的竞争，在这场竞争中， 拥有用户就意味着拥有市场。为此，以用户为中心，分析用户行为尤其是用户网络浏览行 为，不断满足用户需求并为用户创造价值，与用户建立和保持一种长期、良好的合作关系， 赢得用户信任，就成为成功与否的关键要素。
[0215] 用户分类的定义
[0216] 用户分类的主要思想是每个人作为消费者，其对同一种产品的具体功能需求和关 注点是不同的，作为为用户提供服务的网站运营商，必须尽可能的考虑这些差异，发现这些 存在于用户整体内部的具有不同特征或消费习惯的用户群体，然后再根据每个群体的特征 执行针对性的管理或营销策略。这个把用户分成不同群体的过程称之为"用户分类"。
[0217] 用户分类是用户关系经济学的基本原则之一。对网站运营商而言，不同的用户具 有不同的价值，网站运营商用户关系管理作为一个获取、保持和增加可获利顾客的过程，其 最主要的任务之一是采取有效的方法对用户进行分类，发现内在价值高的用户，将网站运 营商有限的资源集中于这些用户，更好地为他们提供服务，培育用户忠诚度，防止优质用户 被挤压而失去。因此，网站运营商能否维系住老用户和优质用户，是决定网站运营商赢利能 力大小的关键，也是网站运营商核心竞争力的重要组成部分。
[0218] 对用户行为进行分类研究的必要性
[0219]网站运营商的资原是有限的，因此必须根据市场的状况，根据用户的消费行为进 行划分，以采取更有效的营销策略；同时对用户进行了细分，可以使网站运营商深刻认识用 户，对不同的用户群提供相应的个性化服务，使双方都受益。对用户的划分可根据地理环 境、产品利润、使用率、品牌忠诚度、购买阶段等因素进行，划分的手段可根据网站运营商的 营销战略选择适当的挖掘技术，如聚类技术等。
[0220] 作为网络营销管理的基础，细分与目标市场的思想始终贯穿于营销管理的全过 程。从本质上看，细分与市场的思想实际上就是认为同类用户具有同样的行为特征即同质 性特征，因此可以根据这类用户的共同的行为特征采取适当的有针对性的策略；还可以根 据已知用户行为模式，通过对其它用户类型的判断来推测其行为。
[0221] 在用户关系管理理念下，用户行为模式的研究注重于每一个用户的个体差异性特 征。但显然，孤立地研究个体行为模式不仅在经济上是高成本的，而且忽视了个体间客观存 在共同的行为特征。因此，依据市场细分理论，在首先研究网络细分市场同类用户的共同行 为模式的基础上，进一步研究个体行为模式的差异性是符合逻辑的。
[0222] 基于聚类的用户行为分析过程：
[0223]用户行为分析，特别是群体分析的基础是根据用户行为的相关数据对用户进行聚 类和分类，形成具有不同特征的用户群体，进而分析各个用户群体，根据他们的特点再制定 相应的市场策略。用户聚类是用户行为分析的一个重要分析手段，用户聚类是把大量的用 户聚成不同的类，在每个类里的用户拥有相似的属性，而不同类里的用户的属性则不同，细 致而切实可行的用户聚类对网站运营商的经营策略有很大益处。
[0224]基于聚类的用户行为分析的一般过程如图2所示。首先，从数据仓库中抽取原始 数据并进行转换和清洁等预处理，形成待聚类的模式；然后，应用聚类算法获得细分的用户 群，进而对用户按群组进行针对性分析，发现关键用户，并提出相应得经营策略。
[0225]具体分析过程如下：
[0226] 1、元数据
[0227]为了对用户的浏览行为进行研究，我们要通过各种途径获得用于Web挖掘的有效 数据信息。如用户的注册信息、浏览行为信息、浏览日志信息、页面超链信息、页面内容等 等。根据采集用户行为数据的位置不同可以分为：基于服务器端采集、基于客户端采集和基 于代理服务器端采集3种；根据数据采集的策略不同，即为了采集用户行为数据是否对服 务器中Web页面进行专门的修改可分为：主动方式和被动方式。
[0228]服务器端Log分析技术是目前发展最快的分支之一，已经有了很多商业化的产品 出现：他1：1'四〇1^1'、16131：代11(18、361€41(1、11^等。它们的主要功能是针对原始1^文件对用 户访问行为数据进行统计和查询。另一种服务器方式为帧嗅探器（Sniffer)检测网络传输 的信息，并从TCP/IP帧中直接抽取出相关的使用数据。客户端采集数据的方式主要利用远 程Agent(用Javaapplet或JavaScript编写而成）来帮助收集客户端(单用户/多网站） 访问浏览情景，或者修改浏览器，让浏览器直接获取用户浏览行为信息。从代理服务器端来 看，由于一个Web代理（Proxy)作为用户浏览器与Web服务器之间通讯的主要通道，代理端 可以跟踪来自多个客户访问多个服务器的请求，但建立在代理服务器端的用户行为分析软 件较少。
[0229]服务器端、代理服务器端、客户端都很好地提供了不同种类的数据源。服务器端 所提供的数据记录了所有用户访问服务器的详细资料；代理服务器记录了多个用户在多个Web站点间的浏览行为；而用户端数据则很直接地反映了某个个体的单一的浏览行为。所 以三个不同的数据源分别反映了不同的研究对象群体。
[0230] 本发明中用于用户兴趣挖掘的元数据主要是用户浏览页面的内容信息，它被用于 基于内容的聚类分析。这些页面的内容信息主要来源于Web服务器端，首先根据用户的浏 览日志记录，得到单一用户的浏览历史页面URL，然后从数据库服务器中取出这些URL对应 的Web页面另存于该用户的浏览页面文件夹中如图3所示。
[0231] 2、数据预处理
[0232]Web页面本身具有一定的复杂性，基于用户浏览内容的挖掘对象是一组HTML格式 的文档集，与数据库中数据的结构化和组织性相比，Web页面缺乏同一的结构，即使具有一 些结构，也是着重于格式而非文档内容，它包含了远比任何一组书籍或其它文本发明档多 得多的风格和内容。此外，一个中文文本表现为一个由汉字和标点符号组成的字符串，由字 构成词，由词构成短语，进而形成句、段、节、章、篇等结构。这里，把字、词、短语等等称为语 义特征项。这些语义特征项是人类所使用的自然语言，计算机很难处理其语义。所以，在进 行聚类分析之前需要对文本进行预处理，用结构化的形式保存作为文档的中间表示形式。 从文本所蕴含信息的角度来看，一个中文文本可以由特征项的频率及其相互之间的顺序来 完整表达。要表示文本中特征项之间的顺序信息，就必然要使用有向的指针结构，整个文本 就变成了一个复杂的图，比如树或者网；与之相反的是表示文本中特征项的频率信息，仅 仅使用一个向量就足够了。然而信息检索和文本聚类/分类处理要求定义一种距离函数， 以表示文本之间的相似程度。如果使用复杂的图结构表示文本的话，则很难定义一种合理 的距离函数，因为存在这样的问题：怎样的两棵树才能说很相似？又是什么样的两个网才 能说是距离比较小呢？而使用向量来表示文本，则不会遇到这种困难，数学中有很多种定 义距离的方式可资使用，比如欧式距离、相关系数等。正因为存在以上的困难，所以不得不 舍弃不好利用的顺序信息，只使用特征项的频率向量表示文本。
[0233] 1988年G.Salton提出的向量空间模型VSM(VectorSpaceModel)即是使用向量 来表示文本，并成功应用到SMART系统中，是应用最成功的模型。该模型及相关的技术在文 本分类、自动索引、信息检索等领域得到了广泛的应用，向量空间模型已逐渐成为最简便最 高效的文本表示模型之一。
[0234] 用于聚类分析的数据预处理过程如下图所示。首先，将从用户的浏览历史记录中 获取用户所浏览的HTML页面集合进行清理和规范化处理。然后，采用抽取算法对文本集进 行特征抽取，得到代表文本的特征向量列表。接着，计算特征向量在文本之中的重要性，即 特征权重。最后，采用向量空间模型来表示文本页面，每张文本页面表示为一个特征向量矩 阵。数据预处理是进行Web挖掘的基础，它将非数值型的样本表示为数值形式，这样就可以 采用一般的数据挖掘方法对它们进行分析。数据预处理的好坏，即页面文本表示的正确与 否，直接影响到下一步聚类分析的效果，它是进行用户兴趣挖掘的基础。只有准确地描述了 页面文本，第四章数据预处理才能得到准确的聚类结果，基于聚类结果所得到的用户兴趣 模型才能准确地表示用户的兴趣和喜好行为，如图4、图5所示。
[0235] (1) HTML页面规范化
[0236] 现在因特网上的很多页面都是HTML格式，这些页面由一系列的HTML标记内容组 成。近年来很多学者对Web的数据模型进行了研究，大多数学者倾向于将Web作为一种半 结构化的数据源。
[0237] 根据W3C组织对HTML语言的定义，HTML页面是一层层标记的嵌套体，诸如 〈html>〈head>〈/head>〈body>〈/body>〈/html>的形式，有一个开始标记就应该有一个结束 标记与它相对应。但是实际中的HTML并不完全遵循这样的规范化格式，就算只有开始没有 结束，往往也能显示正确的内容。这就使得因特网中存在了大量的不规范的网页，这给网页 内容分析工作带来了极大的困难。因此，在进行网页内容抽取工作之间必须对网页进行规 范化，提高特征抽取的准确性。
[0238] 规范化网页主要包括两部分，首先要进行一系列的语法和词法分析，将缺少的tag 标记符号补全。该任务可以使用tidy分析工具来完成。第二部分就是删除与文本内容信 息无关的网页信息，包括某些脚本语句、框架结构信息、超链接信息等等。由于这些信息对 接下来的文本内容抽取没贡献，而且还可能产生干扰，所以必须将它们清理，保留有用的内 容信息。
[0239] (2)文本特征向量的抽取
[0240] 向量空间模型表达效果的优劣直接依赖于特征项的选取，以及权重的计算。对于 其中的关键技术，选取特征项有以下几个原则：一是应当选取那些包含语义信息较多，对 文本的表示能力较强的语言单位作为特征项；二是文本在这些特征项上的分布应当有比 较明显的统计规律性；三是这种选取过程本身应当比较容易实现，其时间和空间开销都不 应当太大。一篇中文文本有字、词、短语、句、段等各个层次，在实际应用中常常采用字、词或 短语作为特征项。
[0241] 在对文档进行特征提取之前，需要先进行文本信息的预处理一一特征词条的选 择。从分类文本中有意义地抽取关键词项的相关信息，是非常重要的技术，也是文本处理的 基本要求。从自然语言理解的角度来看，名词及名词短语、动词及动词短语是一个文本的核 心，它们的简单组合可以作为整个文档的简单表示。目前，文本信息预处理所采用的方法主 要包括英文文档的Stemming处理和中文文档的词条切分处理。本发明采用基于词典的正 向匹配、逐词遍历的分词方法。
[0242] 词、词组和短语组成文档的基本元素，并且在不同内容的文档中，各词条出现频率 有一定的规律性，因此可以根据词条的频率特性进行目标特征提取。不同的词条在文档中 的作用是不同的，常用词在所有文档中都有很高的出现频率，无法体现目标内容，而稀有词 在所有文档中出现的次数都很少，其词频统计特性很难确定，这两类词都不能作为特征项， 还有一些词在所有文档中出现的频率都基本相同，区分性差，也不能作为特征项。
[0243] -个有效的特征项集必须具备以下两个特征：
[0244] 1)完全性：特征项能够确实表示目标内容；
[0245] 2)区分性：根据特征项集，能够将目标同其它文档相区分。
[0246] 经过分词处理后获得的原始特征向量维数通常都非常大，这样的高维特征向量使 得系统在运行过程中需要大量的时间和空间，极大地影响了系统的效率；另一方面，在自然 语言中，有很多表达语气的虚词、助词等是没有实际意义的，将它们也纳入特征项集合中不 但增加了系统处理时间，还给系统带来了噪音影响。因此，在不降低 系统性能的前提下，将 高维特征向量转变为低维特征向量是必须的。
[0247]目前对WWW文档特征所采取的特征子集抽取算法一般是构造一个权重评价函数， 对特征集中的每个特征进行独立的评估，这样每个特征都获得一个评估分，然后对所有的 特征按照其评估分大小进行排序，选取预定数目的最佳特征作为结果的特征子集。所以，选 取多少个最佳特征以及采取什么评估函数都需要针对一个具体的问题通过实验来决定。一 些已被广泛采用的评估函数有信息增益、期望交叉嫡、相互信息、文本证据权、词频等。这些 评估函数可大致分为：基于统计分析的方法和基于机器学习的方法。
[0248] (3)文本向量矩阵
[0249] 在向量空间模型中，页面文本用特征向量集来表示
[0250] 文档集合这样表示后，使得计算页面之间的相似度变得很容易，两张页面文档之 间的相似度就是矩阵中所对应的两行数据之间的距离值。由于页面之间的相似度在进行聚 类分析时经常调用，所以在第一次计算时就进行保存，避免以后每次用到都重新计算。
[0251] 综上，经过以上的数据预处理，将非结构、非数值型的Web页面文档用结构化的、 数值型的矩阵来表示，对页面文档的Web聚类分析就可以采用经典的数值型聚类算法，从 页面文档中发现隐含的用户兴趣信息。
[0252] 用户行为分类的研究模型
[0253] 根据基于聚类的用户行为分析过程，将用户行为的研究框架概括如图6所示。
[0254] 数据收集
[0255] 用于Web数据挖掘的数据很多，包括日志信息、用户行为数据、页面超链信息、页 面内容数据、用户注册信息、站点拓扑结构信息等，这些数据一般可以从以下数据源获得： 服务器端、客户端、代理服务器端。在获得用于数据挖掘的元数据后，将它们进行整理并以 适当的格式进行保存，供聚类分析和用户兴趣模型建立使用。
[0256] 与数据库中的结构化数据相比，Web文档具有有限的结构，或者根本就没有结构。 即使具有一些结构，也是着重于格式而非文档内容。不同类型文档的结构也不一致。此外， 文档的内容是人类所使用的自然语言，计算机很难处理其语义。Web文本信息源的这些特殊 性使得现有的数据挖掘技术无法直接应用于其上。这就需要对文本进行预处理，抽取代表 其特征的元数据，这些特征可以用结构化的形式保存作为文档的中间表示形式。文本特征 指的是关于文本的元数据，分为描述性特征和语义性特征。描述性特征诸如文本的名称、日 期、大小、类型等易于获得，而语义性特征较难得到，包括文本的作者、机构、标题、内容等。 W3C近来制定的MXL、RDF等规范提供了对Web文档资源进行描述的语言和框架。在此基础 上，可以从半结构化的Web文档中抽取作者、机构等语义性特征。
[0257] 基于上述，本发明的优点为：引入调整过程，传统的蚁群算法是没有调整过程中， 仅依靠蚂蚁反复的搬运过程，导致算法的效率难以提高，并易于导致陷入局部最优和停滞 等。而引入调整过程不仅可以显著改进算法效率，且可以避免局部最优和停滞等。态的观察 半径调整。在聚类过程中，前期和后期所适应的观察半径是不一样的，固定的观察半径无法 同时兼顾精度和效率，而采用动态的观察半径，经过试验证明能够有效的改进效率和精度。 采用新的相似度度量公式，本发明提出的优化蚁群聚类算法采用了与传统蚁群聚类算法不 一样的相似度度量公式。短期记忆，赋予了蚂蚁一个短期记忆，减少蚂蚁所作的一些重复动 作。后续的实验证明，这些改进之处使得算法无论是在精度还是效率上都比现有算法表现 更为优异。
[0258] 以上显示和描述了本发明的基本原理、主要特征和本发明的优点。本行业的技术 人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是说明本 发明的原理，在不脱离本发明精神和范围的前提下本发明还会有各种变化和改进，这些变 化和改进都落入要求保护的本发明范围内。本发明要求保护范围由所附的权利要求书及其 等同物界定。
【主权项】
1.基于群体智能的行为聚类系统，其特征在于，该系统的数据表示包括数据结构和数 据类型，采用K均值混合聚类算法； 数据类型是一组值的集合和定义在这个值集合之上的一组操作的总称，与数据本身相 关，包括数值性、布尔型、可分类型、混合型等； 数据结构是数据的组织形式，通常指存储在计算机内存中的数据；本系统采用的聚类 算法所用的数据主要有以下两种数据结构： 1、矢量表示；2、相似矩阵表示； 采用k均值混合聚类算法，将蚁群聚类算法与k均值聚类算法结合起来，该算法主要分 成两个部分，第一部分进行蚁群聚类，第二部分用k均值算法收集蚁群聚类的结果，在k均 值混合聚类算法中，相似度公式与蚁群聚类的基本模型及LF算法类似，但采用了更为简单 的概率转换函数，它是两条斜率为k的直线，如下所示；在基本模型中，概率转换函数的参数包括两个阈值常数Ic1和k2，并且阈值常数的选取 和实验数据相关密切，而在k均值混合聚类算法中，概率转换函数只有k，并且通过实验证 明，简化后概率转换函数的参数k并没有根据实验数据变化而变化，因此新算法的概率转 换函数变化同样减轻了算法参数选取的复杂度，提高了算法的实用性，K均值混合聚类算法 的运行过程如下： 算法：K均值混合聚类算法 输入：P个模式矢量 输出：被标记聚类类别的P个模式 方法： 步骤1 :参数初始化，a，ant_number，k，R，size, dist.最大循环次数n，标注类别值 clusterno 等； 步骤2 :将待聚类模式随机分散于一个平面上，即随机赋给每一个模式一对（x，y)坐 标； 步骤3 :给一组蚂蚁赋初始模式值，初始状态为无负载； 步骤 4 :for i=l，2...，η ; 步骤 4. Ifor j=l, 2, ··· ant_number ； 步骤4. I. I以本只蚂蚁初始模式对应坐标为中心，r为观察半径，利用群体相似度公式 计算此模式在观察半径范围内的群体相似度； 步骡4. 1. 2若本只蚂蚁无负载，则计算拾起概率pp ; 步骤4. 1. 3与一随机概率&相比较，若pPk，则蚂蚁不拾起此模式，再随机赋给蚂蚁一 个模式值，否则蚂蚁拾起此模式，蚂蚁状态改为有负载，随机给蚂蚁一个新坐标； 步骤4. 1. 4若本只蚂蚁有负载，则计算放下概率pd ; 步骤4. 1. 5与一随机概率&相比较，若pd>h则蚂蚁放下此模式，将蚂蚁的坐标赋给此 模式，蚂蚁状态改为无负载，再随机赋给蚂蚁一个模式值.否则蚂蚁继续携带此模式，蚂蚁 状态仍为有负载，再次随机给蚂蚁一个新坐标； 步骤 5 :for i=l，2···，pattern_num ;// 对于每一个模式 步骤5. 1若此模式未被标注类别； 步骤5. I. 1标注此模式的类别； 步骤5. 1. 2用同一类别标注值递归标注所有相距小于dist的模式，即在平面上收集所 有属于同一集簇的模式； 步骤5. I. 3if同一集簇模式数大于1，类别标注值clusterno++ ; else标注此模式为例外； 步骤6 :生成聚类中心模板，即计算不包括例外的每一个聚类中心的平均值； 步骤 7 :Repeat ; 步骤7. 1 (再次）将每一个模式以距离最近的规则划分到所属聚类中心； 步骤7. 2更新聚类中心模板； 步骤8Until聚类中心模板没有变化； k均值混合聚类算法主要包括两个阶段，第一阶段是实现基于群体智能的聚类过程，第 二阶段是以第一阶段得到的聚类中心均值模板和聚类中心个数为参数，实现K均值聚类过 程，当然在收集第一阶段聚类结果的时候，由单个模式形成的聚类中心将不列为第二阶段 的初始聚类中心模板。2. 根据权利要求1所述的基于群体智能的行为聚类系统，其特征在于，所述的矢量表 示是通过一个多维空间中的矢量来描述一个对象多方面的特征，矢量的每个维度对应对象 的一个特征，多个对象的矢量可以构成一个模式矩阵（pattern matrix)，矩阵的每一行描 述一个对象，每一列对应一个特征，即（XiPnm,m为特征的个数，Xu为矢量i在特征j上的特 征值，这种表示方法的缺陷之一在于不同的特征有不同的度量标准和尺度，对聚类结果产 生不同的影响，为了消除这种差别，通常采用标准化变换，使所有的特征能够在一个共同的 标准下进行度量，常用的标准化变换如下： (1) ^将所有的特征全部规范到[_1，1]区间中， (2)可以数据标准 化为服从标准正态分布， (3)这种变换有更广泛 的适用范围，并且受异常数据的干扰较小。3. 根据权利要求1所述的基于群体智能的行为聚类系统，其特征在于，所述的相似矩 阵表示它由表示η个对象两两之间的近似性，表现形式为一个η X η维对称矩阵，即（dip m， 且对角线元素为〇，dh是对象i和对象j之间相异性的量化表示，通常为一个非负的数值， 对象i与对象j之间相似程度越大,其值越接近O ;相异程度越大,其值也越大， 通常用对象间的距离来表示对象之间的相似(相异）程度，对距离的度量有很多种不同 的方法，最常用的是欧式距离，它的定义如下：其中 Xi= (Xn, Xi2, ···，Xip,)和 Xj= (Xj1, Xj2, ···，Xjp,)是两个 p 维的数据对象， 另一种常见的度量方法是曼哈顿距离，其定义如下： dij= I XiI-Xji I + I Xi2-Xj21+---+1 xIP-xJp 而明考斯基距离是对欧式距离和曼哈顿距离的概化，它的定义如下：另一种应用的比较多的距离度量方法是马氏距离： Clij= (Xi-Xj) ' S-1 (Xi-Xj) 其中P为样本协方差阵的逆矩阵， 对于文本类型的数据的相似度，通常采用余弦距离来进行度量，定义如下： cos (x, y)=x · y/| |x| I · | |y 其中x，y分别表示两矢量。4.根据权利要求1所述的基于群体智能的行为聚类系统，其特征在于，所述的蚁群聚 类中采用优化蚁群聚类算法，优化蚁群聚类算法基于经典算法--LF算法，但引入了新的 相似度度量公式和概率转换函数，采用了新的距离公式，使算法能够很好的处理可分类性 数据，在参考其他的优化改进算法的基础上，综合了原有的各种算法的优点，并创新性地引 入了调整过程，对蚁群搬运过程形成的聚类进行迭代调整，优化蚁群聚类算法的公式及函 数定义如下： 定义一：相似度度量公式 相似度是指一个对象与其所在一定的局部的环境中所有的对象的综合也相似度，设数 据集中包含η个对象，其中对象Xi的相似度是指该对象的各个属性的属性概率的算术平均 值，即Xi的相似度f (Xi)定义为：定义二：概率转换函数 概率转换函数是将相似度转换为简单个体的移动待聚类对象概率的函数，它是以群体 相似度为自变量的函数，函数的值域为[〇, 1]，概率转换函数的主要原则是相似度越大，对 象拾起转换概率越小，相似度越小，对象拾起转概率越大；而对象放下转换概率遵循相反的 规律， 蚁群聚类算法中，概率转换函数定义如下：其中Pp是指概率拾起函数，Pd指概率放下函数，概率放下函数为一向上凸的函数，且对 于不同的C值，函数收敛速度不同，C值越大，函数收敛得越快 定义三：距离 设数据集中包含对象Xi和Xp则Xi和\的距离定义为：
【专利摘要】本发明提出基于群体智能的行为聚类系统，该系统的数据表示包括数据结构和数据类型，采用K均值混合聚类算法；采用k均值混合聚类算法，将蚁群聚类算法与k均值聚类算法结合起来，该算法主要分成两个部分，第一部分进行蚁群聚类，第二部分用k均值算法收集蚁群聚类的结果，在k均值混合聚类算法中，相似度公式与蚁群聚类的基本模型及LF算法类似，但采用了更为简单的概率转换函数，它是两条斜率为k的直线，后续的实验证明，这些改进之处使得算法无论是在精度还是效率上都比现有算法表现更为优异。
【IPC分类】G06N3/00, G06F17/30
【公开号】CN104899229
【申请号】CN201410084026
【发明人】李臻, 纪敏
【申请人】上海市玻森数据科技有限公司
【公开日】2015年9月9日
【申请日】2014年3月7日
最新回复(0)