Clustering apparatus, clustering method, and program
Provided is a clustering apparatus capable of securely performing hierarchical clustering while concealing all of a calculation process and values in the middle. A clustering apparatus includes: a cluster ID update unit that combines two clusters closest to each other and updates a cluster ID of a cluster ID table in which a data ID and a cluster ID are associated with each other on a one-to-one basis; and an inter-cluster distance update unit that executes deletion processing of deleting information corresponding to clusters to be combined from an inter-cluster distance table that is a table of distances between all clusters and addition processing of adding a distance between a newly combined cluster and another cluster to the inter-cluster distance table, and updates the inter-cluster distance table, in which information of the cluster ID table and the inter-cluster distance table is encrypted, and processing in the cluster ID update unit and the addition processing in the inter-cluster distance update unit are performed by using information encrypted without being decrypted.
1 . A clustering apparatus comprising:
a processor and a memory to store instructions, the instructions are executed by the processor to perform:
combine two clusters closest to each other and updates a cluster ID of a cluster ID table in which a data ID and a cluster ID are associated with each other on a one-to-one basis; and
execute deletion processing of deleting information corresponding to clusters to be combined from an inter-cluster distance table that is a table of distances between all clusters and addition processing of adding a distance between a newly combined cluster and another cluster to the inter-cluster distance table, and update the inter-cluster distance table, wherein
information of the cluster ID table and the inter-cluster distance table is encrypted, and
processing in updating the cluster ID and the addition processing in processing in updating the inter-cluster distance are performed by using information encrypted without being decrypted.
2 . The clustering apparatus according to claim 1 , further comprising:
the processor configured to;
add two cluster IDs of clusters to be combined and a distance between the clusters to an output distance table that is a table of distances between clusters combined, and update the output distance table, wherein
information of the output distance table is encrypted, and
processing in updating the output distance table is performed by using information encrypted without being decrypted.
3 . The clustering apparatus according to claim 1 , wherein
the processing in updating inter-cluster distance, the processor uses an inter-data distance table that is a table of distances between all data, and two cluster IDs of clusters to be combined, to generate key information is used for extracting necessary information from the inter-data distance table wherein performing the addition processing in processing updating the inter-cluster distance, and calculating, to the inter-cluster distance table, a distance between a newly combined cluster and another cluster by using the key information and the inter-data distance table.
4 . The clustering apparatus according to claim 1 , wherein
processing in updating the inter-cluster distance, the processor calculates a distance between a newly combined cluster and another cluster on a basis of Lance-Williams updating formula:
d
(
C
1
,
C
2
)
=
n
1
a
×
d
(
C
1
a
,
C
2
)
+
n
1
b
×
d
(
C
1
b
,
C
2
)
n
1
a
+
n
1
b
on a basis of a number of data n 1a and n 1b included in respective two clusters (C 1a , C 1b ) to be combined, a distance d(C 1a , C 2 ) between the cluster C 1a that is one of the clusters to be combined and a cluster C 2 not combined, and a distance d(C 1b , C 2 ) between the cluster C 1b that is another of the clusters to be combined and the cluster C 2 not combined.
5 . A clustering method performed by a clustering apparatus, wherein a processor and a memory to store instructions, the instructions are executed by the processor to perform the clustering method comprising:
a cluster ID update step of combining two clusters closest to each other and updating a cluster ID of a cluster ID table in which a data ID and a cluster ID are associated with each other on a one-to-one basis; and
an inter-cluster distance update step of executing deletion processing of deleting information corresponding to clusters to be combined from an inter-cluster distance table that is a table of distances between all clusters and addition processing of adding a distance between a newly combined cluster and another cluster to the inter-cluster distance table, and updating the inter-cluster distance table, wherein
information of the cluster ID table and the inter-cluster distance table is encrypted, and
processing in the cluster ID update step and the addition processing in the inter-cluster distance update step are performed by using information encrypted without being decrypted.
6 . The clustering method according to claim 5 , further comprising:
an output distance table update step of adding two cluster IDs of clusters to be combined and a distance between the clusters to an output distance table that is a table of distances between clusters combined, and updating the output distance table, wherein
information of the output distance table is encrypted, and
processing in the output distance table update step is performed by using information encrypted without being decrypted.
7 . The clustering method according to claim 5 , wherein
the inter-cluster distance update step uses an inter-data distance table that is a table of distances between all data, and two cluster IDs of clusters to be combined, to generate key information is used for extracting necessary information from the inter-data distance table wherein performing the addition processing in the inter-cluster distance update step, and calculating, to the inter-cluster distance table, a distance between a newly combined cluster and another cluster by using the key information and the inter-data distance table.
8 . The clustering method according to claim 5 , wherein
the inter-cluster distance update step calculates a distance between a newly combined cluster and another cluster on a basis of Lance-Williams updating formula:
d
(
C
1
,
C
2
)
=
n
1
a
×
d
(
C
1
a
,
C
2
)
+
n
1
b
×
d
(
C
1
b
,
C
2
)
n
1
a
+
n
1
b
on a basis of a number of data n 1a and n 1b included in respective two clusters (C 1a , C 1b ) to be combined, a distance d(C 1a , C 2 ) between the cluster C 1a that is one of the clusters to be combined and a cluster C 2 not combined, and a distance d(C 1b , C 2 ) between the cluster C 1b that is another of the clusters to be combined and the cluster C 2 not combined.
9 . A non-transitory computer-readable storage medium storing a program for causing a computer to function as the clustering apparatus according to claim 1 .