**对比文件名称**：2002-10-15_US6466946B_发明授权_US06466946B1 Computer implemented scalable, incremental and parallel clustering based on divide and conquer
**目标专利名称**：用于非平稳数据的凝聚群集的并行方法 CN105247487B
**本次调用模型名称**：专利创造性评估
### **特征比对表格**
| 技术特征描述及公开性判断结果 | 对比文件原文引用 | 公开性论述 |
| **A. 包括：接收所述数据点流** <br>《隐含公开》 | “The divide and conquer method receives, as input, a set, S, of n points...”（详细描述部分） | 对比文件公开了其方法接收一个点集S作为输入（即数据点的集合）。虽然对比文件没有明确使用“流(stream)”这一术语来描述数据点的输入方式，但其处理的“数据集(dataset)”在增量式（incremental）实施例中，是作为一系列子集(P1, P2, ..., Pr)依次输入的（参见“In one embodiment, the divide and conquer technique of the present invention utilizes, in part, a farthest point (“FP”) method. The input to the FP method is a set, S, of n points...”以及“The divide and conquer method of the present invention has application as an incremental method. For this application, a collection of points, Pi, are input to each increment...”）。本领域技术人员能够理解，这种依次输入的数据子集序列构成了数据点流。因此，对比文件隐含公开了“接收数据点流”这一技术特征。 |
| **B. 确定多个群集质心** <br>《直接公开》 | “The divide and conquer method receives, as input, a set, S, of n points and k number of clusters, and generates, as an output, a plurality of centroids of S (i.e., c1 . . . ck).”（详细描述部分） | 对比文件明确记载了其分治方法的输入是点集S和簇数k，输出是S的多个质心(c1...ck)。该方法的核心步骤之一就是在每个分区（divide步骤）和合并后（conquer步骤）计算质心。例如，在分区步骤中，“The computer processes the subset of points to generate a plurality of partition or divide centroids, Q, k for each of the r partitions”。这直接公开了“确定多个群集质心”这一技术特征。 |
| **C. 将所述多个群集质心划分成多个群集质心群，其中每个群集质心群包含所述多个群集质心的子集并由多个线程和/或处理器中不同的线程和/或处理器独立地采用** <br>《隐含公开》 | “(P1, . . . , Pr)=arbitrary partition of S into r (disjoint) subsets; For i=1 to r Qi=A(Pi,k) End For”（详细描述部分的算法描述）以及“FIG. 7 is a block diagram illustrating one embodiment for implementing the divide and conquer technique in a parallel processing computer system... the dataset is partition the into “p” partitions. Each of the “p” partitions are processed independently (i.e., one partition for each CPU in the multi processor computer system 700).”（详细描述部分及图7说明） | 对比文件公开了将数据集S划分为r个不相交子集(P1...Pr)，然后对每个子集Pi独立应用聚类算法A（如FP方法）生成k个质心Qi。这样，每个处理器/线程处理一个数据子集Pi，并输出一个质心子集Qi（即k个质心）。这些由不同处理器独立生成的质心子集Qi，整体上构成了“多个群集质心群”，每个群（即每个Qi）都是最终质心集合的一个子集。虽然对比文件没有使用“划分质心”这一表述，但其技术方案的实质是：通过划分数据集，让不同处理器并行地、独立地从各自的数据子集中生成质心子集。本领域技术人员可以毫无疑义地推断，这些并行生成的质心子集（Qi）在合并（conquer）之前，就是由不同处理器独立采用的、包含最终质心子集的“群”。因此，该特征被对比文件隐含公开。 |
| **D. 向所述多个线程和/或处理器中的每个线程和/或处理器指派所述数据点流的一部分** <br>《直接公开》 | “(P1, . . . , Pr)=arbitrary partition of S into r (disjoint) subsets;”（详细描述部分的算法描述）以及“the dataset is partition the into “p” partitions. Each of the “p” partitions are processed independently (i.e., one partition for each CPU in the multi processor computer system 700).”（详细描述部分） | 对比文件明确公开了将数据集S任意划分为r（或p）个不相交子集（P1...Pr），并且在并行处理实施例中（图7），每个分区由一个独立的CPU进行处理。这直接对应于向每个处理器指派数据点流（即数据集S）的一部分（即一个分区Pi）。因此，该技术特征被直接公开。 |
| **E. 组合由所述多个线程和/或处理器生成的多个群集以生成全局群集域** <br>《直接公开》 | “{(c1, . . . , ck)}=A(Q1 ∪ . . . Qr,k)”（详细描述部分的算法描述）以及“The divide centroids are merged into a set of partition centroids... Thereafter, the partition centroids are processed... to generate a plurality of conquer centroids, c1, . . . , ck.”（发明内容部分） | 对比文件公开了在“分治(divide)”步骤中，每个处理器生成了分区质心Qi。随后，在“征服(conquer)”步骤中，将这些来自所有分区的质心（Q1 ∪ . . . ∪ Qr）合并，并再次应用聚类算法A，生成最终的k个征服质心(c1...ck)。这个“合并(merge)”并再次聚类的过程，就是组合由多个处理器生成的多个（中间）群集（以质心集合表示）以生成全局群集域（以最终的质心集合表示）的过程。因此，该技术特征被直接公开。 |
| **F. 其特征在于，所述接收包括：从一个或多个传感器接收所述数据点流** <br>《未公开》 | 无相关描述。 | 对比文件通篇讨论的是对存储在计算机中（如磁盘）的一般性数据集进行聚类，例如文本文档集合（“documents accessible on the world wide web”）。没有提及数据点流来自传感器。因此，该技术特征未被对比文件公开。 |
| **G. 其特征在于，所述一个或多个传感器是加速计、陀螺仪、磁力计、或话筒中的一者或多者** <br>《未公开》 | 无相关描述。 | 对比文件未提及任何具体的传感器类型，更未提及加速计、陀螺仪等移动设备传感器。因此，该技术特征未被对比文件公开。 |
| **H. 其特征在于，所述数据点流按循环方式被指派给所述多个线程和/或处理器** <br>《未公开》 | “(P1, . . . , Pr)=arbitrary partition of S into r (disjoint) subsets;”（详细描述部分的算法描述） | 对比文件仅公开了“任意划分(arbitrary partition)”数据集，并未指定任何具体的划分或指派策略，如“循环方式(round-robin)”。因此，该技术特征未被对比文件公开。 |
| **I. 其特征在于，所述数据点流按阶层式方式被指派给所述多个线程和/或处理器** <br>《未公开》 | 无相关描述。 | 对比文件未提及任何阶层式（hierarchical）的数据指派方法。因此，该技术特征未被对比文件公开。 |
| **J. 其特征在于，指派所述数据点流的一部分包括：将接收到的数据点指派给所述多个群集质心中的一个群集质心** <br>《隐含公开》 | “1) The data is partitioned according to the centroids as follows: Cj={s∈S : s is closer to cj than any other centroid ck (j≠k)}”（详细描述部分，描述FP方法步骤） | 对比文件在描述其基础聚类算法（如FP方法）时，明确公开了“根据质心划分数据”的步骤：对于每个点s，找到离其最近的质心cj，并将该点指派给该质心对应的簇Cj。这直接公开了“将接收到的数据点指派给多个群集质心中的一个群集质心”这一子步骤。虽然这是聚类算法内部步骤，但它是整个数据处理流程的一部分。因此，该技术特征被对比文件隐含公开。 |
| **K. 以及将所述接收到的数据点指派给与所述多个群集质心中的这一个群集质心相对应的线程或处理器** <br>《未公开》 | 无相关描述。 | 对比文件公开了将数据子集（分区）整体指派给处理器，也公开了在聚类算法内部将点指派给质心，但并未公开根据一个“质心”来动态决定将“单个接收到的数据点”指派给哪个“线程或处理器”。目标专利中描述的是一种基于质心的阶层式分发机制，而对比文件中的分发是基于对数据集的预先静态划分。因此，该技术特征未被对比文件公开。 |
| **L. 其特征在于，所述多个群集质心中的群集质心数目对应于线程和/或处理器数目** <br>《未公开》 | 无相关描述。 | 对比文件未提及在阶层式分发或任何其他机制中，用于分发目的的质心数目与线程/处理器数目存在对应关系。在对比文件的并行实施例中，每个处理器生成的质心数目是算法参数k，与处理器数目p无关。因此，该技术特征未被对比文件公开。 |
| **M. 其特征在于，所述多个群集质心中的群集质心数目大于线程和/或处理器数目，并且其中所述接收到的数据点基于与所述多个群集质心中的每个群集质心相关联的数据点计数被指派给线程或处理器** <br>《未公开》 | 无相关描述。 | 对比文件未提及任何基于“与质心相关联的数据点计数”来将数据点指派给线程或处理器的机制。因此，该技术特征未被对比文件公开。 |
| **N. 其特征在于，所述数据点流基于所述多个线程和/或处理器中的每个线程和/或处理器的速度被指派给所述多个线程和/或处理器** <br>《未公开》 | 无相关描述。 | 对比文件未提及在划分或指派数据时需要考虑处理器的速度。其划分是“任意的(arbitrary)”。因此，该技术特征未被对比文件公开。 |
| **O. 其特征在于，所述多个线程和/或处理器中的每个线程和/或处理器生成围绕向所述多个线程和/或处理器中的每个线程和/或处理器置备的一个或多个质心的一个或多个群集** <br>《直接公开》 | “For i=1 to r Qi=A(Pi,k) End For”（详细描述部分的算法描述）以及“The computer processes the subset of points to generate a plurality of partition or divide centroids, Q, k for each of the r partitions.”（发明内容部分） | 对比文件明确公开了每个处理器（或每个分区i）对其获指派的子数据集Pi运行聚类算法A(Pi, k)，从而生成k个分区质心Qi。这些质心Qi就是该处理器“生成”的“一个或多个质心”。聚类算法（如FP方法）的本质就是围绕这些质心形成簇（群集）。因此，该技术特征被对比文件直接公开。 |
| **P. 其特征在于，所述多个线程和/或处理器中的每个线程和/或处理器在其开始接收所述数据点流的所述部分时开始生成所述一个或多个群集** <br>《未公开》 | 无相关描述。 | 对比文件没有描述处理器开始生成群集的时机。其算法描述是顺序性的：先划分数据集，然后对每个分区顺序处理。在增量式实施例中，也是处理完一个增量Pi后生成结果。没有提及“一旦开始接收数据即开始处理”的流式处理细节。因此，该技术特征未被对比文件公开。 |
| **Q. 其特征在于，所述多个线程和/或处理器中的每个线程和/或处理器在开始生成所述一个或多个群集之前缓冲所述部分的数据点中的一个或多个数据点** <br>《未公开》 | 无相关描述。 | 对比文件没有提及任何关于缓冲(buffering)数据点的操作。因此，该技术特征未被对比文件公开。 |
| **R. 其特征在于，还包括：丢弃所述数据点流中的数据点以减少所述数据点流中的数据点数目** <br>《未公开》 | 无相关描述。 | 对比文件虽然提到了处理大规模数据集和I/O效率，但其解决方案是分治和采样（sampling），在发明背景中提到了“discards the remaining points”是其他现有技术的方法，并非本对比文件自身权利要求或实施例的一部分。对比文件自身并未公开主动丢弃数据点以控制流大小的步骤。因此，该技术特征未被对比文件公开。 |
| **S. 其特征在于，还包括：降低生成所述数据点流的一个或多个传感器的采样率以减少所述数据点流中的数据点数目** <br>《未公开》 | 无相关描述。 | 对比文件未涉及传感器，更未提及调整传感器采样率。因此，该技术特征未被对比文件公开。 |
| **T. 其特征在于，还包括：对所述全局群集域执行后处理** <br>《未公开》 | 无相关描述。 | 对比文件在生成最终的“征服质心(conquer centroids)”后，没有描述任何进一步的后处理步骤（如数据挖掘）。因此，该技术特征未被对比文件公开。 |
| **U. 其特征在于，所述多个处理器和/或线程驻留在一用户装备上** <br>《未公开》 | “FIG. 5 is a block diagram illustrating one embodiment for implementing the divide and conquer technique in a computer system.”（详细描述部分） | 对比文件将其实施环境描述为通用的“计算机系统(computer system)”或“多处理器计算机系统(multi processor computer system)”（图5、图7），并未限定于“用户装备(UE)”这种特定的移动设备。因此，该技术特征未被对比文件公开。 |
| **V. 其特征在于，所述多个处理器和/或线程驻留在多个用户装备上** <br>《未公开》 | 无相关描述。 | 对比文件未提及处理任务分布在多个用户装备（UE）上。其并行处理是在单个多处理器计算机系统内的多个CPU之间进行的（图7）。因此，该技术特征未被对比文件公开。 |
<<<B>>><<<D>>><<<E>>><<<O>>><<<a>>><<<c>>><<<j>>>