半自动教区记录单词标准化与ALEH描述逻辑下的概念相似度计算

### 半自动教区记录单词标准化与ALEH描述逻辑下的概念相似度计算 #### 半自动教区记录单词标准化 在处理单词匹配时，会出现这样的情况：每个单词都可能与多个其他单词匹配，形成一系列匹配的单词。但有时会出现两对单词 (s1, s2) 和 (s2, s3) 被分类为匹配，而 (s1, s3) 却被分类为不匹配的情况。这种情况可以通过传递闭包来解决，即将 (s1, s3) 也分类为匹配。 #### 实现 这是一个众包项目的一部分，目标是创建一个数据库和图形用户界面（GUI），让志愿者转录教区书籍的记录，并为聚类的单词提供标准化变体。标准化过程是自动进行的，标准化单词会自动选择为聚类中最常见的单词。不过，由于真正的标准单词可能不同，每个单词都可以手动更改其标准单词。更改或输入标准化单词有两种方式： 1. 一次性更改所有相同单词的标准单词。 2. 在输入新记录后，为其中的每个单词设置标准单词。 DEMoS 网络的总体方案如下： ```mermaid graph LR classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; A(Application for word clustering):::process --> B(Database):::process A --> C(Web application DEMoS):::process C --> D(no. of most similar cluster (cluster_id)):::process C --> E(word):::process C --> F(standardised variants for entered word):::process C --> G(no. of cluster (cluster_id)):::process C --> H(standardised variants for cluster):::process C --> I(Suggestion of proposed standardised variants based on no. of cluster):::process C --> J(Explicit cluster search most similar to entered word):::process ``` 该网络使用 PHP（Nette 框架）创建，数据存储在 MySQL 数据库中，分类程序用 Python 3 编写。使用了 NumPy 库处理矩阵，fuzzy 用于 NYSIIS，pyphonetics 用于 Soundex，metaphone 用于 Double-Metaphone，textdistance 用于编辑距离计算。由于计算非常耗时且易于并行化，因此使用了多进程进行并行处理。 #### 并行化 单词对的比较是程序中最耗时的部分，需要计算每对单词的相似度并存储在数组中。对于约 3100 个单词，这一过程大约需要 24 分钟。但由于相似度计算相互独立，可以使用并行化，将所需时间减少到 4 分钟。 #### 测试 使用 17 至 19 世纪的真实教区记录数据进行测试，这些记录使用捷克语、拉丁语和德语书写。单词分为五种类型：名字、姓氏、职业、村庄和人际关系。为这些记录创建了真实标签，即知道每个单词属于哪个聚类。针对每种类型，创建了阈值、语音编码、编辑距离和传递闭包的各种组合。 编辑距离计算使用了 Damerau - Levenshtein、Q - gram、Jaro - Winkler 和最长公共子串，未使用基本的 Levenshtein 方法，因为其结果与扩展方法相似。语音编码测试了 Soundex、Double - Metaphone 和 NYSIIS，还测试了不使用语音编码的变体。对于每种类型的单词，测试了 20 种不同阈值、有和没有传递闭包的所有参数组合，每种单词类型共进行 4 * 4 * 20 * 2 = 640 次测试。 为了衡量算法的质量，使用了精度、召回率和 F - 度量。计算公式如下： - 精度：$precision = \frac{TP}{TP + FP}$ - 召回率：$recall = \frac{TP}{TP + FN}$ - F - 度量：$F - measure = \frac{2 * precision * recall}{precision + recall}$ 其中，TP 表示真阳性，FP 表示假阳性，FN 表示假阴性。 测试结果表明，不同编辑距离和语音编码组合的表现不同。Q - gram 的结果总是最差，Jaro - Winkler 距离的结果在最高阈值处，最长公共子串和 Damerau - Levenshtein 的结果在中间。使用传递闭包时，最大 F - 度量通常在较高阈值处出现，且值更大。除姓氏外，F - 度量值在 0.93 至 0.96 之间，姓氏的 F - 度量值仅为 0.85，可能是因为测试单词数量最多，接近 2500 个，而其他类型的单词数量少于 1000 个（名字除外，有 1570 个）。 以下是最佳 F - 度量值及其参数的概述： | 单词类型 | 编辑距离 | 语音编码 | 传递闭包 | 阈值 | F - 度量 | | ---- | ---- | ---- | ---- | ---- | ---- | | 名字 | LCS | S | 是 | 0.82 | 0.95 | | 姓氏 | LCS | S | 是 | 0.825 | 0.85 | | 职业 | LCS | DM | 是 | 0.85 | 0.96 | | 村庄 | JW | N | 是 | 0.9 | 0.93 | | 人际关系 | JW | N | 是 | 0.9 | 0.96 | #### ALEH 描述逻辑下的概念相似度计算 #### 引言 概念相似度指的是人类对一对概念相似度程度的感知，这种感知在多个领域都有应用，如生物医学本体应用中发现基因的功能相似性，以及类比推理等。然而，许多概念相似度的计算方法没有考虑本体中定义的逻辑关系，也无法根据主观因素（即主体的偏好）进行个性化调整。本文介绍了一种针对描述逻辑 ALEH 的概念相似度计算方法，该方法在主体偏好下从结构上计算两个概念描述之间的相似度，并基于本体中的逻辑定义进行分析。还通过水稻病害检测的例子说明了其适用性。 #### 预备知识：描述逻辑 ALEH 在描述逻辑（DLs）中，概念描述通过一组构造函数、一组原子概念 NC 和原子角色 NR 归纳定义。对于 DL ALEH，概念 C 和 D 正式定义为： $C, D ::=⊤|⊥| A | ¬A | C ⊓D | ∃r.C | ∀r.C$ 其中，$A∈NC$，$r∈NR$，¬ 表示原子否定，⊤ 表示顶级概念，⊥ 表示底部概念。 术语表或 TBox T 是一个有限集合，形式包括概念包含（$C ⊑D$）、概念相等（$C ≡D$）和角色层次（$r ⊑s$）。如果 TBox 中每个概念名最多有一个概念定义且不包含循环依赖，则称为可展开的。当 TBox T 可展开时，任何 $A ⊑C$ 都可以通过规则 $A ⊑C ⇒A ≡X ⊓C$ 转换为语义等价的形式，其中 X 是一个新的原子概念。 将原子概念分为名字符号（NT）和基本符号（BT），分别表示出现在 TBox 语句左侧和右侧的原子概念。任何 ALEH 概念描述 C 都可以完全展开为特定形式，相关集合分别用 PC、EC 和 AC 表示。同时，定义了角色的超角色集合 R∃r 和子角色集合 R∀r。概念在展开后需要进行规范化。 非正式地，任何 ALEH 概念 C 都可以递归地转换为对应的 ALEH 描述树 GC，树的根节点 v0 具有 PC 作为标签，有 m 条标记为 R∃rj 的 ∃ - 边指向顶点 vj，n 条标记为 R∀sk 的 ∀ - 边指向顶点 vk，子树以相同方式递归定义。 #### 在主体偏好下计算 ALEH 概念描述之间的相似度 假设 TBox 是可展开的，因此可以完全展开概念并在决策过程中忽略 TBox。ALEH 概念相似度的计算方法可以通过计算两个对应描述树的结构匹配程度来实现。具体来说，如果两个概念描述的对应描述树完全匹配，则它们被认为是最大相似的。但当情况并非如此时，相似度水平会根据主观因素（如主体的偏好）而变化。 为了将主观性纳入概念相似度计算，扩展了之前为 ELH 概念描述开发的偏好配置文件概念。具体定义如下： - **原始概念重要性**：设 BT 和 NR 分别是基本符号集合和原子角色集合，原始概念重要性是一个部分函数 $ic : BT →[0, 2]$。对于任何 $A ∈BT$，$ic(A) := 1$ 表示 A 的重要性为正常，$ic(A) > 1$ 表示 A 具有更高的重要性，$ic(A) < 1$ 表示 A 具有较低的重要性，$ic(A) := 0$ 表示 A 对主体没有重要性。同样的方式也适用于角色重要性函数 $ir : NR →[0, 2]$。此外，函数 ic 还会以适当的方式递归扩展以处理基本符号的原子否定，即 $ic(¬A) := ic(A)$。 - **原始概念相似度**：对于任何 $A, B ∈BT$，原始概念相似度是一个部分函数 $sc : BT × BT →[0, 1]$，满足 $sc(A, B) = sc(B, A)$ 且 $sc(A, A) := 1$。 - **原始角色相似度**：对于任何 $r, s ∈NR$，原始角色相似度是一个部分函数 $sr : NR × NR →[0, 1]$，满足 $sr(r, s) = sr(s, r)$ 且 $sr(r, r) := 1$。 ### 半自动教区记录单词标准化与ALEH描述逻辑下的概念相似度计算（续） #### 不同参数对单词标准化测试结果的影响分析 通过上述测试，我们可以进一步分析不同参数组合对五类单词标准化效果的具体影响。 - **编辑距离算法的影响**：从测试结果来看，最长公共子串（LCS）和 Jaro - Winkler（JW）在编辑距离算法中表现最佳。这两种算法在与三种语音编码算法结合时都能取得较好的效果。例如，在名字和姓氏的处理上，LCS 与 Soundex 结合能达到较高的 F - 度量值；在职业的处理上，LCS 与 Double - Metaphone 结合表现出色；而在村庄和人际关系的处理上，JW 与 NYSIIS 结合效果良好。 - **语音编码算法的影响**：不同的语音编码算法对不同类型的单词有着不同的适用性。Soundex 算法在处理名字和姓氏时效果最佳；Damerau - Levenshtein 在处理职业时表现出色；NYSIIS 则在处理村庄和人际关系时效果较好。 - **阈值的影响**：所有测试的阈值都相对较高，范围在 0.82 到 0.9 之间。较高的阈值意味着算法对单词匹配的要求更为严格，能够减少误匹配的情况，但也可能会遗漏一些潜在的匹配。 以下是不同参数组合下各类单词的 F - 度量值表格，进一步展示了参数对结果的影响： | 单词类型 | 编辑距离 | 语音编码 | 传递闭包 | 阈值 | F - 度量 | | ---- | ---- | ---- | ---- | ---- | ---- | | 名字 | LCS | S | 是 | 0.82 | 0.95 | | 姓氏 | LCS | S | 是 | 0.825 | 0.85 | | 职业 | LCS | DM | 是 | 0.85 | 0.96 | | 村庄 | JW | N | 是 | 0.9 | 0.93 | | 人际关系 | JW | N | 是 | 0.9 | 0.96 | #### 基于测试结果的单词标准化流程优化 根据测试结果，我们可以对单词标准化的流程进行优化，以提高处理效率和准确性。具体流程如下： 1. **数据预处理**：对原始的教区记录数据进行清洗和整理，去除噪声和无效信息。 2. **参数选择**：根据单词的类型，选择合适的编辑距离算法、语音编码算法和阈值。例如，对于名字和姓氏，优先选择 LCS 和 Soundex 算法，阈值设置为 0.82 左右；对于职业，选择 LCS 和 Double - Metaphone 算法，阈值设置为 0.85 左右。 3. **相似度计算**：使用选定的算法计算单词之间的相似度，并将结果存储在数组中。由于相似度计算是独立的，可以使用并行化处理来提高计算效率。 4. **传递闭包处理**：对计算得到的相似度结果进行传递闭包处理，解决可能出现的匹配不一致问题。 5. **标准化处理**：根据聚类结果，自动选择标准化单词。同时，提供手动更改标准化单词的功能，以满足不同的需求。 以下是该优化流程的 mermaid 流程图： ```mermaid graph LR classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; A(数据预处理):::process --> B(参数选择):::process B --> C(相似度计算):::process C --> D(传递闭包处理):::process D --> E(标准化处理):::process ``` #### ALEH 概念相似度计算在实际应用中的拓展 ALEH 描述逻辑下的概念相似度计算方法在水稻病害检测的例子中得到了验证，展示了其在实际应用中的潜力。我们可以进一步拓展该方法在其他领域的应用，例如： - **医学诊断**：在医学领域，医生可以根据患者的症状描述，使用 ALEH 概念相似度计算方法来查询可能的疾病。通过将患者的症状与医学本体中的疾病描述进行相似度匹配，能够快速准确地做出诊断。 - **信息检索**：在信息检索系统中，可以利用 ALEH 概念相似度计算方法来提高检索结果的准确性。用户输入的查询词可以与文档中的概念进行相似度匹配，从而筛选出最相关的文档。 #### 主体偏好对 ALEH 概念相似度计算的影响深入探讨 主体偏好是 ALEH 概念相似度计算中的一个重要因素。不同的主体可能对不同的概念和角色有不同的重要性评估和相似度判断。例如，在水稻病害检测中，农民可能更关注症状的特征，而对颜色的关注度较低。因此，在计算概念相似度时，需要根据主体的偏好来调整原始概念重要性和原始角色相似度。 以下是主体偏好影响 ALEH 概念相似度计算的具体步骤： 1. **偏好收集**：通过问卷调查、用户反馈等方式，收集主体对不同概念和角色的偏好信息。 2. **偏好量化**：将收集到的偏好信息转化为具体的数值，即原始概念重要性和原始角色相似度。 3. **相似度计算**：在计算概念相似度时，将主体的偏好信息纳入计算过程，以得到更符合主体需求的结果。 通过以上步骤，可以使 ALEH 概念相似度计算方法更加个性化和准确，满足不同主体的需求。 综上所述，半自动教区记录单词标准化和 ALEH 描述逻辑下的概念相似度计算方法在实际应用中具有重要的价值。通过对参数的优化和主体偏好的考虑，可以进一步提高这两种方法的准确性和适用性，为相关领域的研究和应用提供有力的支持。