HDC
概述
K最近邻（kNN, k-NearestNeighbor）算法，也称最近邻算法，是一种根据目标节点的k个最近（最相似）节点的分类对目标节点进行分类的技术。kNN由T.M. Cover和P.E. Hart于1967年提出，此后成为最广泛使用的分类算法之一：
- T.M. Cover, P.E. Hart, Nearest Neighbor Pattern Classification (1967)
尽管名称中包含单词“邻居”，但 kNN 在计算相似性时并不明确考虑节点之间的边，它只关注节点的属性。
基本概念
相似度指标
嬴图的kNN算法计算目标节点与图中所有其他节点之间的余弦相似度，然后选择与目标节点相似度最高的k个节点。
选举分类
用节点的某个属性作为分类标签。找到与目标节点最近的k个节点后，将k个节点中出现次数最多的标签分配给目标节点。
如果出现次数最多的标签有多个，则选取其中相似度相最高的节点的标签。
示例图集
创建示例图集：
// 在空图集中逐行运行以下语句
create().node_schema("image")
create().node_property(@image,"d1",int32).node_property(@image,"d2",int32).node_property(@image,"d3",int32).node_property(@image,"d4",int32).node_property(@image,"type",string)
insert().into(@image).nodes([{_id:"image1", d1:50, d2:160, d3:20, d4:35}, {_id:"image2", d1:42, d2:90, d3:30, d4:90, type:"Gold"}, {_id:"image3", d1:24, d2:50, d3:55, d4:70, type:"Silver"}, {_id:"image4", d1:38, d2:20, d3:32, d4:70, type:"Gold"}, {_id:"image5", d1:98, d2:10, d3:15, d4:36, type:"Copper"}, {_id:"image6", d1:51, d2:56, d3:44, d4:30, type:"Copper"}])
创建HDC图集
将当前图集全部加载到HDC服务器hdc-server-1上，并命名为 hdc_knn：
CALL hdc.graph.create("hdc-server-1", "hdc_knn", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
})
hdc.graph.create("hdc_knn", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
}).to("hdc-server-1")
参数
算法名：knn
参数名 |
类型 |
规范 |
默认值 |
可选 |
描述 |
|---|---|---|---|---|---|
node_id |
_uuid |
/ | / | 否 | 通过_uuid指定目标节点 |
node_schema_property |
[]"<@schema.?><property>" |
/ | / | 否 | 用于计算余弦相似度的数值类型点属性；需包含至少两个属性。点的schema必须与目标节点相同 |
top_k |
Integer | >0 | / | 否 | 待选取的最近节点数 |
target_schema_property |
"<@schema.?><property>" |
/ | / | 否 | 作为分类标签的数值类型或字符串类型点属性。点的schema必须与目标节点相同 |
return_id_uuid |
String | uuid, id, both |
uuid |
是 | 在结果中使用_uuid、_id或同时使用两者来表示点 |
文件回写
CALL algo.knn.write("hdc_knn", {
params: {
return_id_uuid: "id",
// 指定image1为目标节点
node_id: 15420327323139833857,
node_schema_property: ["d1", "d2", "d3", "d4"],
top_k: 4,
target_schema_property: "@image.type"
},
return_params: {
file: {
filename: "knn.txt"
}
}
})
algo(knn).params({
projection: "hdc_knn",
return_id_uuid: "id",
// 指定image1为目标节点
node_id: 15420327323139833857,
node_schema_property: ["d1", "d2", "d3", "d4"],
top_k: 4,
target_schema_property: "@image.type"
}).write({
file: {
filename: "knn.txt"
}
})
结果：
Gold:2
top k(_id):
image2,0.85516
image6,0.841922
image3,0.705072
image4,0.538975
文件第一行代表k个最近点中出现最多的标签及其数量。从第三行起，显示与目标节点最相似的k个点及对应的相似度分数。
完整返回
CALL algo.knn("hdc_knn", {
params: {
return_id_uuid: "id",
// 指定image1为目标节点
node_id: 15420327323139833857,
node_schema_property: ["d1", "d2", "d3", "d4"],
top_k: 4,
target_schema_property: "@image.type"
},
return_params: {}
}) YIELD r
RETURN r
exec{
algo(knn).params({
return_id_uuid: "id",
// 指定image1为目标节点
node_id: 15420327323139833857,
node_schema_property: ["d1", "d2", "d3", "d4"],
top_k: 4,
target_schema_property: "@image.type"
}) as r
return r
} on hdc_knn
结果：
| _ids | similarity |
|---|---|
| image2 | 0.85516 |
| image6 | 0.841922 |
| image3 | 0.705072 |
| image4 | 0.538975 |
流式返回
CALL algo.knn("hdc_knn", {
params: {
return_id_uuid: "id",
// 指定image1为目标节点
node_id: 15420327323139833857,
node_schema_property: ["d1", "d2", "d3", "d4"],
top_k: 4,
target_schema_property: "type"
},
return_params: {
stream: {}
}
}) YIELD r
RETURN r
exec{
algo(knn).params({
return_id_uuid: "id",
// 指定image1为目标节点
node_id: 15420327323139833857,
node_schema_property: ["d1", "d2", "d3", "d4"],
top_k: 4,
target_schema_property: "type"
}).stream() as r
return r
} on hdc_knn
结果：
| _ids | similarity |
|---|---|
| image2 | 0.85516 |
| image6 | 0.841922 |
| image3 | 0.705072 |
| image4 | 0.538975 |