NNC 的整数规划
Integer Programming for NNC
我正在尝试使用 cvxpy 在 python 中实现最近邻分类器的整数规划。
简短介绍
给定一个包含 n 个颜色（红色或蓝色）点的数据集，我们想选择最少数量的候选点，s.t 对于每个不是候选点的点，其最接近的候选人具有相同的颜色。
我的流量
给定一组 n 个点（带颜色）定义一个指标向量 I (|I| = n),
I_i = 1 if and only if vertex i is chosen as a candidate
此外，我定义了另外两个向量，命名为A和B（|A| = |B| = n）如下：
A_i = the distance between v_i to it's closest candidate with the **same** color
B_i = the distance between v_i to it's closest candidate with a **different** color
因此，我有 n 约束条件是：
B_i > A_i
对于任何 i
我的目标是最小化向量的总和I（代表候选数）
我的问题
似乎向量 A、B 正在发生变化，因为它们受到 I 的影响，因为当一个候选者被选中时，它会影响它在 [=16= 中的条目] 影响 A 和 B 并且约束取决于这些向量..
有什么建议吗？
谢谢！
回顾一下：您想要找到属于给定训练集的最小示例集，以便生成的最近邻分类器在该训练集上达到完美的准确性。
我建议您将其表述如下。为每个示例 e 创建一个 0–1 变量 x(e)，指示是否选择了 e。对于每对具有不同标签的有序示例 e 和 e'，写一个约束
x(e′) ≤ ∑e′′∈C(e,e′) x(e′′)
其中 C(e, e') 是与 e 具有相同标签的示例集 e'' 使得 e'' 更接近 e 比 e' 更接近 e（包括 e'' = e） .这意味着，如果选择了 e'，那么它不是最接近 e 的选择示例。
我们还需要
∑e x(e) ≥ 1
禁止空集。最后，objective 是
minimize ∑e x(e).
我正在尝试使用 cvxpy 在 python 中实现最近邻分类器的整数规划。
简短介绍
给定一个包含 n 个颜色（红色或蓝色）点的数据集，我们想选择最少数量的候选点，s.t 对于每个不是候选点的点，其最接近的候选人具有相同的颜色。
我的流量
给定一组 n 个点（带颜色）定义一个指标向量 I (|I| = n),
I_i = 1 if and only if vertex i is chosen as a candidate
此外，我定义了另外两个向量，命名为A和B（|A| = |B| = n）如下：
A_i = the distance between v_i to it's closest candidate with the **same** color
B_i = the distance between v_i to it's closest candidate with a **different** color
因此，我有 n 约束条件是：
B_i > A_i
对于任何 i
我的目标是最小化向量的总和I（代表候选数）
我的问题
似乎向量 A、B 正在发生变化，因为它们受到 I 的影响，因为当一个候选者被选中时，它会影响它在 [=16= 中的条目] 影响 A 和 B 并且约束取决于这些向量..
有什么建议吗？
谢谢！
回顾一下：您想要找到属于给定训练集的最小示例集，以便生成的最近邻分类器在该训练集上达到完美的准确性。
我建议您将其表述如下。为每个示例 e 创建一个 0–1 变量 x(e)，指示是否选择了 e。对于每对具有不同标签的有序示例 e 和 e'，写一个约束
x(e′) ≤ ∑e′′∈C(e,e′) x(e′′)
其中 C(e, e') 是与 e 具有相同标签的示例集 e'' 使得 e'' 更接近 e 比 e' 更接近 e（包括 e'' = e） .这意味着，如果选择了 e'，那么它不是最接近 e 的选择示例。
我们还需要
∑e x(e) ≥ 1
禁止空集。最后，objective 是
minimize ∑e x(e).