Changeset 10
- Timestamp:
- 07/13/15 19:16:30 (9 years ago)
- Location:
- trunk
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/bin/analyze_packets
r5 r10 44 44 45 45 start = time.time() 46 import cProfile 47 #cProfile.run('num_probes = analyzeProbes(db)') 46 48 num_probes = analyzeProbes(db) 47 49 end = time.time() -
trunk/bin/graph
r6 r10 10 10 import json 11 11 12 import numpy 12 13 import matplotlib.mlab as mlab 13 14 import matplotlib.pyplot as plt … … 85 86 86 87 print('packet_rtt diff median: %f' % statistics.median(diffs)) 87 print('packet_rtt diff midhinge: %f' % mid hinge(diffs))88 print('packet_rtt diff midhinge: %f' % midsummary(diffs)) 88 89 print('packet_rtt diff trimean: %f' % trimean(diffs)) 90 print('packet_rtt diff quadsummary: %f' % quadsummary(diffs)) 91 print('packet_rtt diff ubersummary: %f' % ubersummary(diffs)) 89 92 print('packet_rtt diff MAD: %f' % mad(diffs)) 90 93 print('reported diff trimean: %f' % trimean(reported_diffs)) 94 print('reported diff quadsummary: %f' % quadsummary(reported_diffs)) 95 print('reported diff ubersummary: %f' % ubersummary(reported_diffs)) 91 96 print('reported diff MAD: %f' % mad(reported_diffs)) 97 98 import cProfile 99 kresults = kfilter({},diffs) 100 #print('packet_rtt diff kfilter: ', numpy.mean(kresults['est']), kresults['var']) 101 print('packet_rtt diff kfilter: ', kresults['est'][-1], kresults['var'][-1]) 102 kresults = kfilter({},reported_diffs) 103 #print('reported diff kfilter: ', numpy.mean(kresults['est']), kresults['var'][-1]) 104 print('reported diff kfilter: ', kresults['est'][-1], kresults['var'][-1]) 92 105 93 106 -
trunk/bin/train
r9 r10 26 26 27 27 from nanownlib import * 28 from nanownlib.stats import * 29 from nanownlib.parallel import WorkerThreads 28 30 import nanownlib.storage 29 from nanownlib.stats import boxTest,multiBoxTest,subsample,bootstrap,bootstrap2,trimean,midhinge,midhingeTest,samples2Distributions,samples2MeanDiffs 30 from nanownlib.parallel import WorkerThreads 31 31 32 32 33 … … 35 36 #parser.add_argument('-c', dest='cases', type=str, default='{"short":10000,"long":1010000}', 36 37 # help='JSON representation of echo timing cases. Default: {"short":10000,"long":1010000}') 38 parser.add_argument('--retrain', action='append', default=[], help='Force a classifier to be retrained. May be specified multiple times.') 39 parser.add_argument('--retest', action='append', default=[], help='Force a classifier to be retested. May be specified multiple times.') 37 40 parser.add_argument('session_data', default=None, 38 41 help='Database file storing session information') 39 42 options = parser.parse_args() 40 43 41 42 43 def trainBoxTest(db, unusual_case, greater, subseries_size): 44 44 45 def trainBoxTest(db, unusual_case, greater, num_observations): 46 db.resetOffsets() 47 45 48 def trainAux(low,high,num_trials): 46 49 estimator = functools.partial(multiBoxTest, {'low':low, 'high':high}, greater) 47 estimates = bootstrap3(estimator, db, 'train', unusual_case, subseries_size, num_trials)48 null_estimates = bootstrap3(estimator, db, 'train_null', unusual_case, subseries_size, num_trials)50 estimates = bootstrap3(estimator, db, 'train', unusual_case, num_observations, num_trials) 51 null_estimates = bootstrap3(estimator, db, 'train_null', unusual_case, num_observations, num_trials) 49 52 50 53 bad_estimates = len([e for e in estimates if e != 1]) … … 116 119 117 120 num_trials = 500 118 widths = [good_width+(x/100.0) for x in range(- 60,75,5) if good_width+(x/100.0) > 0.0]121 widths = [good_width+(x/100.0) for x in range(-70,75,5) if good_width+(x/100.0) > 0.0] 119 122 performance = [] 120 123 for width in widths: … … 124 127 job_id,errors = wt.resultq.get() 125 128 fp,fn = errors 126 performance.append(((fp+fn)/2.0, job_id, fn, fp)) 129 #performance.append(((fp+fn)/2.0, job_id, fn, fp)) 130 performance.append((abs(fp-fn), job_id, fn, fp)) 127 131 performance.sort() 128 132 #pprint.pprint(performance) … … 133 137 wt.stop() 134 138 params = json.dumps({"low":best_low,"high":best_low+best_width}) 135 return {'algorithm':"boxtest", 139 return {'trial_type':"train", 140 'num_observations':num_observations, 141 'num_trials':num_trials, 136 142 'params':params, 137 'sample_size':subseries_size,138 'num_trials':num_trials,139 'trial_type':"train",140 143 'false_positives':performance[0][3], 141 144 'false_negatives':performance[0][2]} 142 145 143 146 144 def trainMidhinge(db, unusual_case, greater, subseries_size): 145 147 def trainSummary(summaryFunc, db, unusual_case, greater, num_observations): 148 db.resetOffsets() 149 stest = functools.partial(summaryTest, summaryFunc) 150 146 151 def trainAux(distance, threshold, num_trials): 147 estimator = functools.partial( midhingeTest, {'distance':distance,'threshold':threshold}, greater)148 estimates = bootstrap3(estimator, db, 'train', unusual_case, subseries_size, num_trials)149 null_estimates = bootstrap3(estimator, db, 'train_null', unusual_case, subseries_size, num_trials)152 estimator = functools.partial(stest, {'distance':distance,'threshold':threshold}, greater) 153 estimates = bootstrap3(estimator, db, 'train', unusual_case, num_observations, num_trials) 154 null_estimates = bootstrap3(estimator, db, 'train_null', unusual_case, num_observations, num_trials) 150 155 151 156 bad_estimates = len([e for e in estimates if e != 1]) … … 158 163 #determine expected delta based on differences 159 164 mean_diffs = [s['unusual_case']-s['other_cases'] for s in db.subseries('train', unusual_case)] 160 threshold = trimean(mean_diffs)/2.0165 threshold = summaryFunc(mean_diffs)/2.0 161 166 #print("init_threshold:", threshold) 162 167 … … 181 186 num_trials = 500 182 187 performance = [] 183 for t in range( 50,154,4):188 for t in range(80,122,2): 184 189 wt.addJob(threshold*(t/100.0), (good_distance,threshold*(t/100.0),num_trials)) 185 190 wt.wait() … … 187 192 job_id,errors = wt.resultq.get() 188 193 fp,fn = errors 189 performance.append(((fp+fn)/2.0, job_id, fn, fp)) 194 #performance.append(((fp+fn)/2.0, job_id, fn, fp)) 195 performance.append((abs(fp-fn), job_id, fn, fp)) 190 196 performance.sort() 191 197 #pprint.pprint(performance) … … 217 223 job_id,errors = wt.resultq.get() 218 224 fp,fn = errors 219 performance.append(((fp+fn)/2.0, job_id, fn, fp)) 225 #performance.append(((fp+fn)/2.0, job_id, fn, fp)) 226 performance.append((abs(fp-fn), job_id, fn, fp)) 220 227 performance.sort() 221 228 #pprint.pprint(performance) … … 225 232 wt.stop() 226 233 params = json.dumps({'distance':best_distance,'threshold':best_threshold}) 227 return {'algorithm':"midhinge", 234 return {'trial_type':"train", 235 'num_observations':num_observations, 236 'num_trials':num_trials, 228 237 'params':params, 229 'sample_size':subseries_size,230 'num_trials':num_trials,231 'trial_type':"train",232 238 'false_positives':performance[0][3], 233 239 'false_negatives':performance[0][2]} 234 240 235 241 236 classifiers = {'boxtest':{'train':trainBoxTest, 'test':multiBoxTest}, 237 'midhinge':{'train':trainMidhinge, 'test':midhinge}} 242 def trainKalman(db, unusual_case, greater, num_observations): 243 db.resetOffsets() 244 245 def trainAux(params, num_trials): 246 estimator = functools.partial(kalmanTest, params, greater) 247 estimates = bootstrap3(estimator, db, 'train', unusual_case, num_observations, num_trials) 248 null_estimates = bootstrap3(estimator, db, 'train_null', unusual_case, num_observations, num_trials) 249 250 bad_estimates = len([e for e in estimates if e != 1]) 251 bad_null_estimates = len([e for e in null_estimates if e != 0]) 252 253 false_negatives = 100.0*bad_estimates/num_trials 254 false_positives = 100.0*bad_null_estimates/num_trials 255 return false_positives,false_negatives 256 257 mean_diffs = [s['unusual_case']-s['other_cases'] for s in db.subseries('train', unusual_case)] 258 good_threshold = kfilter({},mean_diffs)['est'][-1]/2.0 259 260 wt = WorkerThreads(2, trainAux) 261 num_trials = 200 262 performance = [] 263 for t in range(90,111): 264 params = {'threshold':good_threshold*(t/100.0)} 265 wt.addJob(good_threshold*(t/100.0), (params,num_trials)) 266 wt.wait() 267 while not wt.resultq.empty(): 268 job_id,errors = wt.resultq.get() 269 fp,fn = errors 270 #performance.append(((fp+fn)/2.0, job_id, fn, fp)) 271 performance.append((abs(fp-fn), job_id, fn, fp)) 272 performance.sort() 273 #pprint.pprint(performance) 274 best_threshold = performance[0][1] 275 #print("best_threshold:", best_threshold) 276 params = {'threshold':best_threshold} 277 278 wt.stop() 279 280 return {'trial_type':"train", 281 'num_observations':num_observations, 282 'num_trials':num_trials, 283 'params':json.dumps(params), 284 'false_positives':performance[0][3], 285 'false_negatives':performance[0][2]} 286 287 288 #determine expected delta based on differences 289 classifiers = {'boxtest':{'train':trainBoxTest, 'test':multiBoxTest, 'train_results':[]}, 290 'midsummary':{'train':functools.partial(trainSummary, midsummary), 'test':midsummaryTest, 'train_results':[]}, 291 #'ubersummary':{'train':functools.partial(trainSummary, ubersummary), 'test':ubersummaryTest, 'train_results':[]}, 292 'quadsummary':{'train':functools.partial(trainSummary, quadsummary), 'test':quadsummaryTest, 'train_results':[]}, 293 'kalman':{'train':trainKalman, 'test':kalmanTest, 'train_results':[]}, 294 #'_trimean':{'train':None, 'test':trimeanTest, 'train_results':[]}, 295 } 238 296 239 297 … … 242 300 import cProfile 243 301 244 def trainClassifier(db, unusual_case, greater, trainer): 302 def trainClassifier(db, unusual_case, greater, classifier, retrain=False): 303 if retrain: 304 print("Dropping stored training results...") 305 db.deleteClassifierResults(classifier, 'train') 306 307 trainer = classifiers[classifier]['train'] 245 308 threshold = 5.0 # in percent 246 size = 4000 309 num_obs = 1000 310 max_obs = int(db.populationSize('train')/5) 247 311 result = None 248 while size < db.populationSize('train')/5: 249 size = min(size*2, int(db.populationSize('train')/5)) 250 result = trainer(db,unusual_case,greater,size) 312 while num_obs < max_obs: 313 num_obs = min(int(num_obs*1.5), max_obs) 314 result = db.fetchClassifierResult(classifier, 'train', num_obs) 315 if result != None: 316 train_time = "(stored)" 317 else: 318 start = time.time() 319 result = trainer(db,unusual_case,greater,num_obs) 320 result['classifier'] = classifier 321 train_time = "%f" % (time.time()-start) 322 251 323 error = statistics.mean([result['false_positives'],result['false_negatives']]) 252 print("subseries size: %d | error: %f | false_positives: %f | false_negatives: %f" 253 % (size,error,result['false_positives'],result['false_negatives'])) 324 print("number of observations: %d | error: %f | false_positives: %f | false_negatives: %f | train time: %s | params: %s" 325 % (num_obs, error, result['false_positives'],result['false_negatives'], train_time, result['params'])) 326 db.addClassifierResults(result) 327 classifiers[classifier]['train_results'].append(result) 328 254 329 if error < threshold: 255 330 break 256 if result != None:257 db.addClassifierResults(result)258 331 259 332 return result 333 334 335 336 def testClassifier(db, unusual_case, greater, classifier, retest=False): 337 target_error = 5.0 # in percent 338 num_trials = 1000 339 max_obs = int(db.populationSize('test')/5) 340 341 tester = classifiers[classifier]['test'] 342 343 def testAux(params, num_trials, num_observations): 344 estimator = functools.partial(tester, params, greater) 345 estimates = bootstrap3(estimator, db, 'test', unusual_case, num_observations, num_trials) 346 null_estimates = bootstrap3(estimator, db, 'train_null', unusual_case, num_observations, num_trials) 347 348 bad_estimates = len([e for e in estimates if e != 1]) 349 bad_null_estimates = len([e for e in null_estimates if e != 0]) 350 351 false_negatives = 100.0*bad_estimates/num_trials 352 false_positives = 100.0*bad_null_estimates/num_trials 353 print("testAux:", num_observations, false_positives, false_negatives, params) 354 return false_positives,false_negatives 355 356 357 if retest: 358 print("Dropping stored test results...") 359 db.deleteClassifierResults(classifier, 'test') 360 361 362 test_results = [] 363 lte = math.log(target_error/100.0) 364 for tr in classifiers[classifier]['train_results']: 365 db.resetOffsets() 366 params = json.loads(tr['params']) 367 num_obs = tr['num_observations'] 368 369 print("initial test") 370 fp,fn = testAux(params, num_trials, num_obs) 371 error = (fp+fn)/2.0 372 print("walking up") 373 while (error > target_error) and (num_obs < max_obs): 374 increase_factor = 1.5 * lte/math.log(error/100.0) # don't ask how I came up with this 375 #print("increase_factor:", increase_factor) 376 num_obs = min(int(increase_factor*num_obs), max_obs) 377 fp,fn = testAux(params, num_trials, num_obs) 378 error = (fp+fn)/2.0 379 380 print("walking down") 381 while (num_obs > 0): 382 current_best = (num_obs,error,params,fp,fn) 383 num_obs = int(0.95*num_obs) 384 fp,fn = testAux(params, num_trials, num_obs) 385 error = (fp+fn)/2.0 386 if error > target_error: 387 break 388 389 test_results.append(current_best) 390 391 test_results.sort() 392 best_obs,error,best_params,fp,fn = test_results[0] 393 394 return {'classifier':classifier, 395 'trial_type':"test", 396 'num_observations':best_obs, 397 'num_trials':num_trials, 398 'params':best_params, 399 'false_positives':fp, 400 'false_negatives':fn} 260 401 261 402 … … 268 409 print(":", end-start) 269 410 270 271 for c,funcs in classifiers.items(): 411 for c in sorted(classifiers.keys()): 412 if classifiers[c]['train'] == None: 413 continue 272 414 start = time.time() 273 415 print("Training %s..." % c) 274 result = trainClassifier(db, unusual_case, greater, funcs['train'])416 result = trainClassifier(db, unusual_case, greater, c, c in options.retrain) 275 417 print("%s result:" % c) 276 418 pprint.pprint(result) 277 419 print("completed in:", time.time()-start) 278 420 279 sys.exit(0) 280 281 start = time.time() 282 results = trainBoxTest(db, unusual_case, greater, 6000) 283 #db.addClassifierResults(results) 284 print("multi box test result:") 285 pprint.pprint(results) 286 print(":", time.time()-start) 421 db.clearCache() 422 423 for c in sorted(classifiers.keys()): 424 start = time.time() 425 print("Testing %s..." % c) 426 result = testClassifier(db, unusual_case, greater, c, c in options.retest) 427 print("%s result:" % c) 428 pprint.pprint(result) 429 classifiers[c]['test_error'] = (result['false_positives']+result['false_negatives'])/2.0 430 print("completed in:", time.time()-start) -
trunk/lib/nanownlib/__init__.py
r6 r10 4 4 import sys 5 5 import time 6 import traceback 6 7 import random 7 8 import argparse … … 209 210 def removeDuplicatePackets(packets): 210 211 #return packets 211 suspect = None212 suspect = '' 212 213 seen = {} 213 214 # XXX: Need to review this deduplication algorithm and make sure it is correct 214 215 for p in packets: 215 216 key = (p['sent'],p['tcpseq'],p['tcpack'],p['payload_len']) 216 if (key not in seen)\ 217 or p['sent']==1 and (seen[key]['observed'] < p['observed'])\ 218 or p['sent']==0 and (seen[key]['observed'] > p['observed']): 219 #if (key not in seen) or (seen[key]['observed'] > p['observed']): 217 if (key not in seen): 220 218 seen[key] = p 221 222 if len(seen) < len(packets): 223 suspect = 'd' 224 #sys.stderr.write("INFO: removed %d duplicate packets.\n" % (len(packets) - len(seen))) 219 continue 220 if p['sent']==1 and (seen[key]['observed'] > p['observed']): #earliest sent 221 seen[key] = p 222 suspect += 's' 223 continue 224 if p['sent']==0 and (seen[key]['observed'] > p['observed']): #earliest rcvd 225 seen[key] = p 226 suspect += 'r' 227 continue 228 229 #if len(seen) < len(packets): 230 # sys.stderr.write("INFO: removed %d duplicate packets.\n" % (len(packets) - len(seen))) 225 231 226 232 return suspect,seen.values() … … 230 236 suspect,packets = removeDuplicatePackets(packets) 231 237 232 #sort_key = lambda d: (d['tcpseq'],d['tcpack']) 233 sort_key = lambda d: (d['observed'],d['tcpseq']) 238 sort_key = lambda d: (d['tcpseq'],d['observed']) 234 239 sent = sorted((p for p in packets if p['sent']==1 and p['payload_len']>0), key=sort_key) 235 240 rcvd = sorted((p for p in packets if p['sent']==0 and p['payload_len']>0), key=sort_key) 236 241 237 if len(sent) <= trim_sent: 238 last_sent = sent[-1] 239 else: 240 last_sent = sent[trim_sent] 241 242 if len(rcvd) <= trim_rcvd: 243 last_rcvd = rcvd[0] 244 else: 245 last_rcvd = rcvd[len(rcvd)-1-trim_rcvd] 242 alt_key = lambda d: (d['observed'],d['tcpseq']) 243 rcvd_alt = sorted((p for p in packets if p['sent']==0 and p['payload_len']>0), key=alt_key) 244 245 s_off = trim_sent 246 if s_off >= len(sent): 247 s_off = -1 248 last_sent = sent[s_off] 249 250 r_off = len(rcvd) - trim_rcvd - 1 251 if r_off <= 0: 252 r_off = 0 253 last_rcvd = rcvd[r_off] 254 if last_rcvd != rcvd_alt[r_off]: 255 suspect += 'R' 246 256 247 257 packet_rtt = last_rcvd['observed'] - last_sent['observed'] … … 272 282 query=""" 273 283 SELECT packet_rtt-(SELECT avg(packet_rtt) FROM probes,trim_analysis 274 WHERE sent_trimmed=:strim AND rcvd_trimmed=:rtrim AND trim_analysis.probe_id=probes.id AND probes.test_case!=:unusual_case AND sample=u.sample AND probes.type in ('train','test')) 275 FROM (SELECT probes.sample,packet_rtt FROM probes,trim_analysis WHERE sent_trimmed=:strim AND rcvd_trimmed=:rtrim AND trim_analysis.probe_id=probes.id AND probes.test_case=:unusual_case AND probes.type in ('train','test')) u 284 WHERE sent_trimmed=:strim AND rcvd_trimmed=:rtrim AND trim_analysis.probe_id=probes.id AND probes.test_case!=:unusual_case AND sample=u.s AND probes.type in ('train','test')) 285 FROM (SELECT probes.sample s,packet_rtt FROM probes,trim_analysis WHERE sent_trimmed=:strim AND rcvd_trimmed=:rtrim AND trim_analysis.probe_id=probes.id AND probes.test_case=:unusual_case AND probes.type in ('train','test') AND 1 NOT IN (select 1 from probes p,trim_analysis t WHERE p.sample=s AND t.probe_id=p.id AND t.suspect LIKE '%R%')) u 286 """ 287 query=""" 288 SELECT packet_rtt-(SELECT avg(packet_rtt) FROM probes,trim_analysis 289 WHERE sent_trimmed=:strim AND rcvd_trimmed=:rtrim AND trim_analysis.probe_id=probes.id AND probes.test_case!=:unusual_case AND sample=u.s AND probes.type in ('train','test')) 290 FROM (SELECT probes.sample s,packet_rtt FROM probes,trim_analysis WHERE sent_trimmed=:strim AND rcvd_trimmed=:rtrim AND trim_analysis.probe_id=probes.id AND probes.test_case=:unusual_case AND probes.type in ('train','test')) u 276 291 """ 277 292 … … 280 295 differences = [row[0] for row in cursor] 281 296 282 return trimean(differences),mad(differences)297 return ubersummary(differences),mad(differences) 283 298 284 299 … … 287 302 db.conn.execute("CREATE INDEX IF NOT EXISTS packets_probe ON packets (probe_id)") 288 303 pcursor = db.conn.cursor() 289 kcursor = db.conn.cursor()304 db.conn.commit() 290 305 291 306 pcursor.execute("SELECT tcpts_mean FROM meta") … … 297 312 pcursor.execute("DELETE FROM trim_analysis") 298 313 db.conn.commit() 314 315 def loadPackets(db): 316 cursor = db.conn.cursor() 317 cursor.execute("SELECT * FROM packets ORDER BY probe_id") 318 319 probe_id = None 320 entry = [] 321 ret_val = [] 322 for p in cursor: 323 if probe_id == None: 324 probe_id = p['probe_id'] 325 if p['probe_id'] != probe_id: 326 ret_val.append((probe_id,entry)) 327 probe_id = p['probe_id'] 328 entry = [] 329 entry.append(dict(p)) 330 ret_val.append((probe_id,entry)) 331 return ret_val 332 333 start = time.time() 334 packet_cache = loadPackets(db) 335 print("packets loaded in: %f" % (time.time()-start)) 299 336 300 337 count = 0 301 338 sent_tally = [] 302 339 rcvd_tally = [] 303 for pid, in pcursor.execute("SELECT id FROM probes"): 304 kcursor.execute("SELECT * FROM packets WHERE probe_id=?", (pid,)) 340 for probe_id,packets in packet_cache: 305 341 try: 306 analysis,s,r = analyzePackets( kcursor.fetchall(), timestamp_precision)307 analysis['probe_id'] = p id342 analysis,s,r = analyzePackets(packets, timestamp_precision) 343 analysis['probe_id'] = probe_id 308 344 sent_tally.append(s) 309 345 rcvd_tally.append(r) 346 db.addTrimAnalyses([analysis]) 310 347 except Exception as e: 311 print(e)312 sys.stderr.write("WARN: couldn't find enough packets for probe_id=%s\n" % p id)348 traceback.print_exc() 349 sys.stderr.write("WARN: couldn't find enough packets for probe_id=%s\n" % probe_id) 313 350 314 351 #print(pid,analysis) 315 db.addTrimAnalyses([analysis])316 352 count += 1 317 353 db.conn.commit() … … 326 362 if strim == 0 and rtrim == 0: 327 363 continue # no point in doing 0,0 again 328 for pid, in pcursor.execute("SELECT id FROM probes"): 329 kcursor.execute("SELECT * FROM packets WHERE probe_id=?", (pid,)) 364 for probe_id,packets in packet_cache: 330 365 try: 331 analysis,s,r = analyzePackets( kcursor.fetchall(), timestamp_precision, strim, rtrim)332 analysis['probe_id'] = p id366 analysis,s,r = analyzePackets(packets, timestamp_precision, strim, rtrim) 367 analysis['probe_id'] = probe_id 333 368 except Exception as e: 334 369 print(e) … … 336 371 337 372 db.addTrimAnalyses([analysis]) 338 373 db.conn.commit() 339 374 340 375 # Populate analysis table so findUnusualTestCase can give us a starting point … … 359 394 for strim in range(1,num_sent): 360 395 delta,mad = evaluations[(strim,0)] 361 if abs(good_delta - delta) < abs(delta_margin*good_delta) and mad < good_mad:396 if delta*good_delta > 0.0 and (abs(good_delta) - abs(delta)) < abs(delta_margin*good_delta) and mad < good_mad: 362 397 best_strim = strim 363 398 else: … … 367 402 for rtrim in range(1,num_rcvd): 368 403 delta,mad = evaluations[(best_strim,rtrim)] 369 if (abs(delta) > abs(good_delta) or abs(good_delta - delta) < abs(delta_margin*good_delta)) and mad < good_mad:404 if delta*good_delta > 0.0 and (abs(good_delta) - abs(delta)) < abs(delta_margin*good_delta) and mad < good_mad: 370 405 best_rtrim = rtrim 371 406 else: … … 425 460 cursor = db.conn.cursor() 426 461 cursor.execute("SELECT packet_rtt FROM probes,analysis WHERE probes.id=analysis.probe_id AND probes.type in ('train','test')") 427 global_tm = trimean([row['packet_rtt'] for row in cursor])462 global_tm = quadsummary([row['packet_rtt'] for row in cursor]) 428 463 429 464 tm_abs = [] … … 432 467 for tc in test_cases: 433 468 cursor.execute("SELECT packet_rtt FROM probes,analysis WHERE probes.id=analysis.probe_id AND probes.type in ('train','test') AND probes.test_case=?", (tc,)) 434 tm_map[tc] = trimean([row['packet_rtt'] for row in cursor])469 tm_map[tc] = quadsummary([row['packet_rtt'] for row in cursor]) 435 470 tm_abs.append((abs(tm_map[tc]-global_tm), tc)) 436 471 437 472 magnitude,tc = max(tm_abs) 438 473 cursor.execute("SELECT packet_rtt FROM probes,analysis WHERE probes.id=analysis.probe_id AND probes.type in ('train','test') AND probes.test_case<>?", (tc,)) 439 remaining_tm = trimean([row['packet_rtt'] for row in cursor])474 remaining_tm = quadsummary([row['packet_rtt'] for row in cursor]) 440 475 441 476 ret_val = (tc, tm_map[tc]-remaining_tm) -
trunk/lib/nanownlib/stats.py
r8 r10 2 2 import sys 3 3 import os 4 import functools 4 5 import math 5 6 import statistics … … 133 134 134 135 135 def midhinge(values, distance=25): 136 return (numpy.percentile(values, 50-distance) + numpy.percentile(values, 50+distance))/2.0 136 def midsummary(values, distance=25): 137 #return (numpy.percentile(values, 50-distance) + numpy.percentile(values, 50+distance))/2.0 138 l,h = numpy.percentile(values, (50-distance,50+distance)) 139 return (l+h)/2.0 137 140 138 141 def trimean(values, distance=25): 139 return (midhinge(values, distance) + statistics.median(values))/2 140 142 return (midsummary(values, distance) + statistics.median(values))/2 143 144 def ubersummary(values, distance=25): 145 left2 = 50-distance 146 left1 = left2/2.0 147 left3 = (left2+50)/2.0 148 right2 = 50+distance 149 right3 = (right2+50)/2.0 150 right1 = (right2+100)/2.0 151 l1,l2,l3,r3,r2,r1 = numpy.percentile(values, (left1,left2,left3,right3,right2,right1)) 152 #print(left1,left2,left3,50,right3,right2,right1) 153 #print(l1,l2,l3,m,r3,r2,r1) 154 return (l1+l2*4+l3+r3+r2*4+r1)/12.0 155 #return statistics.mean((l1,l2,l3,m,r3,r2,r1)) 156 157 def quadsummary(values, distance=25): 158 left2 = 50-distance 159 left1 = left2/2.0 160 right2 = 50+distance 161 right1 = (right2+100)/2.0 162 l1,l2,r2,r1 = numpy.percentile(values, (left1,left2,right2,right1)) 163 #print(left1,left2,left3,50,right3,right2,right1) 164 #print(l1,l2,l3,m,r3,r2,r1) 165 return (l1+l2+r2+r1)/4.0 166 #return statistics.mean((l1,l2,l3,m,r3,r2,r1)) 167 168 def quadsummary(values, distance=25): 169 left1 = 50-distance 170 left2 = (left1+50)/2.0 171 right1 = 50+distance 172 right2 = (right1+50)/2.0 173 l1,l2,r2,r1 = numpy.percentile(values, (left1,left2,right2,right1)) 174 #print(left1,left2,left3,50,right3,right2,right1) 175 #print(l1,l2,l3,m,r3,r2,r1) 176 return (l1+l2+r2+r1)/4.0 177 #return statistics.mean((l1,l2,l3,m,r3,r2,r1)) 178 179 141 180 def weightedMean(derived, weights): 142 181 normalizer = sum(weights.values())/len(weights) … … 170 209 171 210 172 def estimateMid hinge(derived):173 return mid hinge([(d['long']-d['short']) for d in derived.values()])211 def estimateMidsummary(derived): 212 return midsummary([(d['long']-d['short']) for d in derived.values()]) 174 213 175 214 … … 348 387 rest = [s['other_cases'] for s in samples] 349 388 350 uc_high = numpy.percentile(uc, params['high'])351 rest_ low = numpy.percentile(rest, params['low'])389 uc_high,uc_low = numpy.percentile(uc, (params['high'],params['low'])) 390 rest_high,rest_low = numpy.percentile(rest, (params['high'],params['low'])) 352 391 if uc_high < rest_low: 353 392 if greater: … … 356 395 return 1 357 396 358 uc_low = numpy.percentile(uc, params['low'])359 rest_high = numpy.percentile(rest, params['high'])360 397 if rest_high < uc_low: 361 398 if greater: … … 369 406 # Returns 1 if unusual_case is unusual in the expected direction 370 407 # 0 otherwise 371 def midhingeTest(params, greater, samples):408 def summaryTest(f, params, greater, samples): 372 409 diffs = [s['unusual_case']-s['other_cases'] for s in samples] 373 410 374 mh = midhinge(diffs, params['distance']) 375 #mh = trimean(diffs, params['distance']) 411 mh = f(diffs, params['distance']) 376 412 if greater: 377 413 if mh > params['threshold']: … … 385 421 return 0 386 422 423 midsummaryTest = functools.partial(summaryTest, midsummary) 424 trimeanTest = functools.partial(summaryTest, trimean) 425 ubersummaryTest = functools.partial(summaryTest, ubersummary) 426 quadsummaryTest = functools.partial(summaryTest, quadsummary) 387 427 388 428 def rmse(expected, measurements): … … 392 432 def nrmse(expected, measurements): 393 433 return rmse(expected, measurements)/(max(measurements)-min(measurements)) 434 435 436 class KalmanFilter1D: 437 def __init__(self, x0, P, R, Q): 438 self.x = x0 439 self.P = P 440 self.R = R 441 self.Q = Q 442 443 def update(self, z): 444 self.x = (self.P * z + self.x * self.R) / (self.P + self.R) 445 self.P = 1. / (1./self.P + 1./self.R) 446 447 def predict(self, u=0.0): 448 self.x += u 449 self.P += self.Q 450 451 452 def kfilter(params, observations): 453 x = numpy.array(observations) 454 movement = 0 455 est = [] 456 var = [] 457 kf = KalmanFilter1D(x0 = quadsummary(x), # initial state 458 #P = 10000, # initial variance 459 P = 10, # initial variance 460 R = numpy.std(x), # msensor noise 461 Q = 0) # movement noise 462 for round in range(1): 463 for d in x: 464 kf.predict(movement) 465 kf.update(d) 466 est.append(kf.x) 467 var.append(kf.P) 468 469 return({'est':est, 'var':var}) 470 471 472 def kalmanTest(params, greater, samples): 473 diffs = [s['unusual_case']-s['other_cases'] for s in samples] 474 475 m = kfilter(params, diffs)['est'][-1] 476 if greater: 477 if m > params['threshold']: 478 return 1 479 else: 480 return 0 481 else: 482 if m < params['threshold']: 483 return 1 484 else: 485 return 0 486 487 488 def kalmanTest2(params, greater, samples): 489 diffs = [s['unusual_case']-s['other_cases'] for s in samples] 490 491 estimates = [] 492 size = 500 493 for i in range(100): 494 off = random.randrange(0,len(diffs)) 495 sub = diffs[off:size] 496 if len(sub) < size: 497 sub += diffs[0:size-len(sub)] 498 estimates.append(kfilter(params, sub)['est'][-1]) 499 500 m = quadsummary(estimates) 501 if greater: 502 if m > params['threshold']: 503 return 1 504 else: 505 return 0 506 else: 507 if m < params['threshold']: 508 return 1 509 else: 510 return 0 511 -
trunk/lib/nanownlib/storage.py
r9 r10 4 4 import os 5 5 import uuid 6 import random 6 7 import threading 7 8 import sqlite3 8 9 9 10 import numpy 11 # Don't trust numpy's seeding 12 numpy.random.seed(random.SystemRandom().randint(0,2**32-1)) 10 13 11 14 def _newid(): … … 18 21 _population_sizes = None 19 22 _population_cache = None 23 _offset_cache = None 24 _cur_offsets = None 20 25 21 26 def __init__(self, path): … … 26 31 self._population_sizes = {} 27 32 self._population_cache = {} 33 self._offset_cache = {} 34 self._cur_offsets = {} 28 35 29 36 if not exists: … … 79 86 self.conn.execute( 80 87 """CREATE TABLE classifier_results (id BLOB PRIMARY KEY, 81 algorithm TEXT, 88 classifier TEXT, 89 trial_type TEXT, 90 num_observations INTEGER, 91 num_trials INTEGER, 82 92 params TEXT, 83 sample_size INTEGER,84 num_trials INTEGER,85 trial_type TEXT,86 93 false_positives REAL, 87 94 false_negatives REAL) … … 109 116 110 117 def subseries(self, probe_type, unusual_case, size=None, offset=None, field='packet_rtt'): 111 if (probe_type,unusual_case,field) not in self._population_cache: 118 cache_key = (probe_type,unusual_case,field) 119 120 if cache_key not in self._population_cache: 112 121 query=""" 113 122 SELECT %(field)s AS unusual_case, … … 121 130 cursor = self.conn.cursor() 122 131 cursor.execute(query, params) 123 self._population_cache[(probe_type,unusual_case,field)] = [dict(row) for row in cursor.fetchall()] 124 125 population = self._population_cache[(probe_type,unusual_case,field)] 132 p = [dict(row) for row in cursor.fetchall()] 133 self._population_cache[cache_key] = p 134 self._offset_cache[cache_key] = tuple(numpy.random.random_integers(0,len(p)-1, len(p)/5)) 135 self._cur_offsets[cache_key] = 0 136 137 population = self._population_cache[cache_key] 126 138 127 139 if size == None or size > len(population): 128 140 size = len(population) 129 141 if offset == None or offset >= len(population) or offset < 0: 130 offset = numpy.random.random_integers(0,len(population)-1) 131 142 offset = self._offset_cache[cache_key][self._cur_offsets[cache_key]] 143 self._cur_offsets[cache_key] = (offset + 1) % len(self._offset_cache[cache_key]) 144 132 145 try: 133 ret_val = population[offset:offset+size] 146 offset = int(offset) 147 size = int(size) 134 148 except Exception as e: 135 149 print(e, offset, size) 136 150 return None 151 152 ret_val = population[offset:offset+size] 137 153 if len(ret_val) < size: 138 154 ret_val += population[0:size-len(ret_val)] 139 155 140 156 return ret_val 141 142 157 158 159 def resetOffsets(self): 160 for k in self._cur_offsets.keys(): 161 self._cur_offsets[k] = 0 162 163 143 164 def clearCache(self): 144 165 self._population_cache = {} 166 self._offset_cache = {} 167 self._cur_offsets = {} 145 168 146 169 … … 188 211 self.conn.commit() 189 212 return ret_val 213 214 def fetchClassifierResult(self, classifier, trial_type, num_observations): 215 query = """ 216 SELECT * FROM classifier_results 217 WHERE classifier=? AND trial_type=? AND num_observations=? 218 ORDER BY false_positives+false_negatives 219 LIMIT 1; 220 """ 221 cursor = self.conn.cursor() 222 cursor.execute(query, (classifier, trial_type, num_observations)) 223 ret_val = cursor.fetchone() 224 225 if ret_val != None: 226 ret_val = dict(ret_val) 227 return ret_val 228 229 def deleteClassifierResults(self, classifier, trial_type, num_observations=None): 230 params = {"classifier":classifier,"trial_type":trial_type,"num_observations":num_observations} 231 query = """ 232 DELETE FROM classifier_results 233 WHERE classifier=:classifier AND trial_type=:trial_type 234 """ 235 if num_observations != None: 236 query += " AND num_observations=:num_observations" 237 238 self.conn.execute(query, params) 239 self.conn.commit() 240
Note: See TracChangeset
for help on using the changeset viewer.