python-一种对集合进行分区以从子集中获取最小方差总和的策略
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python-一种对集合进行分区以从子集中获取最小方差总和的策略，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3984字，纯文字阅读大概需要6分钟。
内容图文
问题是：
我有一组数字,需要将其分为k个子集.我必须找到最佳的分区策略,以使每个子集的方差最小.没有子集可以为空
(方差是标准偏差的平方.)
k是大于0的整数.
近似值可以是1e 7
到目前为止,这是我的解决方案,适用于一些示例,但并非总是如此：
>按升序对样本(一组数字)进行排序.
>计算两个连续元素的距离.构造一个列表列表,子列表具有左元素和距离的索引(即[[idx,dist],[idx,dist] ……]).按距离降序对列表进行排序.
>使用我拥有的列表中的索引,从左到右获取索引以对升序排序的样本进行分区
Python代码：
class MinimumVariancePartition(object):
def minDev(self, mixedSamples, k):
# mixedSamples is a tuple, k is an integer.
samples_ascending = sorted(mixedSamples)
# Build a list of lists contains indices and distances.
idx_dist = []
for index in range(len(samples_ascending) - 1):
starting_idx = index
dist = abs(samples_ascending[index] - samples_ascending[index + 1])
idx_dist.append([starting_idx, dist])
sorted_idx_dist = sorted(idx_dist, key=lambda x: x[1], reverse=True)
# Get a list of indices to split the sample.
split_idx = []
for i in range(k - 1):
split_idx.append(sorted_idx_dist[i][0])
# Get a list of subsets.
partitions = []
if len(split_idx) == 0:
partitions.append(mixedSamples)
else:
split_idx = sorted(split_idx)
prev = 0
for idx in split_idx:
partitions.append(samples_ascending[prev:idx + 1])
prev = idx + 1
partitions.append(samples_ascending[prev:])
# Compute the sum of variances
result = 0
for partition in partitions:
variance = self.variance(partition)
result += variance
return result
def variance(self, partition):
# Compute variance of a subset
size = len(partition)
s = sum(partition)
mean = float(s) / size
variance = 0
for n in partition:
temp = round(n - mean, 14)**2 # use round() to avoid float number 'trick'
variance += temp
variance /= size
return variance
测试通过：
input: (3, 4, 7, 10), 1
output: 7.5
input: (1000,500,1,500), 3
output: 0.0
input: (42,234,10,1,123,545,436,453,74,85,34,999), 5
output: 1700.7397959183672
测试失败：
input: (197, 611, 410, 779, 203, 15, 727, 446, 992, 722, 439, 296, 201, 820, 416, 272, 89, 146, 687, 203, 598, 65, 865, 945, 446, 783, 581, 270, 960, 22, 970, 698, 456, 706, 14, 901, 371, 688, 914, 925, 551, 15, 326, 620, 842, 82, 594, 99, 827, 660), 21
expected output: 757.3225
actual output: 824.586388889
input: (359, 408, 124, 89, 26, 878, 677, 341, 166, 434, 886, 539, 227, 420, 655, 330, 835, 378, 763, 401, 883, 332, 215, 424, 365, 841, 113, 825, 777, 969, 970, 668, 602, 708, 874, 930, 423, 549, 236), 13
expected output: 1588.0486111111109
actual output: 2163.79166667
input: (706, 835, 160, 432, 148, 472, 26, 917, 736, 342, 442, 479, 95, 800, 956), 4
expected output: 8172.465
actual output: 11259.875
我在想解决方案中的问题可能在于查找分区索引步骤,但是仍然不知道为什么它不起作用.
解决方法:
这是行不通的,因为您的算法思想不正确(仅考虑两个相邻元素之间的距离并不一定总能得出最佳解决方案).
您可以改用动态编程：
1.对数组排序.
2.假设f(first_free,sets_count)是方差的最小和,如果first_free元素是尚未添加到任何集合中的第一个元素,并且完全已经创建了sets_count个集合.
3.基本情况为f(0,0)=0.它对应一个空前缀.
4.过渡看起来像这样：
for first_free = 0 ... n - 1:
for new_first_free = first_free + 1 ... n:
for sets_count = 0 ... k - 1:
f(new_first_free, sets_count + 1) = min(f(new_first_free, sets_count + 1),
f(first_free, sets_count) + variance of the subset [first_free, new_first_free - 1])
>答案f(n,k)(其中n是集合中元素的数量).
这是我的实现(可以优化,它只是一个草图,但是可以正常工作)：
a = [706, 835, 160, 432, 148, 472, 26, 917, 736, 342, 442, 479, 95, 800, 956]
k = 4
mem = dict()
INF = 1e10
def get_variance(partition):
size = len(partition)
s = sum(partition)
mean = float(s) / size
variance = 0
for n in partition:
temp = round(n - mean, 14) ** 2
variance += temp
variance /= size
return variance
def calc(pos, cnt):
if (pos, cnt) in mem.keys():
return mem[(pos, cnt)]
if pos == 0 and cnt >= 0:
return 0.0
if cnt < 0:
return INF
res = INF
for old_pos in range(0, pos):
res = min(res, calc(old_pos, cnt - 1) + get_variance(a[old_pos: pos]))
mem[(pos, cnt)] = res
return res
if __name__ == '__main__':
a.sort()
print(calc(len(a), k))
内容总结
以上是互联网集市为您收集整理的python-一种对集合进行分区以从子集中获取最小方差总和的策略全部内容，希望文章能够帮你解决python-一种对集合进行分区以从子集中获取最小方差总和的策略所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。