英语原文共 9 页
在电子商务中的个性化数据的K均值聚类算法
摘要
这篇文章描叙了K均值聚类算法，分段k均值聚类算法的组合具有广为人知的空间数据结构，即范围树，允许快速范围搜索。它为了发展提供实时解决方案，因为它允许消费者沿着多个维度的偏好，搜索产品信息，然后为了增强他的购买决策而回收的产品生成数据集群。本文还讨论了在网上购物环境的发展和消费者决策辅助中的传统和移动电子商务应用的这种方法其含义和优点。
在过去的几年中，我们见证了许多组织的巨大增长，他们开发了复杂的交互式Web环境，以适应消费者的在线购物体验。购物者希望根据自己的个人需求，在电子购物环境中定义自己的偏好和定制购买信息。在大多数情况下，值得注意的是，他们评估了所有可用的替代方案，并且通常遵循两步模型来实现其采购流程。在第一步中，他们通过从广泛的领域中进行选择来确定可用替代方案的子集。
在第二步中，他们对产品进行相对比较，得出决策[12]。交互式决策辅助工具，帮助购物者进行采购活动的工具，对采购过程的质量和效率都有很强的有利影响[6]
同时，数据聚类算法承诺为在线商店环境中，随着信息量的增加，消费者之间的交互所产生的许多问题提供有效的解决方案。术语“聚类”指的是一个无监督的过程，通过这个过程，大量的数据项根据相似性被分为不相交的和同质的组（聚类）。尽管在模式分类、数据挖掘或决策等许多应用领域都很有前景，但当对数据性质的先验信息知之甚少时，它仍然会对决策者施加一定的限制。因此，考虑到这些限制，选择适当的方法对有效探索数据项之间的相互关系至关重要，以便做出有意义的评估。通过优化全局（在所有模式上）或局部（在模式的子集上）定义的标准函数来生成集群的一个简单且常用的算法是k-均值算法[10]。它从一个随机的初始分区开始，并根据模式和集群之间的概要信息不断地将模式重新分配给集群。它的主要缺点仍然是，对于在实际应用程序中遇到的非常大的模式集来说，它是非常昂贵的，但它通常会收敛到局部的最小值。
在我们的研究方法中，消费者将自己的每一个偏好都建模为一个在特定区间内的值范围。这些值区间形成了一个多维的“偏好向量”，其中维度由决策参数的数字d定义。这个D维的“偏好向量”被映射到一个面向ISO的矩形，矩形的每一侧对应于D决策偏好维度中的每一个[11]。同时，在一个在线商店中列出的每一个产品对于每个对应的决策维度都具有一定的值。商店中每个产品的NAN D维数据点的这些值。因此，符合消费者设定标准的产品子集由位于面向ISO的矩形内的数据点组成，然后使用k-均值聚类算法将这些数据点分类为不相交的聚类，使消费者能够很容易地区分备选方案并在第一级消除。主宰集群和第二级主宰数据项
本文结合多维距离树和K均值算法，提出了一种正交距离数据聚类方法，为电子商务应用中的有效个性化决策提供了方便。上述方法允许消费者沿着多个维度（而不仅仅是价格）建模决策偏好，并以此方式定义多维决策向量。然后，范围搜索减少了需要在这些多维维度上检查相似性的模式的初始数据集，从而显著缩小了决策空间。最后，k-means算法产生不相交的数据集群，消费者可以更有效地集中于搜索适合其需求的最优解决方案。由于它依赖于一组可扩展的、用户直观的、具有可负担的时间和空间复杂性的实时算法，因此这一行动计划允许在电子商务中开发分布式交互式决策辅助工具。
2.第2条研究方法
首先，消费者通过定义每个偏好的值间隔来陈述自己的偏好。为了简单和形象化的目的，我们假设他只陈述了两个。在第一个例子中，他的偏好是在值和x2之间，在值y和y2之间。这样，就形成了一个面向ISO的矩形，名为R，它的边与轴平行。在线商店提供的产品被描述为二维点，其值为p；和gi，且nnq1isin;a=（p1，q），（_2，92），（/n，q n），其中（p，q）isin;2，i，nisin;该表示形成如图i所示的决策场景。
在第二阶段，他将重点放在这些数据点形成的集群上。在图一中，三个集群位于R矩形内，而另外三个集群位于E矩形外。本文提出的算法以一种简单的方式服务于这两个阶段：首先，它使用一个范围搜索来确定消费者偏好矩形内的所有数据点；其次，它使用k-均值算法族来计算相应的簇（图2）。
必须注意的是，对于矩形内的集群，只有其中包含的点会显著地重新减少报告的集群总数，而且会极大地减少计算时间内的一组数据。此外，消费者无需定义其精确的决策策略a prior，而是可以在检索并计算出所需产品项和下一节中相应的分类后，沿着价值区间重新定义其偏好。我们提出了k均值算法及其分类和混合值的变化。在此基础上，对所提出的K均值范围算法进行了描述，并对其计算复杂度进行了评价，讨论了其在消费者决策辅助工具中的应用。
2.1 K均值聚类算法
k均值算法是一种分段的、非层次的数据聚类方法，适用于将大量数据分类为相应的模式。它是最简单和最常用的算法，使用平方误差准则2）提供一组n个数值对象和一个整数k（k n），它计算k簇中模式的分区。这个过程发生在一个迭代中，从一个随机的初始分区开始，继续寻找一个n的分区，这个分区最大限度地减少了组内平方误差之和。k均值算法分四步进行分析[8]
1.选择k个簇中心与k个随机选择的模式或k个随机定义的点在包含模式集的超卷中重合。
2.将每个模式分配到最近的群集中心（群集MO3）。
3.使用当前群集成员身份重新计算群集中心。
4.收敛函数的计算。如果不满足此要求，则从步骤2重复该过程。
K-均值算法适用于大型数值对象集，尽管它的价格昂贵。它对初始分区的选择很敏感，如果初始分区选择不当，则临界函数值可能收敛。另一方面，k-均值算法的大多数变体已被证明是收敛的4，而一些变体，如theodata算法3]包括一个以某种形式的性能为代价搜索最佳k聚类均值的过程，k-均值算法尝试最小化平方误差，如函数（1）中所述：
其中x是属于第i个簇的第i个图案，y/是第i个簇的中心。
为了提高K均值算法的计算效率或扩展其在分类或混合数据中的表达能力，对K均值算法进行了大量的改进。首先，isodagorithm 3]使用合并和拆分集群的技术，从任意初始分区开始，利用适当的阈值执行此过程，以获得最佳分区。动态聚类算法允许使用最大似然估计的聚类中心以外的其他表示，选择不同的标准函数15]。其他研究工作通过减少（离散计算）的数量来提高计算的复杂性（1，13）。但两个k-均值算法族演化的重要步骤包括通过k-模式和k-原型算法的发展，将其扩展到分类、混合数值和分类值7。k-模式使用简单的匹配相异性度量来处理分类对象，而k-原型定义了一个组合的相异性度量，将k-模式和k-均值算法结合起来，以允许混合数字和分类属性的聚类。在函数（2）中描述了这种组合的不同性度量：
其中v是数值属性集，v是分类属性集。此外，第一项是数值属性上的欧氏距离度量，第二项是简单的
在分类属性上匹配不同的度量值。权重y用于避免偏好任何类型的属性[7]。更具体地说，不同性度量在函数（3）中描述，并被称为简单匹配[9]
k均值算法的计算成本为o（tkn），其中t是迭代次数，k是簇数，n是输入数据集中的数据项数。尽管K模式和K原型算法的运行时间随着集群数量和数据项数量的增加呈线性增加。K-模式算法比K-均值和K-原型算法都快得多。最后，当根据数据项的数量和集群的数量对非常大的数据复杂集进行集群时，这三种算法都是可扩展和高效的[7]
2.2 多维范围搜索
多维范围搜索的形式化描述是：在D维空间中一组n个数据点，因此
由一组二维点定义的三维矩形R，每个点代表一个矩形角尺寸。
输出：矩形R内的所有数据点m。
引入了距离树[17]来解决距离搜索问题。这是一个多级结构，因为它的节点有指向关联结构的指针。然后，主树T被称为第一级树，关联结构为第二级树。范围树如何回答二维查询的简短说明如下
设w为平面上的一组n点，1、1、2、2]分别为两个维度中的每个维度的查询范围。首先，我们集中在寻找第一个坐标在x和y之间的点。为了达到这个目的，我们必须在点的第一个坐标上建立一个二元搜索树，然后用x and搜索，直到得到一个节点t，在那里搜索路径被分割。我们从T的左边继续搜索
对于x和搜索路径左边的每个节点，我们报告右子树中的所有点（与搜索路径相邻的节点）。同样地，我们继续用y在u的右子元素和每个节点进行搜索。搜索路径向右，我们报告左子树中的所有点。因为t#39;是平衡的，所以在mosto（log n）上有这样的节点，其中n是数据点的数量。但我们对报告的所有这些要点不感兴趣。我们只需要第二个坐标位于区间[2，y2]的那些坐标。这是另一个类似的查询，前提是我们在第一次搜索报告的点的第二个坐标上有一个二进制搜索树。这将导致构建具有以下属性的数据结构[5]
主树是一个平衡的二进制搜索树t，它建立在w中点的第一个坐标上，t中的每个节点或叶存储一个指向关联结构7的指针，它是w中点的第二个坐标上的平衡二进制搜索树。
二维范围搜索的算法描述如下
算法2d范围查询(T,[X1,Y1], [X2,Y2])
输入：二维范围树t和范围[X1,Y1], [X2,Y2]
输出：t中位于请求范围内的所有点
v1 查找分裂节点(T,[X1,Y1] )
如果v1是叶，则检查存储在v1的点是否必须报告
否则v 左孩子（v1）
如果v1不是叶，如果x1le;x，之后1D范围查询(Tv，（左孩子(v), [X2,Y2]）
v 左孩子（v）
否则v 右孩子（v）
检查存储在v上的点是否必须报告，同样，遵循从右子（d1）到yi的路径，调用路径左侧子树关联结构上范围为[x2，y2]的id 范围查询，并检查存储在最前面的点是否必须报告路径结束。
多维范围树使用空间，并在时间内回答范围搜索问题，其中m是报告的数据点数。此外，使用部分的实际级联技术，查询时间进一步减少到（最后，必须注意的是，对于（d-1）维情况，D维范围树是从相应的树递归定义的。）
2.3 k-均值范围算法
所提出的k均值范围算法是一个包含多维范围搜索、数字数据点的k均值聚类步骤、数字和分类值的k原型聚类步骤的两步过程，因此对所提出的k均值范围算法的描述如下
在D维空间中输入n个数据点，即D维矩形r。
使用D维范围树搜索计算矩形内的所有数据点，即m。
输入k（簇数表示）
初始化k-means，y1,y2,y3..yn
对每个输入数据点重复Xi,
将Xi分配到具有最接近平均Yj的JTH簇，使得数量或者根据属性的性质，是所有j的最小值，当时，重新计算聚类精度，计算函数直到没有数据点改变集群（或上述质量函数小于给定阈值）
在上述算法中，聚类精度r被定义为实例数y；出现在集群cj中，除以数据集中的实例数（其中包含m个数据点报告的扩展范围搜索）。K均值距离算法的时间复杂度可以很容易地计算出两部分对应的复杂度。首先，多维范围搜索可以在时间内解决，其中m是答案的大小，如前一节所述。k-均值部分，或者更准确地说，修改后的k-原型聚类算法（7）的复杂度为o（t k n），其中t#39;是迭代次数，k is是聚类数量，n是输入数据集中的数据项数量。但由于距离搜索产生的数据点集合明显较小，即M（占其他两个因素的主导地位）和K（占K），因此整个时间复杂度相应降低，并变为，这在很大程度上取决于数据的性质。tklt;m，总的时间复杂度为。
3.实验评价
为了评价提出的k-均值距离算法，我们在C 中实现了一个系统。利用该系统，我们在两个数据集（即DSI和DS2）中分别应用了k-均值及其k-原型变量和k-均值范围算法。所有报告的结果都在运行Linux的Pentium计算机上。处理器的时钟速度为90兆赫，内存大小为128兆字节。
3.1数据集特征
第一个数据集DSI由10个组成。从IMDB电影数据库（www.imdb.com），其中每部电影都表示为具有六个属性的记录：媒体类型、分级、年份、类别、价格、长度。第二个数据集包括从亚马逊图书目录（www.Amazon com），其中每本书都被表示为具有六个属性（定价、最终价格、年份、销售排名、客户评级、版本）的记录。
对于每个数据集和集群数量，我们分别计算k-原型上k-均值范围算法的总体执行时间。由于K均值距离算法的第一部分采用了多维距离搜索预处理阶段，因此其执行时间很大程度上取决于所定义值的范围。因此，我们创建了两个查询，第一个查询覆盖数字属性范围的50%和类别属性范围的50%，第二个查询覆盖上述属性范围的40%。
我们的算法的性能如表L所示。对于每个数据集，我们给出K原型算法的执行时间。此外，对于每个数据集和每个查询，我们还提供在范围搜索阶段之后报告的数据点数量和k平均值范围的总执行时间算法。结果表明，我们的算法以K原型的形式提高了K均值算法的性能，因为它显著减少了报告的数据点数量。
4.含义
k-均值范围算法支持单个消费者的直接购买过程。首先，它帮助购物者形成自己的偏好，形成多属性的论据，这是在谈判和交易中需要特别注意的一个步骤；其次，它使用多维范围搜索来计算决策者请求的数据项。在最后一步中，它生成相应的集群，从而帮助消费者对其选项进行分类。自年以来，k-均值范围算法适用于电子商务应用的发展
它可以集成到现有的数据库系统中。范围搜索使用多层叶单键二叉树，这是一种经过大量寻址和分析的数据结构，非常常见于关系数据库管理系统中用于索引的数据结构。所使用的聚类算法在数值和分类数据以及大型数据集的聚类中都有效。还可以与其他可以在其上有效构建的决策方法相结合，允许购物者根据计算的集群重新定义其标准和偏好。而且购物
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
