WO2023058240A1
PCT指定期内
聚类装置、聚类方法及程序
聚类装置、聚类方法及程序
[技术领域]
【0001】 本发明涉及层次聚类技术。
【背景技术】
【0002】 非专利文献1作为层次聚类技术的现有技术而为人所知。 此外,R 的 hclust 函数和 scipy 的链接函数在纯文本中执行层次聚类。 R 是一种用于统计计算和图形的语言和环境,而 scipy 是一个用于高级科学计算的库。
【0003】 非专利文献 1 Stephen C Johnson,“Hierarchical clustering schemes”,Psychometrika,第 32 卷,第 3 期,第 241-254 页,1967 年。
【发明概要】
【发明要解决的问题】
【0004】 然而,使用传统技术,无法在计算中间加密学习数据和值的同时安全地计算层次聚类。
【0005】 根据本发明,聚类中包含的数据点、数据之间或聚类之间的距离等都在一个表中进行管理,从而可以安全地进行层次聚类,同时保留计算过程中和中间的所有值secret. 一个目的是提供一种集群设备、集群方法和程序。
[解决问题的方法]
【0006】 为了解决上述问题,根据本发明的一个方面,一种集群设备将两个最接近的集群连接起来,并在数据ID和集群ID一一对应的集群ID表中设置集群ID。 basis.要更新的簇ID更新单元,删除处理,用于从作为所有簇间距离表的簇间距离表中删除与要加入的簇对应的信息,新加入到簇间的簇distance table and other cluster以及簇间距离更新单元,进行附加处理以添加距离并更新簇间距离表,其中簇ID表和簇间距离表中的信息被加密和加密不解密 使用转换后的信息,执行集群 ID 更新部分中的处理和集群间距离更新部分中的附加处理。
【发明效果】
【0007】 根据本发明,具有可以在保持计算过程和中间值机密的同时安全地执行层次聚类的效果。
【图纸简要说明】
【0008】 用于解释层次聚类的图表。
该图显示了可以通过层次聚类获得的树状图(树图)的示例。
图10是用于说明求出2个簇间的距离时的组平均法的图。
图4是用于说明集群ID表的更新步骤的图。
表示各距离表的例子的图。
安全计算层次聚类的主要算法演示图。
图4是说明簇ID表的更新算法的图。
用于说明删除不需要信息的算法的图。
图4是用于说明聚类合成后的处理图像的图。
groupBy Sum和groupBy Count的计算和关键信息 → k的关系说明图。
关键信息 → k的制作处理流程说明图。
图3是第1实施方式的集群装置的功能框图。
图4是表示第1实施方式的集群化装置的处理流程的一例的图。
该图显示了应用该方法的计算机的结构示例。
【0009】 下面将描述本发明的实施例。 另外,在以下的说明中使用的附图中,对具有相同功能的构成要素和进行相同处理的步骤标注相同的符号,并省略重复的说明。 文中使用的符号“ → 等应该直接写在紧随其后的字符上方,但由于文本符号的限制,它会紧接在相关字符之前。 这些符号写在它们在公式中的原始位置。 此外,除非另有说明,否则对向量或矩阵的每个元素执行的处理将应用于向量或矩阵的所有元素。
【0010】 首先,在描述实施例之前,将描述在实施例中使用的技术。
【0011】 <层次聚类>
‖聚类是归类为无监督学习的机器学习方法之一。 在回归分析和类别分类等监督学习中,目的是准备所需的输出(教师数据)并构建一个模型,以高精度再现该输出,而在聚类等无监督学习中,您不会预先确定输出想。
【0012】 聚类的目的是计算给定的多条数据之间的距离,找到距离较近的数据,即相似数据。 聚类方法大致分为两种类型,一种是非分层方法,如 k-means 方法,其中要创建的聚类数是预先确定的,另一种是最相似的方法,其中聚类数未定义提前。有一种分层方法,可以按顺序对数据进行聚类。 后者的“层次聚类”在本实施例中得到解决。
【0013】 如图 1 所示,层次聚类是一种将数据按降序排列成簇的分析方法。 层次聚类的粗略计算过程如下所示。
【0014】 1.计算所有数据点之间的距离。
【0015】 2. 将最近的两个数据点作为一个新的簇。
【0016】 3. 计算新创建的簇与其他数据点或其他簇的距离。
【0017】 4.取最近的数据点,数据点和簇,或者簇到新的簇。
【0018】 5. 重复步骤 3 和 4,直到所有数据点都在一个簇中。
【0019】 层次聚类的目的是通过这个计算过程计算出所有数据之间的距离,最终得到如图2所示的树状图。 图2中的树状图对应图1中的聚类结果,数据A和B最接近,其次是数据C和D,然后是A和B组成的簇,C和D组成的簇最近。 E是最远的。 当希望详细查看每个数据的接近程度时,使用层次聚类。
【0020】 “如何找到数据之间的距离”和“如何找到聚类之间的距离”在计算层次聚类时很重要。 这些有多种方法,下面将对本实施例中使用的方法进行说明。
【0021】 <欧氏距离>
‖欧几里得距离是最著名的计算数据之间距离的方法之一,两个数据之间的距离 → x=(x 1 ,X 2 ,…,X n )和 → y=(y 1 ,y 2 ,…,y n ) 距离 d( → X, → y)用下式表示。
<组平均法>
组平均法是计算簇间距离时经常使用的距离函数之一。 Ward方法常用于明文层次聚类,但由于其分类敏感性高,计算量大。 另一方面,最短距离法、最长距离法等简单方法由于计算量小,分类灵敏度较低。 组平均法比Ward法计算量小,分类灵敏度优于最短距离法和最长距离法。
【0022】 在使用组平均法计算一个包含数据点ABC的簇与两个包含数据点DE的簇之间的距离时,如图3所示,所有数据点ABC和DE之间的距离的平均值为簇间距离。
【0023】 上文<层次聚类>中说明,首先获取每个数据点之间的所有距离,因此在计算簇间距离时,只需要获取平均值即可。
【0024】 <秘密计算>
・表示法:为了区分明文和密文,a的密文写成[[a]],没有括号的文本为明文。 本实施例中使用的主要函数如下所示。
【0025】 ・加法/减法/乘法:两个密文[[a]]、[[b]]的加法、减法、乘法是密文[[a+b]]、[[a-b]]、[[a×b] ], 分别. ] 进行计算。 这些操作分别写为[[a]]+[[b]],[[a]]-[[b]],[[a]]×[[b]],输入为向量[[ → A]],[[ → b]] 使用相同的符号。
【0026】・ Sum of products:计算矩阵[[A]],[[B]]每一行的乘积和的过程写成hpsum([[A]],[[B]]),hpsum ([[A] ],[[B]]) 是长度为 m [[ → 输出 c]]。
【0027】 Group-By 操作:Group-By Common 是生成中间数据的过程,可以在各种 Group-By 操作(如 Group-By Sum 和 Group-By Count)中通用。 中间数据是替换表[[ → π]] 和一个标志 [[ → e]],通过使用这些,可以有效地执行使用相同键的各种 Group-By 操作。
【0028】 ‖键向量[[ → k]]进行Group-By Common(2),排序后的值属性向量[[ → a']] 和标志 [[ → e]]进行Group-By Sum描述如式(3),Group-By Count描述如式(4)。
【0029】 [[ → π]],[[ → e]],[[ → a']]←groupByCommon([[ → A]],[[ → k]]) (2)
[[ → c]]←groupBySum([[ → A']],[[ → e]]) (3)
[[ → d]]←groupByCount([[ → A']],[[ → e]]) (4)
另外,即使不进行Group-By Common等处理,只要分别执行Group-By Sum和Group-By Count,也可以计算安全计算层次聚类。 但是,使用 Group-By Common 的计算效率更高。
【0030】 ・其他:进行相等判断的equality([[a]],[[b]]), shuffle([[ → 一个]]), 排序([[ → a]]), 逻辑运算 and([[a]],[[b]]) (逻辑积), or([[a]],[[b]]) (逻辑和), not([ [a ]])(逻辑非)等。 当 confidential shuffle 或 confidential sort 的输入是矩阵时,通过替换每一行来执行混洗,同时保持每一行的对应关系。 还有,解密密文的过程写成reveal([[a]])。
【0031】 上述安全计算可以使用各种现有技术来实现,因此省略说明。
【0032】 接下来,将描述在该实施例中执行的安全计算层次聚类。
【0033】 <安全计算层次集群>
在本实施例的安全计算层次聚类中,数据的个数和从数据个数中显而易见的值(例如聚类过程重复了多少次)是保密的。 具体而言,在对以下信息保密的情况下进行计算。
【0034】 ・数据特征
・数据之间、数据与集群之间或集群之间的距离
・合并了哪些数据点或集群
・每个集群中包含哪些数据?
・每个簇中包含的数据数
<安全计算层次集群的要点>
它显示了执行层次聚类的要点,同时隐藏了信息,例如哪个聚类中有多少数据以及包括哪些数据。
【0035】 (集群信息管理)
在本实施例的层次聚类中,需要保存“每个聚类中包括什么数据”的信息,并在每次合并数据点或聚类时更新该信息。 在本实施方式中,如图1所示,将数据ID与簇ID一一对应的表(簇ID表)C被表示为C。 id 管理使用 图4示出了对应于图1和图3的簇ID表C。 id 显示集群 ID 如何从左到右更新。
【0036】 ‖簇ID表C id 这是一个粗略的更新程序。
【0037】 1.作为cluster ID的初始值,从0开始按顺序为每个数据分配编号。 图4中的C id (t1)是分配后的簇ID表。
【0038】 2. 重写包含在簇中的数据点的簇ID,以便与新的组合(新的簇ID按顺序编号)。 图4中的C id (t2) 至 C id (t4) 显示重写后的簇 ID 表。
【0039】 3. 重复(2)直到所有数据成为一簇。 图4中的C id (t5) 显示重复后的簇 ID 表。
【0040】 (距离信息的管理)
在本实施例的层次聚类中,需要保存数据点间的距离,保存和更新簇间的距离。 在本实施方式的隐匿计算层次集群中,距离信息由以下三个表管理。
【0041】 ・所有数据之间的距离表(数据距离表)D data
・所有簇之间的距离表(簇间距离表)D clust
・连接簇之间的距离表(输出距离表)D out
图5表示各距离表的一例。
【0042】 〉数据距离表D data 是存储ID1和ID2数据之间距离信息的表。 例如,如果 ID1=A 且 ID2=B,则数据点 A 和 B 之间的距离在第三列中。
【0043】 ‖聚类距离表D clust 是存储ID1和ID2簇之间距离信息的表。 每个数据点在初始化时被认为是一个簇,因此 D data 和D clust 是同一张表
【0044】 ‖输出距离表D out 对应于层次聚类的输出,它最终创建基于此表的树状图。 输出距离表D out 初始化时是一张空表,但每次加入簇时,都会添加两个加入簇的ID和距离信息。
【0045】 〉数据距离表D data 丁 clust 和输出距离表D out 每次加入集群时都必须更新。 以下两个过程对于实现本实施例的安全计算层次聚类尤为重要。
【0046】 ・簇ID表C id 的更新
・簇间距离表D clust 的更新
<安全计算层次聚类的主要算法>
在图6的算法1中展示了安全计算层次聚类的主要算法之后,我们将展示每个函数的详细处理。
【0047】 第4行的函数calcDataDist(X)就是计算所有数据之间距离的过程。 距离的计算方法可以是任意的,本实施例采用式(1)所示的欧式距离。 欧几里德距离只能通过乘积的减法和求和来秘密计算。 式(1)中包含了平方根的计算,但是聚类只关注大小关系,省略平方根的计算并不改变结果,因此本实施例也省略了平方根的计算。
【0048】 ‖第5行的函数calcClustDist(X)是一个计算所有簇之间距离的过程,但是由于初始状态下每个数据点都被视为一个簇,所以数据距离表D data 和簇间距离表 D clust 是同一张表
【0049】 ‖函数getClosestClust(D clust ) 是最近的两个簇的 ID (cid 1 , 标识符 2 )和距离d,簇间距离表D clust 通过安全计算排序,然后得到第一个元素(距离最小的元素)。
【0050】 ‖第8行的函数updateCid为簇ID表C id 更新。 updateCid的计算过程如图2中的算法2所示。 簇ID表C id更新新加入集群的集群id。
【0051】 ‖第9行的updateDout函数只是在输出距离表Dout的末尾加上cid 1 , 标识符 2 ,d 刚刚添加。
【0052】 ‖第10行的函数updateClustDist是簇间距离表D clust 更新。 函数updateClustDist的计算过程大致由以下两个过程组成。
【0053】 [[D clust ]](参见图 8)。
【0054】 2. 计算新加入的簇与其他簇的距离[[D clust ]].
【0055】 ‖图8中的算法3显示了删除由于集群组合而不再需要的信息的计算过程。
【0056】 ‖在图 8 的算法 3 中,[[cid 1 ]],[[cid 2 由于不再需要有关]]的信息,我们正在处理以留下其他信息。 在图 8 的第 11 行中,[[ → C not ]] 被解码,但是由于第一行被提前打乱了,所以从解码结果中唯一能得到的信息就是要删除的行数。 由于每一步删除的行数从学习数据记录的数量上是显而易见的,所以没有问题。
【0057】 (簇间距离的计算方法)
接下来,我们将描述计算通过组合集群和其他集群创建的新集群之间的距离的过程。
【0058】 作为一个具体的例子,一共有四个数据点,图 9 给出了 ID = 1 和 ID = 2 的簇合并后的处理图像。
【0059】 将ID=1和ID=2的簇合并成一个新簇后,求新簇与其他簇(ID=0,ID=3)的距离。 为此,数据距离表 D data 需要带过来的数据同时满足以下两个条件。
【0060】 1.数据ID1包含在要合并的两个簇中。
【0061】 2.数据ID2不包含在要合并的两个簇中。
【0062】 待合并的两个簇中包含的数据为ID=1和ID=2,ID1=1或ID1=2。 未包含在待合并的两个簇中的数据有ID=0和ID=3,因此ID2=0或ID2=3。 如果ID1和ID2的组合可以提取(1,0)、(1,3)、(2,0)、(2,3)四个数据就足够了。 使用组平均法计算簇间距离时,(1,0)和(2,0)之间的距离的平均值为新簇(簇ID=4)与簇ID为簇的距离d = 0 04 ,(1,3)和(2,3)之间的距离的平均值是新簇(簇ID=4)与簇ID=3的簇之间的距离d 34 变得。
【0063】 〉数据距离表D data 因此,为了得到一个新簇与其他簇之间的距离,需要计算距离的总值和簇中包含的数据在加密状态下的数量,并将总值除以数量数据的。 因此,距离的总值使用groupBy Sum计算,聚类中包含的数据数量使用groupBy Count计算。 计算groupBy Sum和groupBy Count,Group-By操作的关键信息 → 有必要做好k。 具体的,如图所示的关键信息。 → 如果我们可以使 k,我们可以得到 Group-By 操作的预期结果。
【0064】 实际关键信息 → k的生成处理的流程如下所示,对应于该处理流程的具体例如图11所示。 图11得到的关键信息 → k是图10中需要的关键信息 → 匹配 k。 这个关键信息 → 使用k,可以将所有数据的距离表的第三列(distance)作为值属性,进行Group-By操作。 由于信息中不需要的部分位于ID = -1的顶部,因此如果您从Group-By计算结果中提取除顶部元素以外的元素,则只剩下需要的信息。
【0065】 1. 标志向量d 其中所有数据之间的距离表的ID 1 对于包含在待连接的两个簇中的数据为1,否则为0 1 创造
【0066】 2. 标志向量d 其中所有数据之间的距离表的ID2对于包含在待连接的两个簇中的数据为0,否则为1 2 创造
【0067】 3.标志向量d 1 和标志向量 d 2 d 的逻辑与 3 拿。
【0068】 4.连词d 3 从所有元素中减去 1 得到的向量 d 4 创造
【0069】 5.连词d 3 乘以数据ID2对应的簇ID,向量d 5 创造
【0070】 6.向量d 4 , 矢量 d 5 和关键信息 → 得到k。
【0071】 可见,上述过程1至6只需结合相等、逻辑运算和加减乘等轻量级运算即可实现。 结果,可以计算关于新集群的距离信息,同时加密所有信息,例如多少条数据包括在哪个集群中以及哪些集群被链接在一起。
【0072】 算法1的updateClustDist(更新所有簇间的距离表)是通过算法3删除旧的距离信息,并通过上述方法计算新簇的距离信息来实现的。
【0073】 通过在安全计算上实现层次聚类,可以在对以下所有信息保密的同时执行安全层次聚类。
【0074】 ・数据特征
・每个数据之间和集群之间的距离
・合并了哪些数据点或集群
・每个集群中包含哪些数据?
・每个簇中包含的数据数
<本实施例的要点>
‖以下三点使安全的计算层次聚类成为可能。
【0075】 ・簇ID表C id 管理每个集群中包含的数据点
・距离表D data , D clust 管理数据和集群之间的距离
・通过Group-By操作计算簇间的距离
下面将描述实现上述安全计算分层集群的集群设备。
【0076】 <第一实施例>
图12是根据第一实施例的集群设备的功能框图,图13示出了其处理流程。
【0077】 聚类装置包括初始化单元110、数据间距离计算单元120、数据间距离存储单元122、组合簇识别单元140、簇ID更新单元150、簇ID存储单元152、以及输出距离表,包括更新单元160、输出距离存储单元162、簇间距离更新单元170和簇间距离存储单元172。
【0078】 聚类器以加密数据[[X]]为输入,对数据进行保密聚类,输出距离表[[D] out ]] 是输出。
【0079】 例如,数据 [[X]] 是一个加密的 m×n 矩阵。 如上所述,当机密混洗或机密排序的输入是矩阵时,通过替换每一行同时保持每一行的对应来执行混洗。
【0080】集群设备例如是通过将特殊程序加载到具有中央处理单元(CPU:Central Processing Unit)、主存储器(RAM:Random Access Memory)等的已知或专用计算机中而构成的特殊设备。 . 集群设备例如在中央处理器的控制下执行各个进程。 输入到聚类装置的数据和在各处理中获得的数据被存储在例如主存储装置中,存储在主存储装置中的数据根据需要被读出到中央处理单元并用于其他目的。进行处理。 集群设备的各处理单元的至少一部分可以由集成电路等硬件构成。 集群装置中包含的各存储部例如可以由RAM(Random Access Memory)等主存储装置、关系数据库或键值存储等中间件构成。 但是,各存储部不一定必须设置在集群装置的内部,也可以是准备好的结构。
【0081】 下面将解释每个部分。
【0082】 <初始化单元110>
初始化单元110接收数据[[X]],为每一行数据从0开始依次分配编号(簇ID),并建立数据ID之间的对应关系,数据ID为每一行数据的标识,和簇 ID。簇 ID 表 [[C id ]]被初始化并存储在簇ID存储单元152中。 此外,变量 [[cid new ]] 到 [[cid new ]]=[[m]] 初始化并输出。
【0083】 初始化单元110使用输出距离表[[D out ]]被初始化为空表并存储在输出距离存储单元162中。
【0084】 <数据间距离计算单元120和数据间距离存储单元122>
数据间距离计算单元120接收数据[[X]]作为输入,计算所有数据之间的距离,并创建数据间距离表[[D] data ]]被获得(S 120)并且被存储在数据间距离存储单元122中。 距离计算方法如上所述,可以秘密计算。
【0085】 此外,由于每个数据点在初始状态下被视为一个簇,因此类别间距离表[[D clust ]]和数据距离表[[D data ]] 是同一张表。 因此,数据间距离计算单元120获得[[D clust ]](=[[D data ]])存储在簇间距离存储单元172中。
【0086】 <联合集群识别单元140>
组合簇识别单元140检索簇间距离表[[D clust ]] 和两个集群 ID ([[cid 1 ]],[[cid 2 ]])及其距离[[d]]被获取(S140)并输出。 例如,组合簇识别单元140使用距离作为关键字来保持簇间距离表[[D clust 排序后]],得到最前面的元素(距离最小的元素)。
【0087】 <集群ID更新单位150>
簇ID更新单元150使用两个簇ID([[cid 1 ]],[[cid 2 ]]) 和变量 [[cid new ]] 输入,聚类ID表[[C id ]] 和簇 ID 表 [[C id [[cid 1 ]],[[cid 2 ]] 到变量 [[cid new ]] (S150),更新后的簇ID表[[C id ]]存储在簇ID存储单元152中。 例如,簇 ID 表 [[C id ]] 更新。 请注意,变量 [[cid new ]] 在每次更新后递增。
【0088】 <输出距离表更新部160及输出距离存储部162>
‖输出距离表更新单元160更新两个簇ID([[cid 1 ]],[[cid 2 ]])(更新前)及其距离[[d]]作为输入,输出距离表[[D out ]] 和输出距离表 [[D out ]] 在 [[cid 1 ]],[[cid 2 ]],[[d]]给出输出距离表[[D out ]] 和更新后的输出距离表 [[D out ]]存储在输出距离存储单元162中。
【0089】 <簇间距离更新单元170和簇间距离存储单元172>
簇间距离更新单元170更新两个簇ID([[cid 1 ]],[[cid 2 ]])(更新前)被输入,簇间距离表[[D clust ]], 由于加入集群不再需要的信息被集群间距离表[[D clust ]] (S170-1)。 例如,按照上面算法 3 中的描述删除它。
【0090】 此外,簇间距离更新单元170更新数据间距离表[[D data ]],计算新加入的簇与其他簇的距离,计算簇间距离表[[D clust ]] 添加簇间距离表 [[D clust ]]被更新(S170-2)。 例如,新加入的簇与其他簇之间的距离是通过(簇间距离的计算方法)中描述的方法计算的。
【0091】 簇间距离更新单元170更新簇间距离表[[D clust ]]存储在簇间距离存储单元172中。
【0092】 [ [D out ]]被输出(S151中的否)。
【0093】 <效果>
通过上述配置,可以安全地执行层次聚类,同时保持计算过程和中间值的机密性。
【0094】 <修改>
在本实施例中,作为计算数据间距离的方法采用欧式距离,作为计算簇间距离的方法采用组平均法,但也可以采用其他方法。
【0095】 <其他修改>
本发明不限于上述实施例和修改。 例如,上述各种处理不仅可以根据描述按时间顺序执行,还可以根据执行处理的设备的处理能力或根据需要并行或单独执行。 另外,在不脱离本发明的主旨的范围内可以进行适当的变更。
【0096】 <程序和记录媒体>
可以通过将用于执行上述方法的每个步骤的程序加载到图2所示的计算机的存储单元2020中来执行上述各种过程。
【0097】 描述该过程的程序可以记录在计算机可读记录介质上。 可以使用任何计算机可读的记录介质,例如磁记录装置、光盘、磁光记录介质、半导体存储器等。
【0098】 另外,该程序的流通例如通过销售、转让、出借等记录了该程序的DVD、CD-ROM等可移动记录介质来进行。 此外,可以通过将程序存储在服务器计算机的存储设备中并经由网络将程序从服务器计算机传送到其他计算机来分发程序。
【0099】执行这样的程序的计算机例如首先将记录在便携式记录介质上的程序或从服务器计算机暂时传送来的程序存储在其自身的存储设备中。 然后,在执行处理时,该计算机读取存储在其自己的记录介质中的程序并根据读取的程序执行处理。 此外,作为该程序的另一种执行形式,计算机可以直接从便携式记录介质读取程序并根据该程序执行处理,并将该程序从服务器计算机传送到该计算机。每次,根据接收到的程序可以顺序执行。 另外,上述处理是由所谓的ASP(Application Service Provider)型服务执行的,它不将程序从服务器计算机传输到本计算机,仅通过执行指令和结果获取来实现处理功能。或许 需要说明的是,本实施例中的程序包括用于计算机处理的符合该程序的信息(不是对计算机的直接指令,但具有规定计算机处理的属性的数据等) .).
【0100】 另外,在本实施方式中,通过在计算机上执行规定的程序来构成装置,但这些处理内容的至少一部分也可以由硬件来实现。
